Search code examples
a-star

A*: Finding a better solution for 15-square puzzle with one given solution

Given that there is a 15-square puzzle and we will solve the puzzle using a-star search. The heuristic function is Manhattan distance.

Now a solution is provided by someone with cost T and we are not sure if this solution is optimal. With this information provided,

  • Is it possible to find a better solution with cost < T?
  • Is it possible to optimize the performance of searching algorithm?

For this question, I have considered several approaches.

  1. h(x) = MAX_INT if g(x) >= T. That is, the f(x) value will be maximum if the solution is larger than T.
  2. Change the search node as CLOSED state if g(x) >= T.
Solution

  • Is it possible to find a better solution?

    You need to know if T is the optimal solution. If you do not know the optimal solution, use the average cost; a good path is better than the average. If T is already better than average, you don't need to find a new path.

    Is it possible to optimize the performance of the searching algorithm?

    Yes. Heuristics are assumptions that help algorithms to make good decisions. The A* algorithm makes the following assumptions:

    • The best path costs the least (Djikstra's Algorithm - stay near origin of search)
    • The best path is the most direct path (Greedy Search - minimize distance to goal)

    Good heuristics vastly improve performance (A* is useful for this reason). Bad heuristics lead the search away from good solutions and obliterate performance. My advice is to know the game you are searching; in chess, it's generally best to avoid losing a queen, so that may be a good heuristic to use.

    Heuristics will have the largest impact on performance, especially in the case of a 15x15 search space. In larger search spaces (2000x2000), good use of high efficiency data structures like arrays and integers may improve performance.

    Potential solutions

    Both the solutions you provide are effectively the same; if the path isn't as good as the other paths you have, ignore them. Search algorithms like A* do this for you, as j_random_hacker has said in a roundabout manner.

    The OPEN list is a set of possible moves; select the best and ignore the rest. The CLOSED list is the set of moves that have already been selected, not the ones you wish to ignore.

    (1) d(x) = Djikstra's Algorithm 
(2) g(x) = Greedy Search
(3) a*(x) = A* Algorithm = d(x) + g(x)

    To make your A* more greedy (prefer suboptimal but fast solutions), multiply the cost of g(x) to favour a greedy search; (4) a*(x) = d(x) + 1.1 * g(x) I actually tested this in to a search space of 1500x2000. (3), a standard A*, took about 5 seconds to find the goal on the opposite side. (4) took only milliseconds to find the goal, demonstrating the value of using heuristics well.

    You may also add other heuristics to A*, such as:

    • Depth-first search (prefer a greater amount of moves)
    • Bread-first (prefer a smaller amount of moves)
    • Stick to Roads (if terrain determines movement speed, increase the cost of choosing bad terrain)
    • Stay out of enemy territory (if you want to avoid losing units, don't put them in harms way)