网格中的最长路径

Question

网格中的最长路径

3

给定一个网格G，每个单元格可以包含数字[0-9]（含）或大写字母Z；我们可以从左上角开始。然后如果我们所在的单元格数字是a，我们可以向上、下、左或右移动恰好a个单元格，直到我们到达一个字母为止，然后停止。根据这些规则，我们想要找到从起点到网格外的最大路径。如果路径无限，则打印“-1”；

- Hussein Hammoud

1

这是一个典型的动态规划问题，很直接。在当前状态下，除非你更加积极主动，否则你的问题很可能会被关闭。 - Srikar Appalaraju

@SrikarAppal 能否给个指针？我不知道如何解决这个问题。 - G. Bach

“0”是什么情况？它是离一个单元格还是与字母相同？ - Markus Jarderot

2个回答

0

网格形成了一个有可能包含循环的有向图。对于网格中的每个单元格，你将会有一条边延伸到每个方向上距离为n步的单元格。字母节点不会有任何出边。

利用这个图G，试图找到一个拓扑排序。如果存在循环，则无法找到这样的排序，且最长路径将是无限的。使用动态规划计算以每个节点为终点的最长路径。完整的算法可以在最长路径问题上阅读。

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..
....................
....................

- Markus Jarderot

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Srikar Appalaraju · Accepted Answer

好的，要使用动态规划来解决问题，需要具备以下基本特征：

最优子结构 - 较小问题的最优解导致较大问题的最优解。
重叠子问题 - 我们可以存储答案并重复使用它们（这是动态规划效率的来源，否则复杂度将是指数级别）。

那是一些理论知识，回到迷宫问题。由于您希望从起点到终点获得最大路径。这是一个 NP-Hard问题，没有多项式解法存在。具有正权重的图中的一般最大路径问题就像旅行推销员问题一样简单，我们在到达目的地之前访问所有节点，因为最长路径包括所有顶点。

因此，您采取的方法是（也在wiki链接中提到）-

1. 将迷宫视为一个图形。对其执行深度优先搜索（DFS），结果会得到一棵DFS树。 2. 使用深度优先搜索树的根到叶子路径序列，按照搜索遍历它们的顺序，构建具有路径宽度d的图的路径分解。即遍历这个DFS树并且从根到叶子只有一条路径，该路径从a开始，以z结束。 3. 对此路径分解应用动态规划以找到最长路径。