Heuristics: A*-algorithm 2: Unterschied zwischen den Versionen

[unmarkierte Version]

Version vom 19. Juni 2013, 15:00 Uhr

Example: Imagine a navigation device, just simpler: You have a two-dimensional grid (internal represented by a graph were every box is connected if there is no obstacle inbetween) and want to know the shortest path between A (start) and B (target). Cost for moving horicontally and vertically in this example are 10 and moving diagonal costs 14 (Pythagorean theorem). Between the start node and the target node are some obstacles placed (dark box). As a heuristic the airline will be used.

A*-Algorithm

Theory

The A*-Algorithm is an algorithm to find the shortest path between two nodes in a graph. It can be used for any problem wich can be modeled as a graph, e.g. the navigation of a car or computer-enemies in a video game and it is able to find the optimal solution if there is any. It utilizes a heuristical method to calculate the expected total cost through the problem space per node and by this the next node between root node (or start node) and target node (or leaf node) to have a look at.

It may be easier to understand the background of the algorithm if one is aware of the fact that the Dijkstra-Algorithm is a special case of the A*-Algorithm without a heuristic (h(i) = 0).

How it works Before you start you need the following:

Your problem space modelled as a graph. Every node i of the graph has the following attribtues:
- g: the cost from root node of the graph to the the current node
- h: the cost from the node i to the target node. If these costs are unknown an estimator h' is used as h (calculated by the heuristic, e.g. the euclidean distance or the length of the minimal spanning tree + the length of the two shortest :connection )
- f: g(i) + h(i)
- parent node (root node has none)
Also the following lists are neaded:
- „OPEN list“
- „CLOSED list“

1. Put the start node on the OPEN list

2. If the OPEN list is empty then there is no result

3. Choose the node i with minimal f from the OPEN list. Delete i from the and put in on the CLOSED list

4. If i is a target node, A* ends successfully. To look up the optimal path one has to go from the target node back to the root node via the parent-attribute.

5. Otherwise, expand i. Create all successors of i with i as parent node. For each sucessor i':

1. If i' is not yet given in the OPEN or CLOSED list, evalute f(i') (= g(i')+h(i')). Add i' to the OPEN list.
2. If i' is already given in the OPEN or CLOSED list, the pointer must be revised along the path, in order to get the minimum g(i')
3. If i' is on the CLOSED list and the pointers were modified, reopen i', i.e. Remove it from thje CLOSED list and put it back on the OPEN list.

6. Go back to (2)

If your heuristical value for h' is always better than the real value h (h'(i) <= h(i) for every i) (wich means your heuristic is optimistic) the A*-Algorithm found the best way through the problem-space as it will never overlook a better path throughout the search.

Example

Imagine a navigation device, just simpler: You have a two-dimensional grid (internal represented by a graph were every box is connected if there is no obstacle inbetween) and you want to know the shortest path between X (B2) (start) and Y (E7) (target). Cost for moving horicontally and vertically in this example are 10 and moving diagonal costs 14 (Pythagorean theorem). Between the start node and the target node are some obstacles placed (dark box). As a heuristic the airline will be used with costs of 1 per box. This is quiet a bad estimator because the costs are so low they are nearly of no consequences, but we get more Iterations wich is a good thing in order to understand how A* works, If you want a good estimator choosing costs of 10 per box would be sufficient.

g h f parent obstacle

OPEN = {} | CLOSED = {}

1st Iteration

Calculate g, h and f for the start node B2
- g = 0 (there is no node before the start node, so the way from start to B2 is 0)
- h = h' = 5 (B2 → C3 → D4 → E5 → E6 → E7)
- f = g + h = 5
Put the start node on the OPEN list: OPEN = {B2} | CLOSED = {}
Choose the node i with minimal f from the OPEN list: i = B2
Delete i from the and put in on the CLOSED list: OPEN = {} | CLOSED = {B2}
'Expand i. Create all successors of i with i as parent node. For each sucessor i':
- A1,A2,A3,B1,B3,C1,C2,C3: If i' is not yet given in the OPEN or CLOSED list, evalute f(i') (= g(i')+h(i')). Add i' to the OPEN list

