3SUM - 3SUM

В теории сложности вычислений , то 3SUM проблема спрашивает , является ли данный набор действительных чисел содержит три элемента, сумму к нулю. Обобщенная версия k -SUM задает тот же вопрос о k числах. 3SUM можно легко решить во времени, и соответствующие нижние границы известны в некоторых специализированных моделях вычислений ( Erickson 1999 ). ${\ displaystyle n}$${\ Displaystyle О (п ^ {2})}$${\ Displaystyle \ Omega (п ^ {\ lceil k / 2 \ rceil})}$

Было высказано предположение, что любой детерминированный алгоритм для 3SUM требует времени. В 2014 году исходная гипотеза 3SUM была опровергнута Алланом Грёнлундом и Сетом Петти, которые предложили детерминированный алгоритм, который решает 3SUM во времени. Кроме того, Гронлунд и Петти показали, что сложность 4- линейного дерева решений 3SUM равна . Впоследствии эти оценки были улучшены. Самый известный в настоящее время алгоритм для 3SUM работает во времени. Кейн, Ловетт и Моран показали, что сложность 6- линейного дерева решений 3SUM равна . Последняя граница точная (с точностью до логарифмического множителя). Все еще высказывается предположение, что 3SUM невозможно решить за ожидаемое время. ${\ Displaystyle \ Omega (п ^ {2})}$${\ Displaystyle О (п ^ {2} / ({\ журнал п} / {\ журнал \ журнал п}) ^ {2/3})}$${\ Displaystyle О (п ^ {3/2} {\ sqrt {\ log n}})}$${\ Displaystyle О (п ^ {2} (\ журнал \ журнал п) ^ {О (1)} / {\ журнал ^ {2} n})}$${\ Displaystyle О (п {\ журнал ^ {2} п})}$${\ Displaystyle О (п ^ {2- \ Omega (1)})}$

Когда элементы являются целыми числами в диапазоне , 3SUM можно решить во времени, представив входной набор в виде битового вектора , вычислив набор всех попарных сумм как дискретную свертку с использованием быстрого преобразования Фурье и, наконец, сравнив этот набор с . ${\ Displaystyle [-N, \ точки, N]}$${\ Displaystyle О (п + N \ журнал N)}$${\ displaystyle S}$${\ displaystyle S + S}$${\ displaystyle -S}$

Квадратичный алгоритм

Предположим, что входной массив . В целочисленных ( слово RAM ) моделях вычислений 3SUM можно решить в среднем по времени, вставив каждое число в хеш-таблицу , а затем для каждого индекса и проверяя, содержит ли хеш-таблица целое число . ${\ displaystyle S [0..n-1]}$${\ Displaystyle О (п ^ {2})}$${\ Displaystyle S [я]}$${\ displaystyle i}$${\ displaystyle j}$${\ Displaystyle - (S [я] + S [j])}$

Также возможно решить проблему в то же время в модели вычислений на основе сравнения или реальной RAM , для которой хеширование не разрешено. Приведенный ниже алгоритм сначала сортирует входной массив, а затем проверяет все возможные пары в тщательном порядке, чтобы избежать необходимости двоичного поиска пар в отсортированном списке, достигая наихудшего времени, как показано ниже. ${\ Displaystyle О (п ^ {2})}$

sort(S);
for i = 0 to n - 2 do
    a = S[i];
    start = i + 1;
    end = n - 1;
    while (start < end) do
        b = S[start]
        c = S[end];
        if (a + b + c == 0) then
            output a, b, c;
            // Continue search for all triplet combinations summing to zero.
            // We need to update both end and start together since the array values are distinct.
            start = start + 1;
            end = end - 1;
        else if (a + b + c > 0) then
            end = end - 1;
        else
            start = start + 1;
    end
end

