Naprzemienny Łańcuch Wnioskowania (ang. Alternating Inference Chains [AIC]) rozszerza metodę
X-Cykle na nowy wymiar. X-Cykle są związane z jednym wartością kandydata natomiast
AIC używa kandydatów o dowolnych wartościach. Mianowicie możemy łączyć dwóch kandydatów w sektorze (wiersz/kolumna/blok 3x3)
o tej samej wartości (bi-lokalizacja) oraz dwóch różnych kandydatów w tej samej komórce
(bi-wartość). AIC podobnie jak X-Cykle używa mocnych i słabych połączeń, niemniej określenia
te będą trochę inne niż w X-Cyklach. Tworząc łańcuch AIC po połączeniu mocnym następuje połączenie słabe, a po słabym mocne,
z tym, że połączenie słabe może być zastąpione mocnym, ale mocne słabym nie! Czyli jeśli między wezłem nieparzystym a parzystym
jest połączenie mocne, to pomiędzy parzystym a nieparzystym może być słabe bądź mocne.
Prosty Naprzemienny Łańcuch Wnioskowania (Simple AIC)
połaczenie mocne występuje wtedy, gdy:
- W danej komórce występują dwie wartości (między dwoma różnymi wartościami)
- w danym sektorze (wiersz/kolumna/blok 3x3) występują dwie komórki, w których występuje wartość "nVal" (między dwoma
pozycjami dla wartości "nVal"). Definicję tą rozszerzę póżniej przy Grupowym AIC.
połaczenie słabe występuje wtedy, gdy:
- W danej komórce występują więcej niż dwie wartości (między dwoma różnymi wartościami)
- w danym sektorze (wiersz/kolumna/blok 3x3) występują więcej niż dwie komórki, w których występuje wartość "nVal" (między
pozycjami dla wartości "nVal").
Wariant 1. Pętla zamknięta o Parzystej liczbie węzłów
Niech → oznacza połączenie mocne, a ⇒ połączenie słabe
Na przykładzie obok mamy następującą pętlę o 8-miu węzłach:
[7,6]=5 → [8,6]=5 ⇒ [8,6]=3 → [8,5]=3
⇒ [4,5]=3 → [4,5]=2 ⇒ [6,6]=2
→ [7,6]=2 ⇒ [7,6]=5
Usuwamy kandydatów w następujący sposób:
- jeśli dwa kolejne węzły pętli leżą w tej samej pozycji, to usuwamy z tej pozycji wszystkie wartości oprócz wartości należących
do tych węzłów pętli.
- jeśli dwa kolejne węzły pętli leżą w tym samym sektorze (wiersz/kolumna/blok 3x3), czyli mają tą wartość 'nVal' to usuwamy
tą wartość ze wszystkich pozycji sektora, do którego należą te dwa węzły oprócz pozycji wezłów pętli.
W naszym przypadku:
- dwa kolejne węzły leżą w tej samej komórce (pozycja [7,6] usuwamy wartość "6", pozycja [8,6] usuwamy wartość "8")
- dwa kolejne węzły leżą w tym samym sektorze (węzły [8,6]=3 i [4,6]=3, usuwamy wartość "3" z 5-tej kolumny czyli z pozycji [2,5]
i [6,5] oraz węzły [4,5]=2 i [6,6]=2 usuwamy wartość "2" z 5-ego bloku czyli z pozycji [4,4], [6,4], i [6,5]).
|
Wariant 2. Pętla zamknięta o Nieparzystej liczbie węzłów
Na diagramie po lewej stronie mamy następującą pętlę o 7-miu węzłach:
[7,6]=4 → [7,2]=4 ⇒ [7,2]=2 → [7,8]=2
→ [9,9]=2 → [9,9]=4 → [9,6]=4
→ [7,6]=4
Szukamy takiego węzła pętli, który ma mocne połączenie z poprzednim i następnym węzłem pętli oraz liczba kolejnych mocnych
połączeń (aż do słabego połączenia) zarówno od tego węzła wstecz jak i do przodu jest nieparzysta, wówczas usuwamy wszystkie
wartości z tej pozycji węzła oprócz wartości, która należy do tego węzła. Wyjaśniam: liczba kolejnych silnych połączeń od wezła
[7,6]=4
jedno w przód [7,6]=4 → [7,2]=4
pięć wstecz [7,2]=2 → [7,8]=2 → [9,9]=2 →
[9,9]=4 → [9,6]=4 → [7,6]=4
Czyli węzeł [7,6]=4 spełnia warunek wariantu 2-ego zatem usuwamy z komórki [7,4] wszystkie wartości oprócz wartości "4",
w naszym przypadku usuwamy wartości "3", "6" i "9".
|
Wariant 3a. Pętla otwarta o parzystej liczbie węzłów, pierwszy i ostatni węzeł leżą
w różnych sektorach (wiersz/kolumna/blok 3x3) ale ma tą samą wartość 'nVal'.
Na diagramie mamy pętlę o 8-miu węzłach:
[1,4]=3 → [3,4]=3 ⇒ [3,4]=9 → [7,4]=9
⇒ [7,4]=2 → [7,2]=2 → [4,2]=2
→ [4,3]=3
Usuwamy kandydatów o wartości 'nVal' z wszystkich pozycji, które należą jednocześnie do sektorów pierwszego i ostatniego węzła
i nie należą do pętli AIC. W naszym przypadku usuwamy wartość "3" z pozycji [1,2].
|
Wariant 3b. Pętla otwarta o parzystej liczbie węzłów, pierwszy i ostatni węzeł
leżą w tym samym sektorze (wiersz/kolumna/blok 3x3) ale mają różne wartości.
Na diagramie mamy pętlę o 6-ciu węzłach:
[2,1]=7 → [6,1]=7 ⇒ [6,1]=6 → [6,7]=6
→ [2,7]=6 → [2,7]=8
Niech 'nVF' wartość pierwszego wezła, a 'nVL' ostatniego, wówczas usuwamy pierwszej pozycji pętli wartość 'nVL', a z ostatniej
wartość 'nVF', o ile wartości te nie należą do pętli AIC.
W naszym przypadku usuwamy wartość "8" z pozycji [2,1].
|
Zgrupowany Naprzemienny Łańcuch Wnioskowania (Grouped AIC)
połaczenie mocne występuje wtedy, gdy:
- W danej komórce występują dwie wartości (między dwoma różnymi wartościami)
- w danym sektorze (wiersz/kolumna/blok 3x3) pewna wartość "nVal" należy dokładnie do dwóch wierszy, kolumn lub bloków 3x3 chociaż
pozycji w danym sektorze, w których występuje wartość "nVal" może być więcej niż dwie, jeśli tak jest, to połączenie takie nazywamy
zgrupowanym mocnym połączeniem (między dwoma grupami pozycji).
Przykładowy blok 3x3 o początku w punkcie [7,1] i końcu w punkcie [9,3] ma wartość 8
na trzech pozycjach, ale ponieważ wszystkie te pozycje zawierające kandydata 8 występują w dwóch kolumnach 1-szej
i 3-ciej to możemy powiedzieć, że między pozycjami [7,1] a [8,3] i [9,3] jest połączenie mocne. Zapisujemy to
[7,1] → [8,3],[9,3]. Zauważmy, że pozycje [8,3] i [9,3] są zgrupowane i traktujemy
je jak jedną pozycję! Stąd nazwa algorytmu Grupowe X-Cykle, czyli jest to algorytm AIC rozszerzony o
zgrupowane mocne połączenia. Zauważmy, że między pozycjami [7,1] i [8,3] dla wartości 8
jest połączenie słabe w tym bloku bo pozostaje jeszcze nieuwzględniona pozycja [9,3]. Tak samo jest z połączeniem między
pozycjami [7,1] i [9,3] dla wartości 8 (nieuwzględniona pozycja [8,3]).
|
połaczenie słabe występuje wtedy, gdy:
- W danej komórce występują więcej niż dwie wartości (między dwoma różnymi wartościami)
- w danym sektorze połączenie między pozycjami lub grupami pozycji o wartości "nVal" jest słabe jeśli istnieją pozycje w tym
sektorze o wartości "nVal", które nie zostały ujęte w tym połączeniu, zobacz powyższy przykład (między pozycjami dla wartości
"nVal").
Wariant 1. Pętla zamknięta o Parzystej liczbie węzłów
Przykładowa pętla na diagramie obok o 10-ciu węzłach:
[4,2]=1 → [7,2]=1 → [7,7]=1,[7,9]=1 →
[9,9]=1 ⇒ [9,9]=2 → [9,5]=2 ⇒
[7,4]=2,[8,4]=2 → [6,4]=2 ⇒ [6,4]=1
→ [6,3]=1 ⇒ [4,2]=1
Pozycje [7,7]=1,[7,9]=1 oraz [7,4]=2,[8,4]=2 są zgrupowane.
Usuwamy kandydatów w następujący sposób:
- jeśli dwa kolejne węzły pętli leżą w tej samej pozycji, to usuwamy z tej pozycji wszystkie wartości oprócz wartości należących
do tych węzłów pętli.
- jeśli dwa kolejne węzły pętli leżą w tym samym sektorze (wiersz/kolumna/blok 3x3), czyli mają tą wartość 'nVal' to usuwamy
tą wartość ze wszystkich pozycji sektora, do którego należą te dwa węzły oprócz pozycji wezłów pętli.
W naszym przypadku:
- dwa kolejne węzły leżą w tej samej komórce (pozycja [6,4] usuwamy wartości "3" i "8", pozycja [9,9] usuwamy wartość "3")
- dwa kolejne węzły leżą w tym samym sektorze (węzły [4,2]=1 i [6,3]=1 leżą w tym samym bloku: usuwamy wartość "1" z pozycji [4,3]
i [5,3] oraz węzły [7,4]=2,[8,4]=2 i [9,5]=2 leżą w tym samym bloku: usuwamy wartość "2" z pozycji [7,5] i [7,6]).
|
Wariant 2. Pętla zamknięta o Nieparzystej liczbie węzłów
Na diagramie mamy pętlę o 9-ciu węzłach:
[5,4]=8 → [1,4]=8 ⇒ [1,8]=8 →
[1,8]=4 ⇒ [5,8]=4,[6,8]=4 → [5,9]=4 →
[5,9]=2 → [5,5]=2 ⇒ [5,5]=8 → [5,4]=8
Pozycje [5,8]=4,[6,8]=4 są zgrupowane.
Szukamy takiego węzła pętli, który ma mocne połączenie z poprzednim i następnym węzłem pętli oraz liczba kolejnych mocnych
połączeń (aż do słabego połączenia) zarówno od tego węzła wstecz jak i do przodu jest nieparzysta, wówczas usuwamy wszystkie
wartości z tej pozycji węzła oprócz wartości, która należy do tego węzła.
W naszym przypadku usuwamy wartości "3" i "5" z pozycji [5,4].
|
Wariant 3a. Pętla otwarta o parzystej liczbie węzłów, pierwszy i ostatni węzeł leżą
w różnych sektorach (wiersz/kolumna/blok 3x3) ale ma tą samą wartość 'nVal'.
Na diagramie mamy pętlę o 6-ciu węzłach:
[2,5]=4 → [2,5]=1 ⇒ [2,8]=1 →
[8,8]=1,[9,8]=1 ⇒ [9,9]=1 → [9,9]=4
Pozycje [8,8]=1,[9,8]=1 są zgrupowane.
Usuwamy kandydatów o wartości 'nVal' z wszystkich pozycji, które należą jednocześnie do sektorów pierwszego i ostatniego węzła
i nie należą do pętli AIC. W naszym przypadku usuwamy wartość "4" z pozycji [9,5].
|
Wariant 3b. Pętla otwarta o parzystej liczbie węzłów, pierwszy i ostatni węzeł
leżą w tym samym sektorze (wiersz/kolumna/blok 3x3) ale mają różne wartości.
Na diagramie mamy pętlę o 6-ciu węzłach:
[2,6]=3 → [2,6]=8 ⇒ [1,5]=8 → [1,5]=9
→ [1,8]=9,[1,9]=9 → [2,8]=9 ⇒ [2,8]=6
→ [2,7]=6
Pozycje [1,8]=9,[1,9]=9 są zgrupowane.
Niech 'nVF' wartość pierwszego wezła, a 'nVL' ostatniego, wówczas usuwamy pierwszej pozycji pętli wartość 'nVL', a z ostatniej
wartość 'nVF', o ile wartości te nie należą do pętli AIC.
W naszym przypadku usuwamy wartość "3" z pozycji [2,7].
|
Naprzemienny Łańcuch Wnioskowania połączony z ALS
|