Ответ 1
Эта проблема NP-Hard.
Определить 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-Hard.
(1) Покажем, что поиск двух путей, охватывающих все вершины без использования какой-либо вершины дважды, является NP-Hard [пусть назовем такой путь: 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, buffer, vk + 1,..., vn], в G есть 2-путь, 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.
EDIT: более простое решение:
Создать график 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, который может быть решен in O(|V|^2 * 2^|V|) с использованием динамического программирования.
Обратите внимание, что это решение [с использованием TSP] предназначено для одного выровненного театра, но это может быть хорошим способом найти решение для общего случая.