OPEN = {A1,A2,A3,B1,B3,C1,C2,C3} | CLOSED = {B2}

2nd Iteration

Choose the node i with minimal f from the OPEN list: i = B3
Delete i from the and put in on the CLOSED list: OPEN = {A1,A2,A3,B1,C1,C2,C3} | CLOSED = {B2,B3}
Expand i. Create all successors of i with i as parent node. For each sucessor i':
- A4,B4,C4: If i' is not yet given in the OPEN or CLOSED list, evalute f(i') (= g(i')+h(i')). Add i' to the OPEN list
- Note: There is no need to change the path to A3/C3/A2/C2 as the way would be longer than now. For example [A2 → A3 → C3] has costs of 20 while they are at the moment 14, wich is better.

OPEN = {A1,A2,A3,A4,B1,B4,C1,C2,C3,C4} | CLOSED = {B2,B3}

3rd Iteration

i = C2 Note: As there is no connection between C2 and D3 in the graph based on the grid because D3 is a roadblock or something you can ignore D3.

OPEN = {A1,A2,A3,A4,B1,B4,C1,C3,C4,D1,D2} | CLOSED = {B2,B3,C2}

Iterations without Results

For every of the following nodes you may start an iteration without a change of the grid: i = A1, A2, A3, B1, C1, C3 OPEN = {A4,B4,C4,D1,D2} | CLOSED = {A1,A2,A3,B1,B2,B3,C1,C2,C3}

4th Iteration

i = B4

OPEN = {A4,A5,C4,D1,D2} | CLOSED = {A1,A2,A3,B1,B2,B3,B4,C1,C2,C3}

5th Iteration

i = D2

OPEN = {A4,A5,C4,D1,E1,E2} | CLOSED = {A1,A2,A3,B1,B2,B3,B4,C1,C2,C3,D2}

Iterations without Results

i = A4,C4,D1 OPEN = {A5,E1,E2} | CLOSED = {A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2}

6th Iteration

i = E2

OPEN = {A5,E1,F1,F2,F3} | CLOSED = {A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E2}

7th Iteration

i = A5

OPEN = {A6,B6,E1,F1,F2,F3} | CLOSED = {A1,A2,A3,A4,A5,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E2}

Iterations without Results

i = E1 OPEN = {A6,B6,F1,F2,F3} | CLOSED = {A1,A2,A3,A4,A5,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2}

8th Iteration

i = F2

OPEN = {A6,B6,F1,F3,G1,G2,G3} | CLOSED = {A1,A2,A3,A4,A5,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2,F2}

9th Iteration

i = A6

OPEN = {A7,B6,B7,F1,F3,G1,G2,G3} | CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2,F2}

10th Iteration

i = F3

OPEN = {A7,B6,B7,E4,F1,F4,G1,G2,G3,G4} | CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2,F2,F3}

terations without Results

i = F1 OPEN = {A7,B6,B7,E4,F4,G1,G2,G3,G4} | CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3}

11th Iteration

i = B6

OPEN = {A7,B7,C6,C7,E4,F4,G1,G2,G3,G4} | CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3}

Iterations without Results

i = G2 OPEN = {A7,B7,C6,C7,E4,F4,G1,G3,G4} | CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3,G2}

12th Iteration

i = F4

OPEN = {A7,B7,C6,C7,E4,E5,F5,G1,G3,G4,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3,F4,G2}

13th Iteration

i = A7

OPEN = {A8,B7,B8,C6,C7,E4,E5,F5,G1,G3,G4,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3,F4,G2}

terations without Results

i = G3,G1 OPEN = {A8,B7,B8,C6,C7,E4,E5,F5,G4,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3,F4,G1,G2,G3}

14th Iteration

i = C6

OPEN = {A8,B7,B8,C7,D6,E4,E5,F5,G4,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,C1,C2,C3,C4,C6,D1,D2,E1,E2,F1,F2,F3,F4,G1,G2,G3}

15th Iteration

Note: You may found a path wich only misses one step to the target but the algorithm only stops when the target is i. i = B7

