algorithm - 网格中的最长路径

Question

给定一个网格 G。每个单元格可以包含数字 [0 - 9] 或大写字母（比如 Z）；我们可以从左上角开始。然后，如果我们所在的单元格编号是 a，我们可以允许将一个单元格向上、向左或向右移动。直到我们到达一个字母字母，然后我们才停下来。鉴于这些规则，我们希望找到从开始到离开网格的最大路径。如果路径是无限的，打印“-1”；

Answer 1

好的，要使用动态编程解决问题，需要具有这些基本属性 -

1. 最佳子结构 - 最佳溶胶。更小的问题会导致最优解。到更大的问题。
2. 重叠子问题——我们可以存储答案并重用它们（这就是提高动态编程效率的原因，否则复杂性将是指数级的）。

那是一些理论，回到迷宫问题。因为你想要从头到尾的最大路径。这是一个NP-Hard 问题，不存在多项式解决方案。具有正权重的图中的一般最大路径问题就像旅行推销员问题一样简单，我们在到达目的地之前访问所有节点，因为最长路径包括所有顶点。

所以你采取的方法是这样的（也在wiki链接中提到） -

1. 把你的迷宫想象成一个图表。对其执行 DFS，这将产生一个 DFS 树。
2. 使用深度优先搜索树的从根到叶的路径序列，按照搜索遍历的顺序，构造图的路径分解，用 pathwidth die 遍历这棵 DFS 树，一条路径将从根到叶都在那里，从 开始到a结束z。
3. 将动态规划应用于此路径分解以找到最长的路径。

Answer 2

网格形成一个有向图，有可能的循环。对于网格中的每个单元格，您将有一条边沿每个方向延伸到n步外的单元格。字母节点将没有任何传出边。

使用此图 G，尝试找到拓扑排序。如果有任何循环，则不可能有这样的排序，并且最长的路径将是无限的。使用 DP 计算结束于每个节点的最长路径。完整的算法可以在最长路径问题上阅读。

void Main()
{
    string text = @"
        75XXX83XXXXX9X06218X
        XX93X7XX4X87XXX611X6
        4XXXX7X5XXXXX3XXX74X
        X5XXX2XXXX5162X7XX97
        X72X1XXXXXXXX2XXX2XX
        9X617X8XX7XXXX1931XX
        X6X14X43XXXXXXXX0166
        7XXX3XXX10XXX30315XX
        X410XXX2XX91X6XX77XX
        X42XXX7XXXXX59X2XXX5
    ";
    int pathLength = FindLongestPathInGrid(text);
    Console.WriteLine(pathLength);
}

int FindLongestPathInGrid(string text)
{
    int pathLength = -1;

    var grid = StringToGrid(text);
    var nodes = GridToNodes(grid);
    var ordering = TopologicalSort(nodes);

    if (ordering != null)
    {
        var longestPath = FindLongestPath(ordering);
        pathLength = longestPath.Count;
    }

    return pathLength;
}

char[,] StringToGrid(string text)
{
    var lines = text.Split('\n')
        .Select(l => l.Trim())
        .Where(l => !string.IsNullOrEmpty(l))
        .ToList();

    var height = lines.Count;
    var width = lines.Max(l => l.Length);

    var grid = new char[height,width];
    for (int y = 0; y < height; y++)
    {
        var line = lines[y];
        for (int x = 0; x < line.Length; x++)
        {
            grid[y, x] = line[x];
        }
    }
    return grid;
}

class Node
{
    public int Index { get; private set; }
    public int Order { get; set; }
    public List<Node> Outgoing { get; private set; }
    public List<Node> Incoming { get; private set; }

    public Node(int index)
    {
        Index = index;
        Order = index;
        Outgoing = new List<Node>();
        Incoming = new List<Node>();
    }

    public void AddOutgoing(Node other)
    {
        Outgoing.Add(other);
        other.Incoming.Add(this);
    }
}

