Recent Changes

Sunday, October 11

  1. page IDA* edited Iterative-deepening-A* known as IDA* ... search algorithm, A a combination of th the A* al…
    Iterative-deepening-A* known as IDA*
    ...
    search algorithm, Aa combination of ththe A* algorithm
    The idea is that successive iterations correspond not to increasing depth of search, but rather to increasing values of the total cost of a path.
    ...
    the node
    (g)
    (g) plus the
    Algorithm: At each iteration, perform a depth-first search, cutting off a branch when its total cost (g + h) exceeds a given threshold.
    This threshold starts at the estimate of the cost of the initial state, and increases for each iteration of the algorithm. At each iteration, the threshold used for the next iteration is the minimum cost of all values that exceeded the current threshold.
    A well-known property of A* is that it always finds a cheapest solution path if the heuristic is admissible, or in other words never overestimates the actual cost to the goal.
    ...
    for iterative-deepening-A*.
    Furthermore,
    Furthermore, IDA* expands
    Notes: The standard algorithms for brute-force search have serious drawbacks.
    ...
    path to athe solution.
    The depth-first iterative-deepening algorithm, however, is asymptotically optimal in terms of cost of solution, running time, and space required for brute-force tree searches. DFID can also be applied to bi-directional search, heuristic best-first search, and two-person game searches.
    Since almost all heuristic searches have exponential complexity, iterative-deepening-A* is an optimal admissible tree search in practice.
    For example, IDA* is the only known algorithm that can find optimal paths for randomly generated instances of the Fifteen Puzzle
    within practical time and space constraints.
    ...
    IDA* by korkorf
    (view changes)
    1:42 pm
  2. page Admissible Heuristic edited A heuristic function is admissible if it never overestimates the cost of reaching the goal. An admi…
    A heuristic function is admissible if it never overestimates the cost of reaching the goal. An admissible heuristic is also known as an optimistic heuristic.
    Admissible heuristics are an important class of heuristics because they have several desirable properties in various search algorithms. They guarantee shortest path solutions in the A* search algorithm. With admissible heuristics the dynamic weighting (Pohl, 1973) and A* (Pearl, 1984) algorithms guarantee less expensively produced, but boundedly longer solutions. Moreover, it is possible to reduce an exponential average time complexity to a polynomial one using A* and multiples of an admissible heuristic (Chenoweth & Davis, 1991).
    ...
    the problem. asAs shown in
    {pic1.JPG}
    An example for such transformation is Manhattan Distance for the N-Puzzle: it considers the problem by ignoring the blank tile, assuming a tile can go straight to it’s goal position. The sum of the distance from the goal position of all tiles, which underestimates the actual solution path length, is the Manhattan Distance.
    (view changes)
    1:35 pm
  3. page Samples of 8-Puzzle Start Boards edited ... 4 6 3 7 5 Worst: 5 6 7 4 8 3 2 1
    ...
    4 6 3
    7 5
    Worst:
    5 6 7
    4 8
    3 2 1
    (view changes)
    1:32 pm
  4. 1:30 pm
  5. page N-MaxSwap edited Related Problems: N-Puzzle Type:heuristic function h = The number of steps it would take to solve …
    Related Problems: N-Puzzle Type:heuristic function
    h = The number of steps it would take to solve the problem if it was possible to swap any tile with the "space".
    ...
    heuristic. It is an admissible heuristic, since it underestimates the
    The heuristic function can be implemented by using 2 arrays:
    P – represents the current permutation.
    (view changes)
    1:29 pm
  6. page Pattern database edited ... While we normally think of a heuristic as a function computed by an algorithm, any function ca…
    ...
    While we normally think of a heuristic as a function computed by an algorithm, any function can also be computed by a table lookup, given sufficient memory. In fact, for reasons of efficiency, heuristic functions are commonly precomputed and stored in memory.
    Some Definitions:
    ...
    a state). E.g., In the
    A Target pattern: a partial specification of the goal state.
    A pattern database (PDB): is the set of all patterns which can be obtained by permutations of a target pattern. For each pattern in the database we compute the distance (minimum number of moves) to the target pattern using retrograde analysis. This distance is the cost of the pattern. Note that the distance includes the cost of moving the unspecified tiles when required to place the specified ones, but does not require them to be in any particular order.
    (view changes)
    1:20 pm
  7. page Pattern database edited ... While we normally think of a heuristic as a function computed by an algorithm, any function ca…
    ...
    While we normally think of a heuristic as a function computed by an algorithm, any function can also be computed by a table lookup, given sufficient memory. In fact, for reasons of efficiency, heuristic functions are commonly precomputed and stored in memory.
    Some Definitions:
    ...
    a state). E.g., In the
    A Target pattern: a partial specification of the goal state.
    ...
    particular order.
    Example: The Fringe database uses the Fringe target pattern (picture a). For a given arbitrary 15-Puzzle state (picture b), we map the current locations of tiles 3, 7, 11, 12, 13, 14, 15 and the empty tile into an index into the fringe database. The database will tell us the minimum number of moves required to correctly locate these 8 tiles. This is a lower bound on the remaining search effort. Once the fringe pattern has been achieved, all that is left to solve is an 8-Puzzle. Given more memory we can compute additional pattern databases from the remaining tiles.
    (b) ---------------------------------------------------- (a)
    ...
    Note that the red pattern and the blue pattern are disjoint patterns, i.e. have no tiles in common. The maximum of the heuristic values of the disjoint patterns remains admissible and close to the actual optimal cost.
    This approach mimics the human strategy of "divide and conquer" – solving problems non-optimally by moving some of the elements into their correct locations thereby reducing the complexity of the remaining problem.
    ...
    pattern database.
    On 15-puzzle, IDA* with a heuristic based on the disjoint pattern databases can optimally solve random 15 puzzle instances in less than 29 milliseconds on average. This is about 1700 times faster than with Manhattan Distance on the same machine.
    Reference: {Searching with pattern database (Culberson & Schaeffer 1996).pdf}
    (view changes)
    1:19 pm
  8. page Manhattan Distance edited ... {manhattan_distance_example.png} Random 15-puzzle instances were first solved optimally usin…
    ...
    {manhattan_distance_example.png}
    Random 15-puzzle instances were first solved optimally using IDA* with Manhattan distance heuristic (Korf, 1985). Optimal solution lengths average 53 moves, and on average 400 million nodes were generated.
    ...
    combining other heuristic,heuristics, such as
    ...
    Conflict Heuristic.
    This

    The Manhattan Distance
    heuristic is
    (view changes)
    1:15 pm
  9. page Manhattan Distance edited ... In the following example the Manhattan Distance is 3+6=9 moves: {manhattan_distance_example.…
    ...
    In the following example the Manhattan Distance is 3+6=9 moves:
    {manhattan_distance_example.png}
    ...
    were generated. The average solution time is about 50 seconds on current machines.
    The limitation of the Manhattan Distance heuristic is that it considers each tile independently, while in fact tiles interfere with each other. Higher accuracy can be achieved by combining other heuristic, such as the Linear Conflict Heuristic.
    This heuristic is admissble.
    (view changes)
    1:14 pm
  10. page Manhattan Distance edited Related Problems: N-Puzzle Type:heuristic function The Manhattan Distance is the distance between …
    Related Problems: N-Puzzle Type:heuristic function
    The Manhattan Distance is the distance between two points measured along axes at right angles. The name alludes to the grid layout of the streets of Manhattan, which causes the shortest path a car could take between two points in the city.
    ifFor the 8-puzzle, if xi(s) and
    ...
    the heuristic is (for the 8-puzzle): is:
    {formula.JPG}
    In the following example the Manhattan Distance is 3+6=9 moves:
    (view changes)
    1:12 pm

More