OPEN = {A8,B7,B8,C7,C8,D6,E4,E5,F5,G4,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,C1,C2,C3,C4,C6,D1,D2,E1,E2,F1,F2,F3,F4,G1,G2,G3}

Iterations without Results

i = E4,G4,B7 OPEN = {A8,B8,C7,C8,D6,E5,F5,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,D1,D2,E1,E2,E4,F1,F2,F3,F4,G1,G2,G3,G4}

16th Iteration

i = B7

OPEN = {A8,B8,C8,D6,D8,E5,F5,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,C7,D1,D2,E1,E2,E4,F1,F2,F3,F4,G1,G2,G3,G4}

17th Iteration

i = F5

OPEN = {A8,B8,C8,D6,D8,E5,E6,F6,G5,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,C7,D1,D2,E1,E2,E4,F1,F2,F3,F4,F5,G1,G2,G3,G4}

Iterations without Results

i = A8 OPEN = {B8,C8,D6,D8,E5,E6,F6,G5,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,C7,D1,D2,E1,E2,E4,F1,F2,F3,F4,F5,G1,G2,G3,G4}

18th Iteration

i = D6

OPEN = {B8,C8,D8,E5,E6,E7,F6,G5,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,C7,D1,D2,D6,E1,E2,E4,F1,F2,F3,F4,F5,G1,G2,G3,G4}

terations without Results

i = E5,G5,B8,C8 OPEN = {D8,E6,E7,F6,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,E1,E2,E4,E5,F1,F2,F3,F4,F5,G1,G2,G3,G4,G5}

19th Iteration

i = F6

OPEN = {D8,E6,E7,F7,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,E1,E2,E4,E5,F1,F2,F3,F4,F5,F6,G1,G2,G3,G4,G5}

20th Iteration

i = F6

OPEN = {E6,E7,F7,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,D8,E1,E2,E4,E5,F1,F2,F3,F4,F5,F6,G1,G2,G3,G4,G5}

Iterations without Results

i = E6 OPEN = {E7,F7,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,D8,E1,E2,E4,E5,E6,F1,F2,F3,F4,F5,F6,G1,G2,G3,G4,G5}

21th Iteration

i = G6

OPEN = {E7,F7} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,D8,E1,E2,E4,E5,E6,F1,F2,F3,F4,F5,F6,G1,G2,G3,G4,G5,G6}

22th Iteration

i = E7

This is the target node, so A* ends successfully.
To recover the path we start at the target node and go from there to every parent node on our path until there is none (wich means we are at the start node):
E7 → D6 → C6 → B6 → A5 → B4 → B3 → B2
Total cost is g(target node) = 82

Sources

1. OR-Script 2013 (Heuristics.26 ff)

2. Wikipedia (En): A*-Algorithmus: http://en.wikipedia.org/wiki/A*_search_algorithm

Heuristics: A*-algorithm 2: Unterschied zwischen den Versionen

Version vom 19. Juni 2013, 15:00 Uhr

A*-Algorithm

Navigationsmenü

Ansichten

Meine Werkzeuge

Navigation

Suche

Werkzeuge

@@ Zeile 51: / Zeile 51: @@
 <span style="background-color:#00FF00"> g</span> <span style="background-color:#FFFF00"> h</span> <span style="background-color:#00FFFF"> f </span> <span style="background-color:#FF00FF"> parent </span> <span style="background:#000000; color:#808080"> obstacle</span>
+[[Datei:0Iteration.jpg|800px|]]
-A
+OPEN = {} | CLOSED = {}
-B
-X
-C
-D
-E
-Y
-F
-G
-OPEN = {} | CLOSED = {}
 <u>1st Iteration</u>
