C ricerca # minmax grafico

Question

EDIT 3: Va bene, così ho ottenuto il mio codice per lavorare, ma sto di fronte a un problema enorme consumo di memoria se sto utilizzando diciamo 16 nodi e una profondità di ricerca qui sopra 11.

un soemone controlla il codice e dimmi come posso correggere quella perdita di memoria?

Ecco il codice completo:

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

Basta gettare i miei due centesimi su questo, @ mao47 è morto in, in quanto non v'è una perdita di memoria solo una massiccia quantità di memoria necessaria.

Mi sono imbattuto in questo thread mentre cercavo di leggere la ricerca su MinMax e vale la pena aggiungere che c'è un bel po 'di lavoro là fuori sull'ottimizzazione di MinMax e altri algoritmi. Ho trovato this lettura utile della carta per esempio (la lingua era ragionevolmente comprensibile data la mia velocità personale di decadimento accademico e il tempo t da quando ho finito la scuola).