Как решить вопрос теории графов, аналогичный кратчайшему пути?

Question

Я смотрю на несколько проблем схожего формата, но разной сложности.Мы будем благодарны за полиномиальные (желательно относительно быстрые, но не обязательно) и даже за грубые решения любого из них.

Идея всех проблем состоит в том, что у вас есть взвешенный неориентированный граф,и что агент контролирует некоторые узлы графа в начале.Агент может получить контроль над узлом, если он уже контролирует два соседних узла.Агент пытается минимизировать время, затрачиваемое на управление определенным количеством узлов.Проблемы различаются по некоторым деталям.

(1) Вы получаете контроль над узлами по порядку (т.е. вы не можете захватить несколько узлов одновременно).Время, необходимое для управления узлом, определяется как минимум ребер из двух узлов, используемых для его управления.Цель состоит в том, чтобы взять под контроль каждый узел в графе.

(2) Опять же, вы получаете узлы по порядку, и цель состоит в том, чтобы взять под контроль каждый узел в графе.Время, необходимое для получения контроля над узлом, определяется как максимум двух узлов, используемых для его контроля.

(3) Либо (1), либо (2), но с целью получения контроляопределенного количества узлов, не обязательно всех из них.

(4) (3), но вы можете управлять несколькими узлами одновременно.В основном, скажем, узлы 2 и 4 используются для захвата узла 3 во времени 5. В течение этого времени 5, узлы 2 и 4 не могут использоваться для захвата узла, который не является узлом 3. Однако узлы 5 и 6например, может одновременно захватывать узел 1.

(5) (4), но с невзвешенным графиком.

Я начал с задачи (4).Я постепенно облегчил задачу от (4) до (3) - (2) - (1), надеясь, что из этого получу решение для (4).Наконец, я решил (1), но не знаю, как решить любой другой.Мое решение (1) состоит в следующем: из всех узлов-кандидатов, которые имеют два соседних узла, которые мы контролируем, просто выберите тот, который занимает наименьшее количество времени.Это похоже на алгоритм кратчайшего пути Дейкстры.Однако такого рода решение не должно решать ни одно из других.Я полагаю, что, возможно, решение для динамического программирования может работать, но я не знаю, как его сформулировать.Я также не нашел решения грубой силы ни для одной из 4 проблем.Также возможно, что некоторые проблемы не являются полиномиально разрешимыми, и мне было бы любопытно узнать, почему, если это так.

Идея для вопросов принадлежит мне, и я решаю для себяразвлекательная программа.Но я не удивлюсь, если это можно найти в другом месте.

Answer 1

Я пока не смог придумать сокращение, но эти проблемы имеют вид NP-жесткого проекта сети и проблем максимального покрытия, поэтому я был бы весьма удивлен, если бы варианты (3) - (5) былиtractable.

Мое практическое предложение будет заключаться в применении структуры смещенного генетического алгоритма случайного ключа .Связанная колода слайдов охватывает общую часть (индивид - это карта от узлов до чисел; на каждом шаге мы ранжируем индивидов, сохраняем первые x% «элитных» индивидов как есть, производим y% потомства, скрещивая случайного элитного индивида сслучайный неэлитный индивидуум, склонный к выбору элитных хромосом и пополняющий остальную часть населения случайными индивидуумами).Не общая часть переводит человека в решение.Рекомендованной отправной точкой будет выбор использования исследуемого узла с наименьшим номером каждый раз.

Answer 2

Это не ответ на проблему.Это демонстрация того, что жадный подход не подходит для задачи 1.

Предположим, что у нас есть граф с 7 узлами.Мы начинаем с контроля A и B.Стоимость от A до B и B до C и C до D составляет 1.И E, и F подключаются к A, B и D со стоимостью 10.G подключается к A, B, C и D со стоимостью 100.

Жадная стратегия, которую вы описываете, подключится к E и F встоимость 10 каждая, затем D по стоимости 10, затем C по стоимости 1, затем G по стоимости 100 на общую сумму 131.

Лучшая стратегия - подключиться к G по стоимости 100, затем C и D по стоимости 1, затем E и F по стоимости 10 на общую сумму 122 < 131.

И этот пример демонстрирует, что жадность не всегда дает правильный ответ.