Алгоритм карты различий

Алгоритм карты разностей — это алгоритм поиска для решения общих задач удовлетворения ограничений . Это метаалгоритм в том смысле, что он построен на основе более простых алгоритмов, выполняющих проекции на наборы ограничений . С математической точки зрения алгоритм разностной карты представляет собой динамическую систему, основанную на отображении евклидова пространства . Решения кодируются как фиксированные точки отображения.

Хотя изначально алгоритм разностной карты задумывался как общий метод решения фазовой проблемы , он использовался для решения булевой задачи выполнимости , предсказания структуры белка , чисел Рамсея , диофантовых уравнений и судоку . ^[1] а также проблемы с упаковкой сфер и дисков. ^[2] Поскольку эти приложения включают NP-полные задачи, область применения разностной карты аналогична неполному алгоритму . Хотя неполные алгоритмы могут эффективно проверять решения (как только кандидат найден), они не могут доказать, что решение не существует.

Алгоритм карты разностей является обобщением двух итерационных методов Fienup для поиска фазы. : алгоритма гибридного ввода-вывода (HIO) ^[3] и алгоритм Дугласа-Рэчфорда ^[4] для выпуклой оптимизации . Итерационные методы, как правило, имеют долгую историю в области фазового поиска и выпуклой оптимизации. Использование этого типа алгоритма для решения сложных невыпуклых задач является более поздней разработкой.

Алгоритм

Решаемую задачу сначала необходимо сформулировать как задачу пересечения множеств в евклидовом пространстве: найти $x$ на пересечении множеств $A$ и $B$ . Еще одним обязательным условием является реализация прогнозов. $P_{A}$ и $P_{B}$ что, учитывая произвольную входную точку $x$ , вернуть точку в наборе ограничений $A$ или $B$ это самое близкое к $x$ . Одна итерация алгоритма задается отображением:

{\begin{aligned}x\mapsto D(x)&=x+\beta \left[P_{A}\left(f_{B}(x)\right)-P_{B}\left(f_{A}(x)\right)\right],\\f_{A}(x)&=P_{A}(x)-{\frac {1}{\beta }}\left(P_{A}(x)-x\right),\\f_{B}(x)&=P_{B}(x)+{\frac {1}{\beta }}\left(P_{B}(x)-x\right)\end{aligned}}

Реальный параметр $\beta$ не должно быть равно 0, но может иметь любой знак; оптимальные значения зависят от применения и определяются экспериментальным путем. На первый взгляд выбор $\beta =1$ (или $\beta =-1$ ) рекомендуется, поскольку он уменьшает количество вычислений проекции на итерацию:

D(x)=x+P_{A}\left(2P_{B}(x)-x\right)-P_{B}(x)

точка $x$ это фиксированная точка карты $x\mapsto D(x)$ именно тогда, когда $P_{A}\left(f_{B}(x)\right)=P_{B}\left(f_{A}(x)\right)$ . Поскольку левая часть является элементом $A$ и RHS является элементом $B$ равенство означает, что мы нашли общий элемент для двух наборов ограничений. Обратите внимание, что фиксированная точка $x$ само по себе не обязательно принадлежит ни к одной из $A$ или $B$ . Набор фиксированных точек обычно имеет гораздо большую размерность, чем набор решений.

За ходом работы алгоритма можно следить, проверяя норму разности двух проекций:

\Delta =\left|P_{A}\left(f_{B}(x)\right)-P_{B}\left(f_{A}(x)\right)\right|

.

Когда это значение исчезает, найдена точка, общая для обоих наборов ограничений, и алгоритм можно завершить.

Пример: логическая выполнимость

Неполные алгоритмы, такие как стохастический локальный поиск , широко используются для поиска удовлетворяющих истинностных значений логических формул. В качестве примера решения задачи 2-SAT с помощью алгоритма разностной карты рассмотрим следующую формулу (~ означает НЕ):

( q ₁ или q ₂ ) и ( ~ q ₁ или q ₃ ) и ( ~ q ₂ или ~ q ₃ ) и ( q ₁ или ~ q ₂ )

Каждому из восьми литералов в этой формуле мы присваиваем одну действительную переменную в восьмимерном евклидовом пространстве. Структуру формулы 2-SAT можно восстановить, если эти переменные расположить в таблице:

х ₁₁	х ₁₂
( х ₂₁ )		х ₂₂
	( х ₃₁ )	( х ₃₂ )
