奇偶剪枝

s———​​——+​|+​​​|​​​​+———e如圖,為一般情況下非最短路徑的任意走法舉例,step2=14; step2-step1=6,偏移路徑為6,偶數(易證); 故,若t-[abs(ex-sx)+abs(ey-sy)]結果為非偶數(奇數),則無法在t步恰好到達;

是數據結構的搜尋中,剪枝的一種特殊小技巧。
現假設起點為(sx,SY),終點為(ex,ey),給定t步恰好走到終點,
s ​ ​ ​ ​
| ​ ​ ​ ​
| ​ ​ ​ ​
| ​ ​ ​ ​
+ e
如圖所示(“|”豎走,“—”橫走,“+”轉彎),易證abs(ex-sx)+abs(ey-sy)為此問題類中任意情況下,起點到終點的最短步數,記做step,此處step1=8;
s ​
​ + ​
| + ​ ​ ​
| ​ ​ ​ ​
+ e
如圖,為一般情況下非最短路徑的任意走法舉例,step2=14;
step2-step1=6,偏移路徑為6,偶數(易證);
故,若t-[abs(ex-sx)+abs(ey-sy)]結果為非偶數(奇數),則無法在t步恰好到達;
返回,false;
反之亦反。

相關詞條

熱門詞條

聯絡我們