SEG4560 Midterm Solution
Question 1.
(a)
Uninformed Search
• Assumes no knowledge about the problem
• Main difference between the methods is the order in which they consider the states
• Very general, can be applied to any problem but very expensive, since we assume no knowledge about the problem
• Some algorithms are complete, i.e. they will find a solution if one exists
All uninformed search methods have exponential worst-case complexity
Informed search
• Use knowledge about the problem, in the form of a heuristic.
– The heuristic is a guess for the remaining cost to the goal.
– A good heuristic can reduce the search time from exponential to almost linear.
• Best-first search is greedy with respect to the heuristic, not complete and not optimal
• Heuristic search is greedy with respect to f=g+h, where g is the cost so far and h is the estimated cost to go
• A* is heuristic search where h is an admissible heuristic; it is complete and optimal
• A* is a key AI search algorithm
(b)
Systematic search method
Complete algorithms seek any solution or all solutions. The systematic search methods explore systematically (and exhaustively) the whole search space. They view the search space as a search tree. Each node represents mutually exclusive choices which partition the remaining search space into disjoint sub-spaces. This structure enables to remember with acceptable memory requirements, which parts of the search space have already been visited. Usually, a node corresponds to an assignment of a particular value to a particular variable.
Local search method
Incomplete search methods do not explore the whole search space. They search the space either non-systematically or in a systematic manner, but with a limit on some resource. They may not provide a solution but their computational time is reasonably reduced. They can not be applied to find all solutions or to prove that no solution exits.
However, they may be sufficient when just some solution is needed. Another application is to seek a feasible solution of an optimization problem.
(c)
The time complexity of Depth-first search is O(bm) and that of iterative deepening depth-first search is O(bd). When m d, IDS is actually faster than DFS.
(d)
If we relax the constraint for TSP such that each city can be visited more than one time (that is, there may be some cities visited more than one time) and the cost for repeated edges are not count, we can get a solution for MST problem. Thus, this admissible heuristics can be derived from a relaxed version of the TSP. The key point is that the optimal solution cost of a relaxed problem is no greater than the optimal solution cost of the real problem. Minimum spanning tree can be computed in O(n2) and is a lower bound on the shortest (open) tour.
Question 2.
w = 0 gives f(n) = 2g(n). This behaves exactly like uniform-cost search the factor of two makes no difference in the ordering of the nodes.
w = 1 gives A* search.
w = 2 gives f(n) = 2h(n), i.e., greedy best-first search.
Question 3.
(a) Variables:
Domain: {0,1}
Constraints:
(b) Construct a binary tree, where nodes at level i consider the assignment to
variable Bi, i.e., one branches assigns Bi = 1 and the other assigns Bi = 0.
Perform a backtracking search on this binary tree. Return the variable
assignments along the path when the constraint is satisfied at a node; return
failure when the whole tree has been traversed but no solution has been found.
Backtrack condition: when for some d<=n.
Number of leaf nodes: 2n
Question 4.
(a) minimax value=
(b) For a MIN node,
Since a>0, the choice is still the same.
For a chance node,
A MAX node takes the maximum over all chance nodes. So its choice is still
the same.
Question 5.
(a)
(1)
(B2,2 Û (P1,1 Ú P2,2 Ú P3,1)) Ù ØB2,2
= (B2,2 Þ (P1,1 Ú P2,2 Ú P3,1)) Ù ((P1,1 Ú P2,2 Ú P3,1) Þ B2,2) Ù ØB2,2
= (ØB2,2 Ú (P1,1 Ú P2,2 Ú P3,1)) Ù (Ø(P1,1 Ú P2,2 Ú P3,1) Ú B2,2) Ù ØB2,2
= (ØB2,2 Ú P1,1 Ú P2,2 Ú P3,1) Ù ((ØP1,1 Ù ØP2,2 Ù ØP3,1) Ú B2,2) Ù ØB2,2
= (ØB2,2 Ú P1,1 Ú P2,2 Ú P3,1) Ù ((ØP1,1 Ú B2,2) Ù (ØP2,2Ú B2,2) Ù (ØP3,1Ú B2,2)) Ù ØB2,2
= (ØB2,2 Ú P1,1 Ú P2,2 Ú P3,1) Ù (ØP1,1 Ú B2,2) Ù (ØP2,2Ú B2,2) Ù (ØP3,1Ú B2,2) Ù ØB2,2
(2)
(b)
(1)
"x, y Person(x) Ù (Policy(y) Ù Expensive(y) Þ ØBuys(x, y).
(2)
$x Barber(x) Ù "y Man(y) Ù Ø Shaves(y, y) Þ Shaves (x, y).
(3)
"x Person(x) Ù Born(x, UK) Ù ($y Parent(y, x) Þ Citizen(y, UK)) Þ Citizen(x, UK).