title: C# minmax graph search
body: <p>EDIT 3:
  Okay, so i got my code to work, but i'm facing a huge memory consumption problem if i'm using let's say 16 nodes and a search depth above 11.</p>
  
  <p>an soemone check the code and tell me how can i correct that memory leak?</p>
  
  <p>Here's the full code:</p>
  
  <pre><code>public void searchTSP(
      int depth,
      RouterPoint startpoint,
      bool isRound,
      IRouter&lt;RouterPoint&gt; router)
  {
    #region TSP_startpointCheck
    if (!routepoints[0].Location.Equals(startpoint.Location))
    {
      int index = Array
        .FindIndex(routepoints, x =&gt; x.Location == startpoint.Location);
  
      if (index != -1 &amp;&amp; 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&lt;int[], double&gt;(new IntArrayComparer());
      fillDictionary();
    }            
  
    DecisionPath bestPath = new DecisionPath();
    //DecisionPath currentPath = new DecisionPath();
    //List&lt;DecisionPath&gt; listOfPaths = new List&lt;DecisionPath&gt;();
    //List&lt;int&gt; visited = new List&lt;int&gt;();
    //List&lt;RouterPoint&gt; 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&lt;short&gt;();
    root.memory.Add(root.curr);
    calculateChildren(root);
  
    double bestval=double.MaxValue;
    while (bestPath.list.Count &lt; routepoints.GetLength(0))
    {
      bestval = double.MaxValue;
      int bestIndex = 0;
      for (int i = 0; i &lt; root.children.Count; i++)
      {
        RouteNode child = root.children[i];
        double t = minimax(child, depth);
        if (t &lt; 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&lt;RouteNode&gt; children { get; set; }
    public List&lt;short&gt; memory { get; set; }
  }
  
  /// &lt;summary&gt;
  /// List of all children of a node that should be removed
  /// &lt;/summary&gt;
  private List&lt;RouteNode&gt; killList;
  
  /// &lt;summary&gt;
  /// MiniMax recursive search for deciding witch ode to go to
  /// &lt;/summary&gt;
  /// &lt;param name="point"&gt;Input node&lt;/param&gt;
  /// &lt;param name="depth"&gt;How deep will we search&lt;/param&gt;
  /// &lt;returns&gt;Weight value&lt;/returns&gt;
  private double minimax(RouteNode point, int depth)
  {
    if (point.isTerminal || depth &lt;= 0)
    {
      //if (point.isTerminal)
      if (point.weight &lt; 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&lt;RouteNode&gt;();
    for (int i=0; i&lt; point.children.Count; i++)
    {
      RouteNode child = point.children[i];
      if (child != null)
      {
        if (!child.isTerminal &amp;&amp; child.weight &gt; bestyVal)
        {
          child = null;
          continue;
        }
  
        alpha = Math.Min(alpha, minimax(child, depth - 1));
      }
      else
        continue;
    }
  
    point.children.RemoveAll( e =&gt; killList.Contains(e));
    //killList = null;
      return alpha;
  }
  
  /// &lt;summary&gt;
  /// Calculates possible children for a node
  /// &lt;/summary&gt;
  /// &lt;param name="node"&gt;Input node&lt;/param&gt;
  private void calculateChildren(RouteNode node)
  {
    int c = node.curr;
    List&lt;int&gt; possibleIndexes = Enumerable
        .Range(0, routepoints.GetLength(0))
        .ToList();
  
    RouteNode curNod = node;
  
    if (node.children == null)
      node.children = new List&lt;RouteNode&gt;();
  
    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;    
  }
  </code></pre>