Voronoi-assisted Parallel Bidirectional Heuristic Search - Advances in Computational Science and Engineering - page 81

Result 1 : For the vast majority of tests (more than 80% of test cases), the X-nodes
used in algorithm PBA*-VD are more likely to aid in establishing a path connecting S
and G than the X-nodes used by algorithm PBA*-R. This is illustrated by Table 1.

Table 1. IDA-3 probes for possible search space intersection

PBA*-R PBA*-VD Winner

16,642 25,937 PBA*-VD

15,573 38,015 PBA*-VD

27,980 27,462

PBA*-R

35,753 43,784

PBA*-VD

1,106 3,380 PBA*-VD

28,756 29,584 PBA*-VD

56,574 72,625

PBA*-VD

15,605 19,599 PBA*-VD

239,480 231,296 PBA*-R

61,741 73,515 PBA*-VD

28,598 31,534

PBA*-VD

227,819 235,092 PBA*-VD

150,297 153,509 PBA*-VD

48,063 58,671 PBA*-VD

165,146 205,781 PBA*-VD

69,090 85,686 PBA*-VD

143,781 132,448 PBA*-R

Total 1,332,004 1,467,918

Average 78,353 86,348

wins of PBA*-VD over PBA *-R 82.35%

Note, for all but three cases in Table 1, algorithm PBA*-VD probes more times for
search space intersection.
Result 2 : The overhead for incorporating the Voronoi-Dijkstra method in finding
useful X-nodes is negligible . This is illustrated by Table 2.

Table 2. Total overhead (over all test puzzles)

method Total (sec)

PBA*-R 6,435

PBA*-VD 6,103

GRN overhead 16.437

D/D overhead 8.819

Total Overhead (GRN + D/D) 25