请数学高手帮忙证明算法。

Question

前几天看到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.
我用如下代码解，其中用到了两个假设：
1. 对于给定操作步骤，操作顺序可以打乱。（将各位编号，交换同时交换编号，增减操作绑定编号）
2. 对于可通过纯交换实现的变化，则最少交换步骤等同于将源组合冒泡排序至目标组合。

calculate函数求解，参数为 源状态 终状态，结果为 (最少步数, _)

1. import Data.Maybe
2. import Data.List
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')
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 .. ]
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'

复制代码

Answer 1

这个貌似是BFS获取最小步数吧，你想证明什么
daybreakcx 发表于 2010-08-31 20:50

    算是个bfs的应用优化问题吧。目的是减少需要遍历的元素。

Answer 2

这个貌似是BFS获取最小步数吧，你想证明什么{:3_196:}