В следующем примере показано выполнение этого алгоритма на небольшом отсортированном массиве. Текущие значения a показаны красным, значения b и c показаны пурпурным.

 -25 -10 -7 -3 2 4 8 10  (a+b+c==-25)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-22)
 . . .
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-7)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-7)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-3)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==2)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==0)

Правильность алгоритма можно увидеть в следующем. Предположим, у нас есть решение a + b + c = 0. Поскольку указатели движутся только в одном направлении, мы можем запускать алгоритм до тех пор, пока крайний левый указатель не укажет на a. Запустите алгоритм, пока один из оставшихся указателей не укажет на b или c, в зависимости от того, что произойдет раньше. Затем алгоритм будет работать до тех пор, пока последний указатель не укажет на оставшийся член, давая положительное решение.

Варианты

Ненулевая сумма

Вместо поиска чисел, сумма которых равна 0, можно искать числа, сумма которых является любой константой C, следующим образом:

• Вычтите C / 3 из всех элементов входного массива.
• В модифицированном массиве найдите 3 элемента, сумма которых равна 0.

Например, если A = [1,2,3,4] и вас попросят найти 3-ю сумму для C = 4, тогда вычтите все элементы A на 4/3 и решите это обычным способом 3-х сумм, т. Е.${\ Displaystyle (AC / 3) + (BC / 3) + (CC / 3) = 0}$

Или вы можете просто изменить исходный алгоритм для поиска целого числа в хеш-таблице . ${\ Displaystyle (С- (S [я] + S [j]))}$

3 разных массива

Вместо того, чтобы искать 3 числа в одном массиве, мы можем искать их в 3 разных массивах. Т.е. по трем массивам X, Y и Z найдите три числа a ∈ X , b ∈ Y , c ∈ Z , такие что . Назовите вариант с 1 массивом 3SUM × 1 и вариант с 3 массивами 3SUM × 3. ${\ displaystyle a + b + c = 0}$

Имея решатель для 3SUM × 1, задача 3SUM × 3 может быть решена следующим образом (предполагая, что все элементы являются целыми числами):

