Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Потрепаться";
Текущий архив: 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.65 MB
Время: 0.054 c
1-17003
Артём В.
2003-02-24 23:25
2003.03.06
Нужна поддержка скинов


14-17388
IGORYOK
2003-02-16 11:09
2003.03.06
О context и ReadProcessMemory


14-17336
Maximator Vetera
2003-02-12 10:23
2003.03.06
Димедрол.


3-16918
malish
2003-02-15 19:00
2003.03.06
Парольна пародоксе


8-17208
vitaliy_new
2002-11-21 12:08
2003.03.06
Фоновый рисунок формы





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский