Поиск пути -> Форум на Исходниках.Ру

	Наши проекты: Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту

Здравствуйте, Гость ! [216.73.216.3]

правила раздела Алгоритмы

1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке

Модераторы: Akina, shadeofgray

Новое голосование

Поиск пути

o_serg	Сообщ. #1 , 23.04.02, 18:59
Unregistered	Может кто подскажет как построить путь между двумя точками? Волновой не подходит для стратегий, слишком медленный.

Mamochka	Сообщ. #2 , 23.04.02, 19:02
Unregistered	Как насчет алгоритмов маршрутизации

Сообщ. #3 , 24.04.02, 09:09

Profi

Профиль · PM

Рейтинг (т): 78

Цитата o_serg, 23.04.02, 22:59:05

Может кто подскажет как построить путь между двумя точками? Волновой не подходит для стратегий, слишком медленный.

А если его оптимизировать?
Скажем пускать волну с 2х концов сразу, или рамку наложить?

o_serg	Сообщ. #4 , 24.04.02, 18:08
Unregistered	А как определить где эти волны встретились ?

o_serg	Сообщ. #5 , 24.04.02, 18:11
Unregistered	- Как насчет алгоритмов маршрутизации - А подробнее можно ?..

Сообщ. #6 , 25.04.02, 09:01

Profi

Профиль · PM

Рейтинг (т): 78

Цитата o_serg, 24.04.02, 22:08:12

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

Как обычно, присваиваешь значения клеткам, на каждой итерации смотришь не достиг ли фронт волны клетки, на которой уже побывала встречная волна.
На самом деле с т.зр. статистики лучшая оптимизация получается при накладывании рамки. Т.е. рабочее поле ограничивается рамкой размера на 15-20\% больше мин. прямоугольника, охватывающего исходные точки. При отрицательном рез-те рамка либо расширяется, либо снимается. (Так поступают в САПР при трассировке соединителей).

Насчет маршрутизации, Mamochka видимо имел ввиду OSPF (если я неправ, поправь).
Там используется алгоритм Дийкстры для поиска кратчайшего пути в взвешенном графе

Удачи

Mamochka	Сообщ. #7 , 25.04.02, 09:38
Unregistered	Посмотри http://book.itep.ru/4/44/rut_4411.htm

o_serg	Сообщ. #8 , 26.04.02, 18:21
Unregistered	Yes !!! Сделал ... Всем ААААААААгромное спасибо.

1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)

0 пользователей:

[ Script execution time: 0,0696 ] [ 14 queries used ] [ Generated: 18.07.25, 00:30 GMT ]