• Для каждого элемента в X , Y и Z , установлено: , , .${\ displaystyle X [i] \ получает X [i] * 10 + 1}$${\ Displaystyle Y [я] \ получает Y [я] * 10 + 2}$${\ displaystyle Z [i] \ получает Z [i] * 10-3}$
• Пусть S будет конкатенация массивов X , Y и Z .
• Используйте оракул 3SUM × 1, чтобы найти три таких элемента , что .${\ displaystyle a '\ in S, \ b' \ in S, \ c '\ in S}$${\ displaystyle a '+ b' + c '= 0}$
• Вернуться .${\ displaystyle a \ gets (a'-1) / 10, \ b \ gets (b'-2) / 10, \ c \ gets (c '+ 3) / 10}$

Кстати , мы преобразованного массивы, гарантируется , что ∈ X , B ∈ Y , гр ∈ Z .

Сумма свертки

Вместо поиска произвольных элементов массива, таких что:

${\ Displaystyle S [к] = S [я] + S [j]}$

свертка 3sum проблема (Conv3SUM) ищет элементы в определенных местах:

${\ Displaystyle S [я + J] = S [я] + S [J]}$

Снижение с Conv3SUM до 3SUM

Имея решатель для 3SUM, проблема Conv3SUM может быть решена следующим образом.

• Определите новый массив T так , чтобы для каждого индекса i : (где n - количество элементов в массиве, а индексы меняются от 0 до n -1).${\ Displaystyle Т [я] = 2 нс [я] + я}$
• Решить 3SUM на массиве Т .

Доказательство правильности:

• Если в исходном массиве существует тройная с , то , таким образом , это решение будет найдено 3SUM на T .${\ Displaystyle S [я + J] = S [я] + S [J]}$${\ Displaystyle Т [я + j] = 2nS [я + j] + я + j = (2nS [i] + i) + (2nS [j] + j) = T [i] + T [j]}$
• И наоборот, если в новом массиве есть тройка с , то . Потому что , обязательно и , таким образом , это правильное решение для Conv3SUM на S .${\ Displaystyle Т [к] = Т [я] + Т [j]}$${\ Displaystyle 2nS [к] + к = 2n (S [я] + S [j]) + (я + j)}$${\ Displaystyle я + j <2n}$${\ Displaystyle S [к] = S [я] + S [j]}$${\ Displaystyle к = я + j}$

Снижение с 3SUM до Conv3SUM

Имея решатель для Conv3SUM, проблема 3SUM может быть решена следующим образом.

При сокращении используется хеш-функция . В первом приближении предположим, что у нас есть линейная хеш-функция, то есть функция h такая, что:

${\ Displaystyle ч (х + у) = ч (х) + ч (у)}$

Предположим, что все элементы являются целыми числами в диапазоне: 0 ... N -1, и что функция h отображает каждый элемент на элемент в меньшем диапазоне индексов: 0 ... n -1. Создайте новый массив T и отправьте каждому элементу S его хеш-значение в T , то есть для каждого x в S ( ): ${\ displaystyle \ forall x \ in S}$

${\ Displaystyle Т [час (х)] = х}$

Первоначально предположим, что отображения уникальны (т.е. каждая ячейка в T принимает только один элемент из S ). Решить Conv3SUM на T . Сейчас же:

• Если есть решение для 3SUM: , то: и , таким образом , это решение будет найдено решателем Conv3SUM на Т .${\ Displaystyle г = х + у}$${\ Displaystyle Т [час (г)] = Т [час (х)] + Т [час (у)]}$${\ Displaystyle ч (г) = ч (х) + ч (у)}$
• И наоборот, если Conv3SUM находится на Т , то , очевидно , что соответствует решению 3SUM на S , так как Т просто перестановка S .

Это идеализированное решение не работает, потому что любая хеш - функция может отобразить несколько различных элементов S в одной и те же ячейки T . Хитрость заключается в том, чтобы создать массив , выбрав один случайный элемент из каждой ячейки T , и запустить Conv3SUM . Если решение найдено, то это правильное решение для 3SUM на S . Если решение не найдено, создайте другое случайное число и повторите попытку. Предположим, что в каждой ячейке T содержится не более R элементов . Тогда вероятность найти решение (если решение существует) - это вероятность того, что случайный выбор выберет правильный элемент из каждой ячейки, а именно . Выполнив Conv3SUM раз, решение будет найдено с высокой вероятностью. ${\ displaystyle T ^ {*}}$${\ displaystyle T ^ {*}}$${\ displaystyle T ^ {*}}$${\ Displaystyle (1 / R) ^ {3}}$${\ displaystyle R ^ {3}}$

К сожалению, у нас нет линейного идеального хеширования, поэтому мы должны использовать почти линейную хеш-функцию , то есть функцию h, такую, что:

${\ Displaystyle ч (х + у) = ч (х) + ч (у)}$ или

${\ Displaystyle ч (х + у) = ч (х) + ч (у) +1}$

Это требует дублирования элементов S при копировании их в T , т.е. помещать каждый элемент как в (как раньше), так и в . Таким образом, каждая ячейка будет иметь 2 элемента R , и нам придется запускать Conv3SUM раз. ${\ displaystyle x \ in S}$${\ Displaystyle Т [час (х)]}$${\ Displaystyle Т [час (х)] - 1}$${\ displaystyle (2R) ^ {3}}$

3SUM-жесткость

Задача называется 3SUM-сложной, если ее решение в субквадратичном времени подразумевает алгоритм субквадратичного времени для 3SUM. Концепция твердости 3SUM была введена Gajentaan & Overmars (1995) . Они доказали, что большой класс задач вычислительной геометрии является 3SUM-сложным, включая следующие. (Авторы признают, что многие из этих проблем созданы другими исследователями.)

• Имеются ли три линии на плоскости, которые пересекаются в одной точке?
• Учитывая набор непересекающихся отрезков прямых, параллельных осям, существует ли линия, разделяющая их на два непустых подмножества?
• Учитывая набор бесконечных полос на плоскости, полностью ли они покрывают данный прямоугольник?
• Дан набор треугольников на плоскости, вычислите их меру.
• Имеется ли в их соединении отверстие для набора треугольников на плоскости?
• Ряд проблем видимости и планирования движения, например,
  • Учитывая набор горизонтальных треугольников в пространстве, можно ли увидеть конкретный треугольник из определенной точки?
  • Учитывая набор непересекающихся препятствий на плоскости, параллельных осям, может ли данный стержень перемещаться посредством перемещений и вращений между начальным и конечным положениями без столкновения с препятствиями?

К настоящему времени в эту категорию попадает множество других проблем. Примером является решающая версия сортировки X + Y : заданы наборы чисел X и Y, состоящие из n элементов в каждом, существуют ли n ² различных x + y для x ∈ X , y ∈ Y ?

Смотрите также

• Проблема суммы подмножества

Примечания

использованная литература

• Кейн, Дэниел М .; Ловетт, Шахар; Моран, Шэй (2018). «Почти оптимальные линейные деревья решений для k-SUM и родственных задач». Материалы 50-го ежегодного симпозиума ACM SIGACT по теории вычислений (STOC) : 554–563. arXiv : 1705.01720 . DOI : 10.1145 / 3188745.3188770 . ISBN 9781450355599.
• Чан, Тимоти М. (2018), «Дополнительные ускорения логарифмического фактора для 3SUM, (median, +) - Convolution и некоторые геометрические 3SUM-сложные задачи», Труды Двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам ( SODA) : 881-897, DOI : 10,1137 / 1.9781611975031.57 , ISBN 978-1-61197-503-1
• Grønlund, A .; Петти, С. (2014). Втроем, вырожденные и любовные треугольники . 55-й ежегодный симпозиум IEEE по основам компьютерных наук, 2014 г. п. 621. arXiv : 1404.0799 . Bibcode : 2014arXiv1404.0799G . DOI : 10.1109 / FOCS.2014.72 . ISBN 978-1-4799-6517-5.
• Фрейнда, Ари (2017), "Улучшенная Subquadratic 3SUM", Algorithmica , 44 (2): 440-458, DOI : 10.1007 / s00453-015-0079-6.
• Золото, Омер; Шарир, Миха (2017), «Улучшенные границы для 3SUM, k -SUM и линейного вырождения», In Proc. 25-й ежегодный европейский симпозиум по алгоритмам (ESA) , LIPIcs, 87 : 42: 1–42: 13, doi : 10.4230 / LIPIcs.ESA.2017.42
• Баран, Илья; Демейн, Эрик Д .; Pătraşcu Михай (2008), "Subquadratic алгоритмы 3SUM" , Algorithmica , 50 (4): 584-596, DOI : 10.1007 / s00453-007-9036-3.
• Демейн, Эрик Д .; Митчелл, Джозеф SB ; О'Рурк, Джозеф (июль 2005 г.), «Проблема 11: 3SUM Hard Problems» , The Open Problems Project , заархивировано из оригинала 15 декабря 2012 г. , извлечено 2 сентября 2008 г..
• Эриксон, Джефф (1999), "Нижние оценки для задач линейной выполнимости" , Чикагский журнал теоретической информатики , MIT Press, 1999.
• Гаджентаан, Анка; Овермарс, Марк Х. (1995), "Об одном классе задач вычислительной геометрии O ( n ² )", Computational Geometry: Theory and Applications , 5 (3): 165–185, doi : 10.1016 / 0925-7721 (95 ) 00022-2 , ЛВП : 1874/17058.
• Кинг, Джеймс (2004 г.), Обзор сложных задач 3SUM (PDF).