我的遞歸訪問函數有什麼問題？

Question

我想寫一個小片段，通過一系列點來計算最短路徑。

下面的代碼：

using System.Collections.Generic; 
using System.Linq; 
using System; 

namespace ConsoleApplication1 
{ 

    public class Waypoint 
    { 
     public Point P; 
     public bool Visited; 
    } 

    public class Point 
    { 
     public double X; 
     public double Y; 

     public Point(double x, double y) 
     { 
      this.X = x; 
      this.Y = y; 
     } 

    class Program 
    { 
     static List<Point> AllPoints = new List<Point>(); 
     static Point startPoint = new Point(0, 0); 
     static Point endPoint = new Point(4, 3); 
     static List<List<Waypoint>> weightedList = new List<List<Waypoint>>(); 

     static void Main(string[] args) 
     { 
      AllPoints.Add(new Point(0, 0)); 
      AllPoints.Add(new Point(1, 1)); 
      AllPoints.Add(new Point(1, 2)); 
      AllPoints.Add(new Point(1, 3)); 
      AllPoints.Add(new Point(2, 2)); 
      AllPoints.Add(new Point(2, 3)); 
      AllPoints.Add(new Point(3, 2)); 
      AllPoints.Add(new Point(3, 3)); 
      AllPoints.Add(new Point(4, 3)); 

      // select all points within reach, its a 1x1 square between points so the max  distance is 1.42 
      var filteredList = from p in AllPoints 
       where DistanceBetweenTwoPoints(p, startPoint) < 1.42 && p.X !=  startPoint.X && p.Y != startPoint.Y 
       select p; 

      List<Waypoint> currList = new List<Waypoint>(); 
      currList.Add(new Waypoint() { P = new Point(startPoint.X, startPoint.Y), Visited =  true }); 

      foreach (var p in filteredList) 
      { 
       currList.Add(new Waypoint() { P = new Point(p.X, p.Y), Visited = true }); 

       RecusivlyVisitPoint(currList[currList.Count-1], currList); 
      } 
     } 

     static void RecusivlyVisitPoint(Waypoint wp, List<Waypoint> list) 
     { 
      // we have reached the end 
      if (wp.P == endPoint) 
      { 
       weightedList.Add(list); 

       return; 
      } 

      // select all points within reach, its a 1x1 square between points so the max  distance is 1.42 
      List<Point> allPointsWithInReach = (from p in AllPoints 
       where DistanceBetweenTwoPoints(p, wp.P) < 1.42 
       select p).ToList<Point>(); 

      // filter with already visited 
      for (int k = allPointsWithInReach.Count<Point>()-1; k >= 0; k--) 
      { 
       Point p = allPointsWithInReach[k]; 

       foreach (var lP in list) 
        if (lP.P == p) 
         allPointsWithInReach.RemoveAt(k); 
      } 

      // there are no other points to go thru 
      if (allPointsWithInReach.Count == 0) 
      { 
       weightedList.Add(list); 

       return; 
      } 

      // recursivly go thru the list 
      foreach (var p in allPointsWithInReach) 
      { 
       List<Waypoint> newList = new List<Waypoint>(); 
       foreach (var e in list) 
        newList.Add(e); 

       newList.Add(new Waypoint() { P = new Point(p.X, p.Y), Visited = true }); 

       RecusivlyVisitPoint(newList[newList.Count - 1], newList); 
      } 
     } 

     static double DistanceBetweenTwoPoints(Point p1, Point p2) 
     { 
      return Math.Sqrt(Math.Pow(Math.Abs(p1.X - p2.X), 2) + Math.Pow(Math.Abs(p1.Y -  p2.Y), 2)); 
     } 
    } 
} 

這是一個1x1的「網格」，所以你可以看到我用的1.42距離，而不是已經訪問了從當前立足點過濾可能的點。

這裏的問題是，它運行通過所有點，返回所有點如果(wp.P == endPoint)。我錯過了什麼？我創建了一個新列表，並按照每個節點的遞歸進一步發送它。

最後，還沒有實施，即時總結所有在weightedList列表中的所有列表項，並選擇一個元素最少的列表項。

Answer 1

首先，當我試圖運行你的代碼，我看到這樣的代碼：

for (int k = allPointsWithInReach.Count<Point>()-1; k >= 0; k--) 
{ 
    Point p = allPointsWithInReach[k]; 

    foreach (var lP in list) 
     if (lP.P == p) 
      allPointsWithInReach.RemoveAt(k); 
} 

不移除任何你已經去了點。所以這意味着它進行了無限循環並創建了一個stackoverflow異常。

我刪除了你用linq去的要點，這更簡潔。爲了做到這一點，我需要評估2點是否相等，因此我在點類中添加了2個方法。 下面的代碼：

using System.Collections.Generic; 
using System.Linq; 
using System; 
namespace ConsoleApplication1 
{ 
    public class Waypoint 
    { 
     public Point P; 
     public bool Visited; 
    } 
    public class Point : IEquatable<Point> 
    { 
     public double X; 
     public double Y; 

