Почти задача коммивояжера - помогите с алгоритмом

k1a2r3t4a

Помогите, пожалуйста, отыскать удобоваримый (пусть даже и неточный) алгоритм к следующей задаче.
На координатной плоскости заданы N точек. Среди этих точек выбрать такое множество, что замкнутый машрут, соединяющий выбранные точки не превышал заданной длины L и причем количество выбранных точек максимально возможное. (двигаться по такому маршруту можно только в одном направлении, т.е. вернувшись в исходную точку, можно побывать во всех выбранных точках не более одного раза)
Нутром чую, что задача близка к задаче коммивояжера. Но подобного варианта этой задачи пока не нашел.
Как вариант, вижу что задача сводится к задаче коммивояжера для фиксированной выборки точек, с последующим перебором всех возможных множеств точек из исходного множества N, пока подмножество точек не станет максимально возможным по количеству точек. Но это ж очень ме-е-е-едленно....

natunchik

Как вариант, вижу что задача сводится к задаче коммивояжера для фиксированной выборки точек, с последующим перебором всех возможных множеств точек из исходного множества N, пока подмножество точек не станет максимально возможным по количеству точек. Но это ж очень ме-е-е-едленно....

Во-первых, ты говоришь это так, как если бы тебе был известен быстрый способ решить задачу коммивояжера. Это не так.
Во-вторых, ну, для начала можно решить более простую задачу: найти хоть какой-то путь из начала в конец, решается тупо волной. Дальше, можно ли добавлять типа окольные пути к этому пути, это интересная задача. Она например решается невьебенным динамическим программированием где для каждой ноды ты хранишь ваще все возможные длины путей которыми ты в неё можешь попасть (ну, меньше L понятно). Это будет О(n_vertices^2 * L я думаю. Если это ок, то бери и пиши.
В любом случае это не экспоненциально от количества вершин, так что совсем не NP-hard.

natunchik

Хотя нет, если хранить только длину пути это не позволяет обработать ограничение что нельзя возвращаться в одну и ту же ноду. Хм. Тогда не знаю. Интересная задачка!

maksim23

На координатной плоскости заданы N точек.

1) http://www.ugatu.ac.ru/assets/files/documents/dissov/06/2014...
Задача 2 (стр. 37) — это не твоя ли?
И ещё другие задачи (1, 3, 4) глянь.
2) Если нет...
Я бы вот такую упрощённую рассмотрел:
http://rain.ifmo.ru/cat/view.php/vis/graph-circuits-cuts/bit...
Не самое нормальное приближение, зато требование начала и конца в одной точке уже учтено.
Сложность О(n²). Перебор всех подмножеств увеличит ещё сложность, на сколько — сказать не могу, но можно предположить (по опыту близкой задачи, где тоже был перебор с отсечением что в итоге будет О(n³ log n). Решение задачи не изотропно, так что можно сделать несколько прогонов, после каждого поворачивая точки на плоскости на какой-то угол.
После того, как решение найдено, его можно попытаться улучшить, например, жадным алгоритмом.

k1a2r3t4a

Спасибо за ссылки!
Оставить комментарий
Имя или ник:
Комментарий: