|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
15.05.2010, 10:20 | #1 |
Регистрация: 15.05.2010
Сообщений: 6
|
Поиск самого дешёвого пути. Волновой алгоритм
Необходимо написать программу на делфи. Карта местности задаётся пользователем в виде сетки N на N клеток определённого типа. На карте выбирается местоположение двух населённых пунктов. Требуется проложить самую дешёвую дорогу, связывающую эти 2 пункта, если известна стоимость участка дороги на местности каждого типа(лес-10, поле-20, болото-28 и т.п.).
Так и не смогла разобраться в волновом алгоритме. Помогите пожалуйста |
15.05.2010, 19:22 | #2 |
Пользователь
Регистрация: 23.07.2009
Сообщений: 66
|
Тут, скорее, алгоритм Дейкстры. Волновой алгоритм хорошо отработает на деревьях, а на обычных графах не будет искать оптимальный путь, если у вас ребра имеют различный вес.
O(n)
|
17.05.2010, 09:36 | #3 |
Регистрация: 15.05.2010
Сообщений: 6
|
Спасибо, sabbathist, это как раз то, что нужно, но как реализовать на делфи, я так и не нашла(((
|
17.05.2010, 10:00 | #4 |
Форумчанин
Регистрация: 04.05.2010
Сообщений: 495
|
Может это подойдет:
http://www.delphisources.ru/pages/so...-algoritm.html
Нажми на весы, поставь +
Для благодарностей : WebMoney WMR R252732729948 |
17.05.2010, 10:35 | #5 |
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
Уже проще свой написать . В майском выпуске журнала Программист будет описание алгоритма Дейкстры, к нему будет выложен исходники аналогичной программы, но с комментарии и самостоятельным классом для использования в качестве графа, цель которого находить кратчайшее расстояние до точек, а также с составлением наикратчайшего маршрута до каждой из этих точек
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика |
17.05.2010, 10:41 | #6 |
А может и не...
Участник клуба
Регистрация: 27.03.2010
Сообщений: 1,269
|
Когда планируется выход номера???
Перемешивай дело с бездельем и не сойдешь с ума...
|
17.05.2010, 10:56 | #7 |
Форумчанин
Регистрация: 19.02.2009
Сообщений: 622
|
Жми на весы!!!
|
17.05.2010, 14:49 | #8 |
Регистрация: 15.05.2010
Сообщений: 6
|
всё это оч похоже. Мне нужно сделать вот такую же программу, но чтоб был алгоритм Дейкстры или хотя бы полегче, чем эта
|
17.05.2010, 21:35 | #9 |
Пользователь
Регистрация: 23.07.2009
Сообщений: 66
|
Вам нужен точный алгоритм или тот, что используется в играх (например, когда юниты бегают по карте)? Если точный не нужен, то можно использовать вместо Дейкстры алгоритм A* (А-стар).
Дейкстра есть на паскале, позже выложу.
O(n)
|
17.05.2010, 22:55 | #10 |
Пользователь
Регистрация: 23.07.2009
Сообщений: 66
|
Код:
тут дейкстра и построение графа. Но вам ведь надо строить "особый граф". Где вес ребер будет равен "стоимости клетки". Но это уже за вами
O(n)
Последний раз редактировалось sabbathist; 17.05.2010 в 23:18. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм Флойда. Поиск Кратчайшего пути. | Shady | Помощь студентам | 5 | 06.10.2014 18:29 |
Волновой алгоритм (алгоритм Ли) | MrRockchip | Общие вопросы C/C++ | 4 | 10.05.2010 13:26 |
Волновой алгоритм сферическая волна | ArtInt | Общие вопросы Delphi | 2 | 24.04.2010 15:43 |
Поиск наименьшего и самого редкоповторяющегося числа в Memo (Delphi) | giga_person | Помощь студентам | 5 | 21.03.2010 19:20 |
Волновой алгоритм поиска | Merkator | Gamedev - cоздание игр: Unity, OpenGL, DirectX | 8 | 12.02.2009 16:15 |