請數(shù)學高手幫忙證明算法。

Magicloud

前幾天看到hdu 1195：
Now an emergent task for you is to open a password lock. The password is consisted of four digits. Each digit is numbered from 1 to 9.
Each time, you can add or minus 1 to any digit. When add 1 to '9', the digit will change to be '1' and when minus 1 to '1', the digit will change to be '9'. You can also exchange the digit with its neighbor. Each action will take one step.

Now your task is to use minimal steps to open the lock.

Note: The leftmost digit is not the neighbor of the rightmost digit.
我用如下代碼解，其中用到了兩個假設(shè)：
1. 對于給定操作步驟，操作順序可以打亂。（將各位編號，交換同時交換編號，增減操作綁定編號）
2. 對于可通過純交換實現(xiàn)的變化，則最少交換步驟等同于將源組合冒泡排序至目標組合。

calculate函數(shù)求解，參數(shù)為 源狀態(tài) 終狀態(tài)，結(jié)果為 (最少步數(shù), _)

1. import Data.Maybe
   
2. import Data.List
   
3. 
   
4. steps4Exchange :: [ Int ] -> Int
   
5. steps4Exchange dst =
   
6.   snd $ iterate swapPass (dst, 0) !! (length dst - 1)
   
7.   where swapPass ([ x ], i) = ([ x ], i)
   
8.         swapPass (x : y : zs, i)
   
9.           | x > y =
   
10.             let (xs, i') = swapPass (x : zs, i + 1) in
    
11.             (y : xs, i')
    
12.           | otherwise =
    
13.               let (xs, i') = swapPass (y : zs, i) in
    
14.               (x : xs, i')
    
15. 
    
16. steps4Move :: [ Int ] -> [ Int ] -> Int
    
17. steps4Move src dst =
    
18.   sum $ map (\(s, i) ->
    
19.               let d = dst !! i in
    
20.               min (abs (d - s)) (9 + s - d)
    
21.            ) $ zip src [ 0 .. ]
    
22. 
    
23. calculate :: [ Int ] -> [ Int ] -> (Int, [ Int ])
    
24. calculate src dst =
    
25.   let src' = zip src [ 0 .. ] in
    
26.   foldl1 (\(a, a') (b, b') ->
    
27.            if a > b then
    
28.              (b, b')
    
29.            else
    
30.              (a, a')
    
31.         ) $ map (\mid' ->
    
32.                    let mid = fst $ unzip mid' in
    
33.                    (steps4Exchange (snd $ unzip mid') + steps4Move mid dst, mid)
    
34.                 ) $ permutations src'

復制代碼

daybreakcx

這個貌似是BFS獲取最小步數(shù)吧，你想證明什么{:3_196:}

Magicloud

這個貌似是BFS獲取最小步數(shù)吧，你想證明什么
daybreakcx 發(fā)表于 2010-08-31 20:50

    算是個bfs的應(yīng)用優(yōu)化問題吧。目的是減少需要遍歷的元素。