Генерация случайного цикла, который приближается к данному весу

Question

Существует ли графовый алгоритм для решения следующей задачи:

Учитывая взвешенный неориентированный график G (все веса положительные), начальный узел N и общий вес W*. Создайте случайный цикл на графике, начинающийся и заканчивающийся в узле N, из которого общий вес (суммарный вес всех ребер) приблизительно равен данному весу W*.

Можно было бы увидеть, что это генерирует цикл , который best приближается к W*, но генерирует a цикл, который приближается W* с некоторой погрешностью тоже хорошо.

Answer 1

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