Scribd Logo
Upload

Welcome to Scribd!

  • 281 views

    Finding Optimal Solution of 15 Puzzle

    Uploaded by

    Marvin RFortin
    This document discusses using the A* search algorithm to find the optimal solution, or shortest move sequence, to solve the 15 puzzle problem from any given start state to the goal state. It first introduces the 15 puzzle problem and A* search. Then it provides an example of how A* search works, showing the fringe and expanded nodes. It discusses the pros and cons of A* search, including how heuristics and data structures can improve its efficiency. Finally, it proposes using a pattern database heuristic instead of Manhattan distance to further speed up the A* search for solving large 15 puzzle instances.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    Finding Optimal Solution of 15 Puzzle

    Uploaded by

    Marvin RFortin
    281 views15 pages
    This document discusses using the A* search algorithm to find the optimal solution, or shortest move sequence, to solve the 15 puzzle problem from any given start state to the goal state. It first introduces the 15 puzzle problem and A* search. Then it provides an example of how A* search works, showing the fringe and expanded nodes. It discusses the pros and cons of A* search, including how heuristics and data structures can improve its efficiency. Finally, it proposes using a pattern database heuristic instead of Manhattan distance to further speed up the A* search for solving large 15 puzzle instances.

    Original Description:

    Finding_Optimal_Solution_of_15_puzzle c#

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses using the A* search algorithm to find the optimal solution, or shortest move sequence, to solve the 15 puzzle problem from any given start state to the goal state. It first introduces the 15 puzzle problem and A* search. Then it provides an example of how A* search works, showing the fringe and expanded nodes. It discusses the pros and cons of A* search, including how heuristics and data structures can improve its efficiency. Finally, it proposes using a pattern database heuristic instead of Manhattan distance to further speed up the A* search for solving large 15 puzzle instances.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    281 views15 pages

    Finding Optimal Solution of 15 Puzzle

    Uploaded by

    Marvin RFortin
    This document discusses using the A* search algorithm to find the optimal solution, or shortest move sequence, to solve the 15 puzzle problem from any given start state to the goal state. It first introduces the 15 puzzle problem and A* search. Then it provides an example of how A* search works, showing the fringe and expanded nodes. It discusses the pros and cons of A* search, including how heuristics and data structures can improve its efficiency. Finally, it proposes using a pattern database heuristic instead of Manhattan distance to further speed up the A* search for solving large 15 puzzle instances.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    You are on page 1of 15

    Finding Optimal Solution

    of 15 puzzle
    B94902062 NTUCSIE
    Kai-Yung Chiang

    15 puzzle introduction

    Initial states: a solvable puzzle, including


    numbered 1~15 tiles and a blank tile 0
    Goal state: puzzle in which tiles 0 ~ 15 are in
    well permutation from row to column
    A (valid) move: swap blank tile with its
    neighboring tile
    The optimal solution: given a initial state, find
    the move sequence such that it is a solution
    taking the fewest moves to reach the goal state

    Searching Algorithm

    A* search
    Each node has heuristic (the estimating
    distance from current state to goal state)
    Each nodes evaluation function = heuristic
    + total moves from initial state
    A* always expands the fringe node whose
    evaluation function is minimum

    Example
    h=45, f=45

    : fringe nodes

    : expanded nodes h: heuristic f: evaluation function

    Example
    h=45, f=45

    h=41, f=42

    : fringe nodes

    h=45, f=46

    h=42, f=43

    : expanded nodes h: heuristic f: evaluation function

    Example
    h=45, f=45

    h=41, f=42

    h=45, f=47

    : fringe nodes

    h=42, f=44

    h=45, f=46

    h=42, f=43

    h=43, f=45

    : expanded nodes h: heuristic f: evaluation function

    Example
    h=45, f=45

    h=41, f=42

    h=45, f=47

    h=42, f=44

    h=45, f=46

    h=43, f=45
    h=40, f=42

    : fringe nodes

    h=42, f=43

    h=39, f=41 h=45, f=47

    : expanded nodes h: heuristic f: evaluation function

    Pros and cons for A* search

    Pros:
    Can find the optimal solution (or admissible) if
    heuristic function will never overestimate

    Eliminate number of expanded nodes


    Cons:
    Taking more time on expanding each nodes
    (compared with DFS or BFS):

    Find minimum nodes (in fringe) to expand


    Compute heuristic and evaluation function
    Check, eliminate and update repetitive states
    Maintain data structure

    Speed up by good data structure

    Priority queue: Fibonacci heap


    Extract minimum and decrease key in
    (amortized) O(logn)
    Insert in O(1)
    Hash function:
    Used in checking repetitive states, eliminate
    number of searching nodes
    A* search with above data structure and Manhattan
    distance as heuristic function could solve 8 puzzle
    in (averaged) 0.002 seconds
    However, still too slow to solve 15 puzzle

    More speed up technique

    Still too many nodes need to be expanded


    (though eliminate repetitive states)
    If f(n) = 2h(n) + moves(n)
    Could speed up much, but not admissible.
    Ideas: try to improve h(n) to be more close to
    truly needed optimal moves, while still
    maintaining admissible
    Disjoint pattern database heuristic instead of
    Manhattan distance
    New heuristic = i number of needed moves to
    well order tiles in pattern i

    Pattern database

    Divide puzzle into 3 disjoint patterns


    Each pattern has 16!/10!5.7 * 106 different
    combination orders of tiles, and each of them
    corresponds to a database entry
    Each entry records moves for aligning these
    pattern tiles to correct position

    Building pattern database

    Constructed by bottom up approach


    Start with well ordered tiles
    BFS moving blank tile to new states, move is
    added only when tile in this pattern is
    swapped with blank tile
    Add new entry to pattern database if current
    state has not been traversed (using a bits of
    array to record this information)

    Benchmark and outcome

    Randomly generate 100 solvable puzzles:

    Benchmark and outcome

    Pattern database heuristic improves nearly 10


    moves than Manhattan distance in averaged
    In most problem instances
    Expanded nodes are less than 100,000
    Could be solved in 30 seconds, and more
    than half could be solved in 10 seconds
    CPU% are less than 20%. It might suggest
    that lots of time are took in communication
    with database
    Pattern database heuristic improves a lot

    Demo

    http://140.112.249.168/phpAdmin

    You might also like