Численное 3-мерное сопоставление - Numerical 3-dimensional matching

Численное 3-мерное сопоставление является НП-полный проблема решения. Это дают три мультимножества из целые числа ${ displaystyle X}$, ${ displaystyle Y}$ и ${ displaystyle Z}$, каждый из которых содержит ${ displaystyle k}$ элементы и граница ${ displaystyle b}$. Цель - выбрать подмножество ${ displaystyle M}$ из ${ Displaystyle X раз Y раз Z}$ так что каждое целое число в ${ displaystyle X}$, ${ displaystyle Y}$ и ${ displaystyle Z}$ происходит ровно один раз и для каждой тройки ${ Displaystyle (х, у, г)}$ в подмножестве ${ displaystyle x + y + z = b}$ Эта проблема обозначена как [SP16] в.^[1]

Пример

Брать ${ Displaystyle X = {3,4,4 }}$, ${ Displaystyle Y = {1,4,6 }}$ и ${ Displaystyle Z = {1,2,5 }}$, и ${ displaystyle b = 10}$. У этого экземпляра есть решение, а именно ${ Displaystyle {(3,6,1), (4,4,2), (4,1,5) }}$. Обратите внимание, что каждая тройная сумма ${ displaystyle b = 10}$. Набор ${ Displaystyle {(3,6,1), (3,4,2), (4,1,5) }}$ не является решением по нескольким причинам: не все числа используются ( ${ displaystyle 4 in X}$ отсутствует), номер используется слишком часто ( ${ displaystyle 3 in X}$), а не каждые тройные суммы ${ displaystyle b}$ (поскольку ${ Displaystyle 3 + 4 + 2 = 9 neq b = 10}$). Однако есть по крайней мере одно решение этой проблемы, которое является тем свойством, которое нас интересует с проблемами решения. ${ displaystyle b = 11}$ для того же ${ displaystyle X}$, ${ displaystyle Y}$ и ${ displaystyle Z}$, эта проблема не имеет решения (сумма всех чисел равна ${ displaystyle 30}$, что не равно ${ Displaystyle к cdot b = 33}$ в этом случае).

Связанные проблемы

Каждый случай числовой задачи трехмерного сопоставления является примером как Проблема с 3 разделами, а 3-мерное соответствие проблема.

Доказательство NP-полноты

NP-полнота проблемы 3-разбиений сформулирована Гэри и Джонсоном в книге «Компьютеры и неразрешимость; Руководство по теории NP-полноты», где эта проблема упоминается в коде [SP16].^[1] Это делается путем редукции от 3-мерного сопоставления через 4-разбиение. Чтобы доказать NP-полноту числового 3-мерного сопоставления, доказательство аналогично, но сокращение от 3-мерного сопоставления с помощью числовой 4-мерной задачи сопоставления должен быть использован.

Рекомендации