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

Итерации 0, 100, 200, 300 и 400 в реконструкции разностной карты изображения в градациях серого по его модулю преобразования Фурье

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

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

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

Алгоритм [ править ]

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

${\displaystyle {\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}}}$

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

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

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

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

${\displaystyle \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 можно восстановить, если расположить эти переменные в таблице:

х 11	х 12
( х 21 )		х 22
	( х 31 )	( х 32 )
х 41	( х 42 )

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

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

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

х ₂₂ = - х ₃₂

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

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

x ₁₁ → a ₁   x ₂₁ → - a ₁   x ₄₁ → a ₁

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

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

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

Это несложное упражнение для проверки того, что обе описанные операции проекции минимизируют евклидово расстояние между входными и выходными значениями. Более того, если алгоритму удается найти точку x, которая лежит в обоих наборах ограничений, то мы знаем, что (i) все предложения, связанные с x, являются ИСТИННЫМИ , и (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)

а затем проецируется на другое ограничение P _A (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 ₂ . Итерация не изменилась, потому что две проекции совпадают. Из P _B ( x ₂ ),

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

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

Хаотическая динамика [ править ]

Временной ряд нормы приращения разностной карты Δ в процессе решения случайного экземпляра 3-SAT с 1000 переменными и 4200 пунктами.

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

Извлечение фазы [ править ]

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

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

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

Внешние ссылки [ править ]

• Sudoku Solver - Судоку решатель на основе разностного алгоритма на карте.

Заметки [ править ]