C# minmax Graph Suche

Question

EDIT 3: Okay, so habe ich meinen Code zu arbeiten, aber ich bin ein großer Speicherverbrauch Problem konfrontiert, wenn ich die 16 Knoten bin mit sagen wir mal und eine Suchtiefe über 11

ein Soemone überprüfen Sie den Code und sagen Sie mir, wie kann ich das Speicherleck korrigieren?

Hier ist der vollständige Code:

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

Gerade meine zwei Cent auf das zu werfen, @ mao47 tot ist, dass es nicht ein Speicherverlust ist nur eine enorme Menge an Speicher benötigt.

Ich bin auf diesen Thread gestoßen, als ich nach der MinMax-Suche suchte, und es lohnt sich, hinzuzufügen, dass dort ein gutes Stück Arbeit zur Optimierung von MinMax und anderen Algorithmen steckt. Ich fand this Papier nützliche lesen zum Beispiel (Sprache war einigermaßen verständlich angesichts meiner persönlichen Rate von akademischen Verfall und Zeit t seit ich die Schule beendet).