х ₄₁	( х ₄₂ )

Строки — это элементы формулы 2-SAT, а литералы, соответствующие одной и той же логической переменной, расположены в столбцах, где отрицание указывается в круглых скобках. Например, действительные переменные x ₁₁ , x ₂₁ и x ₄₁ соответствуют одной и той же логической переменной ( q ₁ ) или ее отрицанию и называются репликами .Значения 1 и -1 удобно ассоциировать с ИСТИНОЙ и ЛОЖЬЮ, а не с традиционными 1 и 0. При таком соглашении совместимость между репликами принимает форму следующих линейных уравнений:

х ₁₁ = - х ₂₁ = х ₄₁

х ₁₂ = - х ₃₁ = - х ₄₂

х ₂₂ = - х ₃₂

Линейное подпространство, в котором удовлетворяются эти уравнения, является одним из пространств ограничений, скажем A , используемых разностной картой. Чтобы проецировать это ограничение, мы заменяем каждую реплику средним значением реплики со знаком или его отрицательным значением:

а ₁ = ( х ₁₁ - х ₂₁ + х ₄₁ ) / 3

х ₁₁ → а ₁ х ₂₁ → - а ₁ х ₄₁ → а ₁

Второе ограничение карты различий применяется к строкам таблицы — предложениям. При удовлетворительном присваивании двум переменным в каждой строке должны быть присвоены значения (1, 1), (1, -1) или (-1, 1). Таким образом , соответствующий набор ограничений B представляет собой набор из 3 ⁴ = 81 балл. При проецировании этого ограничения к каждой строке применяется следующая операция. Сначала два действительных значения округляются до 1 или -1; затем, если результат равен (-1, -1), большее из двух исходных значений заменяется на 1. Примеры:

(-.2, 1.2) → (-1, 1)

(-.2, -.8) → (1, -1)

Проверить, что обе описанные операции проецирования минимизируют евклидово расстояние между входными и выходными значениями, несложно. Более того, если алгоритму удается найти точку x предложения, связанные с x , которая лежит в обоих наборах ограничений, то мы знаем, что (i) все , являются TRUE и (ii) присвоения репликам согласуются с присвоением истинности исходные логические переменные.

Чтобы запустить алгоритм, сначала создается начальная точка x ₀ , скажем

-0.5	-0.8
(-0.4)		-0.6
	(0.3)	(-0.8)
0.5	(0.1)

Используя β = 1, следующим шагом будет вычисление P _B ( x ₀ ) :

1	-1
(1)		-1
	(1)	(-1)
1	(1)

Далее следует 2 P _B ( x ₀ ) - x ₀ ,

2.5	-1.2
(2.4)		-1.4
	(1.7)	(-1.2)
1.5	(1.9)

а затем проецируется на другое ограничение, PA ₍ 2 P _B ( x ₀ ) - x ₀ ):

0.53333	-1.6
(-0.53333)		-0.1
	(1.6)	(0.1)
0.53333	(1.6)

Увеличение x ₀ на разницу двух проекций дает первую итерацию карты разности D ( x ₀ ) = x ₁ :

-0.96666	-1.4
(-1.93333)		0.3
	(0.9)	(0.3)
0.03333	(0.7)

Вот вторая итерация, D ( x ₁ ) = x ₂ :

-0.3	-1.4
(-2.6)		-0.7
	(0.9)	(-0.7)
0.7	(0.7)

Это фиксированная точка: D ( x ₂ ) = x ₂ . Итерация не изменится, поскольку две проекции согласуются. Из П _Б ( х ₂ ),

1	-1
(-1)		1
	(1)	(-1)
1	(1)

мы можем считать удовлетворяющее истинному присвоение: q ₁ = ИСТИНА , q ₂ = ЛОЖЬ , q ₃ = ИСТИНА .

Хаотическая динамика

В приведенном выше простом примере 2-SAT норма приращения разностной карты Δ монотонно уменьшалась до нуля за три итерации. Это контрастирует с поведением Δ, когда разностной карте дается жесткий пример 3-SAT , где она сильно колеблется до открытия фиксированной точки. разностная карта является динамической системой Считается, что и что искомое пространство является странным аттрактором .

Фазовый поиск

