C#中如何使用prim算法遍历矩形数组中的单元格

Question

在一个矩形数组中，我需要获取一条路径，该路径由一系列从给定起点（单元格）开始的最长路径组成。我做了一个简单的搜索，搜索什么是合适的搜索算法来实现这样的任务，发现素数算法是最可取的技术。它实际上是 "Prime Algorithm" 还是其他？

我尝试使用基于 Dijkstra 算法的标准递归，但无法获得正确的路径。

下面的代码是针对windows表单应用的，有时会输出正确的结果，有时却不会：

namespace AUV_Topology
{
    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.IO;


        /* Class Cell */
        /*****************************************************************************************************************************/

        public class Cell
        {
            public int row { get; set; }
            public int col { get; set; }
            public int value { get; set; }
            public Boolean visited { get; set; }
        }

        /* Class EnumCell  */
        /*****************************************************************************************************************************/

        public class EnumCell : IEnumerator<Cell>
        {
            public EnumCell() { }

            public EnumCell(int startRow, int startCol, List<List<Cell>> graph)
            {
                this.row = startRow;
                this.col = startCol;
                this.numberOfRows = graph.Count;
                this.numberOfCols = graph[0].Count;
                this.graph = graph;
            }

            public enum XY
            {
                Y = 0,  //row
                X = 1   //col
            }

            public enum LOCATIONS : byte
            {
                TOP_LEFT = 0,
                TOP_MIDDLE,
                TOP_RIGHT,
                LEFT,
                RIGHT,
                BOTTOM_LEFT,
                BOTTOM_MIDDLE,
                BOTTOM_RIGHT,
                END,
                INVALID
            }

            public List<List<Cell>> graph { get; set; }
            public int row { get; set; }
            public int col { get; set; }
            public int numberOfRows { get; set; }
            public int numberOfCols { get; set; }

            //offsets are in same order as enum location as y-offset(row), x-offset (col)
            private List<List<int>> offsets = new List<List<int>>() {
                    new List<int>() { -1, -1 },
                    new List<int>() { -1, 0 },
                    new List<int>() { -1, +1 },
                    new List<int>() { 0, -1 },
                    new List<int>() { 0, +1 },
                    new List<int>() { +1, -1 },
                    new List<int>() { +1, 0 },
                    new List<int>() { +1, +1 }
                };
            public LOCATIONS position { get; set; }

            public EnumCell GetEnumerator()
            {
                return new EnumCell(row, col, graph);
            }

            object IEnumerator.Current
            {
                get {
                    return Current;
                }
            }

            /* Class Current Cell  */
            /*****************************************************************************************************************************/
            public Cell Current
            {
                get {
                    try {
                        // move to first valie postion
                        for (LOCATIONS location = position; location < LOCATIONS.END; location++) {
                            if ((row + offsets[(byte)location][(int)XY.Y] >= 0) && (row + offsets[(byte)location][(int)XY.Y] < numberOfRows) &&
                                (col + offsets[(byte)location][(int)XY.X] > 0) && (col + offsets[(byte)location][(int)XY.X] < numberOfCols)) {
                                position = (LOCATIONS)location;
                                int newRow = row + offsets[(byte)location][(int)XY.Y];
                                int newCol = col + offsets[(byte)location][(int)XY.X];
                                return graph[newRow][newCol];
                            }
                        }
                        throw new InvalidOperationException();
                    } catch (IndexOutOfRangeException) {
                        throw new InvalidOperationException();
                    }
                }
            }

            public Boolean MoveNext()
            {
                Boolean results = false;
                for (LOCATIONS location = ++position; location < LOCATIONS.END; location++) {
                    int y = offsets[(byte)location][(int)XY.Y];
                    int x = offsets[(byte)location][(int)XY.X];
                    if ((row + y >= 0) && (row + y < numberOfRows) &&
                        (col + x > 0) && (col + x < numberOfCols)) {
                        if (graph[row + y][col + x].value == 1) {
                            position = (LOCATIONS)location;
                            return true;
                        }
                    }
                }
                return results;
            }

            public void Reset()
            {
                position = LOCATIONS.TOP_LEFT;
            }

            public void Dispose()
            {
            }
        }

