KEMBAR78
A Star Algorithm | PDF | Graph Theory | Operations Research
Scribd
Upload
179 views27 pages

A Star Algorithm

The A* algorithm is used to find the shortest path between a starting node and goal node in a graph. It maintains a priority queue of paths ordered by cost + heuristic value. At each step, it removes the lowest cost path from the queue, generates its child paths, adds them to the queue, and removes any dominated paths. It continues until a goal path is found or the queue is empty, indicating no path exists. The example demonstrates running A* on a sample graph, explicitly showing the priority queue at each step.

Uploaded by

Sahil Sharma
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
179 views27 pages

A Star Algorithm

The A* algorithm is used to find the shortest path between a starting node and goal node in a graph. It maintains a priority queue of paths ordered by cost + heuristic value. At each step, it removes the lowest cost path from the queue, generates its child paths, adds them to the queue, and removes any dominated paths. It continues until a goal path is found or the queue is empty, indicating no path exists. The example demonstrates running A* on a sample graph, explicitly showing the priority queue at each step.

Uploaded by

Sahil Sharma
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 27

Exercises: Artificial Intelligence

A*
A*

A* ALGORITHM
A* Algorithm
• Input:
– QUEUE: Path only containing root
• Algorithm:
– WHILE (QUEUE not empty && first path not reach goal) DO
• Remove first path from QUEUE
• Create paths to all children
• Reject paths with loops
• Add paths and sort QUEUE (by f = cost + heuristic)
• IF QUEUE contains paths: P, Q
AND P ends in node Ni && Q contains node Ni
AND cost_P ≥ cost_Q
THEN remove P
– IF goal reached THEN success ELSE failure
A*

FIRST EXAMPLE ON A*
A* algorithm by Example
f = accumulated path cost + heuristic
0
7 S 7
QUEUE = path containing root

QUEUE: <S>

7 5

S C
1 1 6 5
9
9 12
10 A B G 0
A* algorithm by Example
f = accumulated path cost + heuristic
S Remove first path, Create paths to all
children, Reject loops and Add paths.
1 1
Sort QUEUE by f
10 A 11
9 B 10

QUEUE: <SB,SA>

7 5

S C
1 1 6 5
9
9 12
10 A B G 0
A* algorithm by Example
f = accumulated path cost + heuristic
S Remove first path, Create paths to all
children, Reject loops and Add paths.
1
Sort QUEUE by f
10 A 11 B
QUEUE: <SA,SBC,SBG,SBA>
10 7 13
10 A 20
5 C 12
0 G 13 7 5

S C
1 1 6 5
9
9 12
10 A B G 0
A* algorithm by Example
f = accumulated path cost + heuristic
S IF P terminating in I with cost_P &&
Q containing I with cost_Q AND
1
cost_P ≥ cost_Q THEN remove P
10 A 11 B
QUEUE: <SA,SBC,SBG,SBA>
10 7 13
10 A 20
5 C 12
0 G 13 7 5

S C
1 1 6 5
9
9 12
10 A B G 0
A* algorithm by Example
f = accumulated path cost + heuristic
S Remove first path, Create paths to all
children, Reject loops and Add paths.
Sort QUEUE by f
A B
QUEUE: <SBC,SBG,SAB>
10 7 13
9 B 19
5 C 12
0 G 13 7 5

S C
1 1 6 5
9
9 12
10 A B G 0
A* algorithm by Example
f = accumulated path cost + heuristic
S IF P terminating in I with cost_P &&
Q containing I with cost_Q AND
cost_P ≥ cost_Q THEN remove P
A B
QUEUE: <SBC,SBG,SAB>
10 7 13
9 B 19
5 C 12
0 G 13 7 5

S C
1 1 6 5
9
9 12
10 A B G 0
A* algorithm by Example
f = accumulated path cost + heuristic
S Remove first path, Create paths to all
children, Reject loops and Add paths.
Sort QUEUE by f
B
QUEUE: <SBCG,SBG>
13
C 0 G 13 7 5

