Форум: "Потрепаться";
Текущий архив: 2003.03.06;
Скачать: [xml.tar.bz2];
ВнизПривет! Ребята, подскажите пожалуйста алгоритм поиска наиме.. Найти похожие ветки
← →
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 для поиска в графах.
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2003.03.06;
Скачать: [xml.tar.bz2];
Память: 0.51 MB
Время: 0.011 c