• Q:JPS那一节3:47,diagonal中的2,5节点的最短距离:6->4->2 = 1 + √2 , 6->x->2 = √2 + 1, 这样看来节点2也应被放弃,节点5同理。 

     

    A: 

    这里没有错。这里其实是讲课时候的一个疏忽,谢谢同学指正。不知道怎么上传图片,那同学们可以打开后面的链接,参照JPS的论文 (http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf) 中的公式1和2。

    可以看到, Look ahead rule的两条本身就是一个是<=的时候prune,一个是<的时候prune。这样做是因为,如果两种规则都是<=,在diagonal中也把2, 5 prune掉,这两个节点就永远不会被看到了。同时,在jump rule里是先straight 再diagonal的移动的,这样,如果前一个条件是<=, 后一个是<, 2, 5 在前一个里面prune后一个里面保留,就不会损失可能的最优性。