程序代写代做代考 algorithm Activity 4.1:  Path Search Algorithms on a Graph

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

Posted in Uncategorized

Leave a Reply

Your email address will not be published. Required fields are marked *