CS 470 Artificial Intelligence, Winter 2021, Instructor: Jeffrey Horn ASSIGNMENTS
| Heuristic
Designation |
DESCRIPTION |
EXAMPLE1 |
| h0 |
h(s1,s2)
always returns zero, hence it is the least informed heursitic
possible! When used in A* search the result is
BREADTH-FIRST search (i.e., UNINFORMED search). Question:
Is A* with h0 still A*? I.e., is h0 an admissable heuristic? |
0 |
| h4 |
h4(s1,s2)
returns the number of blocks that are not in the "goal column".
More specifically for each block b if b is in column c in state s1 and
in column c' in state s2 (and c ≠ c' ) then h4(s1,s2) is incremented by
one. |
3 |
| h6 |
h6(s1,s2) returns the total of distances that each block is out of place, in terms of columns. More specifically for each block b if b is in column c in state s1 and in column c' in state s2 (and c ≠ c' ) then h6(s1,s2) is incremented by |c'-c|. | 6 |
| ??? |
(insert YOUR heuristic! This is Task 2 of A3) | |
| h∞ |
h∞(s1,s2)
is the ACTUAL cost of the shortest plan to get from s1 to s2. h∞
is included in this table for completeness and for comparison with
other heuristics. In our Blocks World the only way I can think of
to implement h∞ would be to actually conduct an admissable search of
plans from s1 to s2! This would mean there would be no
savings (in search time) for using this heuristic versus just
conducting breadth-first search (i.e., using h0)! |
6 |