Кратчайший путь через несколько точек?

Question

[New Developer]

На прямоугольной сетке есть несколько ключевых точек, через которые в заданной последовательности надо найти кратчайший маршрут без пересечения ранее посещенных точек и путей. Существует ли алгоритм для решения такой задачи, кроме Дейкстры или A* объединенных с перебором ?
Дополнил: соединение узлов может быть горизонтальным или вертикальным, без диагонального.

Comments

[Akina]

Сетка ограниченная, или не имеет внешней границы?
В любом случае задача топологическая, либо вся, либо первый этап.

[New Developer]

Akina, сетка 10 на 10 клеток.

[Wataru]

New Developer, Сетка 10x10, а ключевых точек много?

[New Developer]

Wataru, от 3 до 6. Например, 3 точки, все пронумерованы от 1 до 3, соответственно соединить 1 со 2, а 2 с 3.

[mayton2019]

Очень похоже на задачу Коммивояжера если исключить (или по другому истолковать) фразу в заданной последовательности.

[Wataru]

mayton2019, Тут все сложнее коммивояжора, потому что нельзя используемые в одном пути вершины/ребра использовать в следующем. Так что даже если фиксировать последовательность, кратчайшие пути фиг найдешь.

[mayton2019]

Wataru, мда.

Но чертов DFS всё разрулит. Главное - правильно поставить ему задачу.

[Wataru]

New Developer, А ребра все длины 1? Сетка полная - без стенок/дырок?

[Wataru]

mayton2019, ну, если с откатом, то такой полный перебор, конечно, все разрулит.

[New Developer]

Wataru, сетка без стенок/дырок, если не считать стенками ранее пройденные пути, насчет ребер - подобную задачу раньше не решал, но читал что в невзвешенном графе в начале расчетов для ребер нужно ставить длину 1.

[Alexandroppolus]

New Developer, для некоторых кейсов задача не решается, например
A(0,0) -> B(9,9) -> C(9,0) -> D(0,9)
То есть по углам сетки

[New Developer]

Alexandroppolus, да, не решается, в том числе если все узлы у одного края, но расположены не по порядку или если расположены вплотную друг к другу и соседние по диагонали A(1,2) -> B(2,3) -> C(2,2) -> D(1,3)

[New Developer]

Решил задачу следующим образом: пусть n - количество соединяемых узлов, k - количество связей между узлами, или сегментов, k = n - 1. Например, есть 4 узла, которые надо соединить в порядке 1-2-3-4. Нужно сгенерировать k - 1 уровней сегментов, а на последнем, k уровне соединить оставшийся узел/сегмент с предыдущей комбинацией сегментов. Для всех уровней, кроме k, важен порядок соединения, так как например, A* с манхэттенской эвристикой находит разные маршруты для точек 1 и 2 в зависимости от порядка их соединения. Рассмотрим первый уровень сегментов для 4 узлов. На нем возможно 2 * k поисков A*, а именно: 1-2, 2-1, 2-3, 3-2, 3-4, 4-3. Теперь для каждого сегмента необходимо сгенерировать второй уровень сегментов. На примере 1-2 получаем варианты соединений с соседними узлами, либо генерируем варианты соединений остальных точек, а 1-2 отмечаем препятствием: 12-3, 3-21, 3-4, 4-3. Получили k - 1 уровней. Теперь на последнем, k уровне находим маршрут в любом направлении между 2 предыдущими уровнями или предыдущим уровнем и последним узлом, то есть: 123-4, 321-4, 34-12, 43-12. Теперь проделываем то же самое для остальных 5 сегментов первого уровня и находим кратчайший маршрут.
Количество сгенерированных вариантов соединений всех узлов равно 2^(k - 1) * k! Для 3, 4, 5, 6 узлов это будет 4, 24, 192, 1920 вариантов соответственно. Количество запусков поиска пути будет равно сумме поисков на каждом уровне генерации сегментов, то есть 8, 54, 440, 4410 для 3, 4, 5, 6 узлов соответственно, найдено эмпирическим методом, общая формула похожа на сумму арифметико-геометрической прогрессии. Ниже приведен код на JS для подсчета вариантов соединений и поисков пути.

let n = 5, k = n - 1, acc = k > 1 ? 2 * k : 0, out = acc || 1;
for (let prev = acc - 2; prev > 2; prev -= 2) {
  acc *= prev;
  out += acc
}
console.log('Количество вариантов соединения =', acc || 1);
console.log('Количество поисков A* =', out + acc);
/*
n = 3, k = 2: 8: 4 + 4;
n = 4, k = 3: 54: 6 + 24 + 24;
n = 5, k = 4: 440: 8 + 48 + 192 + 192;
n = 6, k = 5: 4410: 10 + 80 + 480 + 1920 + 1920
*/

Answer 1

[Wataru]

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

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

Похоже, что в вашей задаче может хорошо работать метод отжига, или генетический алгоритм.

Я сомневаюсь, что даже для графа-сетки есть какой-то более простой алгоритм.

Comments

[New Developer]

Ознакомлюсь с этими алгоритмами. Пока предположил, что можно ставить преграды на точках, которые не являются начальными или конечными. Эти "тупики" должны окружать узел так, что к нему можно попасть только с одной стороны. Потом вращать эти преграды, чтобы получить новые комбинации "стенок", одновременно с алгоритмами A* или Дейкстры. Оставшиеся начальный и конечный узел выбирать по приоритету: либо по наибольшему количеству свободных связей в соседней точке, либо по наименьшему расстоянию к соседу. Примерно максимальная сложность такого метода будет (n - 1)*4^(n - 2) поисков пути, где n - количество соединяемых узлов, но если не выбирать приоритет крайних точек, то в 2 раза больше.

[New Developer]

New Developer, предположение оказалось неправильным.