Возникла необходимость решить след. задачу:
есть набор городов и описание связей между ними (цена билета, время на поездку etc.).
Нужно сделать так: юзер вводит пункты отправки/назначения и насколько ему важно время, а прога находит оптимальный путь, возможно с пересадками.
Собственно, проблемка не в алгоритме, а в их количестве. Поискал в сети, встречаются генетические алгоритмы, нейронные сети и т.п
Народ, может, кто занимался этим делом? Киньте свое мнение, что лучше (какой алгоритм), что хуже и почему. Буду очень признателен. ;)

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

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

Ну на самом деле это классический алгоритм Дейкстры поиска оптимального пути между двумя вершинами графа. Можно посоветовать algolist.manual.ru - там хорошо это все описано. Если не поймешь, я могу выложить реализацию на паскале

Вот решил выложить сразу чтоб ты не мучался...

Взято из Кормен, Лейзерсон, Ривест - "Алгоритмы: построение и анализ" и переведено на українську мову для моей квалификационной работы. Уж прости...

Цитата

Уявимо собі карту автомобільних шляхів України. Як знайти найкоротший шлях із Дніпропетровська в Київ? Можна, звичайно, перебрати всі можливі варіанти і вибрати мінімальний з них. Але тоді ми одержуємо мільйони свідомо невірних операцій (наприклад, навіщо нам їхати з Дніпропетровська в Київ через Донецьк, що знаходиться зовсім в іншому боці). Далі буде розглянутий спосіб ефективного рішення цієї задачі. Тут буде розглядатися тільки пошук найкоротших шляхів з однієї вершини: даний зважений граф G і початкова вершина s. Потрібно знайти всі найкоротші шляхи з s в усі вершини графу. Алгоритм Дейкстри здатний знайти найкоротший шлях тільки для графів, у яких усі ребра недодатньої ваги. Багато алгоритмів пошуку найкоротших шляхів використовують особливу техніку - техніку релаксації. І алгоритм Дейскстри - не виключення. Техніка релаксації полягає в наступному. Для кожного ребра v ми зберігаємо деяке число d[v], яке є верхньою оцінкою ваги найкоротшого шляху з s в v. Початкове значення встановлюється наступною процедурою: Inintialize-Single-Sourche(s) 1 for (для) всіх вершин v 2    do d[v]= MAX 3          parent[v]=NIL Релаксація ребра (u,v) полягає в наступному: значення d[v] зменшується до d[u]+w(u,v) (якщо друге значення менше за перше). Також можно змінити значення parent[v], щоб прослідити шлях, використаний при отриманні вищої оцінки. Relax(u,v,w) 1 if d[v]> d[u]+w(u,v) 2    then d[v]=d[u]+w(u,v) 3          parent[v]=u Алгоритм Дейкстри вирішує задачу пошуку найкоротшого шляху з однієї вершини для зваженого орієнтованого графа з початковою вершиною s, в якому ваги всіх ребер невід'ємні. В процесі роботи алгоритму підтримується множина S, що складається з вершин v, для яких знайдений найкоротший шлях. Алгоритм вибирає вершину u з якнайменшим d[u], додає її до множини S і проводить релаксацію всіх ребер, що виходять з u, після чого цикл повторюється. Dijkstra(G,w,s) 1 Initialize-Single-Sourche(G,s) 2 S=NIL 3 Q=усі вершини графа 4 while Q<>NIL 5    do u=Extract-Min(Q) 6        S=S+{u} 7    for (для) всіх вершин v - нащадків u 8          do Relax(u,v,w)

И реализация на паскале... Моя.

Код

program dijkstra; var  G:array[1..100,1..100] of integer; {матричное задание графа с максимум сто вершин, G[i,j] - стоимость переезда из i в j}  Q,W:array[1..100]  of byte;  i,j:word;  s:word;  d:array[1..100] of word;  p:array[1..100] of word;  f:text;  n:word;  nQ:word;  nW:word;  min,mI:word; begin  assign(f,'dijkstra.dat'); reset(f);  for i:=1 to 100 do   for j:=1 to 100 do     G[i,j]:=-1;  read(f,n); readln(f,s);  while not EOF(f) do   begin    read(f,i); read(f,j); readln(f,G[i,j]);   end;  close(f);  for i:=1 to n do   begin    d[i]:=65535;    p[i]:=0;   end;  d[s]:=0;  for i:=1 to n do   Q[i]:=i;  nq:=n; nW:=0;  while nq<>0 do   begin     min:=65535;     for i:=1 to n do       if (Q[i]<>0) and (d[i]<min) then         begin          min:=d[i]; mI:=i;         end;     dec(nQ);     Q[mI]:=0;     inc(nW); W[nW]:=mI;     for j:=1 TO n DO      if G[mi,j]<>-1 then        if d[j]>d[Mi]+G[Mi,j] then         begin          d[j]:=d[mi]+g[mi,j];          p[j]:=mi;         end;   end; for i:=1 to n do  writeln(d[i]); end.

