Эта проблема NP-Hard .
Define L={(G,n,m)|there is a legal seating for G in m×m matrix,(u,v) in E if u is friend of v} L является формальным определением этой проблемы как языка.
Доказательство:
Мы покажем Гамильтонова задача ≤ (p) 2-путь ≤ (p) Эта задача в 2 этапа [Гамильтониан и 2-путь определены ниже], и, таким образом, мы заключаем, что эта задача является NP-трудной.
(1) Мы покажем, что поиск двух путей, охватывающих все вершины без использования одной вершины дважды, является NP-сложным [назовем такой путь: 2-путь, и эта задача - как задача 2-пути]
Сокращение от задачи о гамильтоновом пути :
input: a graph G=(V,E)
Output: a graph G'=(V',E) where V' = V U {u₀}.
Корректность:
- если G имеет гамильтонов путь: v₁ → v₂ → ... → vn, то G 'имеет 2-путь:
v₁ → v₂ → ... → уп, u₀
- если G 'имеет 2-путь, так как u₀ изолирован от остальных вершин, существует
путь: v₁ → ... → vn, который является гамильтонианом в G.
Таким образом: у G есть гамильтонов путь 1 ⇔ G имеет 2 пути, и, таким образом: задача с 2 путями NP-Hard.
(2) Теперь мы покажем, что наша задача [L] также NP-Hard:
Мы покажем сокращение от задачи с 2 путями, определенной выше.
input: a graph G=(V,E)
output: (G,|V|+1,1) [a long row with |V|+1 sits].
Корректность:
- Если у G есть 2 пути, то мы можем усадить людей и использовать 1 место для
использовать в качестве «буфера» между двумя путями, это будет законное идеальное размещение
так как если v₁ сидит рядом с v₂, то v₁ v₁ → v₂ находится на пути, и, таким образом,
(v₁, v₂) находится в E, поэтому v₁, v₂ - друзья.
- Если (G, | V | +1,1) является законным местом: [v₁, ..., vk, буфер , vk + 1, ..., vn], существует 2-дорожка в G,
v₁ → ... → vk, vk + 1 → ... → vn
Вывод: Эта проблема является NP-Hard, поэтому для нее нет полиномиального решения.
Экспоненциальное решение:
Возможно, вы захотите использовать решение backtracking : в основном: создайте все подмножества E с размером | V | -2 или меньше, отметьте, какое лучше.
static best <- infinity
least_enemies(G,used):
if |used| <= |V|-2:
val <- evaluate(used)
best <- min(best,val)
if |used| == |V|-2:
return
for each edge e in E-used: //E without used
least_enemies(G,used + e)
здесь мы предполагаем, что оценка (использованная) дает «оценку» для этого решения. если это решение полностью незаконно [т.е. вершина появляется дважды], evaluate(used)=infinity. Конечно, можно сделать оптимизацию, обрезав эти случаи. чтобы получить фактическое заседание, мы можем сохранить лучшее на данный момент решение.
(*) Возможно, есть лучшие решения, это просто простое возможное решение, основная цель в этом ответе - доказательство эта проблема - NP-Hard.
РЕДАКТИРОВАТЬ: более простое решение:
Создайте график G'=(V U { u₀ } ,E U {(u₀,v),(v,u₀) | for each v in V}) [u₀ - это ненужная вершина для буфера] и весовую функцию для ребер:
w((u,v)) = 1 u is friend of v
w((u,v)) = 2 u is an enemy v
w((u0,v)) = w ((v,u0)) = 0
Теперь у вас есть классический TSP , который можно решить в O(|V|^2 * 2^|V|) с помощью динамического программирования.
Обратите внимание, что это решение [с использованием TSP] предназначено для одного театра, но это может быть хорошим способом найти решение для общего случая.