При фазовом поиске сигнал или изображение восстанавливается по модулю (абсолютному значению, величине) его дискретного преобразования Фурье . Например, источником данных о модуле может быть дифракционная картина Фраунгофера , образующаяся при освещении объекта когерентным светом .

Проекция на ограничение модуля Фурье, скажем, , _PA выполняется путем сначала вычисления дискретного преобразования Фурье сигнала или изображения, изменения масштаба модулей для согласования с данными, а затем обратного преобразования результата. Это проекция в том смысле, что евклидово расстояние до ограничения минимизировано, поскольку (i) дискретное преобразование Фурье, как унитарное преобразование , сохраняет расстояние и (ii) изменение масштаба модуля (без изменения фазы) является наименьшее изменение, которое реализует ограничение по модулю.

Чтобы восстановить неизвестные фазы преобразования Фурье, карта разностей опирается на проекцию на другое ограничение, P _B . Это может принимать несколько форм, поскольку может быть известно, что реконструируемый объект положителен, имеет ограниченную опору и т. д. Например, при реконструкции изображения поверхности эффект проекции P _B заключался в том, чтобы обнулить все значения вне прямоугольная опора, а также обнулить все отрицательные значения внутри опоры.

Внешние ссылки

Sudoku Solver — решатель судоку, основанный на алгоритме карты различий.

Примечания

^ Эльзер, В.; Ранкенбург, И.; Тибо, П. (9 января 2007 г.). «Поиск по повторяющимся картам» . Труды Национальной академии наук . 104 (2): 418–423. дои : 10.1073/pnas.0606359104 . ПМЦ 1766399 . ПМИД 17202267 .
^ Гравий, Саймон; Эльзер, Вейт (22 сентября 2008 г.). «Разделяй и соглашайся: общий подход к удовлетворению ограничений». Физический обзор E . 78 (3): 036706. arXiv : 0801.0222 . Бибкод : 2008PhRvE..78c6706G . дои : 10.1103/PhysRevE.78.036706 . ПМИД 18851188 . S2CID 27814394 .
^ Фиенуп, младший (1 августа 1982 г.). «Алгоритмы поиска фазы: сравнение». Прикладная оптика . 21 (15): 2758–2769. Бибкод : 1982ApOpt..21.2758F . дои : 10.1364/AO.21.002758 . ПМИД 20396114 . S2CID 10777701 .
^ Баушке, Хайнц Х.; Комбеттс, Патрик Л.; Люк, Д. Рассел (1 июля 2002 г.). «Фазовый поиск, алгоритм уменьшения ошибок и варианты Fienup: взгляд с точки зрения выпуклой оптимизации». Журнал Оптического общества Америки А. 19 (7): 1334–1345. Бибкод : 2002JOSAA..19.1334B . CiteSeerX 10.1.1.75.1070 . дои : 10.1364/JOSAA.19.001334 . ПМИД 12095200 .

[1] Эльзер, В.; Ранкенбург, И.; Тибо, П. (9 января 2007 г.). «Поиск по повторяющимся картам» . Труды Национальной академии наук . 104 (2): 418–423. дои : 10.1073/pnas.0606359104 . ПМЦ 1766399 . ПМИД 17202267 .

[2] Гравий, Саймон; Эльзер, Вейт (22 сентября 2008 г.). «Разделяй и соглашайся: общий подход к удовлетворению ограничений». Физический обзор E . 78 (3): 036706. arXiv : 0801.0222 . Бибкод : 2008PhRvE..78c6706G . дои : 10.1103/PhysRevE.78.036706 . ПМИД 18851188 . S2CID 27814394 .

[3] Фиенуп, младший (1 августа 1982 г.). «Алгоритмы поиска фазы: сравнение». Прикладная оптика . 21 (15): 2758–2769. Бибкод : 1982ApOpt..21.2758F . дои : 10.1364/AO.21.002758 . ПМИД 20396114 . S2CID 10777701 .

[4] Баушке, Хайнц Х.; Комбеттс, Патрик Л.; Люк, Д. Рассел (1 июля 2002 г.). «Фазовый поиск, алгоритм уменьшения ошибок и варианты Fienup: взгляд с точки зрения выпуклой оптимизации». Журнал Оптического общества Америки А. 19 (7): 1334–1345. Бибкод : 2002JOSAA..19.1334B . CiteSeerX 10.1.1.75.1070 . дои : 10.1364/JOSAA.19.001334 . ПМИД 12095200 .

[1]

[2]

[3]

[4]