c# - 递归树搜索

Question

考虑到 5x5 的网格，它需要记录所有可能的马移动组合，从每个起始方格到每个后续方格。

我设想它是一个类似二叉树的结构，但由于棋盘上的每个方 block 都可以有超过 2 个潜在的下一步，我认为它行不通。我研究了 A*/Pathfinding 算法，但据我所知，它们都需要一个端节点才能使用，而且我不知道端节点，因为它每次都在进行并且会有所不同。

到目前为止我的伪代码是:

For each square on the board
    Check if this key has potential moves
        If Potential moves
            <Some way of selecting a next move (this could be the square we just originated from too!)>
            Register this move into a collection we can check against for subsequent                             moves
            Recursively call function with the square we just landed on 
        Else Continue
End

任何建议/指针将不胜感激，因为我很迷茫!

Answer 1

好吧，正如评论所暗示的那样，可能的移动顺序会非常多。这是我的想法，所以请耐心等待。

非递归版本:您需要一个位置列表列表(称为位置列表)，这将是您的最终答案，我将该列表称为路线列表。

为每个起始位置创建一个列表，并将它们全部放入路线列表中。

While the routes list has a position list that's less than the required length
{
    Get a position list that's too short.
    Remove it from the routes list
    Create new position lists that are a copy of the list we just removed + a possible next position from the last position in the list.
    Add those lists to the routes list.
}

---

编辑:递归版本:

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

namespace ConsoleApplication1
{
    class Program
    {
        static int GridSize = 5;

        static void Main(string[] args)
        {
            List<List<Point>> Positions = (from X in Enumerable.Range(0, GridSize)
                                           from Y in Enumerable.Range(0, GridSize)
                                           select new List<Point>() { new Point(X, Y) }).ToList();

            var PossibleRoutes = WalkGraph(Positions, 5);
        }

        static List<List<Point>> WalkGraph(List<List<Point>> RoutesList, int DesiredLength)
        {
            List<List<Point>> Result = new List<List<Point>>();

            foreach (var Route in RoutesList)
            {
                if (Route.Count < DesiredLength)
                {
                    // Extend the route (produces a list of routes) and recurse
                    Result.AddRange(WalkGraph(ExtendRoute(Route), DesiredLength));
                }
                else
                {
                    Result.Add(Route);
                }
            }

            return Result;
        }

        static List<List<Point>> ExtendRoute(List<Point> Route)
        {
            List<List<Point>> NextMoveRoutes = new List<List<Point>>();

            // Itterate through each possible move
            foreach (var NextMove in PossibleMoves(Route.Last()))
            {
                // Create a copy of the route, and add this possible move to it.
                List<Point> NextMoveRoot = new List<Point>(Route);
                NextMoveRoot.Add(NextMove);
                NextMoveRoutes.Add(NextMoveRoot);
            }

            return NextMoveRoutes;
        }

        static List<Point> PossibleMoves(Point P)
        {
            // TODO Generate a list of possible places to move to

            List<Point> Result = new List<Point>();

            Result.Add(new Point(P.X + 1, P.Y + 2));
            Result.Add(new Point(P.X - 1, P.Y + 2));
            Result.Add(new Point(P.X + 1, P.Y - 2));
            Result.Add(new Point(P.X - 1, P.Y - 2));

            Result.Add(new Point(P.X + 2, P.Y + 1));
            Result.Add(new Point(P.X - 2, P.Y + 1));
            Result.Add(new Point(P.X + 2, P.Y - 1));
            Result.Add(new Point(P.X - 2, P.Y - 1));

            Result.RemoveAll(PossibleMove => PossibleMove.X < 0 || PossibleMove.X > GridSize ||
                                             PossibleMove.Y < 0 || PossibleMove.Y > GridSize);

            return Result;
        }
    }
}

---

编辑:下面是一个使用 IEnumerable 的版本，以消除初始计算时间，并大幅减少内存占用。

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

namespace ConsoleApplication1
{
    class Program
    {
        static int GridSize = 5;

        static void Main(string[] args)
        {
            IEnumerable<IEnumerable<Point>> Positions = from X in Enumerable.Range(0, GridSize)
                                                        from Y in Enumerable.Range(0, GridSize)
                                                        select new List<Point>() { new Point(X, Y) } as IEnumerable<Point>;

            var PossibleRoutes = WalkGraph(Positions, 100);

            foreach (var Route in PossibleRoutes)
            {
                Console.WriteLine(Route.Select(P => P.ToString()).Aggregate((curr, next) => curr + " " + next));
                //Thread.Sleep(500); // Uncomment this to slow things down so you can read them!
            }

            Console.ReadKey();
        }

        static IEnumerable<IEnumerable<Point>> WalkGraph(IEnumerable<IEnumerable<Point>> RoutesList, int DesiredLength)
        {
            foreach (var Route in RoutesList)
            {
                if (Route.Count() < DesiredLength)
                {
                    // Extend the route (produces a list of routes) and recurse
                    foreach (var ExtendedRoute in WalkGraph(ExtendRoute(Route), DesiredLength))
                        yield return ExtendedRoute;
                }
                else
                {
                    //Result.Add(Route);
                    yield return Route;
                }
            }
        }

        static IEnumerable<IEnumerable<Point>> ExtendRoute(IEnumerable<Point> Route)
        {
            // Itterate through each possible move
            foreach (var NextMove in PossibleMoves(Route.Last()))
            {
                // Create a copy of the route, and add this possible move to it.
                List<Point> NextMoveRoute = new List<Point>(Route);
                NextMoveRoute.Add(NextMove);
                yield return NextMoveRoute;
            }
        }

        static IEnumerable<Point> PossibleMoves(Point P)
        {
            List<Point> Result = new List<Point>();

            Result.Add(new Point(P.X + 1, P.Y + 2));
            Result.Add(new Point(P.X - 1, P.Y + 2));
            Result.Add(new Point(P.X + 1, P.Y - 2));
            Result.Add(new Point(P.X - 1, P.Y - 2));

            Result.Add(new Point(P.X + 2, P.Y + 1));
            Result.Add(new Point(P.X - 2, P.Y + 1));
            Result.Add(new Point(P.X + 2, P.Y - 1));
            Result.Add(new Point(P.X - 2, P.Y - 1));

            Result.RemoveAll(PossibleMove => PossibleMove.X < 0 || PossibleMove.X > GridSize ||
                                             PossibleMove.Y < 0 || PossibleMove.Y > GridSize);

            return Result as IEnumerable<Point>;
        }
    }
}