Смотри алгоритмы Дейкстры и Флойда-Уоршилла

Г.А. на мой взгляд лучшее решение таких задач.

Цитата(neutrino @ 16.10.2004, 16:39)

Г.А. на мой взгляд лучшее решение таких задач.

А что такое Г.А.?

Цитата

А что такое Г.А.?

here

Цитата

Г.А. на мой взгляд лучшее решение таких задач.

У тебя, случаем, нет его реализации для моей задачи?
Чтоб не с нуля начинать..
Смотрел на BaseGroup (ссылка выше..), но там немного не то - как я понимаю, в моей задаче хоромосомы имеют РАЗНОЕ количество генов. Или можно как-то свести к "однородным" хромосомам, чтоб кол-во генов было одинаково?
В роли гена я хотел брать номер города, т.е. для пути 5-6-7 хромосома имеет 3 гена: 5, 6, 7.
А для пути 5-7 - только два: 5, 7.
Есть другой способ закодировать путь?

Kurt
Будешь смеяться, но я сам пытаюсь решить эту задачу. Хотел сделать движок для транспортных сайтов. Есть интересные наработки с 2-OPT, 1-OR, 2-OR и EX1 эвристиками. Но сама программа еще не готова. Я пока еще не знаю как это применить к нашей задаче, но чувствую надо использовать именно их, т.к. они самые быстрые. А у тебя есть какие-нить предложения?

Цитата(Kurt @ 17.10.2004, 19:31)

Есть другой способ закодировать путь?

Пустых генов добавить, чтобы они не учитывались оценщиком.

Цитата

Будешь смеяться, но я сам пытаюсь решить эту задачу

Ого! Да мы, оказывается, конкуренты! У меня очень похожая задачка.

Цитата

Пустых генов добавить, чтобы они не учитывались оценщиком

Хмм... А как ты обозначишь пустой ген? Допустим, некоторым числом, скажем, -1. Т.е. if(someArray[i]!=-1) тады учитывать.
Все хорошо. НО! Что будет при скрещивании и мутациях? Ведь разрыв может произойти в любом месте хромосомы? Честно говоря, этот момент очень тревожен..
Т.е. есть, например, набор очень "удачных" хромосом, но при скрещивании они дадут потомство полностью неприспособленных особей, существенно оттянув тем самым конец алгоритма.
Кстати, ты еще не пробовал, как все это работает при "пустых" генах?

Цитата(Kurt @ 17.10.2004, 21:31)

В роли гена я хотел брать номер города, т.е. для пути 5-6-7 хромосома имеет 3 гена: 5, 6, 7. А для пути 5-7 - только два: 5, 7. Есть другой способ закодировать путь?

Сразу оговорюсь, что все мои знания о Г. А. - из вышеупомянутой статьи, так что я могу сказать глупость

Только вот я не понимаю, как может при таком выборе описания гена этот алгоритм сойтись. Может быть, попробовать так: ген номер x - это номер вершины графа, а 1 означает, что путь проходит через неё... В этом случае интуитивно я могу представить себе, как такое может дать результат. Но вот оценочная функция будет долгой... Хотя, если подумать... не так и долго...

А если ещё подумать, то не так и быстро... Пока лезет в голову только определение сопротивления цепи между двумя точками - исходной и назначения, где каждое ребро графа - это резистор с сопротивлением, равным времени меремещения между вершинами. Тут та ещё работка Нужны более быстрые алгоритмы.
Или если рекурсивно применять алгоритм
Всё, пошёл спать, глупости в голову какие-то лезут

Не ломайте зря голову, все равно оптимальнее Дейкстры (если из одного пункта) алгоритма не найти. Ребро графа и будет временем (стоимостью и т.п.).
P.S.
Morpheus правильное решение предложил. Сложность O(N^2)
Если найдете более оптимальное решение, то станете известными как Дейкстра

Alex101, здесь, как я понял, не ставится цель решить задачу с абсолютной точностью, а ставится цель найти лучшее решение за ограниченное количество итераций со сложностью, меньшей квадратичной.

Morpheus, разбираю твой код (с принципом алгоритма ознакомился. )
Не могу понять:

Цитата

Q,W:array[1..100] of byte;

Нафига массив W, если он используется тока в одной сомнительной строчке:

Цитата

W[nW]:=mI;

В чем его предназначение?

Согласно этому:

Цитата

перенести i-ю строку матрицы A в массив B

.
У тебя соответственно, A=G и B=d.
Такого заполенния у тебя нет. Оно и без этого корректно работает?

Цитата

if (Q[i]<>0) and (d[i]<min) then begin min:=d[i]; mI:=i; end;

ээ... Ввиду:

Цитата

for i:=1 to n do begin d[i]:=65535; p[i]:=0; end;

он же всегда вернет 65535... Блин, или вообще ни разу не зайдет в if..
Иль я где-то ошибаюсь?
Подскажите, как правильно.