c# - 在大网格中路由路径的最佳方法是什么？

Question

我正在研究一种算法，用于在网格中找到一组不相交的路径给定点对..对于这些对，就像这样:(9,4) 和 (12,13)

输出应该是这样的:

    9,10,11,7,3,4

    13,14,15,16,12

如果不能路由所有路径则打印“Blocked”

首先我搜索了一个已经制定的算法来找到 2 之间的所有简单路径图形或网格中的点。我通过@Casey Watson 和@svick here 找到了这个..它工作得很好，但只适用于小图。

我将它转换为 C#.NET 并对其进行了一些增强，以便能够找到最大长度 X. 并以此为基础构建我的总体算法。

我构建的那个在小图表中运行良好..这是 8x8 网格中的 9 对路线。

但在较大的模型(如 16x16)甚至我打算做的最后一个模型(16x16x2 的 3D 模型)中需要花费大量时间像这样

该算法被开发为深度优先搜索RECURSIVE算法，但它花了很长时间才将值(value)返回给用户。所以我决定将其转换为循环而不是递归调用，这样我就可以受益于 .NET 中的yield return 功能但它仍然没有任何帮助。

该算法的循环版本在不到一秒的时间内找到了一对点的路径，但递归算法花费了 90 多秒。

当我尝试使用 2 对时，循环版本花费了大约 342 秒，而递归版本花费了大约 200..

所以我不知道哪个更快..!?递归或循环一个..

我真的很想知道最好的方法..

注意:节点编号的第一个数字决定层(从 1 开始)..

