USA: +1 (725) 712-1730 
Sign in
Consider a search space, where each state can be red, green, blue, yellow, or black. Multiple states may have the same color. The goal is to reach any black state. Here are some rules on the successors of different states, based on their color: Any path between a red and a green state has cost > = 20. Any path between a red and a blue state has cost > = 30. Any path between a blue and a yellow state has cost > = 40. Any path between a green and a yellow state has cost > = 50. Any path between a red and a yellow state must go through a green or blue state. Any path connecting a red, green, or blue state to a black state must go through a yellow state. Define the best admissible heuristic H that you can, using the above information. H should assign a value to a node based on the color of that node’s state. H(red) = H(green) = H(blue) = H(yellow) = H(black) =
Expert Answer
Consider H(red). According to the last condition any path connecting read to black has to pass through yellow state.
According to the 2nd last condition any path connecting read and yellow has to pass through a green or blue state.
So red’s path to yellow will be either (red to green(min cost 20)+green to yellow(min cost 50)) or (red to blue(min cost 30)+blue to yellow(min cost 40))
Both these path have min cost 70. So it does not matter if A reaches yellow by going through green or blue.
H(red)=H(yellow)+70
Consider H(green). According to the last condition any path connecting green to black has to pass through yellow state. Also green has no direct path to blue and going to red will be of no use due to path cost of 70. So from green to black, the states wil include the green to yellow path + yellow to black path.
H(green)=H(yellow)+50
Consider H(blue). According to the last condition any path connecting green to black has to pass through yellow state. Also blue has no direct path to green and going to red will be of no use due to path cost of 70. So from blue to black, the states wil include the green to yellow path + yellow to black path.
H(blue)=H(yellow)+40
Consider H(yellow). As all the other nodes need to go through H to reach black, yellow should go directly to black.
So H(yellow)=cost of Path(yellow to black)
H(black)=0 as black is the final state
