Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

You want to use A* search to tell you the best route from block S to the nearest goal block (G1 or G2assume they are

You want to use A* search to tell you the best route from block S to the nearest goal block (G1 or G2assume they are a couple of coffee shops or something). Each block has a single-letter name, and a heuristic distance given in parentheses. Fill out the following table, as for the in class exercise, showing the final route to the nearer of goal nodes G1 and G2, and showing all the items in the queue at each stage of the algorithm. The distance of each edge is 1. When two nodes are an equal f-value from the nearest goal, expand the node whose name comes first in the alphabet.

image text in transcribed

image text in transcribed

A(4) B(3) C(2) D(1) G1 E(5) F(4) UNDER CONST. H(2) UNDER CONST. UNDER CONST. (2) J(1) K(1) L(3) M(3) N(2) UNDER CONST. G2 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - +------7----------------- ------ ---------- ----- - - - - -- - - - - - - - - - - - - - - - + - - - - - - - - - - - - - - - - - - - - + ------ ---------- ------ + ------ --- -- ---- + ------ Priority Queue After Expanding Node (except for head of queue, order is irrelevant) nf via nf via nf via nf via nf via nf via s S 6 ! 6 E E SL S (head of queue) 5 1 : 4 L M s + - - - - - - - - - - - - - - - - - - - - - - - - - - + - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Solution: (leftmost column is vertex being expanded) (I did the first two lines for you) - - - - - - - - - - - - - - - - - - ------ --- - ----- -- ---- --- ------ ---- - --- ---- -- -- ----- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - + - - - - - - - ver. A(4) B(3) C(2) D(1) G1 E(5) F(4) UNDER CONST. H(2) UNDER CONST. UNDER CONST. (2) J(1) K(1) L(3) M(3) N(2) UNDER CONST. G2 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - +------7----------------- ------ ---------- ----- - - - - -- - - - - - - - - - - - - - - - + - - - - - - - - - - - - - - - - - - - - + ------ ---------- ------ + ------ --- -- ---- + ------ Priority Queue After Expanding Node (except for head of queue, order is irrelevant) nf via nf via nf via nf via nf via nf via s S 6 ! 6 E E SL S (head of queue) 5 1 : 4 L M s + - - - - - - - - - - - - - - - - - - - - - - - - - - + - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Solution: (leftmost column is vertex being expanded) (I did the first two lines for you) - - - - - - - - - - - - - - - - - - ------ --- - ----- -- ---- --- ------ ---- - --- ---- -- -- ----- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - + - - - - - - - ver

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

More Books

Students also viewed these Databases questions