@@ Zeile 136: / Zeile 68: @@
+[[Datei:1Iteration.jpg|1200px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
+OPEN = {A1,A2,A3,B1,B3,C1,C2,C3} | CLOSED = {B2}
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-C
-6 16 B2
-5 15 B2
-4 18 B2
-D
-E
-Y
-F
-G
-OPEN = {A1,A2,A3,B1,B3,C1,C2,C3} | CLOSED = {B2}
 <u>2nd Iteration</u>
@@ Zeile 217: / Zeile 81: @@
+[[Datei:2Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
+OPEN = {A1,A2,A3,A4,B1,B4,C1,C2,C3,C4} | CLOSED = {B2,B3}
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-D
-E
-Y
-F
-G
-OPEN = {A1,A2,A3,A4,B1,B4,C1,C2,C3,C4} | CLOSED = {B2,B3}
 <u>3rd Iteration</u>
@@ Zeile 295: / Zeile 91: @@
 Note: As there is no connection between C2 and D3 in the graph based on the grid because D3 is a roadblock or something you can ignore D3.
+[[Datei:3Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
+OPEN = {A1,A2,A3,A4,B1,B4,C1,C3,C4,D1,D2} | CLOSED = {B2,B3,C2}
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-D
-6 30 C2
-5 25 C2
-E
-Y
-F
-G
-OPEN = {A1,A2,A3,A4,B1,B4,C1,C3,C4,D1,D2} | CLOSED = {B2,B3,C2}
 <u>Iterations without Results</u>
@@ Zeile 372: / Zeile 100: @@
 For every of the following nodes you may start an iteration without a change of the grid: i = A1, A2, A3, B1, C1, C3
 OPEN = {A4,B4,C4,D1,D2} | CLOSED = {A1,A2,A3,B1,B2,B3,C1,C2,C3}
 <u>4th Iteration</u>
@@ Zeile 377: / Zeile 106: @@
 i = B4
+[[Datei:4Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
+OPEN = {A4,A5,C4,D1,D2} | CLOSED = {A1,A2,A3,B1,B2,B3,B4,C1,C2,C3}
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-D
-6 30 C2
-5 25 C2
-E
-Y
-F
-G
-OPEN = {A4,A5,C4,D1,D2} | CLOSED = {A1,A2,A3,B1,B2,B3,B4,C1,C2,C3}
 <u>5th Iteration</u>
@@ Zeile 454: / Zeile 115: @@
 i = D2
+[[Datei:5Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
+OPEN = {A4,A5,C4,D1,E1,E2} | CLOSED = {A1,A2,A3,B1,B2,B3,B4,C1,C2,C3,D2}
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-D
-6 30 C2
-5 25 C2
-E
-6 40 D2
-5 35 D2
-Y
-F
-G
-OPEN = {A4,A5,C4,D1,E1,E2} | CLOSED = {A1,A2,A3,B1,B2,B3,B4,C1,C2,C3,D2}
 <u>Iterations without Results</u>
@@ Zeile 531: / Zeile 124: @@
 i = A4,C4,D1
 OPEN = {A5,E1,E2} | CLOSED = {A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2}
 <u>6th Iteration</u>
@@ Zeile 536: / Zeile 130: @@
 i = E2
+[[Datei:6Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
+OPEN = {A5,E1,F1,F2,F3} | CLOSED = {A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E2}
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-D
-6 30 C2
-5 25 C2
-E
-6 40 D2
-5 35 D2
-Y
-F
-6 50 E2
-5 45 E2
-4 48 E2
-G
-OPEN = {A5,E1,F1,F2,F3} | CLOSED = {A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E2}
 <u>7th Iteration</u>
@@ Zeile 613: / Zeile 139: @@
 i = A5
+[[Datei:7Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
-4 48 A5
+OPEN = {A6,B6,E1,F1,F2,F3} | CLOSED = {A1,A2,A3,A4,A5,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E2}
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-4 52 A5
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-D
-6 30 C2
-5 25 C2
-E
-6 40 D2
-5 35 D2
-Y
-F
-6 50 E2
-5 45 E2
-4 48 E2
-G
-OPEN = {A6,B6,E1,F1,F2,F3} | CLOSED = {A1,A2,A3,A4,A5,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E2}
 <u>Iterations without Results</u>
@@ Zeile 690: / Zeile 148: @@
 i = E1
 OPEN = {A6,B6,F1,F2,F3} | CLOSED = {A1,A2,A3,A4,A5,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2}
 <u>8th Iteration</u>
@@ Zeile 695: / Zeile 154: @@
 i = F2
+[[Datei:8Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
-4 48 A5
+OPEN = {A6,B6,F1,F3,G1,G2,G3} | CLOSED = {A1,A2,A3,A4,A5,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2,F2}
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-4 52 A5
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-D
-6 30 C2
-5 25 C2
-E
-6 40 D2
-5 35 D2
-Y
-F
-6 50 E2
-5 45 E2
-4 48 E2
-G
-6 60 F2
-5 55 F2
-4 58 F2
-OPEN = {A6,B6,F1,F3,G1,G2,G3} | CLOSED = {A1,A2,A3,A4,A5,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2,F2}
 <u>9th Iteration</u>
@@ Zeile 772: / Zeile 163: @@
 i = A6
+[[Datei:9Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
-4 48 A5
-4 58 A6
-B
+OPEN = {A7,B6,B7,F1,F3,G1,G2,G3} | CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2,F2}
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-4 52 A5
-3 61 A6
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-D
-6 30 C2
-5 25 C2
-E
-6 40 D2
-5 35 D2
-Y
-F
-6 50 E2
-5 45 E2
-4 48 E2
-G
-6 60 F2
-5 55 F2
-4 58 F2
-OPEN = {A7,B6,B7,F1,F3,G1,G2,G3} | CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2,F2}
 <u>10th Iteration</u>
@@ Zeile 849: / Zeile 172: @@
 i = F3
+[[Datei:10Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
-4 48 A5
-4 58 A6
-B
+OPEN = {A7,B6,B7,E4,F1,F4,G1,G2,G3,G4} | CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2,F2,F3}
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-4 52 A5
-3 61 A6
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-D
-6 30 C2
-5 25 C2
-E
-6 40 D2
-5 35 D2
-3 61 F3
-Y
-F
-6 50 E2
-5 45 E2
-4 48 E2
-3 57 F3
-G
-6 60 F2
-5 55 F2
-4 58 F2
-3 61 F3
-OPEN = {A7,B6,B7,E4,F1,F4,G1,G2,G3,G4} | CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2,F2,F3}
 <u>terations without Results</u>
@@ Zeile 926: / Zeile 181: @@
 i = F1
 OPEN = {A7,B6,B7,E4,F4,G1,G2,G3,G4} | CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3}
 <u>11th Iteration</u>
@@ Zeile 931: / Zeile 187: @@
 i = B6
+[[Datei:11Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
-4 48 A5
-4 58 A6
-B
+OPEN = {A7,B7,C6,C7,E4,F4,G1,G2,G3,G4} | CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3}
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-4 52 A5
-3 61 A6
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-2 60 B6
-2 64 B6
-D
-6 30 C2
-5 25 C2
-E
-6 40 D2
-5 35 D2
-3 61 F3
-Y
-F
-6 50 E2
-5 45 E2
-4 48 E2
-3 57 F3
-G
-6 60 F2
-5 55 F2
-4 58 F2
-3 61 F3
-OPEN = {A7,B7,C6,C7,E4,F4,G1,G2,G3,G4} | CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3}
 <u>Iterations without Results</u>
@@ Zeile 1.008: / Zeile 196: @@
 i = G2
 OPEN = {A7,B7,C6,C7,E4,F4,G1,G3,G4} | CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3,G2}
 <u>12th Iteration</u>
@@ Zeile 1.013: / Zeile 202: @@
 i = F4
+[[Datei:12Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
-4 48 A5
-4 58 A6
-B
+OPEN = {A7,B7,C6,C7,E4,E5,F5,G1,G3,G4,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3,F4,G2}
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-4 52 A5
-3 61 A6
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-2 60 B6
-2 64 B6
-D
-6 30 C2
-5 25 C2
-E
-6 40 D2
-5 35 D2
-3 61 F3
-2 70 F4
-Y
-F
-6 50 E2
-5 45 E2
-4 48 E2
-3 57 F3
-2 66 F4
-G
-6 60 F2
-5 55 F2
-4 58 F2
-3 61 F3
-2 70 F4
-OPEN = {A7,B7,C6,C7,E4,E5,F5,G1,G3,G4,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3,F4,G2}
 <u>13th Iteration</u>
@@ Zeile 1.090: / Zeile 211: @@
 i = A7
+[[Datei:13Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
-4 48 A5
-4 58 A6
-4 68 A7
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-4 52 A5
+OPEN = {A8,B7,B8,C6,C7,E4,E5,F5,G1,G3,G4,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3,F4,G2}
-3 61 A6
-3 71 A7
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-2 60 B6
-2 64 B6
-D
-6 30 C2
-5 25 C2
-E
-6 40 D2
-5 35 D2
-3 61 F3
-2 70 F4
-Y
-F
-6 50 E2
-5 45 E2
-4 48 E2
-3 57 F3
-2 66 F4
-G
-6 60 F2
-5 55 F2
-4 58 F2
-3 61 F3
-2 70 F4
-OPEN = {A8,B7,B8,C6,C7,E4,E5,F5,G1,G3,G4,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3,F4,G2}
 <u>terations without Results</u>
@@ Zeile 1.167: / Zeile 220: @@
 i = G3,G1
 OPEN = {A8,B7,B8,C6,C7,E4,E5,F5,G4,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,C1,C2,C3,C4,D1,D2,E1,E2,F1,F2,F3,F4,G1,G2,G3}
 <u>14th Iteration</u>
@@ Zeile 1.172: / Zeile 226: @@
 i = C6
+[[Datei:14Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
-4 48 A5
-4 58 A6
-4 68 A7
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-4 52 A5
+OPEN = {A8,B7,B8,C7,D6,E4,E5,F5,G4,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,C1,C2,C3,C4,C6,D1,D2,E1,E2,F1,F2,F3,F4,G1,G2,G3}
-3 61 A6
-3 71 A7
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-2 60 B6
-2 64 B6
-D
-6 30 C2
-5 25 C2
-1 69 C6
-E
-6 40 D2
-5 35 D2
-3 61 F3
-2 70 F4
-Y
-F
-6 50 E2
-5 45 E2
-4 48 E2
-3 57 F3
-2 66 F4
-G
-6 60 F2
-5 55 F2
-4 58 F2
-3 61 F3
-2 70 F4
-OPEN = {A8,B7,B8,C7,D6,E4,E5,F5,G4,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,C1,C2,C3,C4,C6,D1,D2,E1,E2,F1,F2,F3,F4,G1,G2,G3}
 <u>15th Iteration</u>
@@ Zeile 1.250: / Zeile 236: @@
 i = B7
+[[Datei:15Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
-4 48 A5
-4 58 A6
-4 68 A7
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-4 52 A5
+OPEN = {A8,B7,B8,C7,C8,D6,E4,E5,F5,G4,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,C1,C2,C3,C4,C6,D1,D2,E1,E2,F1,F2,F3,F4,G1,G2,G3}
-3 61 A6
-3 71 A7
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-2 60 B6
-2 64 B6
-2 74 B7
-D
-6 30 C2
-5 25 C2
-1 69 C6
-E
-6 40 D2
-5 35 D2
-3 61 F3
-2 70 F4
-Y
-F
-6 50 E2
-5 45 E2
-4 48 E2
-3 57 F3
-2 66 F4
-G
-6 60 F2
-5 55 F2
-4 58 F2
-3 61 F3
-2 70 F4
-OPEN = {A8,B7,B8,C7,C8,D6,E4,E5,F5,G4,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,C1,C2,C3,C4,C6,D1,D2,E1,E2,F1,F2,F3,F4,G1,G2,G3}
 <u>Iterations without Results</u>
@@ Zeile 1.327: / Zeile 245: @@
 i = E4,G4,B7
 OPEN = {A8,B8,C7,C8,D6,E5,F5,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,D1,D2,E1,E2,E4,F1,F2,F3,F4,G1,G2,G3,G4}
 <u>16th Iteration</u>
@@ Zeile 1.332: / Zeile 251: @@
 i = B7
+[[Datei:16Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
-4 48 A5
-4 58 A6
-4 68 A7
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-4 52 A5
+OPEN = {A8,B8,C8,D6,D8,E5,F5,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,C7,D1,D2,E1,E2,E4,F1,F2,F3,F4,G1,G2,G3,G4}
-3 61 A6
-3 71 A7
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-2 60 B6
-2 64 B6
-2 74 B7
-D
-6 30 C2
-5 25 C2
-1 69 C6
-1 77 C7
-E
-6 40 D2
-5 35 D2
-3 61 F3
-2 70 F4
-Y
-F
-6 50 E2
-5 45 E2
-4 48 E2
-3 57 F3
-2 66 F4
-G
-6 60 F2
-5 55 F2
-4 58 F2
-3 61 F3
-2 70 F4
-OPEN = {A8,B8,C8,D6,D8,E5,F5,G5} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,C7,D1,D2,E1,E2,E4,F1,F2,F3,F4,G1,G2,G3,G4}
 <u>17th Iteration</u>
@@ Zeile 1.409: / Zeile 260: @@
 i = F5
+[[Datei:17Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
-4 48 A5
-4 58 A6
-4 68 A7
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-4 52 A5
+OPEN = {A8,B8,C8,D6,D8,E5,E6,F6,G5,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,C7,D1,D2,E1,E2,E4,F1,F2,F3,F4,F5,G1,G2,G3,G4}
-3 61 A6
-3 71 A7
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-2 60 B6
-2 64 B6
-2 74 B7
-D
-6 30 C2
-5 25 C2
-1 69 C6
-1 77 C7
-E
-6 40 D2
-5 35 D2
-3 61 F3
-2 70 F4
-1 79 F5
-Y
-F
-6 50 E2
-5 45 E2
-4 48 E2
-3 57 F3
-2 66 F4
-1 75 F5
-G
-6 60 F2
-5 55 F2
-4 58 F2
-3 61 F3
-2 70 F4
-2 80 F5
-OPEN = {A8,B8,C8,D6,D8,E5,E6,F6,G5,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,C7,D1,D2,E1,E2,E4,F1,F2,F3,F4,F5,G1,G2,G3,G4}
 <u>Iterations without Results</u>
@@ Zeile 1.486: / Zeile 269: @@
 i = A8
 OPEN = {B8,C8,D6,D8,E5,E6,F6,G5,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,C7,D1,D2,E1,E2,E4,F1,F2,F3,F4,F5,G1,G2,G3,G4}
 <u>18th Iteration</u>
@@ Zeile 1.491: / Zeile 275: @@
 i = D6
+[[Datei:18Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
-4 48 A5
-4 58 A6
-4 68 A7
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-4 52 A5
+OPEN = {B8,C8,D8,E5,E6,E7,F6,G5,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,C7,D1,D2,D6,E1,E2,E4,F1,F2,F3,F4,F5,G1,G2,G3,G4}
-3 61 A6
-3 71 A7
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-2 60 B6
-2 64 B6
-2 74 B7
-D
-6 30 C2
-5 25 C2
-1 69 C6
-1 77 C7
-E
-6 40 D2
-5 35 D2
-3 61 F3
-2 70 F4
-1 79 F5
-Y 82 0 82 D6
-F
-6 50 E2
-5 45 E2
-4 48 E2
-3 57 F3
-2 66 F4
-1 75 F5
-G
-6 60 F2
-5 55 F2
-4 58 F2
-3 61 F3
-2 70 F4
-2 80 F5
-OPEN = {B8,C8,D8,E5,E6,E7,F6,G5,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,C1,C2,C3,C4,C6,C7,D1,D2,D6,E1,E2,E4,F1,F2,F3,F4,F5,G1,G2,G3,G4}
 <u>terations without Results</u>
@@ Zeile 1.568: / Zeile 284: @@
 i = E5,G5,B8,C8
 OPEN = {D8,E6,E7,F6,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,E1,E2,E4,E5,F1,F2,F3,F4,F5,G1,G2,G3,G4,G5}
 <u>19th Iteration</u>
@@ Zeile 1.573: / Zeile 290: @@
 i = F6
+[[Datei:19Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
-4 48 A5
-4 58 A6
-4 68 A7
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-4 52 A5
+OPEN = {D8,E6,E7,F7,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,E1,E2,E4,E5,F1,F2,F3,F4,F5,F6,G1,G2,G3,G4,G5}
-3 61 A6
-3 71 A7
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-2 60 B6
-2 64 B6
-2 74 B7
-D
-6 30 C2
-5 25 C2
-1 69 C6
-1 77 C7
-E
-6 40 D2
-5 35 D2
-3 61 F3
-2 70 F4
-1 79 F5
-Y 82 0 82 D6
-F
-6 50 E2
-5 45 E2
-4 48 E2
-3 57 F3
-2 66 F4
-1 75 F5
-1 85 F6
-G
-6 60 F2
-5 55 F2
-4 58 F2
-3 61 F3
-2 70 F4
-2 80 F5
-OPEN = {D8,E6,E7,F7,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,E1,E2,E4,E5,F1,F2,F3,F4,F5,F6,G1,G2,G3,G4,G5}
 <u>20th Iteration</u>
@@ Zeile 1.650: / Zeile 299: @@
 i = F6
+[[Datei:20Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
-4 48 A5
-4 58 A6
-4 68 A7
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-4 52 A5
+OPEN = {E6,E7,F7,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,D8,E1,E2,E4,E5,F1,F2,F3,F4,F5,F6,G1,G2,G3,G4,G5}
-3 61 A6
-3 71 A7
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-2 60 B6
-2 64 B6
-2 74 B7
-D
-6 30 C2
-5 25 C2
-1 69 C6
-1 77 C7
-E
-6 40 D2
-5 35 D2
-3 61 F3
-2 70 F4
-1 79 F5
-Y 82 0 82 D6
-1 87 D8
-F
-6 50 E2
-5 45 E2
-4 48 E2
-3 57 F3
-2 66 F4
-1 75 F5
-1 85 F6
-G
-6 60 F2
-5 55 F2
-4 58 F2
-3 61 F3
-2 70 F4
-2 80 F5
-OPEN = {E6,E7,F7,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,D8,E1,E2,E4,E5,F1,F2,F3,F4,F5,F6,G1,G2,G3,G4,G5}
 <u>Iterations without Results</u>
@@ Zeile 1.727: / Zeile 308: @@
 i = E6
 OPEN = {E7,F7,G6} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,D8,E1,E2,E4,E5,E6,F1,F2,F3,F4,F5,F6,G1,G2,G3,G4,G5}
 <u>21th Iteration</u>
@@ Zeile 1.732: / Zeile 314: @@
 i = G6
+[[Datei:21Iteration.jpg|800px|]]
-A
-6 20 B2
-5 15 B2
-4 18 B2
-4 28 B3
-4 38 B4
-4 48 A5
-4 58 A6
-4 68 A7
-B
-6 16 B2
-X 0 5 5
-4 14 B2
-3 23 B3
-4 52 A5
+OPEN = {E7,F7} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,D8,E1,E2,E4,E5,E6,F1,F2,F3,F4,F5,F6,G1,G2,G3,G4,G5,G6}
-3 61 A6
-3 71 A7
-C
-6 16 B2
-5 15 B2
-4 18 B2
-3 27 B3
-2 60 B6
-2 64 B6
-2 74 B7
-D
-6 30 C2
-5 25 C2
-1 69 C6
-1 77 C7
-E
-6 40 D2
-5 35 D2
-3 61 F3
-2 70 F4
-1 79 F5
-Y 82 0 82 D6
-1 87 D8
-F
-6 50 E2
-5 45 E2
-4 48 E2
-3 57 F3
-2 66 F4
-1 75 F5
-1 85 F6
-G
-6 60 F2
-5 55 F2
-4 58 F2
-3 61 F3
-2 70 F4
-2 80 F5
-2 90 G6
-OPEN = {E7,F7} | CLOSED = {A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,B4,B6,B7,B8,C1,C2,C3,C4,C6,C7,C8,D1,D2,D6,D8,E1,E2,E4,E5,E6,F1,F2,F3,F4,F5,F6,G1,G2,G3,G4,G5,G6}
 <u>22th Iteration</u>