Алгоритм поиска мимимального пути
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Алгоритм поиска мимимального пути - 2009-11-08 08:06:16.073333
|
|
|
freegat
Сообщений: 18
Оценки: 0
Присоединился: 2008-09-29 17:09:33.843333
|
Доброго времени суток, господа форумчане.
Заинтересовала тема ГИС, и соответственно вопрос - как ПРАКТИЧЕСКИ реализуется алгоритм минимального поиска пути, применительно к карте!??!
Погуглил, нашёл множество алгоритмов по этому поводу (на графах и прочие), но как именно ПРАКТИЧЕСКИ алгоритм реализуется и применяется я не нашёл…..буду очень благодарен за помощь.
|
|
|
|
|
RE: Алгоритм поиска мимимального пути - 2009-11-08 11:23:51.336666
|
|
|
Рукс
Сообщений: 58
Оценки: 0
Присоединился: 2009-08-08 22:50:04.093333
|
Вот писал курсовой проект - Поиск минимального остного дерева (минимальный путь). Задаешь количество точек. Расстояние между ними. Выбираешь 2 точки и выводиться минимальный путь.
Реализованный на С++, приложение консольное.
Изучи:
//—————————————————————————
#include <vcl.h>
#pragma hdrstop
#include<iostream.h>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define word unsigned int
#pragma argsused
int i, j, n, p, xn, xk;
int flag[11];
word c[11][11], l[11];
char s[80], path[80][11];
int min(int n)
{
int i, result;
for(i=0;i<n;i++)
if(!(flag)) result=i;
for(i=0;i<n;i++)
if((l[result]>l)&&(!flag)) result=i;
return result;
}
word minim(word x, word y)
{
if(x<y) return x;
return y;
}
void main()
{
cout<<"Vvedite kolichestvo tochek: ";
cin>>n;
for(i=0;i<n;i++)
for(j=0;j<n;j++) c[j]=0;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
cout<<"Vvedite rasstoyanie ot x"<<i+1<<" do x"<<j+1<<": ";
cin>>c[j];
}
cout<<" ";
for(i=0;i<n;i++) cout<<" X"<<i+1;
cout<<endl<<endl;
for(i=0;i<n;i++)
{
printf("X%d",i+1);
for(j=0;j<n;j++)
{
printf("%6d",c[j]);
c[j]=c[j];
}
printf("\n\n");
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(c[j]==0) c[j]=65535;
cout<<"Vvedite nachalnuy tochku: ";
cin>>xn;
cout<<"Vvedite konechnuy tochku: ";
cin>>xk;
xk–;
xn–;
if(xn==xk)
{
cout<<"Nachalnaya I konechnaya tochki sovpadayt."<<endl;
getch();
return;
}
for(i=0;i<n;i++)
{
flag=0;
l=65535;
}
l[xn]=0;
flag[xn]=1;
p=xn;
itoa(xn+1,s,10);
for(i=1;i<=n;i++)
{
strcpy(path,"X");
strcat(path,s);
}
do
{
for(i=0;i<n;i++)
if((c[p]!=65535)&&(!flag)&&(i!=p))
{
if(l>l[p]+c[p])
{
itoa(i+1,s,10);
strcpy(path[i+1],path[p+1]);
strcat(path[i+1],"-X");
strcat(path[i+1],s);
}
l=minim(l,l[p]+c[p]);
}
p=min(n);
flag[p]=1;
}
while(p!=xk);
if(l[p]!=65535)
{
cout<<"Put: "<<path[p+1]<<endl;
cout<<"Dlina puti: "<<l[p]<<endl;
}
else
cout<<"takogo puti ne syshestvuet!"<<endl;
getch();
}
|
|
|
|
|
RE: Алгоритм поиска мимимального пути - 2009-11-08 15:44:38.440000
|
|
|
freegat
Сообщений: 18
Оценки: 0
Присоединился: 2008-09-29 17:09:33.843333
|
Спасибо за пример…..НО МНЕ БЫ ПРИМЕНИТЕЛЬНО К РЕАЛЬНОЙ КАРТЕ (например к части карты города Москвы)…8|
|
|
|
|
|
RE: Алгоритм поиска мимимального пути - 2009-11-08 16:58:08.706666
|
|
|
Zmaster
Сообщений: 930
Оценки: 0
Присоединился: 2007-02-09 19:02:43.500000
|
http://pmg.org.ru/index.html - тут все есть.
|
|
|
|
|
RE: Алгоритм поиска мимимального пути - 2009-11-09 17:59:37.950000
|
|
|
freegat
Сообщений: 18
Оценки: 0
Присоединился: 2008-09-29 17:09:33.843333
|
GPS навигаторы именно их и используют?!?
|
|
|
|
|
RE: Алгоритм поиска мимимального пути - 2009-11-09 18:21:06.220000
|
|
|
psina007
Сообщений: 98
Оценки: 0
Присоединился: 2009-05-09 22:41:33.580000
|
Почитай эту статью, может поможет.
|
|
|
|
|
RE: Алгоритм поиска мимимального пути - 2009-11-09 22:24:45.270000
|
|
|
ХреновыйСтудент
Сообщений: 100
Оценки: 0
Присоединился: 2009-06-30 18:30:40.363333
|
quote:
как ПРАКТИЧЕСКИ реализуется алгоритм минимального поиска пути, применительно к карте!??!
в том числе также, как и к графу.
quote:
НО МНЕ БЫ ПРИМЕНИТЕЛЬНО К РЕАЛЬНОЙ КАРТЕ (например к части карты города Москвы)…
что-то не верится после таких слов, что вас заинтересовала тема.
а что мешает написать свою реализацию известного вам алгоритма, оценить её релевантность на рассматриваемом графе и сделать выводы об актуальности этого алгоритма?
|
|
|
|
|
RE: Алгоритм поиска мимимального пути - 2009-11-10 06:24:46.856666
|
|
|
freegat
Сообщений: 18
Оценки: 0
Присоединился: 2008-09-29 17:09:33.843333
|
Мне ничего не мешает реализовать несколько алгоритмов и оценить их эффективность……
Но зачем "изобретать колесо"!?? Ежели множество людей уже писали реализацию!???!
ХреновыйСтудент, если есть возможность использовать, к примеру STL или Boost, то Вы их использовать не станете, а будете писать сортировку, поиск минимального значения в векторе и пр. "ручками"!??!
Очень сильно сомниваюсь…..Ведь воемя на написание кода увиличиться минимум в 2-3 раза…[sm=ap.gif]
|
|
|
|
|
RE: Алгоритм поиска мимимального пути - 2009-11-10 17:48:11.380000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: freegat
если есть возможность использовать, к примеру STL или Boost
то почему ты их не используешь?
http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/index.html
|
|
|
|
|
RE: Алгоритм поиска мимимального пути - 2009-11-10 20:20:34.506666
|
|
|
freegat
Сообщений: 18
Оценки: 0
Присоединился: 2008-09-29 17:09:33.843333
|
Всем большое спасибо за ответы и ссылки на алгоритмы и материалы.[sm=ap.gif]
Особенно Denaturat'у, за книжку, её я в глаза ни разу не видел и врят ли бы вообще нашёл…[sm=ay.gif]
|
|
|
|
|
RE: Алгоритм поиска мимимального пути - 2009-11-10 22:09:33.603333
|
|
|
ХреновыйСтудент
Сообщений: 100
Оценки: 0
Присоединился: 2009-06-30 18:30:40.363333
|
quote:
если есть возможность использовать, к примеру STL или Boost, то Вы их использовать не станете
это точно
quote:
будете писать сортировку, поиск минимального значения в векторе и пр. "ручками"!??!
смотря на каком уровне абстракции работать, но обычно нет, сортировку и поиск дают примитивы языка/just have библиотеки, которым я пользуюсь.
quote:
Но зачем "изобретать колесо"!?? Ежели множество людей уже писали реализацию!???!
quote:
By themselves, the algorithm patterns do not compute any meaningful quantities over graphs; they are merely building blocks for constructing graph algorithms. The graph algorithms in the BGL currently include
Dijkstra's Shortest Paths
Bellman-Ford Shortest Paths
Johnson's All-Pairs Shortest Paths
Kruskal's Minimum Spanning Tree
Prim's Minimum Spanning Tree
Connected Components
Strongly Connected Components
Dynamic Connected Components (using Disjoint Sets)
Topological Sort
Transpose
Reverse Cuthill Mckee Ordering
Smallest Last Vertex Ordering
Sequential Vertex Coloring
вы уж таки определитесь что вам надо. инструмент для реализации алгоритма или реализация алгоритма.
quote:
НО МНЕ БЫ ПРИМЕНИТЕЛЬНО К РЕАЛЬНОЙ КАРТЕ (например к части карты города Москвы)…
если инструмент, то нехрен пиздеть про колесо. если реализация, то извините, вам нужен исходник, погуглите опен соурс проекты
|
|
|
|
|
RE: Алгоритм поиска мимимального пути - 2009-11-11 19:40:16.543333
|
|
|
freegat
Сообщений: 18
Оценки: 0
Присоединился: 2008-09-29 17:09:33.843333
|
Я иногда плохо формулирую мысли "на бумаге": это ДА……Но,ХреновыйСтудент, не нужно сквернословить….[sm=dont.gif]
|
|
|
|
|
RE: Алгоритм поиска мимимального пути - 2009-11-19 06:54:46.710000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: freegat
за книжку, её я в глаза ни разу не видел и врят ли бы вообще нашёл…[sm=ay.gif]
http://www.ozon.ru/context/detail/id/2457394/
вот издание на русском. enjoy!
|
|
|
|
|
|
