Activity 4.1: Path Search Algorithms on a Graph
Consider the task of ២�nding a path from start state S to goal state G, given the distances and heuristic values in this
diagram:
For each of the following strategies, list the order in which the states are expanded. Whenever there is a choice of states, you should select the one
that comes ៍�rst in alphabetical order. In each case, you should skip any states that have previously been expanded, and you should continue the
search until the goal node is expanded.
Breadth First Search
Depth First Search
Uniform Cost Search [Hint: ៍�rst compute for each state in the graph]
Greedy Search, using the heuristic shown
A*Search, using the heuristic shown
Activity 4.2: A* Search for the 8-Puzzle
Complete the A*Search for the 8-Puzzle activity on the Finding Heuristics page. Discuss your ២�ndings with the group.
0
No tags yet
Activity 4.3: Relationships Between Search Strategies
(Ex 3.22, R&N) Prove each of the following statements, or give a counterexample:
Breadth First Search is a special case of Uniform Cost Search.
Breadth First Search, Depth First Search and Uniform Cost Search are special cases of best-៍�rst search.
Uniform Cost Search is a special case of A*Search.
Activity 4.4: Heuristic Path Algorithm
(Ex 3.28, R&N) The heuristic path algorithm is a best-២�rst search in which the objective function is:
where .
What kind of search does this perform when ? when ? when ?
For what values of is this algorithm complete? For what values of is it optimal, assuming is admissible?
Activity: 4.5 Understanding Informed Search Algorithms with Mazes
Discuss your ៍�ndings and insights from the ‘Fun with Mazes’ activity. Compare your ៍�ndings and discuss any discrepancies.
(a) an environment for which Greedy Search takes much longer than A*Search.
(b) an environment for which Greedy Search produces a path that is much longer than the optimal path.
(c) an environment for which A*Search with the Euclidean Distance heuristic takes much longer than with the Manhattan Distance heuristic.
(d) an environment that is interesting for some other reason.
Alan Blair (/u/alanblair) – 6 days ago (Apr 24 2017, 12:11 p.m.) Be the ៍�rst to like this Like(/u/alanblair)
Comments
Collapse All Sorted by: New Threads
Write a comment…
Reply Like
Share (https://www.openlearning.com/unswcourses/courses/comp93414/tutorial_informed_search?inCohort=unswcourses/courses/COMP93414/Cohorts/Preview#comment-
58ddd878117bd06565c4f630)
(https://www.openlearning.com/u/garyq)Gary Shi (https://www.openlearning.com/u/garyq) · about a month ago
-.-
Reply Like
(https://www.openlearning.com/u/jordan.brown)Jordan Brown (https://www.openlearning.com/u/jordan.brown) · about a month ago
I like these activities, good to stretch the brain!
0
https://www.openlearning.com/u/alanblair
https://www.openlearning.com/u/alanblair
https://www.openlearning.com/unswcourses/courses/comp93414/tutorial_informed_search?inCohort=unswcourses/courses/COMP93414/Cohorts/Preview#comment-58ddd878117bd06565c4f630
https://www.openlearning.com/u/garyq
https://www.openlearning.com/u/garyq
https://www.openlearning.com/u/jordan.brown
https://www.openlearning.com/u/jordan.brown