Algorytm mapy różnic

Iteracje 0, 100, 200, 300 i 400 w rekonstrukcji mapy różnic obrazu w skali szarości z jego modułu transformacji Fouriera

Algorytm mapy różnic jest algorytmem wyszukiwania ogólnych problemów spełniania ograniczeń . Jest to metaalgorytm w tym sensie, że jest zbudowany z bardziej podstawowych algorytmów, które wykonują projekcje na zbiory ograniczeń . Z matematycznego punktu widzenia algorytm mapy różnicowej jest systemem dynamicznym opartym na mapowaniu przestrzeni euklidesowej . Rozwiązania są kodowane jako stałe punkty odwzorowania.

Chociaż pierwotnie pomyślany jako ogólna metoda rozwiązywania problemu fazowego , algorytm mapy różnicowej został użyty do problemu spełnialności logicznej , przewidywania struktury białek , liczb Ramseya , równań diofantycznych i Sudoku , a także problemów z pakowaniem sfer i dysków . Ponieważ aplikacje te obejmują NP-zupełne , zakres mapy różnic obejmuje algorytm niekompletny. Podczas gdy niekompletne algorytmy mogą skutecznie weryfikować rozwiązania (po znalezieniu kandydata), nie mogą udowodnić, że rozwiązanie nie istnieje.

Algorytm mapy różnicowej jest uogólnieniem dwóch iteracyjnych metod : hybrydowego algorytmu wejścia i wyjścia (HIO) Fienupa do odzyskiwania fazy oraz algorytmu Douglasa-Rachforda do optymalizacji wypukłej . Ogólnie rzecz biorąc, metody iteracyjne mają długą historię w odzyskiwaniu faz i optymalizacji wypukłej. Zastosowanie tego stylu algorytmu do trudnych, niewypukłych problemów jest nowszym osiągnięciem.

Algorytm

Problem do rozwiązania należy najpierw sformułować jako $przecięciu$ przecięcia zbioru w przestrzeni euklidesowej $:$ znajdź na zbiorów i $\ displaystyle B}$ . Innym warunkiem wstępnym jest implementacja rzutów i ${\ displaystyle P_$ ${B}}$ , które przy dowolnym punkcie wejściowym punkt w zbiorze ograniczeń ${\ displaystyle P_ {A}$ ${\ displaystyle A}$ lub ${\ displaystyle B}$ , który jest najbliższy ${\ displaystyle x}$ . Jedna iteracja algorytmu jest dana przez mapowanie:

{\ Displaystyle {\ rozpocząć {wyrównane} x \ mapsto D (x) i = 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{wyrównane}}}

$;$ parametr nie powinien być równy 0, ale może mieć dowolny znak optymalne wartości zależą od zastosowania i są ustalane eksperymentalnie. Jako pierwsze przypuszczenie, wybór $) jest zalecany$ lub $\ beta = 1}$ ponieważ zmniejsza liczbę obliczeń projekcji na iterację:

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

Punkt jest stałym punktem mapy $x$ $}$ ${\ Displaystyle P_ {A} \ lewo (f_ {B} (x) \ prawo) = P_ {B} \ lewo (f_ {A} (x) \ prawo)}$ wtedy, gdy . Ponieważ lewa strona jest elementem , $a$ RHS jest elementem , równość oznacza, $.$ znaleźliśmy wspólny element dla dwóch zestawów Zauważ, że sam punkt stały $displaystyle$ musi należeć ani do $A}$ ani ${\ displaystyle B}$ . Zbiór punktów stałych będzie zazwyczaj miał znacznie większy wymiar niż zbiór rozwiązań.

Postęp algorytmu można monitorować, sprawdzając normę różnicy dwóch projekcji:

{\ Displaystyle \ Delta = \ lewo | P_ {A} \ lewo (f_ {B} (x) \ prawo) -P_ {B} \ lewo (f_ {A} (x) \ prawo) \ prawo |}

.

Kiedy to zniknie, znaleziono punkt wspólny dla obu zestawów ograniczeń i algorytm można zakończyć.

Przykład: logiczna spełnialność

Algorytmy niekompletne, takie jak stochastyczne przeszukiwanie lokalne , są szeroko stosowane do znajdowania satysfakcjonujących przypisań prawdy do formuł boolowskich. Jako przykład rozwiązania instancji 2-SAT za pomocą algorytmu mapy różnic, rozważ następującą formułę (~ oznacza NIE):

( q ₁ lub q ₂ ) i (~ q ₁ lub q ₃ ) i (~ q ₂ lub ~ q ₃ ) i ( q ₁ lub ~ q ₂ )

Każdemu z ośmiu literałów w tym wzorze przypisujemy jedną zmienną rzeczywistą w ośmiowymiarowej przestrzeni euklidesowej. Strukturę formuły 2-SAT można odtworzyć, gdy te zmienne zostaną ułożone w tabeli:

x ₁₁	x ₁₂
( x21 ) _{_}		x22 _{_}
	( x ₃₁ )	( x ₃₂ )
x ₄₁	( x ₄₂ )

Wiersze to klauzule w formule 2-SAT, a literały odpowiadające tej samej zmiennej boolowskiej są ułożone w kolumnach, z negacją wskazaną w nawiasach. Na przykład zmienne rzeczywiste x ₁₁ , x ₂₁ i x ₄₁ odpowiadają tej samej zmiennej boolowskiej ( q ₁ ) lub jej negacji i są nazywane replikami . Wygodnie jest powiązać wartości 1 i -1 z PRAWDA i FAŁSZ zamiast tradycyjnych 1 i 0. W tej konwencji zgodność między replikami przyjmuje postać następujących równań liniowych:

x ₁₁ = - x ₂₁ = x ₄₁