        /* Class Graph  */
        /*****************************************************************************************************************************/
        public class Graph
        {
            public Graph(int[,] graph)
            {
                this.graph = new List<List<Cell>>();
                for (int row = 0; row < graph.GetLength(0); row++) {
                    List<Cell> newRow = new List<Cell>();
                    this.graph.Add(newRow);
                    for (int col = 0; col < graph.GetLength(1); col++) {
                        Cell newCell = new Cell();
                        newRow.Add(newCell);

                        newCell.row = row;
                        newCell.col = col;
                        newCell.value = graph[row, col];
                        newCell.visited = false;
                    }
                }
            }
            public List<List<Cell>> graph;
        }

        /* Class SpanningTree  */
        /*****************************************************************************************************************************/
        class SpanningTree
        {
            public static Graph graph = null;
            public static SpanningTree root = new SpanningTree();

            public static int counter = 0;

            public int row { get; set; }
            public int col { get; set; }
            public int length { get; set; }
            public List<SpanningTree> children { get; set; }

            public SpanningTree() { }
            public SpanningTree(int startRow, int startCol, int[,] graph)
            {
                SpanningTree.graph = new Graph(graph);
                RecursiveTree(root, SpanningTree.graph.graph[startRow][startCol]);
            }

            public int RecursiveTree(SpanningTree parent, Cell currentCell)
            {
                int length = 0;
                int maxLength = 0;
                parent.row = currentCell.row;
                parent.col = currentCell.col;

                graph.graph[currentCell.row][currentCell.col].visited = true;

                EnumCell enumCell = new EnumCell(currentCell.row, currentCell.col, graph.graph);
                foreach (Cell cell in enumCell) {
                    if (!cell.visited) {
                        SpanningTree newBranch = new SpanningTree();
                        if (parent.children == null) parent.children = new List<SpanningTree>();
                        parent.children.Add(newBranch);
                        length = RecursiveTree(newBranch, SpanningTree.graph.graph[cell.row][cell.col]);
                        if (length > maxLength) maxLength = length;
                    }
                }
                graph.graph[currentCell.row][currentCell.col].visited = false;

                parent.length = maxLength;
                return maxLength + 1;
            }

            public static void OrderHighLow(SpanningTree parent, int level)
            {
                if (parent.children != null) {
                    parent.children = parent.children.OrderByDescending(x => x.length).ToList();
                    foreach (SpanningTree child in parent.children) {
                        OrderHighLow(child, level + 1);
                    }
                }
            }

            public static void Print(SpanningTree parent, int level, int chromosomeNum)
            {
                FileStream fs = new FileStream("C:/Users/Welcome/Desktop/TreeParser.txt", FileMode.Append, FileAccess.Write);
                using (StreamWriter sw = new StreamWriter(fs)) {
                    sw.WriteLine("------------------- Chromosome : {0} -------------------", chromosomeNum);
                    Print(parent, level, sw);
                    sw.WriteLine("---------Longest----------");
                    PrintLongest(parent, level, sw);
                    counter = 0;
                }
            }

            private static void Print(SpanningTree parent, int level, StreamWriter sw)
            {
                //////////////////////////////////////////////////////////////////////
                sw.WriteLine("{0}Level : '{1}', Row : '{2}', Col : '{3}', Length : '{4}'", new string(' ', 4 * level), level, parent.row, parent.col, parent.length);
                //////////////////////////////////////////////////////////////////////

                if (parent.children != null) {
                    foreach (SpanningTree child in parent.children) {
                        Print(child, level + 1, sw);

                        if (child.length == 0) {
                            sw.WriteLine("||,,,,,,Branch {0},,,,,,||", counter);
                            level = 0;
                            sw.WriteLine("{0}Level : '{1}', Row : '{2}', Col : '{3}', Length : '{4}'", new string(' ', 4 * level), level, root.row, root.col, root.length);
                            counter += 1;
                        }
                    }
                }
            }

            public static void PrintLongest(SpanningTree parent, int level, StreamWriter sw)
            {
                //////////////////////////////////////////////////////////////////////
                sw.WriteLine("{0}Level : '{1}', Row : '{2}', Col : '{3}', Length : '{4}'", new string(' ', 4 * level), level, parent.row, parent.col, parent.length);
                //////////////////////////////////////////////////////////////////////

                if (parent.children != null) {
                    PrintLongest(parent.children[0], level + 1, sw);
                }
            }
        }

}// end name space

