Two Algorithms for Finding k Shortest Paths of a Weighted Pushdown Automaton
Table 1:
['Item', '[ITALIC] β', '[ITALIC] γ']
Unfortunately, though we now spend less time in pre-computing the heuristic, the actual A* search usually ends up taking much longer because of the inexactness. To see why, notice that any instantiation of an item with a weight smaller than the shortest accepting path has to be visited, even if it will only be used in an accepting path far longer than the k shortest ones. When using H1, the following are instantiated before reaching the 1-shortest path: s⇝s:0(H1=0+3=3,Q={q1⇝q1:0})q1⇝q1:0(H1=0+3=3,Q={q1⇝q2:1,q1⇝q3:0})q1⇝q2:1(H1=1+2=3,Q={q1⇝q4:2,q1⇝q3:0})q1⇝q4:2(H1=2+1=3,Q={s⇝q6:2,q1⇝ q3:0})s⇝q6:2(H1=2+1=3,Q={s⇝ f:3,q1⇝ q3:0})s⇝f:3(H1=3+0=3,Q={q1⇝q3:0}) However, when H2 is used, the following are instantiated before the 1-shortest, q1⇝q1:0(H2=0+0=0,Q={q1⇝q3:0,q1⇝q2:1,s⇝s:0})q1⇝ q3:0(H2=0+0=0,Q={q1⇝ q5:0,q1⇝q2:1,s⇝s:0})q1⇝ q5:0(H2=0+0=0,Q={q1⇝ q7:0,q1⇝q2:1,s⇝s:0})q1⇝q7:0(H2=0+0=0,Q={q1⇝q8:0,q1⇝q2:1,s⇝s:0})q1⇝q8:0(H2=0+0=0,Q={q1⇝q2:1,s⇝s:0,s⇝ f:4})q1⇝q2:1(H2=1+1=2,Q={q1⇝q4:2,s⇝s:0,s⇝f:4})q1⇝q4:2(H2=2+0=2,Q={s⇝s:0,s⇝f:4})s⇝s:0(H2=0+3=3,Q={s⇝q6:0,s⇝f:4})s⇝q6:2(H2=2+1=3,Q={s⇝f:3,s⇝ f:4})s⇝f:3(H2=3+0=3,Q={s⇝f:4}) H2 ends up visiting more instantiations along the path from q1 to q8 because that path is shorter in the scope of the enclosing parentheses. The following closing parenthesis completely flips the position, but this is some information H1 “knows” while H2 does not. In practice, we find this happens so frequently that H2 fails to output the shortest path within a reasonable amount of time.