Friday, October 06, 2006

Homework 2 Grading details

Some students might get confusing about the final grade of your homework. Here, I list the details:

For part A, the grade points for each problem is the same as in the solution(in total 41 points).

For Part B, the score for each problem is just 2 points, NOT 3 points as in the solution. So there are actually only 12 points.

As for Part C, a, b, c, d and e are 3 points each. f, g, and h are 2, 4 and 5 points respectively. This part has in total 3*5+2 + 4 + 5 = 26 pts.

Thus, the total score is
41+12+26=79.

2 comments:

Unknown said...

I'm very confused about the wording of question #3B. The question asks if the Manhattan-distance heuristic is monotonic[ally increasing], but the solution shows that the f-value function is monotonic. In fact, the solution also shows that the Manhattan-distance heuristic is NOT monotonic (it can either increase or decrease), so the correct answer should be "No," shouldn't it? I think the question wasn't worded properly, given the solution, and I know I answered it correctly based on the question that was asked.

Lei Tang said...

Actually, you can prove that if f(n) along any path is non-decreasing, then the heuristic must be monotonic.

The sketch of the proof is below:
Choose a node n and its successor n', we have f(n')>=f(n). So

g(n')+h(n') >= g(n)+h(n);
g(n)+c(n, a, n')+h(n') >= g(n)+h(n);

Therefore,
c(n, a, n') + h(n')>= h(n). That is, h(n) <= c(n, a, n')+ h(n')

Hence, h is monotonic based on the definition on Page 99 in the textbook.

Therefore, you can show that f value is non-decreasing along one path to prove h is monotonic.