这是代码

    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.Diagnostics;
    using System.IO;
    using System.Linq;

    namespace AlgorithmTest
    {
     struct Connection
    {
    public int FirstNode;
    public int SecondNode;

    public Connection(int N1,int N2)
    {
        FirstNode = N1;
        SecondNode = N2;
    }
}
enum Algorithm
{ Recursion, Loops }

public class Search
{

    private const int MAX = 15;

    private const int Width = 16;
    private const int Length = 16;
    private const int Height = 2;



    private static void Main(string[] args)
    {


        var graph = new Graph();


        var str = new int[Height,Length, Width];
        var level = ((int)Math.Pow(10, (Length * Width).ToString().Length) >= 100) ? (int)Math.Pow(10, (Length * Width).ToString().Length) : 100;              
        for (var i = 0; i < Height; i++)
        {
            int num = 0;
            for (var j = 0; j < Length; j++)
                for (var k = 0; k < Width; k++)
            {
                str[i, j, k] = ++num + level;

            }
            level += level;
        }


        for (var i = 0; i < Height; i++)
        {
            for (var j = 0; j < Length; j++)
            {
                for (var k = 0; k < Width; k++)
                {

                    if (i < Height - 1) graph.addEdge(str[i, j, k], str[i + 1, j, k]);
                    if (i > 0) graph.addEdge(str[i, j, k], str[i - 1, j, k]);

                    if (k < Width - 1) graph.addEdge(str[i, j, k], str[i, j, k + 1]);
                    if (k > 0) graph.addEdge(str[i, j, k], str[i, j, k - 1]);

                    if (j < Length - 1) graph.addEdge(str[i, j, k], str[i, j + 1, k]);
                    if (j > 0) graph.addEdge(str[i, j, k], str[i, j - 1, k]);


                }
            }
        }



        var wt = new Stopwatch();

       wt.Start();
        var connectedNodes = new List<Connection>()
                                 {



                                     new Connection(1030, 1005),
       //                              new Connection(1002, 1044),
    //                                         new Connection(1015, 1064),
    //                                        new Connection(1041, 1038),
    //                                         new Connection(1009, 1027),
    //                                         new Connection(1025, 1018),
    //                                         new Connection(1037, 1054),
    //                                         new Connection(1049, 1060),
    //                                         new Connection(1008, 1031),
    //                                         new Connection(1001, 1035),

                                 };
        wt.Start();
        Console.WriteLine("Using Loops:");
        Console.WriteLine();
        var allPaths = new Search().FindAllPaths(connectedNodes, graph, MAX, Algorithm.Loops);
        wt.Stop();
        foreach (var path in allPaths)
        {
            PrintPath(path);
        }
        Console.WriteLine("Total Seconds: " + wt.Elapsed.TotalSeconds + ", Number of paths: " + allPaths.Count());
        Console.WriteLine("***************************************************************************************************");
        Console.WriteLine("Using Recursion:");
        Console.WriteLine();
        wt.Reset();
        wt.Start();
        allPaths = new Search().FindAllPaths(connectedNodes, graph, MAX, Algorithm.Recursion);
        wt.Stop();
        foreach (var path in allPaths)
        {
            PrintPath(path);
        }
        Console.WriteLine("Total Seconds: " + wt.Elapsed.TotalSeconds + ", Number of paths: " + allPaths.Count());
        Console.WriteLine();

    }

    private IEnumerable<List<int>> FindAllPaths(List<Connection> connectedNodes, Graph graph, int max, Algorithm algorithm)
    {
        var paths=new Stack<List<int>>();
        var blocked=new List<int>();

        for (var i = 0; i < connectedNodes.Count; i++)
        {
            if (!blocked.Contains(connectedNodes[i].FirstNode)) blocked.Add(connectedNodes[i].FirstNode);
            if (!blocked.Contains(connectedNodes[i].SecondNode)) blocked.Add(connectedNodes[i].SecondNode);
        }

        if (algorithm == Algorithm.Recursion)
        {
            if (FindAllPaths(connectedNodes, 0, max, graph, paths, blocked))
            {
                Console.WriteLine("BLOCKED");
                return new List<List<int>>();
            }
        }
        else if(algorithm==Algorithm.Loops)
        {
            if (!FindAllPaths2(connectedNodes, 0, max, graph, paths, blocked))
            {
                Console.WriteLine("BLOCKED");
                return new List<List<int>>();
            }
        }

        return paths;

    }
    private static bool FindAllPaths(List<Connection> connectedNodes,int order,int max, Graph graph, Stack<List<int>> allPaths, List<int> blocked)
    {

        if (order >= connectedNodes.Count) return false;


        var paths = SearchForPaths(graph, connectedNodes[order].FirstNode, connectedNodes[order].SecondNode, max, blocked);
        if (paths.Count == 0) return true;
        int i;
        for (i = 0; i < paths.Count; i++)
        {
            var path = paths[i];
            allPaths.Push(path);
            blocked.AddRange(path);


            if (!FindAllPaths(connectedNodes, order + 1,max, graph, allPaths, blocked)) break;

            allPaths.Pop();
            foreach (var j in path)
            {
                blocked.RemoveAll(num => num==j);
            }

            paths.RemoveAll(list => IsListsSimilar(list,path));

            i--;

        }
        if (i == paths.Count) return true;


        return false;

    }

    private static bool IsListsSimilar(List<int> L1,List<int> L2)
    {
        if (L2.Count > L1.Count) return false;

        for (int i = 0; i < L2.Count - 1; i++)
        {
            if (L1[i] != L2[i]) return false;
        }
        return true;
    }

    private static List<List<int>> SearchForPaths(Graph graph, int start, int end, int max, List<int> blocked)
    {
        blocked.Remove(start);
        blocked.Remove(end);




        var nodePaths = new List<List<int>>();
        var visited = new LinkedList<int>();
        visited.AddLast(start);
        DepthFirstSearch(graph, visited, end, max, blocked, nodePaths);



        nodePaths = nodePaths.OrderBy(list => list.Count).ToList();

        return nodePaths;

    }
    private static void DepthFirstSearch(Graph graph, LinkedList<int> visited, int end, int max, List<int> blocked, List<List<int>> paths)
    {
        var nodes = graph.adjacentNodes(visited.Last.Value);
        // examine adjacent nodes
        var nodeCount = blocked.Count;
        for (int i = 0; i < nodeCount; i++)
        {
            if (visited.Contains(blocked[i])) return;
        }

        if (visited.Count > max) return;


        nodeCount = nodes.Count;
        for (var i = 0; i < nodeCount; i++)
        {
            if (visited.Contains(nodes[i]) || nodes[i] != end) continue;

            visited.AddLast(nodes[i]);

            {
                paths.Add(new List<int>(visited));

            }
            visited.RemoveLast();
            break;
        }



        nodeCount = nodes.Count;
        for (var i = 0; i < nodeCount; i++)
        {
            if (visited.Contains(nodes[i]) || nodes[i] == end) continue;

            visited.AddLast(nodes[i]);
            DepthFirstSearch(graph, visited, end, max, blocked, paths);
            visited.RemoveLast();
        }

    }

    private static bool FindAllPaths2(List<Connection> connectedNodes, int order, int max, Graph graph, Stack<List<int>> allPaths, List<int> blocked)
    {

        if (order >= connectedNodes.Count) return false;


        foreach (var path in SearchForPaths2(graph, connectedNodes[order].FirstNode, connectedNodes[order].SecondNode, max, blocked))
        {

            allPaths.Push(path);
            blocked.AddRange(path);


            if (!FindAllPaths2(connectedNodes, order + 1, max, graph, allPaths, blocked)) break;

            allPaths.Pop();
            foreach (var j in path)
            {
                blocked.RemoveAll(num => num == j);
            }


        }




        return true;

    }
    private static IEnumerable<List<int>> SearchForPaths2(Graph graph, int start, int end, int max, List<int> blocked)
    {
        blocked.Remove(start);
        blocked.Remove(end);


        var visited = new LinkedList<int>();
        visited.AddLast(start);
        foreach (var VARIABLE in DepthFirstSearch(graph, visited, end, max, blocked))
        {
            yield return VARIABLE;
        }

    }
    private static IEnumerable<List<int>> DepthFirstSearch(Graph graph, LinkedList<int> visited, int end, int max, List<int> blocked)
    {





        var nodes = graph.adjacentNodes(visited.Last.Value);


        var nodeCount = blocked.Count;
        for (int i = 0; i < nodeCount; i++)
        {
            if (visited.Contains(blocked[i])) yield break;
        }


        if (visited.Count > max) yield break;

        nodeCount = nodes.Count;
        for (var i = 0; i < nodeCount; i++)
        {
            if (visited.Contains(nodes[i]) || nodes[i] != end) continue;

            visited.AddLast(nodes[i]);

            yield return (new List<int>(visited));
            visited.RemoveLast();
            break;
        }




        nodeCount = nodes.Count;
        for (var i = 0; i < nodeCount; i++)
        {
            if (visited.Contains(nodes[i]) || nodes[i] == end) continue;

            visited.AddLast(nodes[i]);
            foreach (var P in DepthFirstSearch(graph, visited, end, max, blocked))
            {

                yield return P;

            }

            visited.RemoveLast();

        }






    }


    private static void PrintPath(List<int> visited)
    {

        for (int i = 0; i < visited.Count()-1; i++)
        {
            Console.Write(visited[i]);
            Console.Write(" --> ");
        }
        Console.Write(visited[visited.Count() - 1]);

        Console.WriteLine();
        Console.WriteLine();

    }


}
public class Graph
{
    private readonly Dictionary<int, HashSet<int>> map = new Dictionary<int, HashSet<int>>();

    public void addEdge(int node1, int node2)
    {
        HashSet<int> adjacent = null;

        map.TryGetValue(node1, out adjacent);

        if (adjacent == null)
        {
            adjacent = new HashSet<int>();
            map.Add(node1, adjacent);
        }
        adjacent.Add(node2);
    }

    public List<int> adjacentNodes(int last)
    {
        HashSet<int> adjacent = null;

        map.TryGetValue(last, out adjacent);

        if (adjacent == null)
        {
            return new List<int>();
        }
        return new List<int>(adjacent);
    }
}
    }

