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

На примере ниже данные алгоритмы не сработают, т.к. прямой видимости между верхними точками нет. Хотелось бы алгоритм, который сам бы обошел препятствие сверху или снизу (где оптимальней по расстоянию). Но нагуглить что-то подобное не получилось.



Или вот такой вариант: две двери. В данном случае напрашивается вход через одну дверь, а выход через другую.



Вобщем нужен алгоритм в возможностью трассировки, а не просто прямого соединения. В играх вроде есть что-то такое. Подскажите что гуглить. Мои запросы приводят все к тем же алгоритмам прямого соединения :(

Зы. как итог нужно соединить все точки замкнутым кольцевым путем, без пересечений с самим собой.

alex55555, m7m

Про волновой алгоритм я читал - но везде, где я его встречал он был между двумя точками. У меня же этих точек бывает под две сотни.

Причем сначала пройтись алгоритмом поиска кратчайшего пути без препятствий и найти последовательность, потом волновым попарно - не получится. Я пробовал отключать "препятствия". Путь рисовался красивый, вот только вручную его потом растащить вокруг препятствий не получилось - образовывались петли. Нужен такой алгоритм, который будет сразу знать о всех точках, а не только о двух.

Нет ли такого алгоритма, которому можно указать вспомогательные, необязательные точки.? Т.е. Например на первой картинке препятствие можно обойти сверху и снизу. Наставить вспомогательных точек и там и там (да хоть по периметру препятствия) а алгоритм бы знал что зеленые кружки - обязательные точки, а по остальным опционально пробежаться, чтоб путь замкнулся?

mayton,

Скажи, а этот алгоритм подойдет для моей задачи? На обычном компьютере за разумное время отработает?

У меня всего около тысячи точек, десятки препятствий. Из этих точек выбираются определенные (пока было от 18 до 190 штук). Ну и соответственно между ними нужен кольцевой путь, обходящий препятствия.

Т.к. я заранее не знаю какие точки будут выбраны, специальных вспомогательных заранее расставить не могу. (да и нелегко это на таком объеме)

SashaMercury,

Это то, что ты написал в первом комменте :(

SashaMercury,

Автокад. Есть координаты точек, есть координаты областей. 2Д.

maytonГамильтонов цикл здеь непричем.

Это мне или ему?
Остановился на 2opt. Препятствия ставил как бесконечное расстояние. Это работало, когда было какими точками обойти препятствие, но если есть хоть одна непроходимость - приехали.

Dimitry Sibiryakov,

Так что-то вроде я и хотел... Только вот какой алгоритм работает так, что можно указать какие точки обязательные, а какие нет? Те, что я нашел, проходят обязательно по всем точкам. Т.е. если добавить углы он по ним пойдет, даже если этого не нужно

maytonПоэтому и дом с двумя дверями можно просто
бить на квадратную сетку и не парится.

Чтоб было понятнее - это точки на реальной карте. И вполне себе реальные препятствия в виде зданий, заборов, и остальных непроходимостей. Конкретно этот кусок примерно 1 на 2,5 километра. Мне не кажется простым бить его на квадраты...

Если только автоматически, на квадраты где-то 30х30 сантиметров (чтоб дорогу шириной в метр не пропустить) а потом проверить, препятствие в квадрате или нет... но это получится 27'773'889 квадратов примерно. Даже стремно начинать в этом направлении.

Dimitry Sibiryakov,

Ну я так и делаю... Ты суть проблемы не понял. Если есть препятствия (которые я задаю как расстояния бесконечной длины) алгоритм не работает. Не находит путь. Вот как эта задача коммивояжера отработает например на первой картинке? Зря чтоль я их рисовал :)

kealon(Ruslan),

Алгоритмом 2opt вполне решается. Не хватает трассировки, как в навигаторе :)