Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2]      все
 Re: Вопрос к игроделам по поиску пути  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
iskatelsql,

автор
До сих пор не известен ни один алгоритм с полиномиальным временем, который бы гарантировал точность лучшую, чем 1,5 от оптимальной.
27 фев 19, 19:12    [21821030]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
в принципе если есть и удовлетворяет неоптимальное решение задачи коммивояжера, то весь вопрос лишь в заднии условий для этой задачи, т.е. подсчёте расстояния между точками с учётом препятствий
iskatelsql
Мои запросы приводят все к тем же алгоритмам прямого соединения :(.

правильно приводят
волновым алгоритмом как раз и можно определить эти растояния\пути между точками, и уже их подать в алгоритм К
27 фев 19, 19:37    [21821057]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47076
iskatelsql
Ты суть проблемы не понял. Если есть препятствия (которые я задаю как расстояния бесконечной длины) алгоритм не работает. Не находит путь.

А ты суть совета не понял. Добавь в граф не только реперные точки, но и углы препятствий. Тогда Форд-Фалкерсон на твоём первом рисунке легко обойдёт препятствие сверху.
28 фев 19, 14:48    [21821819]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47076
То есть сначала по расширенному графу находишь все пути между всеми нужными тебе точками маршрута, а потом этот новый граф уже можно скормить коммивояжору (если он действительно нужен).
1 мар 19, 14:51    [21822780]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2]      все
Все форумы / Программирование Ответить