Привет! Ребята, подскажите пожалуйста алгоритм поиска наиме..

← →
ProtoSoft (2003-02-18 00:31) [0]

Привет! Ребята, подскажите пожалуйста алгоритм поиска наименьшего расстояния от точка А до точки Z.
Дело значит вот в чем. Делаю интерактивную карту области. Например, вводишь город откуда и куда. Вывод - плучаещь маршрут движения с указанием всех проездных городов и расстояний между ними. Вот немного придумал. Делать базу с ссылками на близлежащие города, следующие города ссылку на близлежащие. Вот только как это все организовать пока не до пру. Все сводится к тому, что время выполнения такого поиска будет через чур большое. Может кто-нибудь такое уже делал? или есть какие-то предложения.

← →
Пан Сенюта (2003-02-18 00:41) [1]

Есть в Samples на DelphiGFX парочка примеров, довольно доступных.

← →
[NIKEL] (2003-02-18 00:46) [2]

все равно будет очень неточно, нужная точная информация о местности и тд. и тп.
ты ж не будешь расчитывать расстояния по прямой...

← →
Palladin (2003-02-18 00:51) [3]

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

← →
Palladin (2003-02-18 00:52) [4]

расстояние имелось ввиду ессно не на прямую, а длина пути...

← →
[NIKEL] (2003-02-18 00:56) [5]

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

← →
ProtoSoft (2003-02-18 01:08) [6]

>> [NIKEL]

/все равно будет очень неточно, нужная точная информация о \местности и тд. и тп.
/ты ж не будешь расчитывать расстояния по прямой...

Да, это все будет учитываться. Будет база с расстояниями между городами. Тут все продумано. А вот с быстрым поиском проблемы.

====Пан Сенюта
Сейчас посмотрю, что там такое...

← →
ProtoSoft (2003-02-18 01:28) [7]

Значит так. Все это хорошо. Но как построить таблицу, я немного не въежаю.
Вот моя идея.

1 база: Городов. (содержит следующие поля:
Number
Town

2 база: база связей и расстояний (содержит следующие поля:
Number - номер - ссылка на город
Svz - номер ссылка на город
Length - расстояние между городами

Содержание БД1
----
Number Town
1 Селезневка
2 Ивановка
3 Простоквашино
4 Есауловка
5 Пигмеевка
6 Золотаревка
ну и т.д.

(Поля нумбер связаны между собой)
Содеражние второй базы
Number Svz Length
1 2 33
1 4 45
1 5 67
2 1 33
2 3 12
2 4 33
3 2 12
3 4 12

ну и т.д.

Вот что у нас получается:
Из Города 1 можно попасть в 3 города.
Из города два можно проехать еще в три города
Соответственно из этих городов можно попасть в
другие города и т.д. пока не дайдем до последнего,
искомого нами города, но представть, если городов более 1000 и если сделать рекурсивный поиск по этим ссылкам,
то искать будем учень долго. Я кодинг еще не делал,
так как ищу более быстрые решения, но завтра налабаню..проверю..
может кно-нить подскажит?

← →
Palladin (2003-02-18 01:57) [8]

хм...вот что я подумал, вообще на самом деле нужно не длину пути хранить, а время пути... это первое

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

← →
ProtoSoft (2003-02-18 02:07) [9]

>> Palladin
А я не понял, что именно ты имеешь насчет времени пути?
Я имею ввиду расстояние между городов в километрах.

← →
Palladin (2003-02-18 02:14) [10]

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

← →
Думкин (2003-02-18 05:59) [11]

Я не буду, конечно, утверждать, что для решения этой задачи нужно высшее образование - боже упаси. Но концентрированная доза читанной литеры не помешала бы. Ну не въезжаешь - читай книги, - или для начала зайди на Алголист - потусуйся, может стыдно станет и прочитаешь пару-тройку мыслей людей, которые это давно решили. :-)

← →
jack128 (2003-02-18 08:03) [12]

Насколько я понимаю, такие задачи решаются, например, волновым алгоритмом

← →
pasha676 (2003-02-18 09:16) [13]

Есть классическая задача - поиск оптимального пути. Строиться по базе данных граф причем каждое ребро имеет весовой коэффицент (ну типа состояние дороги или трафик на ней). Ну а потом задача решается :). Алгоритмов несколько, все они довольно просты, но (сорри) на вскидку ничего не помню. Никогда не занимался этим.

