2nd Assignment
ai-2.pdf
- termination of A*
- special time/space complexity of A*
- local maximum, plateau and ridge problem of hill-climbing
- proof for non-decreasing f-costs given a heuristic function which
obeys the triangle inequality
- admissible heuristic functions
- using A* to solve the eight-puzzle (with Manhatten distance)
- human problem solving (analogy theory for strings over a finite
alphabet)
1st Programming Assignment
Task:
Implement a problem independent search algorithm in PROLOG that is
parameterized for the following search strategies: DFS, BFS, A* (with
OPEN and CLOSED list and cycle-check), hill-climbing, and uniform cost
search.
Here are two programs that solve this task. They are computing exactly
the same set of solutions and are only differing in efficiency.
search1.pl
search2.pl
Subquestions
- Why is A* with a closed-list still optimal?
- Why gives us A* with closed-list just one solution?
Because the closed-list remains same within backtracking. Since in our
example nearly all nodes are in the closed-list after finding the
optimal solution and there are just a few paths left in the agenda,
there is no chance to find an alternative solution.
- So why use a closed-list, if it is throwing away alternative
solutions?
Because it makes the algorithm more efficient (we want to get as fast as
possible to the optimal solution).