Heuristics: A*-algorithm 2: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
Thau (Diskussion | Beiträge) (Example am Anfang entfernt (Redundant)) |
Thau (Diskussion | Beiträge) (→A*-Algorithm) |
||
Zeile 1: | Zeile 1: | ||
− | == | + | =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. | 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). | + | 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 (<math>h(i) = 0</math>). |
− | How it works | + | ==How it works== |
− | Before you start you need the following | + | ===Before you start you need the following=== |
:*Your problem space modelled as a graph. Every node i of the graph has the following attribtues: | :*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 | :**g: the cost from root node of the graph to the the current node | ||
Zeile 18: | Zeile 14: | ||
:**„OPEN list“ | :**„OPEN list“ | ||
:**„CLOSED list“ | :**„CLOSED list“ | ||
− | + | ===Procedure=== | |
− | + | # Put the start node on the OPEN list | |
− | + | # If the OPEN list is empty then there is no result | |
− | + | # Choose the node i with minimal f from the OPEN list. Delete i from the and put in on the CLOSED list | |
− | + | # 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. | |
− | + | # Otherwise, expand i. Create all successors of i with i as parent node. For each sucessor i': | |
− | + | ## If i' is not yet given in the OPEN or CLOSED list, evalute <math>f(i') = g(i')+h(i')</math>. Add i' to the OPEN list. | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | ## If i' is not yet given in the OPEN or CLOSED list, evalute f(i') | + | |
## 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') | ## 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') | ||
## 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. | ## 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. | ||
+ | # Go back to (2) | ||
+ | ===Optimistic Heuristic=== | ||
+ | If your heuristical value for h' is always better than the real value h (h'(i) <math>\leq</math> 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 besides that 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 better!''' | ||
− | + | <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> | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | <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| | + | [[Datei:0Iteration.jpg|540px|]] |
− | OPEN | + | OPEN = {} |
+ | CLOSED = {} | ||
− | + | ==1st Iteration== | |
*Calculate g, h and f for the start node B2 | *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) | **g = 0 (there is no node before the start node, so the way from start to B2 is 0) | ||
Zeile 61: | Zeile 49: | ||
*Delete i from the and put in on the CLOSED list: OPEN = {} | CLOSED = {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': | *'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') | + | **A1,A2,A3,B1,B3,C1,C2,C3: If i' is not yet given in the OPEN or CLOSED list, evalute <math>f(i') = g(i')+h(i')</math>. Add i' to the OPEN list |
+ | [[Datei:1Iteration.jpg|800px|]] | ||
− | + | 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 | *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} | *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': | *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') | + | **A4,B4,C4: If i' is not yet given in the OPEN or CLOSED list, evalute <math>f(i') = g(i')+h(i')</math>. 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. | **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. | ||
− | [[Datei:2Iteration.jpg| | + | [[Datei:2Iteration.jpg|540px|]] |
− | OPEN = {A1,A2,A3,A4,B1,B4,C1,C2,C3,C4 | + | OPEN = {A1,A2,A3,A4,B1,B4,C1,C2,C3,C4} |
+ | CLOSED = {B2,B3} | ||
− | + | ==3rd Iteration== | |
i = C2 | 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. | 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| | + | [[Datei:3Iteration.jpg|540px|]] |
+ | |||
+ | 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} | |
− | OPEN = {A4,B4,C4,D1,D2 | + | |
+ | CLOSED = {A1,A2,A3,B1,B2,B3,C1,C2,C3} | ||
− | + | ==4th Iteration== | |
i = B4 | i = B4 | ||
− | [[Datei:4Iteration.jpg| | + | [[Datei:4Iteration.jpg|540px|]] |
− | OPEN = {A4,A5,C4,D1,D2 | + | OPEN = {A4,A5,C4,D1,D2} |
+ | CLOSED = {A1,A2,A3,B1,B2,B3,B4,C1,C2,C3} | ||
− | + | ==5th Iteration== | |
i = D2 | i = D2 | ||
− | [[Datei:5Iteration.jpg| | + | [[Datei:5Iteration.jpg|540px|]] |
− | OPEN = {A4,A5,C4,D1,E1,E2 | + | 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 | i = A4,C4,D1 | ||
− | OPEN = {A5,E1,E2 | + | OPEN = {A5,E1,E2} |
+ | CLOSED = {A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2} | ||
− | + | ==6th Iteration== | |
i = E2 | i = E2 | ||
− | [[Datei:6Iteration.jpg| | + | [[Datei:6Iteration.jpg|540px|]] |
− | OPEN = {A5,E1,F1,F2,F3 | + | 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 | i = A5 | ||
Zeile 137: | Zeile 135: | ||
[[Datei:7Iteration.jpg|800px|]] | [[Datei:7Iteration.jpg|800px|]] | ||
− | OPEN = {A6,B6,E1,F1,F2,F3 | + | 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 | i = E1 | ||
− | OPEN = {A6,B6,F1,F2,F3 | + | 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 | i = F2 | ||
− | [[Datei:8Iteration.jpg| | + | [[Datei:8Iteration.jpg|540px|]] |
− | OPEN = {A6,B6,F1,F3,G1,G2,G3 | + | 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 | i = A6 | ||
− | [[Datei:9Iteration.jpg| | + | [[Datei:9Iteration.jpg|540px|]] |
− | OPEN = {A7,B6,B7,F1,F3,G1,G2,G3 | + | 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 | i = F3 | ||
− | [[Datei:10Iteration.jpg| | + | [[Datei:10Iteration.jpg|540px|]] |
− | OPEN = {A7,B6,B7,E4,F1,F4,G1,G2,G3,G4 | + | 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} | ||
− | + | ==Iterations without Results== | |
i = F1 | i = F1 | ||
− | OPEN = {A7,B6,B7,E4,F4,G1,G2,G3,G4 | + | 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 | i = B6 | ||
− | [[Datei:11Iteration.jpg| | + | [[Datei:11Iteration.jpg|540px|]] |
− | OPEN = {A7,B7,C6,C7,E4,F4,G1,G2,G3,G4 | + | 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 | i = G2 | ||
− | OPEN = {A7,B7,C6,C7,E4,F4,G1,G3,G4 | + | 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 | i = F4 | ||
− | [[Datei:12Iteration.jpg| | + | [[Datei:12Iteration.jpg|540px|]] |
− | OPEN = {A7,B7,C6,C7,E4,E5,F5,G1,G3,G4,G5 | + | 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 | i = A7 | ||
Zeile 209: | Zeile 216: | ||
[[Datei:13Iteration.jpg|800px|]] | [[Datei:13Iteration.jpg|800px|]] | ||
− | OPEN = {A8,B7,B8,C6,C7,E4,E5,F5,G1,G3,G4,G5 | + | 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} | ||
− | + | ==Iterations without Results== | |
i = G3,G1 | i = G3,G1 | ||
− | OPEN = {A8,B7,B8,C6,C7,E4,E5,F5,G4,G5 | + | 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 | i = C6 | ||
− | [[Datei:14Iteration.jpg| | + | [[Datei:14Iteration.jpg|540px|]] |
− | OPEN = {A8,B7,B8,C7,D6,E4,E5,F5,G4,G5 | + | 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: | + | Note: A path wich only misses one step to the target was found, but the algorithm only stops when the target is i. |
i = B7 | i = B7 | ||
[[Datei:15Iteration.jpg|800px|]] | [[Datei:15Iteration.jpg|800px|]] | ||
− | OPEN = {A8,B7,B8,C7,C8,D6,E4,E5,F5,G4,G5 | + | 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 | 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 | i = B7 | ||
Zeile 249: | Zeile 262: | ||
[[Datei:16Iteration.jpg|800px|]] | [[Datei:16Iteration.jpg|800px|]] | ||
− | OPEN = {A8,B8,C8,D6,D8,E5,F5,G5 | + | 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 | i = F5 | ||
Zeile 258: | Zeile 272: | ||
[[Datei:17Iteration.jpg|800px|]] | [[Datei:17Iteration.jpg|800px|]] | ||
− | OPEN = {A8,B8,C8,D6,D8,E5,E6,F6,G5,G6 | + | 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 | 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 | i = D6 | ||
Zeile 273: | Zeile 290: | ||
[[Datei:18Iteration.jpg|800px|]] | [[Datei:18Iteration.jpg|800px|]] | ||
− | OPEN = {B8,C8,D8,E5,E6,E7,F6,G5,G6 | + | 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} | ||
− | + | ==Iterations without Results== | |
i = E5,G5,B8,C8 | 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 | i = F6 | ||
Zeile 288: | Zeile 308: | ||
[[Datei:19Iteration.jpg|800px|]] | [[Datei:19Iteration.jpg|800px|]] | ||
− | OPEN = {D8,E6,E7,F7,G6 | + | 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 | i = F6 | ||
Zeile 297: | Zeile 318: | ||
[[Datei:20Iteration.jpg|800px|]] | [[Datei:20Iteration.jpg|800px|]] | ||
− | OPEN = {E6,E7,F7,G6 | + | 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 | 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 | i = G6 | ||
Zeile 312: | Zeile 336: | ||
[[Datei:21Iteration.jpg|800px|]] | [[Datei:21Iteration.jpg|800px|]] | ||
− | OPEN = {E7,F7 | + | 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 | i = E7 | ||
Zeile 324: | Zeile 349: | ||
*Total cost is g(target node) = 82 | *Total cost is g(target node) = 82 | ||
− | + | =Sources for further study= | |
− | + | ||
− | + | ||
:1. OR-Script 2013 (Heuristics.26 ff) | :1. OR-Script 2013 (Heuristics.26 ff) | ||
:2. Wikipedia (En): A*-Algorithmus: http://en.wikipedia.org/wiki/A*_search_algorithm | :2. Wikipedia (En): A*-Algorithmus: http://en.wikipedia.org/wiki/A*_search_algorithm |
Version vom 23. Juni 2013, 18:36 Uhr
Inhaltsverzeichnis
- 1 Theory
- 2 Example
- 2.1 1st Iteration
- 2.2 2nd Iteration
- 2.3 3rd Iteration
- 2.4 Iterations without Results
- 2.5 4th Iteration
- 2.6 5th Iteration
- 2.7 Iterations without Results
- 2.8 6th Iteration
- 2.9 7th Iteration
- 2.10 Iterations without Results
- 2.11 8th Iteration
- 2.12 9th Iteration
- 2.13 10th Iteration
- 2.14 Iterations without Results
- 2.15 11th Iteration
- 2.16 Iterations without Results
- 2.17 12th Iteration
- 2.18 13th Iteration
- 2.19 Iterations without Results
- 2.20 14th Iteration
- 2.21 15th Iteration
- 2.22 Iterations without Results
- 2.23 16th Iteration
- 2.24 17th Iteration
- 2.25 Iterations without Results
- 2.26 18th Iteration
- 2.27 Iterations without Results
- 2.28 19th Iteration
- 2.29 20th Iteration
- 2.30 Iterations without Results
- 2.31 21th Iteration
- 2.32 22th Iteration
- 3 Sources for further study
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 ().
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“
- Your problem space modelled as a graph. Every node i of the graph has the following attribtues:
Procedure
- Put the start node on the OPEN list
- If the OPEN list is empty then there is no result
- Choose the node i with minimal f from the OPEN list. Delete i from the and put in on the CLOSED list
- 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.
- Otherwise, expand i. Create all successors of i with i as parent node. For each sucessor i':
- If i' is not yet given in the OPEN or CLOSED list, evalute . Add i' to the OPEN list.
- 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')
- 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.
- Go back to (2)
Optimistic Heuristic
If your heuristical value for h' is always better than the real value h (h'(i) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \leq
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 besides that 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 better!
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 . 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 . 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}
Iterations 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}
Iterations 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: A path wich only misses one step to the target was found, 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}
Iterations 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 for further study
- 1. OR-Script 2013 (Heuristics.26 ff)
- 2. Wikipedia (En): A*-Algorithmus: http://en.wikipedia.org/wiki/A*_search_algorithm