Answer 1

我认为答案在于您如何对网格中的节点进行编号。对于一个简单的二维网格，4 个节点乘以 4，您可以对它们进行编号:00、01、02、03、10、11、12 ... 30、31、32、33。将它们视为复合数字字符串 (不是十进制值)充当基于维度的节点地址。

在 3 维网格中，它们的编号为 000、001、002 等，直到 330、331、332、333。

如果你想找到两点 10 和 22 之间的所有路线，你可以通过添加维度差异来快速计算它们的距离:1y 与 2y 相差一倍，x0 与 x2 相差二倍。因此节点距离为3，需要经过3条边(共连接4个节点)才能到达目的地。

可以通过创建一组嵌入式 FOR/NEXT 循环(每个维度一个)来枚举解决方案空间(唯一可能涉及解决方案路线的节点)。在这种情况下，10 和 22 的开始值和结束值将产生:10、11、12、20、21 和 22。

现在来了聪明的一点。您可以预先计算(准备)数组中节点之间的“转发”连接表。节点 10 连接到 20 和 11(两者相差 1 个维度)。从中你可以生成从 10 到 22 的一系列有效路径，方法是将一个维度差加到你计划移动的任何方向(在 2-D 数组中你只能选择两种方式之一。在 3-D 中你有三个选择)。

每个答案都应该是尽可能短的距离。这种方法的计算时间应该是毫秒。在 Steam 驱动的 ZX81 上!