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.Approaches:  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? 
How to compare A* with DP approach in finding shortest Path?
algorithms;algorithm analysis;dynamic programming;shortest path;heuristics