Consider a hypercube defined over $n$ dimensions where the edges are associated to strictly positive weights, and nodes are marked with $n$ bit-strings, e.g. the source is marked as (0,0,0) in a 3-dimension hypercube and the farthest node is marked as (1,1,1) (termed as 'target'). Any two neighboring nodes differ by precisely 1 bit.

Task: Find the shortest path from source to target on the given hypercube.

1) Dynamic programming approach. --- Complexity $O(n2^{n})$
2) A$^*$ approach.

What are the factors on which these two approaches can be compared apart from run-time and space requirements?

I tried to run an experiment and found A$^*$ discovers 103 different paths (I meant 103 different new entries where added to priority Queue of A$^*$) before reaching the goal state on a weighted hypercube over 5 dimensions. Since the graph had only $2^5 = 32$ nodes, how could I have compared the no of nodes touched by A$^*$ was less than DP approach which covers the whole graph.

Is it correct that efficiency of A* over DP is $103/(5* 2^{5})$ as mentioned in the above example?

  • 1
    $\begingroup$ The performance of A$^*$ strongly depends on the accuracy of your heuristic function. In case it is perfectly informed then A$^*$ only expands nodes along the optimal path; if it is extremely poor (ie., h(n)=0 $\forall n$) then it behaves as Dijkstra (or Uniform Cost Search). So far, what is the heuristic function you are using here? By the way, the number of entries in the priority queue of A$^*$ are the number of paths traversed so far, ... do not confuse it with the number of nodes $\endgroup$ – Carlos Linares López Feb 27 '16 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.