Коллеги, возник такой странный вопрос. Можно ли свести к задаче коммивояжёра задачу у которой функция стоимости зависит от пути, например выигрыш максимальный если между точкой маршрута А и точкой маршрута B было пройдено ровно N узлов? Если можно, то как?
В принципе, насколько я понимаю, есть (есть ли) мутное решение делать N копий исходного графа и при посещении каждой следущей точки переходить с копии на копию (как это в стат.физике делается), но может есть способ проще?
Здравствуйте, denisko, Вы писали:
D>Коллеги, возник такой странный вопрос. Можно ли свести к задаче коммивояжёра задачу у которой функция стоимости зависит от пути, например выигрыш максимальный если между точкой маршрута А и точкой маршрута B было пройдено ровно N узлов? Если можно, то как?
Ну давай плясать от печки (Кнута). Задача комивояжёра решается методом ветвей и границ.
Догадался, или ещё подсказки нужны?
Здравствуйте, denisko, Вы писали:
D>Коллеги, возник такой странный вопрос. Можно ли свести к задаче коммивояжёра задачу у которой функция стоимости зависит от пути, например выигрыш максимальный если между точкой маршрута А и точкой маршрута B было пройдено ровно N узлов? Если можно, то как?
Хотел завести схожую тему — про алгоритм Соломона vehicle routing with time windows constraints и какие библиотеки кто использовал, что порекомендует, применительно к java. Есть op-tools, но там ядро на c++ — т.е. писать расширения может для знающего только java, может быть затруднительно. Что-то про minizinc нагуглилось.
Может, minizinc- это что тебе нужно для описания ограничений "строго N узлов" и попробовать скормить его в op-tools? Отпишись плиз, если что-то путное получится.
Здравствуйте, alpha21264, Вы писали:
A>Ну давай плясать от печки (Кнута). A>Задача комивояжёра решается методом ветвей и границ. A>Догадался, или ещё подсказки нужны?
Альфыч, здесь не политика, здесь читать надо. Мне не нужно _решить_, мне нужно _свести_.
Здравствуйте, Тёмчик, Вы писали:
Тё>Может, minizinc- это что тебе нужно для описания ограничений "строго N узлов" и попробовать скормить его в op-tools? Отпишись плиз, если что-то путное получится.
Слушай, у меня больше академический или полуакадемический интерес. Хотя если до писании руками дело дойдет, то отпишусь конечно. В любом случае, спасибо за наводку.
Здравствуйте, denisko, Вы писали:
D>Здравствуйте, alpha21264, Вы писали:
A>>Ну давай плясать от печки (Кнута). A>>Задача комивояжёра решается методом ветвей и границ. A>>Догадался, или ещё подсказки нужны? D>Альфыч, здесь не политика, здесь читать надо. Мне не нужно _решить_, мне нужно _свести_.
Ты пожалуйста различай "задачу" и "метод".
Задача не сводится, потому что это другая задача.
Комивояжёру нужно найти минимум весов.
А тебе нужно найти оптимум.
Не сведёшь.
Свести, разумеется, можно. Вопрос, как я понимаю, в том, можно ли свести полиномиальным образом.
Поскольку обе задачи на графах, логично думать о трансформации графа так, чтобы задача приняла стандартный для TSP вид. Самое простое — это построить мульти-граф с теми же вершинами, но в котором ребро между А и Б соответствует некоему пути между А и Б в исходном графе и имеет тот же вес. В общем случае такое сведение естественно не будет полиномиальным, т.к. число путей не полиномиально, но возможно у тебя можно найти некие ограничения в условии исходной задачи, которые сделают это возможным. Ну там, например, есть только полиномиальное число различных весов для всех путей между А и Б, или что-то в таком духе.
Здравствуйте, denisko, Вы писали:
D>Коллеги, возник такой странный вопрос. Можно ли свести к задаче коммивояжёра задачу у которой функция стоимости зависит от пути, например выигрыш максимальный если между точкой маршрута А и точкой маршрута B было пройдено ровно N узлов? Если можно, то как? D>В принципе, насколько я понимаю, есть (есть ли) мутное решение делать N копий исходного графа и при посещении каждой следущей точки переходить с копии на копию (как это в стат.физике делается), но может есть способ проще?
Привет, я правильно понимаю, что нужно каждую вершину графа посетить ровно один раз,
причем на каждом шаге вес ребра зависит от количества уже посещенных вершин?
Здравствуйте, NotImplemented, Вы писали:
NI>Здравствуйте, denisko, Вы писали:
D>>Коллеги, возник такой странный вопрос. Можно ли свести к задаче коммивояжёра задачу у которой функция стоимости зависит от пути, например выигрыш максимальный если между точкой маршрута А и точкой маршрута B было пройдено ровно N узлов? Если можно, то как? D>>В принципе, насколько я понимаю, есть (есть ли) мутное решение делать N копий исходного графа и при посещении каждой следущей точки переходить с копии на копию (как это в стат.физике делается), но может есть способ проще?
NI>Привет, я правильно понимаю, что нужно каждую вершину графа посетить ровно один раз, NI>причем на каждом шаге вес ребра зависит от количества уже посещенных вершин?
Это, в общем-то, не так важно. Задача коммивояжера — NP-полная, поэтому любая задача из класса NP может быть сведена к ней.
Принадлежность Вашей задачи к классу NP можно проверить по определению.
Здравствуйте, denisko, Вы писали:
D>Коллеги, возник такой странный вопрос. Можно ли свести к задаче коммивояжёра задачу у которой функция стоимости зависит от пути, например выигрыш максимальный если между точкой маршрута А и точкой маршрута B было пройдено ровно N узлов? Если можно, то как? D>В принципе, насколько я понимаю, есть (есть ли) мутное решение делать N копий исходного графа и при посещении каждой следущей точки переходить с копии на копию (как это в стат.физике делается), но может есть способ проще?
Небось с хакерранка задачка?
Вот что мне пришло в голову:
1) Начать обход графа в ширину из начальной точки, строя список путей
2) Одновременно делать обход графа в ширину из конечной точки, строя список путей
3) При пересечении обхода с начальной, с обходом из конечной, отправлять получившиеся пути (concat(путь из начала, путь из конца) в priority queue (наивысший приоритет у минимального distance от N), либо просто сохранять в лист путей с одинаковой, с наименее distance from N, длиной.
