Как рассчитать кратчайший путь между двумя точками в сетке

Question

Я знаю, что доступно много алгоритмов для вычисления кратчайшего пути между двумя точками на графике или сетке, например, все пары в ширину (Флойд), Дейкстра.

Однако, как я заметил, все эти алгоритмы вычисляют все пути в этом графе или сетке, а не только те, которые находятся между двумя интересующими нас точками.

МОЙ ВОПРОС: если у меня есть сетка, то есть двумерный массив, и мне интересно вычислить кратчайший путь между двумя точками, скажем, P1 и P2, и если есть ограничения на то, как я могу двигаться по сетке (например, только по диагонали или только по диагонали и вверх и т. д.), какой алгоритм может это вычислить?

Обратите внимание, что если у вас есть ответ, я бы хотел, чтобы вы опубликовали название алгоритма, а не сам алгоритм (конечно, даже лучше, если вы также опубликуете алгоритм); например, алгоритм Дейкстры, Флойда или любой другой.

Пожалуйста, помогите мне, я думал об этом в течение нескольких месяцев!

---

Окей, ребята, я нашел этот алгоритм на 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);
}
};

Answer 1

Алгоритм Ли: http://en.wikipedia.org/wiki/Lee_algorithm

По сути, это поиск BF, вот пример: http://www.oop.rwth -aachen.de / documents / oop-2007 / sss-oop-2007.pdf

Чтобы эффективно реализовать его, проверьте мой ответ здесь: Изменить алгоритм FloodFill, чтобы получить территорию Вороного для двух точек данных? - когда я говорю «отметка», вы отмечаете его номером на позиции, из которой вы пришли + 1.

Например, если у вас есть эта сетка, где a * = препятствие, и вы можете двигаться вверх, вниз, влево и вправо, и вы начинаете с 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 = количество столбцов. Я думаю, что это самый простой алгоритм для реализации на сетках, и он также очень эффективен на практике. Он должен быть быстрее, чем классическая дижстра, хотя дижстра может победить, если вы реализуете его с помощью кучи.

Answer 2

Используйте алгоритм A Star (A *) .

Answer 3

Вы можете быть дезинформированы. Существуют разные варианты алгоритма Дейкстры. Каждый вычисляет кратчайшие пути от каждой точки до каждой другой точки (как у Флойда).

Однако типичный алгоритм Дейкстры основан на очереди с приоритетами и вычисляет только требуемый кратчайший путь. Во время выполнения он создает несколько путей, но все они являются частичными путями от A до некоторых других узлов, которые могут находиться на конечном пути решения.

Следовательно, вы можете легко интерпретировать свою сетку как график (ограничения, такие как диагонали, могут быть соответствующим образом учтены) и выполнить поиск Дейкстры по кратчайшему пути от A до B на этом. Это просто вопрос моделирования вашей проблемы, а не то, что вам нужен какой-то причудливый алгоритм.

Answer 4

Если ваше движение достаточно ограничено (например, вы можете двигаться только вправо, или вверх, или по диагонали вверх и вправо), то вы можете использовать его перекрывающиеся подзадачи и субоптимальную природу субструктуры и использовать динамическое программирование .

Answer 5

Вот реализация Python кратчайшего пути в матрице от (0,0) до (0, m-1), используя BFS Вы можете изменить это, чтобы соответствовать переменным точкам.

n,m,k1,k2=[int(i) for i in input().split()]
arr=[[int(j) for j in input().split()] for i in range(n)]
x=[[-1 for i in range(m)] for j in range(n)]
x[0][0]=0
vis={}
q=[(0,0)]
while len(q)!=0:
    curr=q[0]
    rem=q.pop(0)
    vis[curr]=True
    r=curr[0]
    c=curr[1]
    if r-1>=0 and arr[r-1][c]==0:
        if vis.get((r-1,c),-1)==-1 or vis[(r-1,c)]!=True:
            q.append((r-1,c))
            x[r-1][c]=x[r][c]+1
    if r+1<n and arr[r+1][c]==0:
        if vis.get((r+1,c),-1)==-1 or vis[(r+1,c)]!=True:
            q.append((r+1,c))
            x[r+1][c]=x[r][c]+1
    if c-1>=0 and arr[r][c-1]==0:
        if vis.get((r,c-1),-1)==-1 or vis[(r,c-1)]!=True:
            q.append((r,c-1))
            x[r][c-1]=x[r][c]+1
    if c+1<m and arr[r][c+1]==0:
        if vis.get((r,c+1),-1)==-1 or vis[(r,c+1)]!=True:
            q.append((r,c+1))
            x[r][c+1]=x[r][c]+1
    #for i in x:
        #print(i)
ans=x[0][m-1]
if ans==-1:
    print(-1)
else:
    print(ans)

• входная матрица должна состоять из 0 и 1. 0 для возможного движения.
• n - количество строк.
• m - количество столбцов.
• arr - заданная матрица.
• x - матрица расстояний от (0,0).
• vis - это словарь, дающий логическое значение, если узел посещен.
• вывод -1 показывает, что такой путь невозможен.

Answer 6

Что я не понимаю, так это то, что если вам нужен кратчайший путь между А и В, вам все равно не нужно смотреть на А - С и А - D , если С и D указывают на В ? Ваш кратчайший путь вполне может быть A-C-B или A-D-B. Вам просто нужно выбросить неподключенные узлы. В одном из моих проектов я взял точки A и B, проверил, какие другие точки были связаны, а те, которые не были удалены, были удалены из всего графика. Затем я приступил к использованию алгоритма Дейкстры.

Answer 7

используйте алгоритм * для нахождения пути между двумя точками в 2D-сетке. http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html

Answer 8

Ваша сетка формирует график (или, по крайней мере, может рассматриваться как график). Исключение некоторых направлений движения указывает на то, что это ориентированный граф. Если вы вообще не можете переходить с одного узла на другой, это край, которого нет на графике.

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

Редактировать: Я посмотрел на ответ, который вы опубликовали, но я не уверен, что этот код должен быть / делать. Например, он имеет: if(y>=0) max(abs(x),y);. Это не кажется (по крайней мере мне) большим смыслом - результат от max просто отбрасывается. Чтобы сделать что-то полезное, его нужно вернуть или назначить или что-то в этом порядке. В настоящее время лучшее, на что вы можете надеяться, это то, что компилятор определяет его как мертвый код и ничего для него не генерирует.

Я предполагаю, что код на самом деле работает не совсем так, как задумано, и если он делает что-то полезное, это скорее случайно, чем дизайн. Потребовалось бы немало времени и усилий, чтобы убедиться, что вы разобрались с подобными проблемами до такой степени, что вы действительно были уверены в том, что они сделали, и еще труднее угадать, что на самом деле было задумано.