     public Point(double x, double y) 
     { 
      this.X = x; 
      this.Y = y; 
     } 

     public bool Equals(Point other) 
     { 
      if (Object.ReferenceEquals(other, null)) return false; 
      if (Object.ReferenceEquals(this, other)) return true; 

      return X.Equals(other.X) && Y.Equals(other.Y); 
     } 

     public override int GetHashCode() 
     { 
      int hashX = X.GetHashCode(); 

      int hashY = Y.GetHashCode(); 

      return hashX^hashY; 
     } 
    } 

    class Program 
    { 
     static List<Point> AllPoints = new List<Point>(); 
     static Point startPoint = new Point(0, 0); 
     static Point endPoint = new Point(4, 3); 
     static List<List<Waypoint>> weightedList = new List<List<Waypoint>>(); 

     static void Main(string[] args) 
     { 
      AllPoints.Add(new Point(0, 0)); 
      AllPoints.Add(new Point(1, 1)); 
      AllPoints.Add(new Point(1, 2)); 
      AllPoints.Add(new Point(1, 3)); 
      AllPoints.Add(new Point(2, 2)); 
      AllPoints.Add(new Point(2, 3)); 
      AllPoints.Add(new Point(3, 2)); 
      AllPoints.Add(new Point(3, 3)); 
      AllPoints.Add(new Point(4, 3)); 

      // select all points within reach, its a 1x1 square between points so the max distance is 1.42 
      var filteredList = from p in AllPoints 
        where DistanceBetweenTwoPoints(p, startPoint) < 1.42 && p.X != startPoint.X && p.Y != startPoint.Y 
        select p; 

      List<Waypoint> currList = new List<Waypoint>(); 
      currList.Add(new Waypoint() { P = new Point(startPoint.X, startPoint.Y), Visited = true }); 

      foreach (var p in filteredList) 
      { 
       currList.Add(new Waypoint() { P = new Point(p.X, p.Y), Visited = true }); 

       RecusivlyVisitPoint(currList.Last(), currList); 
      } 
      var min = weightedList.OrderBy(w => w.Count).Take(1).ToList(); 
     } 

     static void RecusivlyVisitPoint(Waypoint wp, List<Waypoint> list) 
     { 
      // we have reached the end 
      if (wp.P.Equals(endPoint)) 
      { 
       weightedList.Add(list); 

       return; 
      } 

      // select all points within reach, its a 1x1 square between points so the max distance is 1.42 
      var allPointsWithInReach = AllPoints.FindAll(p => DistanceBetweenTwoPoints(p, wp.P) < 1.42); 

      // filter with already visited 
      allPointsWithInReach = allPointsWithInReach.Except(list.Select(w => w.P)).ToList(); 

      // there are no other points to go thru 
      if (allPointsWithInReach.Count == 0) 
      { 
       //weightedList.Add(list); 
       // but you didn't get trough the end so it's not a possibility 
       return; 
      } 

      // recursivly go thru the list 
      foreach (var p in allPointsWithInReach) 
      { 
       List<Waypoint> newList = new List<Waypoint>(); 
       foreach (var e in list) 
        newList.Add(e); 

       newList.Add(new Waypoint() { P = new Point(p.X, p.Y), Visited = true }); 

       RecusivlyVisitPoint(newList.Last(), newList); 
      } 
     } 

     static double DistanceBetweenTwoPoints(Point p1, Point p2) 
     { 
      return Math.Sqrt(Math.Pow(Math.Abs(p1.X - p2.X), 2) + Math.Pow(Math.Abs(p1.Y - p2.Y), 2)); 
     } 
    } 
}