Алгоритм нахождения кратчайшего пути!
- Автор темы Kudesnik
- Дата начала
Вот.Kudesnik сказал(а):
От себя - рекомендую пользоваться волновым алгоритмом.
http://itsprogs.chat.ru/Read/puti.htm
Хочу рассказатьнемногооб алгоритмах нахождения кратчайшего пути.
Типа вступление.
Еще на зоре развития компьютерных игр перед программистами игроделами возникла такая проблема: вот у нас есть пересеченная местность, и есть человечек и нужно, чтоб он (человечек) пробежался от одного места до другого. Причем не как попало, а как можно быстрее, чтоб сделать как можно меньше хадов. Десятки, а может и сотни программеров, ломали себе головы над тем как заставить этого человечка бежать по самому лучшему, оптимальному, кратчайшему пути. Ну слава богу не перевелась земля еще умными и находчивыми людьми и сегодня мы можем воспользоваться их трудами. Вот о таких то трудах я и расскажу.
Алгоритм правой - левой руки.
Суть его проста до безобразия! Кто-то великий и мудрый сказал: "да я из любого лабиринта смогу выйти!". Наверно он надеялся на правело правой - левой руки. А суть его такова:
Взяться левой рукой за стенку и не отпускаясь топать, топать, при этом не забывать помечать где уже были т.е. оставлять сзади себя след. Топая, таким образом, может куда-нибудь, и придем (может даже на финишную точку нарвемся). А зачем же нам след? А это на тот случай когда у нас зацикливание и если такое случилось можно, например руку поменять.
Глюк способа: а вдруг мы будем вокруг одного столба крутиться?! Как в том анекдоте: Пьяный вокруг бочки ползает: "Вот блин! Когда этот долбанный забор кончится?!!"
Но на мой взгляд алгоритм оптимально подходит для движения например танчиков (все знают о чем я?) в лабиринте. (например танкам нужно двигаться от своего места рождения до твоего флага, чтоб его уничтожить!)
А теперь посерьезней способ.
Как известно самый короткий путь это прямая, поэтому прокладываем от стартовой точки до финишной прямую. И бежим по ней. Конечно проверяя, что впереди... Если наткнулись на препятствие, то начинаем его обходить по правилу рук (см. выше) до тех пор пока не вернемся на начальную прямую.
По-моему алгоритм мало подходит для сильно пересеченной местности (лабиринт в танчиках, например), но зато более эффективный в стратегиях.
Глючит когда наша прямая проходит через препятствие, напоминающее подкову, наш человечек (или танк или робот или мертвец или что там у вас?) начинает зацикливаться. Но если подумать можно и этот глюк исправить дополнив слегка алгоритм.
Ну и самое серьезное и эффективное Алгоритм А*!
А* - (А звезда) или его еще называют волновым.
По нашей карте от финишной (!) точки распространяется волна. С каждым шагом, увеличиваясь на 1. И так до тех пор, пока не достигнет стартовой (!) точки. Далее действуем от стартовой точки. Берем по убыванию значения волны, прокладывая тем самым путь к финишу. Естественно, что это все делается в вспомогательном массиве, чтобы не повредить исходнуюкарту.
Глюков особых не замечено, путь находится всегда (если он конечно вообще существует). Проблема может только в относительной сложности реализации и работе по времени.
Ну вот, вкратце рассказал... если есть вопросы или что не понятно пишите на мыло. Или следите за обновлениями на моем сайте.
(с) Белоногов Илья, ноябрь 2002.
И еще...
http://www.csu.ac.ru/~yan/mvs2002/Mvslab_7.htm
Лабораторная работа № 7.
Алгоритм нахождения кратчайшего пути.
Задача. Составить и реализовать параллельный алгоритм нахождения кратчайших путей на заданном графе для любой пары вершин графа, используя алгоритм Флойда.
Алгоритм Флойда.
Рассматривается задача нахождения кратчайших путей между всеми парами узлов сети
G
V,E), где V={vi} i=1,n - множество вершин графа, E - множество дуг соединяющих вершины графа E = {(vi,vj)} i не равно j. Граф G - ориентированный граф, задается матрицей смежностей, например.
Фигура 1: Простой ориентированный граф G, и его матрица смежностей, A. Элементы матрицы смежности определяются следующим образом:
aij = 1, если существует дуга из i в j, aij = 0 , если нет дуги из i в j.
Каждой дуге ставится в соответствие число cij - длина дуги направленной из вершины i в вершину j.
Обозначим d*ij - кратчайший путь из вершины i в j. Пусть dij - наилучшая оценка длины кратчайшей цепи, соединяющей вершины (i, j). Первоначально за длину кратчайшей цепи между i и j принимается длина дуги (i, j), соединяющей эти узлы. Затем последовательно проверяются всевозможные промежуточные вершины, расположенные между i и j. Если длина цепи, проходящей через некоторую промежуточную вершину меньше текущего значения dij, то переменной dij присваивается новое значение. Данная процедура повторяется для всевозможных пар узлов, пока не будут получены все значения d*ij.
Фигура 2. Основная операция в алгоритме Флойда. Определяется будет ли путь из вершины i в j через вершину k короче, чем прямой путь из i в j.
Алгоритм Флойда позволяет решить задачу о нахождении кратчайших путей для сети из n вершин за n итераций. Обозначим dij( l ) оценку длины кратчайшей цепи из вершины i в j полученную на l - й итерации, тогда ее получение может быть определено следующей операцией
dij( l) = min{dij( l-1);dil (l-1) + dlj( l-1)} (1).
Если операцию (1) выполнить с данной парой узлов i и j и всеми узлами l в порядке возрастания номеров l, то значение dij( n ) полученное на последней итерации, будет равно длине кратчайшей цепи из узла i в узел j.
Последовательный алгоритм Флойда.
Реализация последовательного алгоритма Флойда приведена в следующей функции matrd.
#include<stdio.h>
#include<stdlib.h>
#define maxs 100
int d[maxs][maxs];
void matrd(int n)
{
int i,j,k;
for(l=0;l<n;l++){
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(d[j] > (d[l]+d[l][j])){
d[j]= d[l]+d[l][j];
}
}
}
}
Чтобы применить этот алгоритм необходимо сформировать матрицу D0={dij(0)}.Построение матрицы D0 выполняется следующим образом:
dij(0) = cij, если существует дуга из i в j;
dij(0) = 0, если i= j;
dij(0) = бесконечности, если нет дуги из i в j.
Матрица D0 подобна матрице смежности только 1 заменяются на соответствующие длины дуг cij . Параллельный алгоритм Флойда.
Рассмотрим параллельный алгоритм Флойда основанный на одноразмерном разбиении матрицы D по P процессорам. Используя функцию Del(N,P,k) необходимо распределить блоками смежные строки матрицы D0 по P процессам, для каждого блока определяется номер первой строки блока и количество строк в блоке. Схематично это можно изобразить следующим образом
Фигура 3: Параллельный алгоритм Флойда основанный на одноразмерной декомпозиции. В (а) расположены данные одной задачи: блок смежных строк.
В (b) на k - м шаге алгоритма находится собственный блок смежных строк и k - я
строка которая передается из другого процессора.
На каждом шаге один процесс передает одну строку всем остальным. Этот процесс будем называть корневым. Сначала процесс П0 передает свою первую строку всем остальным процессорам. Затем все процессы выполняют операцию (1). Затем П0 передает вторую строку и т.д. Когда процесс П0 передаст все свои строки, начинает передачу процесс П1. Процесс заканчивается, когда Пр передаст свою последнюю строку.
/* Начало алгоритма Флойда */
for(l=0;l<n;l++){
if((l>=nrl)&&(l<(nrl+nr))) { /*nrl - номер первой строки в блоке, nr - число строк в блоке*/
for(j=0;j<N;j++) { /*занесение передаваемой строки в буфер на корневом процессе}
buf[j]=d[l][j];
}
}
rk=root1(l,N,P); /* определение номера корневого процесса */
printf("Process % d send all\n",k);
MPI_Bcast(&buf, N, MPI_INT, rk, MPI_COMM_WORLD);
/* передача буфера всем остальным процессам */
MPI_Barrier (MPI_COMM_WORLD);/* точка синхронизации, все должны получить строку */
/* выполнение операции (1) на каждом процессоре*/
for(i=nrl;i<(nrl+nr);i++){
for(j=0;j<N;j++){
if(d[j] > (d[l]+buf[j])){
d[j]= d[l]+buf[j];
}
}/* j */
}/* i */
MPI_Barrier (MPI_COMM_WORLD); /* точка синхронизации, все процессы должны закончить операцию (1) */
}
/*конец алгоритма Флойда */
Далее необходимо реализовать сбор блоков матрицы D в процесс 0 из всех остальных процессов и выдачу матрицы D на экран. Число процессов создаваемых при решении задачи не более 6.
Сначала необходимо отладить этот алгоритм на компьютере с одним процессором. Затем попытайтесь выполнить его на двух или более компьютерах. Определение номера корневого процесса.
В приведенном выше описании логики работы параллельного алгоритма используется функция root1(l,N,P) - которая определяет номер корневого процесса на итерации l.
Ниже приводится определение этой функции.
int root1(int lr,int n, int p)
{/* lr - номер текущей итерации в алгоритме Флойда */
/* n - размер матрицы D */
/* p - число процессов */
/* kr - номер корневого процесса */
int nmod,np,kr;
nmod=n%p;
np=n/p;
if(lr<=nmod*(np+1)) {
kr=lr/(np+1);
}
else{
kr=nmod+(lr-nmod*(np+1))/np;
}
return kr;
} Начальное распределение строк матрицы D блоками по процессорам.
Исходные данные для алгоритма - матрица D0 , размера n, находится в файле set.txt на диске. Распределение блоков строк по процессам можно осуществить различными способами.
Первый способ. Процессор П0 читает всю матрицу D0 в свою память, затем определяет количество строк для каждого процесса и номер первой строки блока который должен быть помещен на соответствующий процесс.
Второй способ. Каждый процесс считывает свой блок строк из файла последовательно.
Сначала считывает процесс П0, затем П1 и т.д.
Для реализации этой последовательности чтения можно использовать две функции
fgetpos(fl1,&pos) - определеить позицию курсора в файле;
fsetpos(fl1,&pos) - установить текущую позицию курсора в файле.
fpos_t pos; /* определение переменной pos*/
fp1 = fopen("set.txt","r");
if(k==0){
/*начали чтение на процессе 0*/
fgetpos(fp1,&pos);/* установить начальное значение переменной pos*/
for(i=0;i<nr;i++){
for(j=0;j<N;j++){
fscanf(fp1,"%d",&d[j]);
}/*j*/
}/*i*/
fgetpos(fp1,&pos);/* взять текущее значение переменной pos*/
/* передать значение pos следующему процессу*/
fclose(fp1);
} /* end matrix on process 0 */
else{
/* начали чтение на следующем */
fgetpos(fp1,&pos);/* взять текущее значение переменной pos*/
/* получить текущее значение переменной pos*/
fsetpos(fp1,&pos); /* установить полученное значение переменной pos*/
for(i=nrl;i<(nr+nrl);i++){
for(j=0;j<N;j++){
fscanf(fp1,"%d",&d[j]);
}/* j*/
} /* i */
fgetpos(fp1,&pos);
if(k < (P-1)){
MPI_Send(&pos, 1, MPI_LONG, k+1, 2, MPI_COMM_WORLD);
}
fclose(fp1);
}/* закончили чтение */
Задание. Исходные данные для задачи находятся в файле set.txt на диске Y:\INFORMAT\YANCH\mvs100\.......
Составить программу реализующую параллельный алгоритм Флойда. Задача обязательна для зачета.
http://www.csu.ac.ru/~yan/mvs2002/Mvslab_7.htm
Лабораторная работа № 7.
Алгоритм нахождения кратчайшего пути.
Задача. Составить и реализовать параллельный алгоритм нахождения кратчайших путей на заданном графе для любой пары вершин графа, используя алгоритм Флойда.
Алгоритм Флойда.
Рассматривается задача нахождения кратчайших путей между всеми парами узлов сети
G
V,E), где V={vi} i=1,n - множество вершин графа, E - множество дуг соединяющих вершины графа E = {(vi,vj)} i не равно j. Граф G - ориентированный граф, задается матрицей смежностей, например.
Фигура 1: Простой ориентированный граф G, и его матрица смежностей, A. Элементы матрицы смежности определяются следующим образом:
aij = 1, если существует дуга из i в j, aij = 0 , если нет дуги из i в j.
Каждой дуге ставится в соответствие число cij - длина дуги направленной из вершины i в вершину j.
Обозначим d*ij - кратчайший путь из вершины i в j. Пусть dij - наилучшая оценка длины кратчайшей цепи, соединяющей вершины (i, j). Первоначально за длину кратчайшей цепи между i и j принимается длина дуги (i, j), соединяющей эти узлы. Затем последовательно проверяются всевозможные промежуточные вершины, расположенные между i и j. Если длина цепи, проходящей через некоторую промежуточную вершину меньше текущего значения dij, то переменной dij присваивается новое значение. Данная процедура повторяется для всевозможных пар узлов, пока не будут получены все значения d*ij.
Фигура 2. Основная операция в алгоритме Флойда. Определяется будет ли путь из вершины i в j через вершину k короче, чем прямой путь из i в j.
Алгоритм Флойда позволяет решить задачу о нахождении кратчайших путей для сети из n вершин за n итераций. Обозначим dij( l ) оценку длины кратчайшей цепи из вершины i в j полученную на l - й итерации, тогда ее получение может быть определено следующей операцией
dij( l) = min{dij( l-1);dil (l-1) + dlj( l-1)} (1).
Если операцию (1) выполнить с данной парой узлов i и j и всеми узлами l в порядке возрастания номеров l, то значение dij( n ) полученное на последней итерации, будет равно длине кратчайшей цепи из узла i в узел j.
Последовательный алгоритм Флойда.
Реализация последовательного алгоритма Флойда приведена в следующей функции matrd.
#include<stdio.h>
#include<stdlib.h>
#define maxs 100
int d[maxs][maxs];
void matrd(int n)
{
int i,j,k;
for(l=0;l<n;l++){
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(d[j] > (d[l]+d[l][j])){
d[j]= d[l]+d[l][j];
}
}
}
}
Чтобы применить этот алгоритм необходимо сформировать матрицу D0={dij(0)}.Построение матрицы D0 выполняется следующим образом:
dij(0) = cij, если существует дуга из i в j;
dij(0) = 0, если i= j;
dij(0) = бесконечности, если нет дуги из i в j.
Матрица D0 подобна матрице смежности только 1 заменяются на соответствующие длины дуг cij . Параллельный алгоритм Флойда.
Рассмотрим параллельный алгоритм Флойда основанный на одноразмерном разбиении матрицы D по P процессорам. Используя функцию Del(N,P,k) необходимо распределить блоками смежные строки матрицы D0 по P процессам, для каждого блока определяется номер первой строки блока и количество строк в блоке. Схематично это можно изобразить следующим образом
Фигура 3: Параллельный алгоритм Флойда основанный на одноразмерной декомпозиции. В (а) расположены данные одной задачи: блок смежных строк.
В (b) на k - м шаге алгоритма находится собственный блок смежных строк и k - я
строка которая передается из другого процессора.
На каждом шаге один процесс передает одну строку всем остальным. Этот процесс будем называть корневым. Сначала процесс П0 передает свою первую строку всем остальным процессорам. Затем все процессы выполняют операцию (1). Затем П0 передает вторую строку и т.д. Когда процесс П0 передаст все свои строки, начинает передачу процесс П1. Процесс заканчивается, когда Пр передаст свою последнюю строку.
/* Начало алгоритма Флойда */
for(l=0;l<n;l++){
if((l>=nrl)&&(l<(nrl+nr))) { /*nrl - номер первой строки в блоке, nr - число строк в блоке*/
for(j=0;j<N;j++) { /*занесение передаваемой строки в буфер на корневом процессе}
buf[j]=d[l][j];
}
}
rk=root1(l,N,P); /* определение номера корневого процесса */
printf("Process % d send all\n",k);
MPI_Bcast(&buf, N, MPI_INT, rk, MPI_COMM_WORLD);
/* передача буфера всем остальным процессам */
MPI_Barrier (MPI_COMM_WORLD);/* точка синхронизации, все должны получить строку */
/* выполнение операции (1) на каждом процессоре*/
for(i=nrl;i<(nrl+nr);i++){
for(j=0;j<N;j++){
if(d[j] > (d[l]+buf[j])){
d[j]= d[l]+buf[j];
}
}/* j */
}/* i */
MPI_Barrier (MPI_COMM_WORLD); /* точка синхронизации, все процессы должны закончить операцию (1) */
}
/*конец алгоритма Флойда */
Далее необходимо реализовать сбор блоков матрицы D в процесс 0 из всех остальных процессов и выдачу матрицы D на экран. Число процессов создаваемых при решении задачи не более 6.
Сначала необходимо отладить этот алгоритм на компьютере с одним процессором. Затем попытайтесь выполнить его на двух или более компьютерах. Определение номера корневого процесса.
В приведенном выше описании логики работы параллельного алгоритма используется функция root1(l,N,P) - которая определяет номер корневого процесса на итерации l.
Ниже приводится определение этой функции.
int root1(int lr,int n, int p)
{/* lr - номер текущей итерации в алгоритме Флойда */
/* n - размер матрицы D */
/* p - число процессов */
/* kr - номер корневого процесса */
int nmod,np,kr;
nmod=n%p;
np=n/p;
if(lr<=nmod*(np+1)) {
kr=lr/(np+1);
}
else{
kr=nmod+(lr-nmod*(np+1))/np;
}
return kr;
} Начальное распределение строк матрицы D блоками по процессорам.
Исходные данные для алгоритма - матрица D0 , размера n, находится в файле set.txt на диске. Распределение блоков строк по процессам можно осуществить различными способами.
Первый способ. Процессор П0 читает всю матрицу D0 в свою память, затем определяет количество строк для каждого процесса и номер первой строки блока который должен быть помещен на соответствующий процесс.
Второй способ. Каждый процесс считывает свой блок строк из файла последовательно.
Сначала считывает процесс П0, затем П1 и т.д.
Для реализации этой последовательности чтения можно использовать две функции
fgetpos(fl1,&pos) - определеить позицию курсора в файле;
fsetpos(fl1,&pos) - установить текущую позицию курсора в файле.
fpos_t pos; /* определение переменной pos*/
fp1 = fopen("set.txt","r");
if(k==0){
/*начали чтение на процессе 0*/
fgetpos(fp1,&pos);/* установить начальное значение переменной pos*/
for(i=0;i<nr;i++){
for(j=0;j<N;j++){
fscanf(fp1,"%d",&d[j]);
}/*j*/
}/*i*/
fgetpos(fp1,&pos);/* взять текущее значение переменной pos*/
/* передать значение pos следующему процессу*/
fclose(fp1);
} /* end matrix on process 0 */
else{
/* начали чтение на следующем */
fgetpos(fp1,&pos);/* взять текущее значение переменной pos*/
/* получить текущее значение переменной pos*/
fsetpos(fp1,&pos); /* установить полученное значение переменной pos*/
for(i=nrl;i<(nr+nrl);i++){
for(j=0;j<N;j++){
fscanf(fp1,"%d",&d[j]);
}/* j*/
} /* i */
fgetpos(fp1,&pos);
if(k < (P-1)){
MPI_Send(&pos, 1, MPI_LONG, k+1, 2, MPI_COMM_WORLD);
}
fclose(fp1);
}/* закончили чтение */
Задание. Исходные данные для задачи находятся в файле set.txt на диске Y:\INFORMAT\YANCH\mvs100\.......
Составить программу реализующую параллельный алгоритм Флойда. Задача обязательна для зачета.
-------------------------------------------------------
Все...
Хочу заметить, что представленный здесь алгоритм А* таковым не является.
A* - это по сути алгоритм Дикстры с ненулевыми эвристиками.
Суть работы его примерно следующая:
На каждом шаге имеем упрядоченный массив открытых узлов, т.е. узлов в которые мы можем попасть из текущего. Из этого массива выбирается "лучший" узел, переходим на него и повторяем процесс.
Критерий выбора "лучшести" узла как лежит на программисте, в простейшем случае это расстояние до финиша по прямой. Алгоритм хорош тем, что работает существенно быстрее обычной волны, т.к. распостранение волны идёт в сторону финиша, а не во все стороны. ПЛЮС критерием выбора узла может выступать тип поверхности, например, при одинаковом расстоянии до финиша из двух узлов выбирается узел на равнине, а не на болоте (в RTS какой-нибудь).
P.S.
Вроде там ещё держится список узлов, в которых побывали, чтоб волна не отскакивала если попалаем в "стакан".
P.P.S.
При правильной реализации метод работает очень быстро и спокойно используется в 3D-шутерах в real-time.
A* - это по сути алгоритм Дикстры с ненулевыми эвристиками.
Суть работы его примерно следующая:
На каждом шаге имеем упрядоченный массив открытых узлов, т.е. узлов в которые мы можем попасть из текущего. Из этого массива выбирается "лучший" узел, переходим на него и повторяем процесс.
Критерий выбора "лучшести" узла как лежит на программисте, в простейшем случае это расстояние до финиша по прямой. Алгоритм хорош тем, что работает существенно быстрее обычной волны, т.к. распостранение волны идёт в сторону финиша, а не во все стороны. ПЛЮС критерием выбора узла может выступать тип поверхности, например, при одинаковом расстоянии до финиша из двух узлов выбирается узел на равнине, а не на болоте (в RTS какой-нибудь).
P.S.
Вроде там ещё держится список узлов, в которых побывали, чтоб волна не отскакивала если попалаем в "стакан".
P.P.S.
При правильной реализации метод работает очень быстро и спокойно используется в 3D-шутерах в real-time.
Последнее редактирование модератором:
я в прошлом семестре писал лабу по кратчайшему пути, хотел написать как раз алгоритм Дейкстра, но начал делать поздно и вообще я такой человек, что если можно не делать, то я не делаю, и вместо этого сдела прогу, которая обходит лишь одиночной препятствие, бред конечно, но аспиранту я ее впарил, потратил на нею где-то полчаса или меньше.
----
комментарий для тех, кто будет юзать прогу
1.указывайте условные координаты старта и финиша
2.нажимайте кнопку "Поставить"
3.Кликами по полю устанавливайте препятствия
4.Нажимайте на кнопку "Поехали"
ВСЕ.
----
комментарий для тех, кто будет юзать прогу
1.указывайте условные координаты старта и финиша
2.нажимайте кнопку "Поставить"
3.Кликами по полю устанавливайте препятствия
4.Нажимайте на кнопку "Поехали"
ВСЕ.