x ₁₂ = - x ₃₁ = - x ₄₂

x ₂₂ = - x ₃₂

Podprzestrzeń liniowa, w której te równania są spełnione, jest jedną z przestrzeni ograniczeń, powiedzmy A , używaną przez mapę różnic. Aby odwzorować to ograniczenie, każdą replikę zastępujemy średnią repliki ze znakiem lub jej wartością ujemną:

za ₁ = ( x ₁₁ - x ₂₁ + x ₄₁ ) / 3

x ₁₁ → za ₁ x ₂₁ → - za ₁ x ₄₁ → za ₁

Drugie ograniczenie mapy różnic dotyczy wierszy tabeli, czyli klauzul. W zadawalającym zadaniu dwóm zmiennym w każdym wierszu należy przypisać wartości (1, 1), (1, -1) lub (-1, 1). Odpowiedni zbiór ograniczeń, B , jest więc zbiorem 3 ⁴ = 81 punktów. Podczas rzutowania na to ograniczenie następująca operacja jest stosowana do każdego wiersza. Najpierw dwie wartości rzeczywiste są zaokrąglane do 1 lub -1; następnie, jeśli wynikiem jest (-1, -1), większa z dwóch pierwotnych wartości jest zastępowana przez 1. Przykłady:

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

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

Jest to proste ćwiczenie, aby sprawdzić, czy obie opisane operacje projekcji minimalizują odległość euklidesową między wartościami wejściowymi i wyjściowymi. Co więcej, jeśli algorytmowi uda się znaleźć punkt x , który leży w obu zbiorach ograniczeń, to wiemy, że (i) wszystkie klauzule związane z x są PRAWDĄ oraz (ii) przypisania do replik są zgodne z przypisaniem prawdy do oryginalne zmienne boolowskie.

₀ Aby uruchomić algorytm, najpierw generuje się punkt początkowy x , powiedzmy

-0,5	-0,8
(-0,4)		-0,6
	(0,3)	(-0,8)
0,5	(0,1)

₀ Używając β = 1, następnym krokiem jest obliczenie P _B ( x ) :

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

₀₀ Po tym następuje 2 P _B ( x ) - x ,

2.5	-1,2
(2.4)		-1,4
	(1,7)	(-1,2)
1.5	(1,9)

₀₀ a następnie rzutowane na inne ograniczenie, P _A (2 P _B ( x ) - x ) :

0,53333	-1,6
(-0,53333)		-0,1
	(1,6)	(0,1)
0,53333	(1,6)

₀₀ Zwiększenie x o różnicę dwóch projekcji daje pierwszą iterację mapy różnic, D ( x ) = x ₁ :

-0,96666	-1,4
(-1,93333)		0,3
	(0,9)	(0,3)
0,03333	(0,7)

Oto druga iteracja, D ( x ₁ ) = x ₂ :

-0,3	-1,4
(-2,6)		-0,7
	(0,9)	(-0,7)
0,7	(0,7)

To jest punkt stały: D ( x ₂ ) = x ₂ . Iteracja pozostaje niezmieniona, ponieważ obie projekcje są zgodne. Z P _B ( x ₂ ),

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

możemy odczytać satysfakcjonujące przypisanie prawdy: q ₁ = PRAWDA , q ₂ = FAŁSZ , q ₃ = PRAWDA .

Chaotyczna dynamika

Szeregi czasowe normy przyrostu mapy różnicowej Δ w trakcie rozwiązywania losowej instancji 3-SAT z 1000 zmiennymi i 4200 klauzulami.

W powyższym prostym przykładzie 2-SAT norma przyrostu mapy różnic Δ spadła monotonicznie do zera w trzech iteracjach. Kontrastuje to z zachowaniem Δ , gdy mapa różnicowa otrzymuje twardą instancję 3-SAT , gdzie silnie się waha przed odkryciem stałego punktu. Uważa się, że jako system dynamiczny mapa różnic jest chaotyczna , a przeszukiwana przestrzeń jest dziwnym atraktorem .

Odzyskiwanie fazy

Moduł transformaty Fouriera (wzór dyfrakcyjny) obrazu w skali szarości pokazany jako rekonstruowany u góry strony.

W odzyskiwaniu fazy sygnał lub obraz jest rekonstruowany z modułu (wartości bezwzględnej, wielkości) jego dyskretnej transformaty Fouriera . Na przykład źródłem danych modułu może być dyfrakcyjny Fraunhofera utworzony, gdy obiekt jest oświetlany spójnym światłem .

Odwzorowanie na ograniczenie modułu Fouriera, powiedzmy PA , jest realizowane przez obliczenie najpierw dyskretnej transformaty Fouriera sygnału lub obrazu, przeskalowanie modułów w celu uzgodnienia z danymi, a następnie odwrotne przekształcenie wyniku _. Jest to projekcja w tym sensie, że odległość euklidesowa do ograniczenia jest zminimalizowana, ponieważ (i) dyskretna transformata Fouriera, jako transformacja jednostkowa, zachowuje odległość, oraz (ii) przeskalowanie modułu (bez modyfikacji fazy) jest najmniejsza zmiana, która realizuje ograniczenie modułu.

Aby odzyskać nieznane fazy transformaty Fouriera, mapa różnic opiera się na odwzorowaniu na inne _ograniczenie PB . Może to przybierać różne formy, ponieważ rekonstruowany obiekt może być dodatni, mieć ograniczone podparcie itp . Na przykład w rekonstrukcji obrazu powierzchni efektem projekcji P _B było unieważnienie wszystkich wartości poza a prostokątnej podpory, a także unieważnić wszystkie wartości ujemne w ramach podpory.

Linki zewnętrzne

Sudoku Solver - Solver Sudoku oparty na algorytmie mapy różnic.

Notatki