4

I have coded A-star Algorithm for 15-puzzle using just Manhattan Heuristic and Manhattan and linear conflict heuristic.

My question is, can for some specific puzzle instances linear conflict cause more nodes to be created and explored than Manhattan heuristic alone using a-Star?

Since most of the puzzle instances I tried solving through my program which require <50 Moves solve in decent time with the given memory using just Manhattan and solve faster combining it with linear conflict as heuristic, instances which require >50 Moves causes the program to run indefinitely and hang up my machine, but for a specific problem which takes 42 moves is solved by my program in ~8 seconds using Manhattan but using linear conflict on the same causes the program to run indefinitely and hang up my machine.

I have gone through my code over and over and I can't find an error in my linear conflict or Manhattan heuristic code.Thus, this general question to make sure.

The following instance causes the problem as stated above.

2,8,7,11                 //Takes 42 Moves to solve
5,0,4,15
13,9,14,3
1,10,6,12
PhoenixDD
  • 121
  • 1
  • 2
  • 12

2 Answers2

7

Both Manhattan Heuristic and Manhattan with linear conflict are admissible heuristics, i.e. they never overestimate the effort to reach the goal. In addition, Manhattan with linear conflict is more informed than simple Manhattan.

We say a heuristic h2 dominates, or is more informed than a heuristic h1 if h2(n) >= h1(n) for every node n. In this case, A* using h2 as heuristic will always expand a subset of the nodes expanded by h1. Answering your question, A* with the Manhattan and linear conflict heuristic can not expand more nodes, in fact, can not expand any node that was not expanded by A* with the simple Manhattan heuristic, i.e. the set of nodes expanded by A* with Manhattan-linear-conflict is a subset of the nodes expanded by A* with plain Manhattan.

Try to review your code with the debugger and find this scenario, this will probably help you finding the bug in the implementation.

For a more formal answer I encourage you to read carefully this post.

Regarding your issue with your machine hanged up in difficult problems, A* must store all closed and open nodes, incurring in exponential waste of memory. To solve 15-puzzle problems go for iterative deepening (IDA*) where the execution time and memory consumption are better.

Community
  • 1
  • 1
FrankS101
  • 2,112
  • 6
  • 26
  • 40
  • Yes I figured the issue in my program, I still wanted to keep the question to make sure. Also let me ask it in a different way, can using linear conflict cause the right path to goal be chosen later than using manhattan for some problem? I hope you understand what I am trying to ask here. – PhoenixDD Mar 04 '16 at 07:38
  • 5
    In summary, yes, it can happen, but I don't have space in a comment to answer this. Elaborate that in a new question and I will answer there. – FrankS101 Mar 04 '16 at 08:47
0

While, as stated by FrankS101, it is not possible that using the Manhattan distance heuristic with linear conflict will expand more nodes than simply using manhttan distance, it IS possible that it will take more time. This is due to the fact that calculating manhattan distance with linear conflict will make the algorithm "spend" more time at each node, as it takes more time to calculate this heuristic.

oded betzalel
  • 213
  • 3
  • 10
  • This may be true but only for very rare cases since when linear conflict is used the number of nodes expanded reduce so drastically compared to manhattan that the time difference between calculating linear conflict + Manhattan and just Manhattan seems trivial as the algorithm still works considerably faster than just using Manhattan! :) – PhoenixDD Mar 27 '16 at 07:08