차분 맵 알고리즘

푸리에 변환 계수에서 그레이스케일 영상의 차분 맵 재구성에서 0, 100, 200, 300 및 400을 반복합니다.

차분 맵 알고리즘은 일반적인 제약 조건 만족 문제에 대한 검색 알고리즘입니다.이는 제약 조건 집합에 투영을 수행하는 보다 기본적인 알고리즘에서 구축된다는 점에서 메타 알고리즘입니다.수학적 관점에서, 차분 맵 알고리즘은 유클리드 공간의 매핑에 기초한 동적 시스템이다.솔루션은 매핑의 고정 지점으로 인코딩됩니다.

원래 위상 문제를 해결하기 위한 일반적인 방법으로 생각되었지만, 차분 맵 알고리즘은 부울 만족도 문제, 단백질 구조 예측, 램지 수, 디오판틴 방정식, 스도쿠 ^[1]문제 및 구면 및 디스크 패킹 ^[2]문제에 사용되어 왔다.이러한 어플리케이션에는 NP 완전 문제가 포함되어 있기 때문에 차분 맵의 범위는 불완전한 알고리즘의 범위입니다.불완전한 알고리즘은 (후보가 발견되면) 솔루션을 효율적으로 검증할 수 있지만 솔루션이 존재하지 않음을 증명할 수는 없습니다.

차분 맵 알고리즘은 다음 두 가지 반복 방법을 일반화한 것입니다.위상^[3] 검색을 위한 Fienup의 Hybrid Input Output(HIO; 하이브리드 입력 출력) 알고리즘과 볼록 최적화를 위한 Douglas-Rachford 알고리즘^[4].일반적으로 반복 방법은 위상 검색 및 볼록 최적화에서 오랜 역사를 가지고 있다.볼록하지 않은 어려운 문제에 대해 이 방식의 알고리즘을 사용하는 것은 보다 최근의 발전입니다.

알고리즘.