我在主窗体中进行了调用：

 int tt = 0;

 foreach (int[,] graph in rectArrays)
 {
     new SpanningTree(indexesX[tt], indexesY[tt], graph);
     SpanningTree.OrderHighLow(SpanningTree.root, 0);
     SpanningTree.Print(SpanningTree.root, 0,tt);
     tt++;
 }

这是最新的结果：Debug

问题 1

有时路径没有预期的那么长，即一些情况（单元格）没有包括在内，但它应该包括在内！，有时路径包含值为零的单元格，有时它从一个单元格移动到另一个单元格，而它们不在彼此相邻！

问题2

当我使用9 x 9或以上的大矩阵时；我得到以下信息：

Exception of type 'System.OutOfMemoryException' was thrown.

Answer 1

在方法RecursiveTree中替换条件

if (!cell.visited)

来自

if (!cell.visited && cell.value == 1)

这会根据需要将搜索限制为值 = 1 的单元格。

你的算法比较复杂和纠结。此外，命名使得很难猜测事情的作用。例如，不清楚 EnumCell 枚举的内容。顾名思义，它是一种通用枚举器；但是，MoveNext() return 仅具有 value == 1 的位置。为什么有一个变量 results 总是 false？为什么逻辑在 MoveNext() 和 Current 之间分裂？ Current 应该只 return 在 MoveNext 中找到的值。如果 MoveNext 工作正常，则 Current 中不需要其他逻辑。您的代码中还有很多其他类似的奇怪之处。 C# 有一个 yield return 语句，它使编写枚举器变得容易得多。

尝试简化您的代码并调试它。

我实现了一个回溯解决方案，return所有解决方案都具有最大路径长度。除了设置和打印结果外，没有涉及其他逻辑：

声明：

private int[,] _world;
private bool[,] _visited;

[DebuggerDisplay("Coord({Row}, {Col})")]
private struct Coord
{
    public Coord(int row, int col)
    {
        this.Row = row;
        this.Col = col;
    }
    public readonly int Row;
    public readonly int Col;
}

回溯算法（在路径的有效起点调用Find）：

// Returns a list of paths of maximum length consisting of lists of coordinates.
private List<List<Coord>> Find(int row, int col)
{
    _visited[row, col] = true;
    var allResults = new List<List<Coord>>();
    for (int i = Math.Max(0, row-1); i <= Math.Min(_world.GetLength(0)-1, row+1); i++) {
        for (int j = Math.Max(0, col-1); j <= Math.Min(_world.GetLength(1)-1, col+1); j++) {
            if (!_visited[i, j] && _world[i, j] == 1) {
                List<List<Coord>> result = Find(i, j);
                allResults.AddRange(result);
            }
        }
    }
    if (allResults.Count == 0) {
        // This is an end-point of a path. Create the new path with current coord.
        // We construct the paths backward.
        allResults.Add(new List<Coord> { new Coord(row, col) });
    } else {
        // Keep only longest results
        int maxLength = allResults.Max(p => p.Count);
        for (int i = allResults.Count - 1; i >= 0; i--) {
            if (allResults[i].Count < maxLength) {
                allResults.RemoveAt(i);
            } else {
                // Prepend current point to path.
                allResults[i].Insert(0, new Coord(row, col));
            }
        }
    }
    _visited[row, col] = false;
    return allResults;
}

请注意，完整的结果树仅存在于调用堆栈中，而不是作为显式数据结构存在。路径（坐标列表）是从路径终点向后到起点创建的。

与这个世界

private int[,] _world = new[,] {
    { 0, 1, 0, 1 },
    { 0, 1, 0, 1 },
    { 0, 1, 1, 0 },
    { 1, 0, 0, 1 },
    { 1, 1, 0, 1 },
 };

对于起始坐标（行 = 0，列 = 1），我的解决方案打印（未显示打印例程本身）：

Result #1, Length = 7
| ||1|| ||·|
| ||2|| ||·|
| ||4||3|| |
|5|| || ||·|
|6||7|| ||·|

Result #2, Length = 7
| ||1|| ||·|
| ||2|| ||·|
| ||4||3|| |
|5|| || ||·|
|7||6|| ||·|

如果您注释掉丢弃较短结果的部分，您可以看到有 8 条可能的路径（2 条长度为 5，4 条长度为 6，2 条长度为 7）。

C#中如何使用prim算法遍历矩形数组中的单元格

How to use prim algorithm to traverse cells in a rectangular array in C#

c#

algorithm

search

tree-traversal

multidimensional-array