古詩詞大全網 - 成語故事 - 怎麽樣判斷壹個八數碼問題有解還是無解啊?

怎麽樣判斷壹個八數碼問題有解還是無解啊?

利用奇偶性判斷所給出的初始狀態有無解.

判別方法是:

以數組為壹維的舉例子.

將八數碼的壹個結點表示成壹個數組a[9],空格用0表示,設臨時函數p(x)定義為:x數所在位置前面的數比x小的數的個數,

其中0空格不算在之內,那設目標狀態為b[9],那r=sigma(p(x)) sigma()表示取所有的x:1-8並求和,

那對於初始狀態a[9],t=sigma(p(x)),如果r和t同為奇數或者同為偶數,那麽該狀態有解,否則無解。

考慮到四種移動方法對sigma(p(x))的影響,左移和右移是不會影響它的值的,

更不會影響奇偶性,如果是上移或者下移就會影響:

上移:壹次上移會使壹個元素向前跳兩個數字的位置,設這兩個數字為a1,a2,

不妨設a1<a2,移的這個數字設為a0,那無非只有以下三次情況:

1,a0<a1<a2,考慮它們三者的p(x)值,p(a0)不變,p(a1)++,p(a2)++,總體增加了2

2,a1<a0<a2,p(a0)--,p(a1)不變,p(a2)++,總體不變

3,a1<a2<a0,p(a0)-=2,p(a1),p(a2)不變,總體減小了2

綜合起來的結論就是不會影響sigma(p(x))的奇偶性。