Возникла необходимость решить след. задачу:
есть набор городов и описание связей между ними (цена билета, время на поездку 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..
Иль я где-то ошибаюсь?
Подскажите, как правильно.

Kurt
Юзверь возвращаться будет?

Есть способы приближенного решения - алгоритм Прима например.

Цитата

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

Цитата

В данном случае задача на плоскости приближенно решается с ошибкой не более чем в 2 раза

время на решение O(E*logV), (где E — мощность множества ребер, а V — множества вершин)

Цитата(Kurt @ 19.10.2004, 22:08)

он же всегда вернет 65535... Блин, или вообще ни разу не зайдет в if..

Посмотри, там сразу после цикла инициализации есть строчка

Код

d[s]:=0;

в которой мы показываем, что путь из s в s равен 0.

Далее в этом цикле мы возьмем вершину mI, в которой значение d будет минимальным (на первом шаге это будет именно s). Делаем пометки в массивы про эту вершину типа Q[mI]=0. Потом для каждой вершины, соединенной ребром с mI мы обновим значение d если это будет нужно. Ну и дальше делаем все с начала...
То есть работает по жадному методу (когда выбираем mI).

Массив W вроде действительно не нужен. (Я видимо когда писал этот код записывал в W порядок следования найденых вершин mI - вот что именно отображает этот массив).

Код точно работает правильно - протестировал.

Это сообщение отредактировал(а) Morpheus - 20.10.2004, 16:38

А реальны пересадки с автобуса на автобус?

neutrino В смысле если ехать из Киева в Москву через Чикаго двумя самолетами, то конечно реально... Это и есть метод "релаксации"

Извините, А этот Дийкстра - это разве не кротчайший путь в графе из точки А в точку Б? А как же пересадки?

neutrino Смотри.
Граф задаем так: если есть автобус из A в B, то есть дуга AB, вес которой - стоимость проезда. Тогда Дейкстра как раз и найдет минимальной по стоимости проезда путь. При этом количество пересадок - количество вершин, пройденных по пути.

З.Ы. Важно, что Дейкстра ищет именно минимальный по стоимости цикл а не колличеству пересадок. То есть если будет дешевле выходить на каждой остановке с учетом того, что кондуктор не успеет взять за проезд и стоимость между двумя соседними остановками будет 0, то дейкстра заставит постоянно выходить из автобуса и ждать следующего.

ВОТ Я ДУРАК!!!

Это ведь так просто! А я со своим Г.А. га га га га

Спасибо, Morpheus

Оказалось не все так просто ... Сложность получается O(2^n*n^2). Н в квадрате дает Дейкстра, плюс на каждой из н остановок можно либо выйти либо войти в автобус. И того 2 варианта на н остановок - 2 в степени н. Для ста тысяч остановок комп заглохнет надолго ... Без эвристик не обойтись ...

Цитата

плюс на каждой из н остановок можно либо выйти либо войти в автобус.

Мы друг друга не понимаем

Цитата(Fedor @ 5.1.2005, 23:04)

Мы друг друга не понимаем

Я что-то не понял. А кто из вас Федор и кто Морфеус?

А на счет сложности алгоритма - попробуй анализировать. У меня получилось именно так. Ведь на каждой остановке можно либо выйти либо остаться в автобусе. 2 варианта. А остановок n значит всего вариантов 2^n. Да еще и Дийкстра дает n в квадрате.

Цитата(neutrino @ 4.2.2005, 10:59)

Я что-то не понял. А кто из вас Федор и кто Морфеус?

Ну... Федор==Морфеус.