CS考试辅导 FIT3080 Semester 2, 2022 Informed Search – codehelp代写
FIT3080 Semester 2, 2022 Informed Search
Monash University Faculty of Information Technology FIT3080 Week 4 Lab 3: Informed Search
Exercise 1: Algorithm A
Consider the (full) state space below. Indicate (1) the order in which nodes are expanded, and (2) the nodes remaining in memory after finding the goal, for the following search strategies (assume typical left-to-right operator tie breaking):
Copyright By cscodehelp代写 加微信 aplg6666
(a) Depth-First Iterative Deepening
(b) Greedy Best-First Search
Let’s consider a new strategy called Algorithm A. This algorithm can be described as a best-first search which uses the following expansion priority for a node 𝑛:
𝐟 (𝐧) = 𝐠(𝐧) + 𝐡(𝐧)
As usual, 𝑔(𝑛) denotes the cost-so-far (i.e., from the start node to node 𝑛) and h(𝑛) is an estimate of the cost-to-go (i.e., from node n to the goal node). We can instantiate Algorithm A as using the Graph-search or Tree-search framework, provided the following invariant properties for the 𝑔− and h−value function are true:
𝑔(𝑛) >= 𝑔∗(𝑛) h(𝑛) >= 0
(c) Instantiate Algorithm A (as Graph or Tree- search) to solve the above problem.
(d) Is algorithm A the same algorithm as A*?
(e) How can we modify things (or what can we modify) so that Algorithm A behaves like A*?
(f) After the modification, what nodes are expanded by A*?
Exercise 2: Algorithm 𝐴(∗) – Traveling Salesman Problem
A salesperson must visit each of 𝑛 cities exactly once. Assume that there is a road between
each pair of cities. Starting at city 𝐴, find the route of minimal distance that visits each of the cities only once and returns to city 𝐴.
(a) Propose a state space and action space for this problem, explaining clearly under what state conditions certain actions are allowed.
(b) Propose two (non-zero) h functions for this problem. Is either of these h functions admissible (a lower bound of h∗)?
(c) Apply algorithm A with one of these h functions to the following 5 city problem:
Exercise 3: Algorithm 𝐼𝐷𝐴(∗) – 5-puzzle problem
Consider a problem called the 8-puzzle. The problem has the start and goal state as follows. Throughout the question, when doing a search, give value of 𝑓(𝑛), 𝑔(𝑛) and h(𝑛) at each node 𝑛. The estimated cost function 𝑔(𝑛) is the number of steps from the initial node.
(a) Construct two non-trivial heuristic functions, h1 and h2, that you think may help the algorithm to quickly find a solution. Are these functions admissible? Explain why?
(b) Which heuristic function is more efficient? Explain why?
(c) Useh1todoanIDA*searchtogetfromthestartstatetothegoalstateintheminimum number of steps. Make sure to show all working including value of 𝑓, h, 𝑔 functions in each steps.
(d) (optional/homework) Use h2 to do an IDA* search to get from the start state to the goal state in the minimum number of steps. Make sure to show all working including value of 𝑓, h, 𝑔 functions in each steps.
程序代写 CS代考 加微信: aplg6666 QQ: 2235208643 Email: kyit630461@163.com