풀어야 할 문제는 먼저 유클리드 공간의 집합 교차 문제로 공식화해야 합니다. $집합$ A(\ $displaystyle$ A $)$ 와 $A$ 집합B(\ $displaystyle$ B $B$ 의 교차점에서 x $(\displaystyle$ x $)$ 를 $x$ 찾아야 합니다.또 다른 전제 조건은 $P_{A}$ $(\$ })와 $P_{A}$ $(\$ )의 구현입니다. $ystyle$ P_ ${B}:$ 임의의 $P_{B}$ $입력점$ x(\ $displaystyle$ x $x$ 가 지정되면 제약조건 $세트$ A(\ $displaystyle$ A $)$ $B$ B $(\displaystyle$ B $)$ 에서 $B$ x(\ $displaystyle$ x $x$ 에 $가장$ 가까운 점을 반환합니다.알고리즘의 반복은 다음과 같습니다.

{signed}x\mapsto D(x)&=x+\beta \left [ P _ { A } \ left ( f _ { B （ x ) \ right ] , \ f _ { A （ x ) （ x ） = { A

실제 $\beta$ $\beta$ β(\ $displaystyle \beta$ })는 0이 아니어야 하지만 어느 하나의 기호를 가질 수 있습니다.최적값은 어플리케이션에 따라 다르며 실험을 통해 결정됩니다.첫 번째 추측으로, β $= 1($ $\beta =-1$ β $\beta =1$ $\beta =-1$ - $(또는$ β = - 1(\displaystyle \ $display$ =- $1$ 을 $\beta =1$ 하면 반복당 투영 계산의 수가 감소하기 때문에 권장된다.

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

$P_{A}\left(f_{B}(x)\right)=P_{B}\left(f_{A}(x)\right)$ A $P_{A}\left(f_{B}(x)\right)=P_{B}\left(f_{A}(x)\right)$ ( $P_{A}\left(f_{B}(x)\right)=P_{B}\left(f_{A}(x)\right)$ B ( $P_{A}\left(f_{B}(x)\right)=P_{B}\left(f_{A}(x)\right)$ ) $x\mapsto D(x)$ $P_{A}\left(f_{B}(x)\right)=P_{B}\left(f_{A}(x)\right)$ $P_{A}\left(f_{B}(x)\right)=P_{B}\left(f_{A}(x)\right)$ B ( $P_{A}\left(f_{B}(x)\right)=P_{B}\left(f_{A}(x)\right)$ $P_{A}\left(f_{B}(x)\right)=P_{B}\left(f_{A}(x)\right)$ ( $P_{A}\left(f_{B}(x)\right)=P_{B}\left(f_{A}(x)\right)$ x $P_{A}\left(f_{B}(x)\right)=P_{B}\left(f_{A}(x)\right)$ ) \ $display style$ P _ { $A$ $x\mapsto D(x)$ \ $left$ ( $f$ _ { $B$ ) \ $right$ ( f $_$ { $B$ ) \ $display style$ x ( $x$ )는 $x$ $x \mapsto D(x)$ $P_{A}\left(f_{B}(x)\right)=P_{B}\left(f_{A}(x)\right)$ 의 고정점입니다 $=$ $P_{B}\left(f_{A}(x)\right$ 왼쪽은A(\ $displaystyle$ A $)$ 의 요소이고 RHS는 B(\ $displaystyle$ B $B$ 의 요소이므로 이 등식은 2개의 제약조건 세트에 공통 요소가 있음을 의미합니다. $고정점$ x(\ $displaystyle$ x $)$ 자체는 $x$ A $(\displaystyle$ A $)$ $B$ B $(\display style$ B $B$ 에 속할 필요는 없습니다.고정점 집합은 일반적으로 솔루션 집합보다 훨씬 높은 차원을 가집니다.

알고리즘의 진행상황은 두 투영의 차이에 대한 규범을 검사하여 모니터링할 수 있습니다.

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

=

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

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

(

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

f

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

(

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

) -

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

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

(

x

) \

displaystyle

\

Delta

= \

left P_{A}

\

left

( f

_ {

B

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

（ x ) \

right

)-

P_{B

} \

left

(

f

_ {

A

（

x

) \

right

) }

이것이 사라지면 두 제약 조건 집합에 공통되는 점이 발견되어 알고리즘을 종료할 수 있습니다.

예: 논리적 만족도

확률적 로컬 검색과 같은 불완전한 알고리즘은 부울 공식에 대한 만족스러운 진실 할당을 찾는 데 널리 사용된다.차분 맵 알고리즘을 사용하여 2-SAT 인스턴스를 해결하는 예로서 다음 공식(~은 NOT를 나타냅니다)을 고려합니다.

(q₁ 또는₂ q) 및 (~q₁ 또는₃ q) 및 (~q₂ 또는 ~q₃) 및 (q₁ 또는 ~q₂)

이 공식에서 8개의 리터럴 각각에 우리는 8차원 유클리드 공간에서 하나의 실제 변수를 할당합니다.2-SAT 공식의 구조는 다음 변수를 테이블에 배열하면 복구할 수 있습니다.

x₁₁	x₁₂
(x₂₁)		x₂₂
	(x₃₁)	(x₃₂)
x₄₁	(x₄₂)

행은 2-SAT 공식의 절이며, 같은 부울 변수에 대응하는 리터럴이 열에 배열되어 있으며, 부정은 괄호로 표시됩니다.예를 들어, 실제 변수₁₁ x, x₂₁ 및₄₁ x는 동일한 부울 변수(q₁) 또는 부정에 대응하며 복제품이라고 합니다.값 1과 -1을 기존의 1과 0이 아닌 TRUE와 FALSE에 관련짓는 것이 편리합니다.이 규칙을 사용하면 복제품 간의 호환성은 다음과 같은 선형 방정식의 형태를 취합니다.

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

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

x₂₂ = -x₃₂

이러한 방정식이 만족되는 선형 부분 공간은 차분 맵에서 사용되는 제약 조건 공간 중 하나(예: A)입니다.이 제약을 적용하기 위해 각 복제본을 서명된 복제본 평균 또는 음수로 바꿉니다.

a₁ = (x₁₁₂₁ - x + x₄₁) / 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와 관련된 절이 모두 TRUE이고 (ii) 복제본에 대한 할당이 원래 부울 변수에 대한 진실 할당과 일치함을 알 수 있습니다.

알고리즘을 실행하려면 먼저 초기 점 x를₀ 생성합니다.

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

β = 1을 사용하여 다음 단계는 P(x₀)를 계산하는_B 것입니다.

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

그 뒤에 2P_B(x₀₀) - x,

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

다른 구속조건인_A P(2P_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₂ = TRUE, q = FALSE, q₃ = TRUE.

카오스 역학

1000개의 변수와 4200개의 절을 사용하여 랜덤 3-SAT 인스턴스를 해결하는 과정에서 차분 맵의 노름의 시계열은 δ를 증가시킵니다.

위의 간단한 2-SAT 예에서는 차분 맵 증분 δ의 노름은 단조롭게 0으로 3회 반복 감소했습니다.이것은 차분 맵에 3-SAT의 하드인스턴스가 주어졌을 때의 δ의 동작과 대조됩니다.이 예에서는 고정점이 발견되기 전에 큰 변동이 발생합니다.동적 시스템으로서 차분 맵은 혼돈하고 탐색되는 공간은 이상한 매력으로 여겨진다.

위상 검색

페이지 상단에 재구성되어 표시된 그레이스케일 화상의 푸리에 변환 계수(회절 패턴)입니다.

위상검색에서 신호 또는 화상은 이산 푸리에 변환의 계수(절대값, 크기)로부터 재구성된다.예를 들어 계수 데이터의 소스는 피사체가 간섭성 빛으로 조명되었을 때 형성되는 프라운호퍼 회절 패턴일 수 있다.

푸리에 계수 제약 조건(예: P_A)에 대한 투영은 먼저 신호 또는 이미지의 이산 푸리에 변환을 계산하고 데이터에 일치하도록 모듈리를 다시 조정한 다음 결과를 역변환함으로써 이루어집니다.(i) 이산 푸리에 변환은 (ii) 단일 변환으로서 거리를 유지하고 (ii) 계수를 재조정하는 것이 계수 구속조건을 실현하는 가장 작은 변화이기 때문에 제약조건에 대한 유클리드 거리가 최소화된다는 점에서 이것은 투영이다.

푸리에 변환의 알 수 없는 위상을 복구하기 위해 차이 맵은 다른 제약 조건인_B P에 대한 투영에 의존합니다.재구성되는 객체가 양의 것으로 알려져 있거나 한정된 지지대가 있는 경우 등 여러 가지 형태를 취할 수 있습니다.예를 들어 표면 화상의 재구성에 있어서 투영_B P의 효과는 직사각형 지지대 외부의 모든 값을 무효화하고 지지대 내의 모든 음의 값을 무효화하는 것이었다.

외부 링크

스도쿠 솔버 - 차분 맵알고리즘에 근거한 스도쿠 솔버.

메모들

^ Elser, V.; Rankenburg, I.; Thibault, P. (9 January 2007). "Searching with iterated maps". Proceedings of the National Academy of Sciences. 104 (2): 418–423. doi:10.1073/pnas.0606359104. PMC 1766399. PMID 17202267.
^ Gravel, Simon; Elser, Veit (22 September 2008). "Divide and concur: A general approach to constraint satisfaction". Physical Review E. 78 (3): 036706. arXiv:0801.0222. Bibcode:2008PhRvE..78c6706G. doi:10.1103/PhysRevE.78.036706. PMID 18851188. S2CID 27814394.
^ Fienup, J. R. (1 August 1982). "Phase retrieval algorithms: a comparison". Applied Optics. 21 (15): 2758–2769. Bibcode:1982ApOpt..21.2758F. doi:10.1364/AO.21.002758. PMID 20396114. S2CID 10777701.
^ Bauschke, Heinz H.; Combettes, Patrick L.; Luke, D. Russell (1 July 2002). "Phase retrieval, error reduction algorithm, and Fienup variants: a view from convex optimization". Journal of the Optical Society of America A. 19 (7): 1334–1345. Bibcode:2002JOSAA..19.1334B. CiteSeerX 10.1.1.75.1070. doi:10.1364/JOSAA.19.001334. PMID 12095200.

[1] Elser, V.; Rankenburg, I.; Thibault, P. (9 January 2007). "Searching with iterated maps". Proceedings of the National Academy of Sciences. 104 (2): 418–423. doi:10.1073/pnas.0606359104. PMC 1766399. PMID 17202267.

[2] Gravel, Simon; Elser, Veit (22 September 2008). "Divide and concur: A general approach to constraint satisfaction". Physical Review E. 78 (3): 036706. arXiv:0801.0222. Bibcode:2008PhRvE..78c6706G. doi:10.1103/PhysRevE.78.036706. PMID 18851188. S2CID 27814394.

[3] Fienup, J. R. (1 August 1982). "Phase retrieval algorithms: a comparison". Applied Optics. 21 (15): 2758–2769. Bibcode:1982ApOpt..21.2758F. doi:10.1364/AO.21.002758. PMID 20396114. S2CID 10777701.

[4] Bauschke, Heinz H.; Combettes, Patrick L.; Luke, D. Russell (1 July 2002). "Phase retrieval, error reduction algorithm, and Fienup variants: a view from convex optimization". Journal of the Optical Society of America A. 19 (7): 1334–1345. Bibcode:2002JOSAA..19.1334B. CiteSeerX 10.1.1.75.1070. doi:10.1364/JOSAA.19.001334. PMID 12095200.

[1]

[2]

[3]

[4]

Search