Блог

Главная - Вопросы по программированию - Какой алгоритм я должен использовать для этой задачи круглого стола?

Какой алгоритм я должен использовать для этой задачи круглого стола?

#algorithm #math #data-structures #graph #computer-science

#алгоритм #математика #структуры данных #График #информатика

Вопрос:

Моя задача — определить, могу ли я усадить N гостей за круглый стол, основываясь на их симпатиях / антипатиях к другим гостям. Существует два требования к расположению мест:

  1. Все гости не должны сидеть рядом с гостями, которые им не нравятся
  2. Все гости должны сидеть рядом с гостями, которые им нравятся

Ввод: likeSet = {guest_id: [список других гостей] }, dislikeSet = {guest_id: [список других гостей] }

Вывод: логическое значение

Решением грубой силы было бы начать с размещения гостя 0 и проверки всех возможных мест, но это определенно неэффективно.

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

Любые входные данные будут оценены!

Комментарии:

1. угадайте вслепую: 1) сборка (направленная?) граф, где вершина — гость, ребро — если гостю нравится другой. 2) найдите гамильтонов цикл

2. @user3386109 Я думаю, что эти два требования являются исключительными, поскольку услуги не обязательно взаимны. Например, если гостю A нравится гость B, но гость B не является гостем A, они не должны сидеть рядом друг с другом. Без требования 1 результат будет включать случай, когда A и B расположены рядом друг с другом.

Ответ №1:

Как указал tym32167 в комментарии, эта проблема похожа на проблему гамильтонова цикла, что означает, что она NP-сложная, и вряд ли для нее будет решение за полиномиальное время.

Для сокращения:

-Предположим, у нас есть эффективное решение проблемы. Мы будем использовать его для решения экземпляра HAM-CYCLE, установленной NP-сложной задачи.

-Для входного графа G = (V, E), затем для каждой пары вершин u, v:

  1. Если (u, v) находится в E, u ‘нравится’ v
  2. Иначе, u ‘не нравится’ v

-Затем мы используем эффективное решение для вычисления логического вывода: могут ли эти гости сидеть за столом? Если они могут, мы знаем, что существует такой порядок гостей, что каждый элемент «любит» соседние элементы (связан с ними), так что последний «любит» первый (цикл), так что каждый гость сидит не более одного раза (простой цикл) и что каждый гостьсидит хотя бы один раз.

-Обладая этими знаниями, мы можем вернуть true или false к задаче цикла HAM, решив ее за полиномиальное время.