Самый длинный путь в сетке

Question

Для заданной сетки G. Каждая ячейка может содержать числа [0 - 9] включительно или алфавитную букву верхнего регистра (скажем, Z); мы можем начать с верхнего левого угла. Тогда, если номер ячейки, на которой мы находимся, равен a, мы можем позволить перемещать ровно ячейку вверх, вниз, влево или вправо. Пока мы не достигнем буквы алфавита, мы останавливаемся. Учитывая эти правила, мы хотим найти максимальный путь от начала до выхода из сетки. Если путь бесконечен, выведите "-1";

Answer 1

Хорошо, чтобы решить с помощью динамического программирования, проблема должна иметь эти существенные свойства -

1. Оптимальная субструктура - оптимальное сол. к меньшим проблемам приводит к оптимальному решению. к большим проблемам.
2. Перекрывающиеся подзадачи - мы можем хранить ответы и использовать их повторно (это то, что дает динамическое программирование, иначе сложность будет экспоненциальной).

Это была некоторая теория, возвращающаяся к проблеме лабиринта. Так как вы хотите МАКСИМАЛЬНЫЙ путь от начала до конца. Это проблема NP-Hard, и полиномиального решения не существует. Общая проблема максимального пути в графе с положительными весами так же проста, как и проблема с коммивояжером, когда мы посещаем все узлы до достижения пункта назначения, поскольку самый длинный путь включает все вершины.

Таким образом, подход, который вы выбираете, это (также упоминается в вики-ссылке) -

1. Рассмотрим ваш лабиринт как график. Выполните DFS на нем, что приведет к DFS-дереву.
2. Используйте последовательность путей от корня к листу дерева поиска в глубину, в том порядке, в котором они были найдены при поиске, чтобы построить декомпозицию пути графа, с указанием ширины пути. Обход этого дерева 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..
....................
....................