1

我正在尝试编写一个小片段，通过一系列点计算最短路径。

这是代码：

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 并且尚未访问过。

这里的问题是它运行通过所有点，返回所有点 if (wp.P == endPoint)。我错过了什么？我创建了一个新列表并将其进一步向下发送到每个节点的递归。

最后，没有实现，我将总结每个列表中的所有列表项，weightedList并选择元素最少的一个。

4

1 回答 1

0

首先，当我尝试运行您的代码时，我看到了这段代码：

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));
        }
    }
}
于 2013-08-23T13:58:29.700 回答