C# minmax graph search

Question

EDIT 3: Được rồi, vì vậy tôi có mã để làm việc, nhưng tôi đang đối mặt với vấn đề tiêu thụ bộ nhớ lớn nếu tôi đang sử dụng giả sử 16 nút và độ sâu tìm kiếm trên 11.

một người kiểm tra mã và cho tôi biết làm thế nào tôi có thể sửa lỗi rò rỉ bộ nhớ đó?

Dưới đây là đoạn code đầy đủ:

public void searchTSP(
    int depth, 
    RouterPoint startpoint, 
    bool isRound, 
    IRouter<RouterPoint> router) 
{ 
    #region TSP_startpointCheck 
    if (!routepoints[0].Location.Equals(startpoint.Location)) 
    { 
    int index = Array 
     .FindIndex(routepoints, x => x.Location == startpoint.Location); 

    if (index != -1 && index != 0) //it's somewhere in the array 
    { 
     RouterPoint temprp = routepoints[0]; 
     routepoints[0] = routepoints[index]; //put it to index 0 
     routepoints[index] = temprp; 
    } 
    else //it's not in the array 
    { 
     //we add it... 
     RouterPoint[] ta = new RouterPoint[routepoints.Length + 1]; 
     routepoints.CopyTo(ta, 0); 
     ta[routepoints.Length] = startpoint; 
     ta.CopyTo(routepoints, 0); 
    } 
    } 
    #endregion 

    selectedRouter = router; 
    if (pathDictionary == null) 
    { 
    pathDictionary = new Dictionary<int[], double>(new IntArrayComparer()); 
    fillDictionary(); 
    }    

    DecisionPath bestPath = new DecisionPath(); 
    //DecisionPath currentPath = new DecisionPath(); 
    //List<DecisionPath> listOfPaths = new List<DecisionPath>(); 
    //List<int> visited = new List<int>(); 
    //List<RouterPoint> waypoints = routepoints.ToList(); 

    DateTime start = DateTime.Now; 
    RouteNode root = new RouteNode(); 
    root.parent = null; 
    root.curr = 0; 
    root.weight = 0.0f; 
    root.isTerminal = false; 
    root.memory = new List<short>(); 
    root.memory.Add(root.curr); 
    calculateChildren(root); 

    double bestval=double.MaxValue; 
    while (bestPath.list.Count < routepoints.GetLength(0)) 
    { 
    bestval = double.MaxValue; 
    int bestIndex = 0; 
    for (int i = 0; i < root.children.Count; i++) 
    { 
     RouteNode child = root.children[i]; 
     double t = minimax(child, depth); 
     if (t < bestval) 
     { 
     bestval = t; 
     bestIndex = i; 
     bestPath.cost = bestval; 
     bestPath.list = child.memory; 
     } 
    } 

    RouteNode temp = root.children[bestIndex]; 
    root.children.Clear(); 
    root.children.Add(temp); 
    root = root.children[0]; 
    } 

    //My result is in the bestPath class 
    // which has two properties: a list of indexes 
    // representing my found result node sequence 
    // and a double containing the total cost of the path 
} 

class RouteNode 
{ 
    public RouteNode parent { get; set; } 
    public short curr { get; set; } 
    public bool isTerminal { get; set; } 
    public float weight { get; set; } 
    public List<RouteNode> children { get; set; } 
    public List<short> memory { get; set; } 
} 

/// <summary> 
/// List of all children of a node that should be removed 
/// </summary> 
private List<RouteNode> killList; 

/// <summary> 
/// MiniMax recursive search for deciding witch ode to go to 
/// </summary> 
/// <param name="point">Input node</param> 
/// <param name="depth">How deep will we search</param> 
/// <returns>Weight value</returns> 
private double minimax(RouteNode point, int depth) 
{ 
    if (point.isTerminal || depth <= 0) 
    { 
    //if (point.isTerminal) 
    if (point.weight < bestyVal) 
    { 
     bestyVal = point.weight; 
     //Console.WriteLine(
     // "{0} - {1}", 
     // string.Join(", ", point.memory.ToArray()), 
     // point.weight.ToString()); 
    } 

    return point.weight; 
    } 

    double alpha = double.PositiveInfinity; 
    if (point.children == null || point.children.Count == 0) 
    calculateChildren(point); 

    killList = new List<RouteNode>(); 
    for (int i=0; i< point.children.Count; i++) 
    { 
    RouteNode child = point.children[i]; 
    if (child != null) 
    { 
     if (!child.isTerminal && child.weight > bestyVal) 
     { 
     child = null; 
     continue; 
     } 

     alpha = Math.Min(alpha, minimax(child, depth - 1)); 
    } 
    else 
     continue; 
    } 

    point.children.RemoveAll(e => killList.Contains(e)); 
    //killList = null; 
    return alpha; 
} 

/// <summary> 
/// Calculates possible children for a node 
/// </summary> 
/// <param name="node">Input node</param> 
private void calculateChildren(RouteNode node) 
{ 
    int c = node.curr; 
    List<int> possibleIndexes = Enumerable 
     .Range(0, routepoints.GetLength(0)) 
     .ToList(); 

    RouteNode curNod = node; 

    if (node.children == null) 
    node.children = new List<RouteNode>(); 

    while (curNod != null) 
    { 
    possibleIndexes.Remove(curNod.curr); 
    curNod = curNod.parent; 
    } 
    //imamo še neobiskane potomce... 
    foreach (int i in possibleIndexes) 
    { 
    RouteNode cc = new RouteNode(); 
    cc.curr = (short)i; 
    cc.parent = node; 
    double temp=0.0; 
    if (!pathDictionary.TryGetValue(new int[] { node.curr, i }, out temp)) 
    { 
     //preracunajPoti(node.curr, i, selectedRouter); 
     throw new Exception(
      String.Format(
       "Missed a path? {0} - {1}", 
       node.curr, 
       i)); 
    } 

    cc.weight = cc.parent.weight + (float)temp; 
    cc.memory = node.memory.ToList(); 
    cc.memory.Add(cc.curr); 

    if (possibleIndexes.Count == 1) 
     cc.isTerminal = true; 
    else 
     cc.isTerminal = false; 

    node.children.Add(cc); 
    } 
    //jih dodamo 
    possibleIndexes = null;  
} 

Answer 1

Chỉ cần ném trong hai xu của tôi về vấn đề này, @ mao47 là chết trên, trong đó có không phải là một bộ nhớ bị rò rỉ chỉ là một số lượng lớn bộ nhớ cần thiết.

Tôi đã xem qua chủ đề này khi tìm kiếm đọc về tìm kiếm MinMax và đáng giá thêm là có một chút công bằng về việc tối ưu hóa MinMax và các thuật toán khác. Tôi đã tìm thấy this đọc sách hữu ích cho ví dụ (ngôn ngữ có thể hiểu được một cách hợp lý vì tỷ lệ phân rã học tập và thời gian t của tôi từ khi tôi học xong).