← →
Думкин (2003-02-18 09:24) [14]

> jack128 © (18.02.03 08:03)
> pasha676 (18.02.03 09:16)
Так об этом и речь - все давно. Хочешь придумывать - придумывай. Не хочешь - читай. Это не вопрос "О перегелии Меркурия в начале 20-го века".

← →
DiamondShark (2003-02-18 10:38) [15]

Попробуйте поискать по ключевым словам "алгоритм Форда"

← →
VictorT (2003-02-18 11:41) [16]

Если не путаю, то это классическая задача коммивояжера.

← →
Sha (2003-02-18 14:21) [17]

Есть 2 похожих способа решения:
1. Волновой алгоритм. См. jack128 © (18.02.03 08:03).
2. Этот пример рассматривается также при изучении динамического программирования.

← →
DAC (2003-02-18 14:42) [18]

> VictorT © (18.02.03 11:41)
> Если не путаю, то это классическая задача коммивояжера.

Не путаете, так оно и есть. Это NP-полная задача. И сейчас не существует полиномиального алгоритма её решения.

> pasha676 (18.02.03 09:16)
> Есть классическая задача - поиск оптимального пути.
> Алгоритмов несколько, все они довольно просты

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

Решение этой задачи приведёт к решению основной проблемы теории сложности (эквивалентность классов P и NPC). В августе индус Манидра вроде бы это доказал, но, даже если правильно, степень полинома у него была 12! Тот кто сможет найти "простой" алгоритм этой задачи, произведёт полный фурор во всём мире. Может свободно претендовать на Нобелевскую и премию Тьюринга.
А вы говорите
Думкин © (18.02.03 05:59)
Я не буду, конечно, утверждать, что для решения этой задачи нужно высшее образование - боже упаси.

← →
wicked (2003-02-18 15:07) [19]

ужас...
задача решаецца при помощи алгоритма с потенциалами (Дийкстра)...
классика, я на этом 3 диплома сделал.... :)
(обьяснять не буду - лень...)

← →
REA (2003-02-18 15:12) [20]

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

← →
Думкин (2003-02-18 15:18) [21]

> DAC © (18.02.03 14:42)

%-)
Это было сказано в видах другой ветки, где люди трунили над высшим и говорили, что пхактика и еще хаз практика - а учатся трепливые идиоты, вот я и цепанул. Так что зря. :-)

← →
DAC (2003-02-18 15:19) [22]

Извиняюсь, может я не понял, но нужно ли обезжать все перечисленные города?

← →
DiamondShark (2003-02-18 16:02) [23]

Один существенный момент забыли: это же БД. Кто мешает повысить избыточность хранимой информации? Вплоть до хранения всех путей в явном виде. Информация обновляется мелкими шагами (один город за раз, одна дорога за раз) ergo поддержка целостности будет происходить просто и быстро. А поиск нужного пути сводится вообще чуть ли не к одному запросу. Объём большой? Во-первых, не такой он на самом деле большой (верхняя оценка -- N*(N-1)/2 путей, где N -- число городов), а во-вторых, это же объём в базе, а не в оперативной памяти.

← →
jack128 (2003-02-18 16:27) [24]

2 DAC
чем сложен тот же волновой ангоритм - непонятно,
да и придумать задачу которую он бы не решил я так и не смог,
не могли бы превести пример.
Да, а что такое полиномиальные алгоритмы?

← →
Труп Васи Доброго (2003-02-18 16:39) [25]

Вы полезли в какие-то дремучие дебри!!! А человеку, по хорошему, надо всего лишь изучить принцип работы маршрутизаторов, немного его подогнать под решаемую задачу и всё!!!
Всё гениальное просто!!!

← →
DAC (2003-02-18 16:55) [26]

Возможно, я не правильно понял условие задачи. Я писал, про тот случай, если нужно обойти все перечисленные города. В противном случае, задача действительно не сложная, и для её решения можно применять алгоритмы типа волнового.

> jack128 © (18.02.03 16:27)
> Да, а что такое полиномиальные алгоритмы?

Алгоритмы, сложность которых о(n^c), где с = const

← →
Uncle Archi (2003-02-18 22:28) [27]

Посмотри на ящике. Программа на Free-Pscale для поиска в графах.

Привет! Ребята, подскажите пожалуйста алгоритм поиска наиме.. Найти похожие ветки