S C
1 1 6 5
12 9
0 G 12 10 A 9
B 12
G 0
A* algorithm by Example
f = accumulated path cost + heuristic
S IF P terminating in I with cost_P &&
Q containing I with cost_Q AND
cost_P ≥ cost_Q THEN remove P
B
QUEUE: <SBCG,SBG>
13
C 0 G 13 7 5

S C
1 1 6 5
12 9
0 G 12 10 A 9
B 12
G 0
A* algorithm by Example
f = accumulated path cost + heuristic
S SUCCESS

B
QUEUE: <SBCG>

C 7 5

S C
1 1 6 5
12 9
0 G 12 10 A 9
B 12
G 0
A*

PROBLEM
Problem
• Perform the A* Algorithm on the following
figure. Explicitly write down the queue at each
step. 10
A 6
4
6
17 13 6
E 4
1 0
5 3
S B 2
F G
7

10 4
D 6

C 6
A*

A* SEARCH
A* Search 10
0 A 6
4
17 S 17
17
6
5 13 6 E 4
1 3 0
S B 2 F G
7 D 6
10 4
C 6
QUEUE:
S
A* Search 10
A 6
4
S 17
6
5 13 6 E 4
1 3 0
S B 2 F G
7 D 6
10 4
6 5 10 C 6
10 A 16
13 B 18
4 C 14
QUEUE:
SC
SA
SB
A* Search 10
A 6
4
S 17
6
5 13 6 E 4
1 3 0
S B 2 F G
7 D 6
10 4
6 5 C 6
10 A 16
13 B 18 C QUEUE:
SA
16
2 D 18 SCD
SB
A* Search 10
A 6
4
S 17
6
5 13 6 E 4
1 3 0
S B 2 F G
7 D 6
10 4
5 C 6
A 13 B 18 C QUEUE:
SAE
12 16
4 E 16
2 D 18 SCD
SB
A* Search 10
A 6
4
S 17
6
5 13 6 E 4
1 3 0
S B 2 F G
7 D 6
10 4
5 C 6
A 13 B 18 C QUEUE:
SAEF
16
E 2 D 18 SCD
SB
18
B 31
16
F 17 SAEB
13 1
A* Search 10
A 6
4
S 17
6
5 13 6 E 4
1 3 0
S B 2 F G
7 D 6
10 4
5 C 6
A 13 B 18 C QUEUE:
SCD
16
E 2 D 18 SB
SAEFG
F SAEFD

22 19
2 D 24
0 G 19
A* Search 10
A 6
4
S 17
6
5 13 6 E 4
1 3 0
S B 2 F G
7 D 6
10 4
5 C 6
A 13 B 18 C QUEUE:
SB
E D SAEFG
SCDF
F 23
B 36
22
F 23 SCDB
13 1

19
0 G 19
A* Search 10
A 6
4
S 17
6
5 13 6 E 4
1 3 0
S B 2 F G
7 D 6
10 4
C 6
A B QUEUE:
SBD
12 11
E 2 D 14
4 E 15 SBE
SAEFG
F
19
0 G 19
A* Search 10
A 6
4
S 17
6
5 13 6 E 4
1 3 0
S B 2 F G
7 D 6
10 4
C 6
A B QUEUE:
SBE
11
E D 4 E 15 SBDF
SAEFG
F 18
C 22
18
F 19 SBDC
4 1

19
0 G 19
A* Search 10
A 6
4
S 17
6
5 13 6 E 4
1 3 0
S B 2 F G
7 D 6
10 4
C 6
A B QUEUE:
SBEF
E D E SAEFG
SBDF
F 18
C 22
18
F 19
17
A 27
15
F 16 SBDC
4 1 10 1
SBEA
19
0 G 19
A* Search 10
A 6
4
S 17
6
5 13 6 E 4
1 3 0
S B 2 F G
7 D 6
10 4
C 6
A B QUEUE:
SBEFG
E D E SAEFG
SBDC
F 18
C 22
17
A 27 F SBEFD
4 10
SBEA
19 21 18
0 G 19
2 D 23
0 G 18

You might also like