IList<Node> GridToNodes(char[,] grid)
{
    int height = grid.GetLength(0);
    int width = grid.GetLength(1);

    // Create the nodes
    var nodes = new List<Node>();
    for (int y = 0; y < height; y++)
    for (int x = 0; x < width; x++)
    {
        nodes.Add(new Node(y*width + x));
    }

    // Connect them
    for (int y = 0; y < height; y++)
    for (int x = 0; x < width; x++)
    {
        var node = nodes[x+y*width];
        if ('0' <= grid[y,x] && grid[y,x] <= '9')
        {
            int n = grid[y,x] - '0' + 1; // '0'..'9' -> 1..10
            if (x-n >= 0) node.AddOutgoing(nodes[x-n+y*width]);
            if (x+n < width) node.AddOutgoing(nodes[x+n+y*width]);
            if (y-n >= 0) node.AddOutgoing(nodes[x+(y-n)*width]);
            if (y+n < height) node.AddOutgoing(nodes[x+(y+n)*width]);
        }
    }

    return nodes;
}

IList<Node> TopologicalSort(IList<Node> Nodes)
{
    // Compute the in-degree of each node
    var incomingCount = Nodes.Select(n => n.Incoming.Count).ToList();

    int nodeCount = Nodes.Count;

    List<Node> result = new List<Node>();
    while (nodeCount > 0)
    {
        // Find the index of any node with in-degree 0
        var node = Nodes
            .Where((n,i) => incomingCount[i] == 0)
            .FirstOrDefault();

        // None found. No ordering possible.
        if (node == null) return null;

        nodeCount--;

        // Add it to the output
        node.Order = result.Count;
        result.Add(node);

        // Remove it from further consideration
        incomingCount[node.Index] = -1;

        // Decrement the in-degree of any connected nodes.
        foreach (var neighbor in node.Outgoing)
        {
            incomingCount[neighbor.Index]--;
        }
    }

    return result;
}

IList<Node> FindLongestPath(IList<Node> nodeOrdering)
{
    int count = nodeOrdering.Count;
    Node[] cameFrom = new Node[count];
    int[] longestPath = new int[count];

    foreach (var node in nodeOrdering)
    {
        if (node.Incoming.Count > 0)
        {
            Node best = node.Incoming.MaxBy(n => longestPath[n.Order]);
            cameFrom[node.Order] = best;
            longestPath[node.Order] = longestPath[best.Order] + 1;
        }
    }

    var maxLength = longestPath.Max();

    var last = nodeOrdering.MaxBy(n => longestPath[n.Order]);
    return ReconstructPath(cameFrom, last);
}

IList<Node> ReconstructPath(Node[] cameFrom, Node last)
{
    var result = new List<Node>();
    while (last != null)
    {
        result.Add(last);
        last = cameFrom[last.Order];
    }

    result.Reverse();
    return result;
}

public static class Extensions
{
    public static TItem MaxBy<TItem,TKey>(this IEnumerable<TItem> items, Func<TItem,TKey> keySelector)
    {
        var currentBestItem = default(TItem);
        var currentBestKey = default(TKey);
        var comparator = Comparer<TKey>.Default;
        bool hasBest = false;
        foreach (var item in items)
        {
            var key = keySelector(item);
            if (!hasBest || comparator.Compare(key, currentBestKey) > 0)
            {
                currentBestKey = key;
                currentBestItem = item;
                hasBest = true;
            }
        }
        return currentBestItem;
    }
}

例子：

75XXX83XXXXX9X06218X
XX93X7XX4X87XXX611X6
4XXXX7X5XXXXX3XXX74X
X5XXX2XXXX5162X7XX97
X72X1XXXXXXXX2XXX2XX
9X617X8XX7XXXX1931XX
X6X14X43XXXXXXXX0166
7XXX3XXX10XXX30315XX
X410XXX2XX91X6XX77XX
X42XXX7XXXXX59X2XXX5

最大路径长度为 11，总共有 4 个这样的路径。这是一个：

....................
...3....4......6.1..
....................
...X................ <-- end
....................
...1................
................0... <-- start
.............30.15..
....................
....................