Hints for :

http://www.cs.iastate.edu/~cs572/assignments/assignment2.pdf

TA ,Jie Bao
Dept of Computer Science
Iowa State University
baojie@cs.iastate.edu 

Those are based on questions you asked during the past week.

1- a) suppose the shallowest goal is located at depth d, you need to prove the memory requirement is O(d). Refer to how do we get the memory requirement of DFS
b) using contradiction. Assume Ad returns a suboptimal goal g2 with f(g2)>f*(s), try to find a contradiction. Note that all nodes with a smaller a f value than f(g2) have already been visited when you visit g2(prove that)

2-  your aim is to visit all nodes with as low total distance (cost) as possible.
1)-     Define your status space. what's the goal status? how many goal nodes in your status space?
2)-     define your g function and h function
3)-     compare those algorithms based on your problem description

3- Using contradiction

monotone there implies consistent. If n2 is a successor of n1, then

  h(n1) – h(n2)<= k(n1,n2)                               (**)

where k(n1,n2) is the cost to go from n1 to n2

notice that k(s,n) = g*(n)

a)    suppose the path found by A* with g(n)> g*(n), try to find a contradiction to the admissibility of A*
b)    suppose there is a decreasing sequence, try to find contradiction between triangular inequality and (**)

4 a) if the memory is not enough, it’s easy to find a loop by example. Set memory capacity to 2 and use the example tree on the text and see what will happens?
b) two steps

i) prove that when a node is regenerated, the f value of its parent will increase. Try to prove some lemmas to support this. This one may be useful:
 - for any node n, f(n) increases when n is completed (you need to prove it)
ii) prove that no identical tree is generated more than once. Note that “identical” means both the nodes and the f-values of all nodes are same in the two trees.

By i) and ii) you can find the algorithm has no loop.

5.

• Four line-label theory means labeling object with "+", "-", "<-" and "->"
• “realizable” means you can label it using certain algorithm (eg. Waltz)
• “polyhedra” means some vertex is formed by the junction of more than three planar surfaces. Eg:



• “no concave” means use only no "-" edges on the object

you need to try to find all possible cased for junctions on polyhedra, for example

 

6- follow the example provided in the handout (Constraint Satisfaction Agents, http://www.cs.iastate.edu/~cs572/notes/week4.pdf)

7- notice that Waltz’s study is based a very simplified case

1-    Every vertex is trihedral
2-    Surface do not contain 0-width cracks
3-    No shadows
4-    The scene is views from a general viewing position.

8- Give examples that use those algorithms

Eg. For stochastic parallel hill climbing: find maximum point on a 2-dimensional complex multi-peak function. For random search: find the oldest student in ISU by randomly interview students in campus.

9- You need to find a goal node (h(x)=0) in a AND-OR tree using A*. Give first 4 steps in your search



10 - You need to define that status space and your constraints. see study guide Chapter 4 (8- queen problem and scene labeling problem, http://www.cs.iastate.edu/~cs572/notes/week4.pdf)

Constraint propagation: http://kti.ms.mff.cuni.cz/~bartak/constraints/propagation.html

To show constraint propagation, you can write either in diagram (shown below) or in text( see study guide Chapter 4, page 9 for example of constraint propagatio in text)



 

 11- Based on your experience. :)