1. The 15 puzzle problem involves arranging 15 numbered tiles in a 4x4 grid into the desired order with the minimum number of moves, where only the empty space can be moved into neighboring tiles.
2. Solving the problem by trying all possible arrangements is infeasible due to the huge search space. Heuristics are used to guide the search of the state space tree.
3. The heuristic estimates the cost of a node as the sum of the path length and number of misplaced tiles, and prioritizes exploring branches with lower estimated cost first to find the solution requiring minimum moves.
1. The 15 puzzle problem involves arranging 15 numbered tiles in a 4x4 grid into the desired order with the minimum number of moves, where only the empty space can be moved into neighboring tiles.
2. Solving the problem by trying all possible arrangements is infeasible due to the huge search space. Heuristics are used to guide the search of the state space tree.
3. The heuristic estimates the cost of a node as the sum of the path length and number of misplaced tiles, and prioritizes exploring branches with lower estimated cost first to find the solution requiring minimum moves.
1. The 15 puzzle problem involves arranging 15 numbered tiles in a 4x4 grid into the desired order with the minimum number of moves, where only the empty space can be moved into neighboring tiles.
2. Solving the problem by trying all possible arrangements is infeasible due to the huge search space. Heuristics are used to guide the search of the state space tree.
3. The heuristic estimates the cost of a node as the sum of the path length and number of misplaced tiles, and prioritizes exploring branches with lower estimated cost first to find the solution requiring minimum moves.
1. The 15 puzzle problem involves arranging 15 numbered tiles in a 4x4 grid into the desired order with the minimum number of moves, where only the empty space can be moved into neighboring tiles.
2. Solving the problem by trying all possible arrangements is infeasible due to the huge search space. Heuristics are used to guide the search of the state space tree.
3. The heuristic estimates the cost of a node as the sum of the path length and number of misplaced tiles, and prioritizes exploring branches with lower estimated cost first to find the solution requiring minimum moves.
1 2 15 5 Can’t move TOP, it will result back 4 13 3 6 into previous state 14 12 9 10 11 7 8 left right bottom 1 2 15 5 1 2 15 5 1 2 15 5 4 13 3 6 4 13 3 6 4 13 3 6 14 12 9 14 11 12 9 14 12 9 10 11 7 8 10 7 8 10 11 7 8 Problem Solving • Cannot try all possible solutions! • Cannot build state space tree – Branch for each move…. Very large… • Need some heuristics to simplify the search • Heuristics decide the fate of state space tree – decides which sub-child to selected for branching – and which should be pruned (bounded) Heuristic for 15 puzzle • For a state node ‘x’ in state space tree let its cost be defined as: 𝑐 (𝑥) = 𝑓 𝑥 + 𝑔(𝑥) • 𝑐 (𝑥) =estimated min cost to reach the goal node • 𝑓 𝑥 length of path from root to node ‘x’ • 𝑔(𝑥) =estimate of length of shortest path from node ‘x’ to a goal node in subtree with root ‘x’
