奇偶剪枝:
對于從起始點 s 到達 終點 e,走且隻走 t 步的可達性問題的一種剪枝政策。
如下列矩陣 :
從任意 0 到達 任意 0,所需步數均為偶數,到達任意 1 ,均為奇數。反之亦然
是以有,若s走且隻走 t 步可到達e,則必有t >= abs(s.x - e.x) + abs(s.y - e.y),且 (t&1) == ((abs(s.x - e.x) + abs(s.y - e.y))&1)。
否則必不可達。
奇偶剪枝:
對于從起始點 s 到達 終點 e,走且隻走 t 步的可達性問題的一種剪枝政策。
如下列矩陣 :
從任意 0 到達 任意 0,所需步數均為偶數,到達任意 1 ,均為奇數。反之亦然
是以有,若s走且隻走 t 步可到達e,則必有t >= abs(s.x - e.x) + abs(s.y - e.y),且 (t&1) == ((abs(s.x - e.x) + abs(s.y - e.y))&1)。
否則必不可達。