Алгоритм краевого клика

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

  1. Рассчитать все максимальные клики с помощью алгоритма Брон-Кербоша, и
  2. Попробуйте, если какой-нибудь 1,2,3,... из них охватит все края, пока я не найду минимальное число

Будет ли это работать и кто-нибудь знает лучший метод; есть ли стандартный алгоритм? К моему удивлению, я не смог найти такой алгоритм. Я знаю, что проблема NP-сложная, поэтому не ожидаю быстрого решения.

Источник

2 ответа

Решение

Я работал над подобной проблемой 2 года назад, и я никогда не видел никаких стандартных существующих подходов к ней. Я сделал следующее:

  1. Вычислить все максимальные клики. MACE был намного лучше, чем Брон-Кербош в моем случае.
  2. Постройте задачу удовлетворения ограничений для определения минимального количества кликов, требуемых для покрытия графа. Для этого вы можете использовать инструменты SAT, Minizinc, MIP. Какой выбрать? Это зависит от ваших навыков, временных ресурсов, окружения и множества других параметров. Если мы говорим о проверке концепции, я бы остановился на Minizinc.

Немного подробностей для второй части. Определите набор булевых переменных относительно каждого ребра, если его значение == True, то оно покрыто, в противном случае это не так. Добавьте ограничения, которые позволяют покрывать наборы ребер только по отношению к каждой клике. Наконец, добавьте переменные, соответствующие каждой клике, если она == True, то она уже используется, в противном случае это не так. Наконец, необходимо, чтобы все ребра были покрыты И количество использованных кликов было минимальным.

Источник

Я бы собрал максимальные клики, как вы делаете сейчас (или, возможно, используя другой алгоритм, как предложено CaptainTrunky), но затем используйте разветвление и ограничение. Это не гарантирует ускорение, но часто приводит к значительному ускорению в "простых" случаях.

Особенно:

  • Вместо того, чтобы пробовать все подмножества максимальных кликов в порядке увеличения размера подмножества, выберите уф-грань и разветвите ее. Это означает:
    • Для каждой максимальной клики C, содержащей uv:
      • Создайте предварительное новое частичное решение, которое содержит все клики в текущем решении.
      • Добавьте C к этому частичному решению
      • Создайте новую подзадачу, содержащую график текущей подзадачи, но со всеми вершинами в C, свернутыми в одну вершину
      • Рекурс, чтобы решить эту меньшую подзадачу.
  • Следите за лучшим полным решением до сих пор. Это ваша верхняя граница (UB). Вам не нужно продолжать обработку любой подзадачи, которая уже достигла этой верхней границы, но все еще имеет ребра; лучшее решение уже существует!
  • Лучше всего выбрать край для ответвления, который покрывается как можно меньшим количеством кликов. Выбирая, в каком порядке попробовать эти клики, попробуйте тот, который, по вашему мнению, будет лучшим (возможно, самым большим) в первую очередь.

И вот идея нижней границы для улучшения уровня обрезки:

Если подграф G'содержит независимый набор размера s, то вам потребуется по крайней мере s клик, чтобы покрыть G' (поскольку ни одна клика не может покрыть две или более вершин в независимом наборе). Вычисление максимально возможного IS является NP-сложным и, следовательно, здесь непрактичным, но вы можете получить дешевую границу, используя 2-аппроксимацию для покрытия вершин: просто продолжайте выбирать ребро и выбрасывать обе вершины, пока ребра не останутся; если вы выбросили k ребер, то останется IS, которое находится в пределах k от оптимального.

Вы можете добавить размер этого IS к общему количеству кликов в вашем решении; если он больше, чем текущий UB, вы можете прервать эту подзадачу, так как мы знаем, что ее дальнейшее развитие не может дать лучшего решения, чем то, которое мы уже видели.

Источник
Другие вопросы по тегам