C＃MINMAXグラフ探索

Question

EDIT 3： わかりましたので、私は仕事に私のコードを得たが、私はのは11

上記の16のノードと検索の深さを言わせて使用​​している場合、私は巨大なメモリ消費の問題に直面しています

soemoneがコードをチェックして、どのようにしてそのメモリリークを修正できるのか教えてください。

はここで完全なコードです：

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

はちょうどこの上で私の2セントで投げ、@ mao47は、必要なメモリだけで膨大な量のメモリリークがないという点で、上で死んでいます。

MinMaxの検索で読んでみるとこのスレッドが出てきましたが、MinMaxやその他のアルゴリズムを最適化するにはかなりの労力がかかります。私はthis紙を読んで有用な読書をしました（例えば、私が学校を終えて以来、私の個人的な学業崩壊率と時間を考えれば、合理的に理解できました）。