Как вычислить кратчайший путь между двумя точками в сетке
Я знаю, что много алгоритмов доступны для вычисления кратчайшего пути между двумя точками в графике или сетке, как в ширину, все-пары (Floyd's), Dijkstra.
Однако как я заметил, все эти алгоритмы вычисляют все пути в том графике или сетке, не только тех, которые между двумя точками, которыми мы интересуемся.
МОЙ ВОПРОС: если у меня есть сетка, т.е. двумерная матрица, и я интересуюсь вычислениями кратчайшего пути между двумя точками, скажите P1 и P2, и если существуют ограничения на способ, которым я могу переместиться в сетку (например, только по диагонали, или только по диагонали и вверх, и т.д.), какой алгоритм может вычислить это?
Заметьте здесь, что, если бы у Вас есть ответ, я хотел бы, чтобы Вы отправили название алгоритма, а не самого алгоритма (конечно, еще лучше если Вы также отправляете алгоритм); например, ли это - алгоритм Dijkstra, или Floyd, или что бы то ни было.
Помогите мне, я думал об этом в течение многих месяцев!
парни okey я нашел этот алгоритм на TOPCODER.COM здесь в сетке, которую можно переместить только (по диагонали и), но я не могу понять, какой алгоритм - это каким-либо образом, кто-либо мог знать?
#include<iostream>
#include <cmath>
using namespace std;
inline int Calc(int x,int y)
{
if(abs(x)>=abs(y)) return abs(x);
int z=(abs(x)+abs(y))/2;
return z+abs(abs(x)-z);
}
class SliverDistance
{
public:
int minSteps(int x1,int y1, int x2, int y2)
{
int ret=0;
if(((x1+y1)&1)!=((x2+y2)&1))y1++,ret++;
return ret+Calc(x2-x1,y2-y1);
}
};
6 ответов
Алгоритм Ли: http://en.wikipedia.org/wiki/Lee_algorithm
По сути, это поиск BF, вот пример: http://www.oop.rwth-aachen.de/documents/oop-2007/sss-oop-2007.pdf
Чтобы реализовать это эффективно, проверьте мой ответ здесь: Изменить алгоритм FloodFill чтобы получить территорию Вороного для двух точек данных? - когда я говорю «отметка», вы отмечаете ее номером в позиции, откуда вы пришли + 1.
Например, если у вас есть эта сетка, где * = препятствие и вы можете двигаться вверх, вниз, влево и вправо, и вы начинаете с S и должны перейти к D, и 0 = свободная позиция:
S 0 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D
Вы помещаете S в свою очередь, затем «расширяете» ее:
S 1 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D
Затем расширяете все его соседи:
S 1 2 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D
И все соседи этих соседей:
S 1 2 3
* * 3 *
* 0 0 *
0 0 * *
* 0 0 D
И так далее, в итоге вы получите:
S 1 2 3
* * 3 *
* 5 4 *
7 6 * *
* 7 8 9
Итак, расстояние от S до D равно 9. Время работы - O ( NM), где N = количество строк и M = количество столбцов.Я думаю, что это самый простой алгоритм для реализации на сетках, и он также очень эффективен на практике. Он должен быть быстрее, чем классический dijkstra, хотя dijkstra может выиграть, если вы реализуете его с использованием кучи.
Возможно, вы дезинформированы. Существуют различные варианты алгоритма Дейкстры. Один вычисляет кратчайшие пути из каждой точки в каждую другую точку (как у Флойда).
Однако типичный алгоритм Дейкстры основан на очереди приоритетов и вычисляет только требуемый кратчайший путь. Он строит несколько путей во время своего выполнения, но это все частичные пути от A к некоторым другим узлам, которые могут быть на конечном пути решения.
Следовательно, вы можете легко интерпретировать вашу сетку как граф (ограничения, такие как диагонали, могут быть учтены соответствующим образом) и запустить поиск кратчайшего пути из A в B по Дейкстре. Это действительно просто вопрос моделирования вашей проблемы, а не того, что вам нужен какой-то причудливый алгоритм.
Если ваше движение достаточно ограничено (например, вы можете двигаться только вправо, или вверх, или по диагонали вверх и вправо), то вы можете воспользоваться его перекрывающимися подпроблемами и субоптимальной природой подструктуры и использовать динамическое программирование.
Я не понимаю, что если вам нужен кратчайший путь между A и B, вам все равно нужно смотреть на A в C и A в D , если C и D указывают на B ? Ваш кратчайший путь вполне может быть A-C-B или A-D-B. Вам просто нужно выкинуть неподключенные узлы. В одном из своих проектов я взял точки A и B, проверил, какие еще точки были соединены, а те, которые не были, были удалены со всего графика. Затем я приступил к использованию алгоритма Дейкстры.
Ваша сетка образует граф (или, по крайней мере, может рассматриваться как граф). Исключение некоторых направлений движения указывает на то, что это направленный граф. Если вы вообще не можете перемещаться от одного узла к другому, то это ребро, которого нет в графе.
Как только вы закодировали вашу сетку в виде графа, это простой вопрос выбора из известных алгоритмов графов (о которых вы, очевидно, уже знаете) для его обхода для получения нужного вам типа результата (например, кратчайшего пути).
Edit: Я просмотрел ответ, который вы опубликовали, но я не уверен, что этот код должен быть/делать. Просто для примера: if(y>=0) max(abs(x),y);. Это не имеет смысла (по крайней мере, для меня) - результат от max просто отбрасывается. Чтобы добиться чего-то полезного, его нужно вернуть, присвоить или что-то в этом роде. В таком виде лучшее, на что вы можете надеяться, это то, что компилятор заметит его как мертвый код и не будет ничего для него генерировать.
Я думаю, что код на самом деле работает не совсем так, как задумывалось, а если он и делает что-то полезное, то скорее случайно, чем специально. Потребуется достаточно много времени и усилий, чтобы убедиться, что вы разобрались с подобными проблемами до такой степени, что вы действительно уверены в том, что это делает, и еще труднее угадать, что действительно было задумано.