CSE 190 Lecture Notes - Lecture 4: Priority Queue, Parker Brothers, Branching Factor

• School: UW
• Department: Computer Science and Engineering
• Course: CSE 190
• Professor: T A N I M O T O, S T E V E N L

Document Summary

Objective: get all tiles in order, using only legal. Slide a tile into the blank space. Said to have been invented by notes palmer chapman around 1874. Although there are 16! orderings of the 15 tiles and one blank, there are only 16!/2 states reachable from the goal state. If the initial state is not one of the even permutation states, then solution is impossible. Important to the history of artificial intelligence, because a variety of heuristics for it could be easily developed and compared. H1: the number of tiles not in their correct places. A heuristic is a function that can be applied to a state to obtain a number that estimates the number of moves still required to reach a goal state. To be most useful, it should never overestimate that number of moves. H2: the distance of tile 1 from its place (total of |dx| + |dy|) H3: sum of the horizontal distances of all.