У меня проблема в голове, я думаю, что это проблема NPC, но я не знаю, как это доказать.
Вот проблема:
В очень большом озере k островов и n понтонов в форме вееров. Эти понтоны имеют одинаковый размер, но имеют разные начальные направления и находятся в разных первоначальных положениях в озере. Понтоны могут свободно вращаться вокруг своего центра масс без каких-либо затрат, связанных с вращением.
Теперь нам нужно переместить эти понтоны, чтобы все острова в озере могли быть соединены. Мы можем гарантировать, что количество понтонов достаточно, чтобы соединить все острова.
[Примечание]: мы не можем повторно использовать понтоны !!
Задача состоит в том, чтобы найти решение, имеющее минимальное суммарное расстояние движущихся понтонов, чтобы соединить все острова. Расстояние перемещения одного понтона можно рассчитать как расстояние между исходным положением центра масс и его развернутым положением.
Чтобы было понятно, я нарисовал такую фигуру. Предположим, у нас есть 3 острова A, B и C. Они расположены где-то в озере. И у меня есть несколько веерообразных пантонов. Теперь решение состоит в том, чтобы найти минимальное суммирование расстояния перемещения для соединения A, B и C, показанное в нижней части рисунка. Надеюсь, это поможет понять проблему. :)
Кажется, проблема в NPC, но я не знаю, чтобы доказать это. Может ли кто-нибудь помочь мне в этом?
источник
Ответы:
Первое: это не проблема коммивояжера. TSP требует идентификации минимального веса гамильтонова цикла; этот цикл не требует цикла или даже минимального веса пути. Это требует минимальной стоимости строительства соединительного набора ребер, где стоимость строительства основана на перемещении понтонов.
Второе: это не проблема связующего дерева с минимальным весом. Смотрите выше - нам требуется минимальная стоимость строительства, а не минимальная идентификация веса.
Третье: кажется, что построенный путь будет составным, но не обязательно с минимальным весом. Альтернатива состоит в том, что это было бы остовное дерево плюс некоторые дополнительные ребра, приводящие к циклу; но если мы начнем с конфигурации без ребер, то у каждого ребра будет некоторая положительная стоимость, и мы всегда сможем найти остовное дерево с меньшим весом, просто не создавая дополнительные ребра.
Четвертое: вы говорите, что понтоны вращаются свободно; Я предполагаю, что это означает, что никакие затраты не связаны с вращением понтонов. Однако вы не указываете, что вращают понтоны: их точки? Их центры масс? Любая внутренняя точка? (Если бы была какая-то внешняя точка, то у нас были бы конструкции с нулевым весом, да?)
Это немного неуловимо, потому что, если мы поворачиваемся на 90 градусов вокруг внутренней точки, скажем, центра масс, какова стоимость? Ничего, потому что это вращение? Некоторая конечная сумма, потому что точка сдвинулась? Теперь нам также нужно знать размер понтонов.
Пятое. Предполагается, что и понтоны, и острова оба включены в евклидову плоскость?
источник
Посмотрев на новые диаграммы, я вижу, что вам может понадобиться несколько понтонов для пересечения между островами. Учитывая это, вы можете очень близко подойти к решению проблемы дерева Штейнера , превратив узлы в острова и создав достаточно разнообразную коллекцию понтонов с маленькими дугами. Википедия говорит, что на самом деле существует PTAS для проблемы дерева Штейнера, поэтому я не могу сразу сказать, что это делает его NP-завершенным. Однако, глядя на детали дерева Штейнера, вы можете либо получить хорошее примерное решение, либо показать, что проблема NP-Complete.
источник
После розыгрыша, это все еще проблема NPC. Даже если мы сократим задачу, чтобы каждый понтон мог принять 1 из n положений (т.е. известных соединительных линий. Чтобы получить наиболее оптимальный ответ, нам нужно было бы попробовать каждый понтон в каждой позиции, добавляя их расстояние, чтобы добраться до этих репозитивных позиций каждый время и сравнение со всеми остальными. Если каждый понтон должен быть испытан в каждой позиции, то необходимо проверить n комбинаций.
Я решил отредактировать изображения оригинального плаката с некоторыми дополнениями, чтобы показать идеи графиков, стоящие за этой проблемой.
На рисунке ниже показаны все (минус 2, чтобы упростить) понтоны разных цветов со всеми потенциальными конечными точками понтона в КРАСНОМ. Я только нарисовал границу между 3 понтонами и всеми конечными точками, но можно было увидеть, как это может сойти с ума.
Скажем, просто ради этого мы выбрали для первого шага бирюзовый понтон в крайнем месте, ближайшем к нему (хотя из TSP мы знаем, что в конце это может быть не оптимальным).
Ниже мы видим точно, что понтон и расстояние (ака взвешенное расстояние перемещения) должны будут пройти.
Отсюда может быть создан виртуальный узел с двумя конечными местоположениями рядом с только что размещенным местоположением. Расстояние от заданного узла, и два соседних узла в виртуальном узле имеют виртуальное расстояние перемещения 0.
Ниже мы видим виртуальный узел, созданный со ВСЕМИ потенциальными весами расстояния перемещения, которые можно разместить там.
Чтобы увидеть, как это будет продолжаться и как не всегда будет наиболее оптимальным решением (как это часто видели с TSP), выбирая кратчайшее расстояние для каждого выбора, нам нужно будет протестировать практически все пути для всех узлов / виртуальных узлов.
В конце концов, первый узел задачи (TSP) может быть любой из потенциальных конечных понтонных точек, и линии, проведенные из этого, являются расстояниями от этой конечной точки до всех других понтонов. все остальные узлы впоследствии становятся виртуальными узлами, как я изобразил, с их линиями, выступающими в качестве расстояний / весов для всех оставшихся понтонов, и так далее, и так далее. То, как эта проблема графа НЕ ТОЛЬКО является проблемой коммивояжера без требования LAST JUMP из гамильтонова цикла, мне недоступно. Чтобы получить точный ответ, нужно проверить все пути через график.
источник