比较短的一个农夫，狼，羊白菜过河问题的解

[Xinyu LIU]

题目很熟悉了，一个农夫，带了狼，羊，白菜要过一条河，有一艘小船。
一次只能带一个东西。求最快的过河方案。

这是一个著名的BFS search的应用了，主要是建模可以稍微做点文章。

令狼=1，羊=2，白菜=4，农夫=8，河的两岸可以看作两个整数，一开始是15, 0；
要通过一系列的规则变换到0, 15。用这个建模的好处是：
每次把8或4, 2, 1三个中的一个从一个整数减去，然后加到另外一个整数上去。
结果不能为3，不能为6，并且不能和历史重复以避免循环。

根据这个建模，程序可以写得比较短（Haskell的例子）：

import Data.Bits -- for bitwise operation

solve = bfsSolve [[(15, 0)]] where
    bfsSolve :: [[(Int, Int)]] -> [(Int, Int)]
    bfsSolve [] = []
    bfsSolve (c:cs) | (fst $ head c) == 0 = reverse c
                    | otherwise = bfsSolve (cs ++ map (:c)
                                      (filter (`valid` c) $ moves $ head c))
    valid (a, b) r = not $ or [ a `elem` [3, 6], b `elem` [3, 6], (a, b) `elem` r]

moves (a, b) = if a .&. 8  /= 0 then trans a b else map swap (trans b a) where
    trans x y = (x - 8, y + 8):[(x .&. (7 - i), y .|. (8 + i))
                                    | i <-[1, 2, 4], (x .&. i) /= 0]
    swap (x, y) = (y, x)

这个程序仅仅找出第一个解，当然可以很方便的扩展它找出所有的解。为了打印出的
结果比较好看，可以写个从整数翻译成农夫，狼，羊，白菜的函数：

toWgc = unlines . map (\(a, b)-> wgc a ++ "----" ++ wgc b) where
    wgc x = show $ map snd $ filter (\(i, _) ->  x .&. i /= 0)
                         [(1, "wolf"), (2, "goat"), (4, "cabbage"), (8, "farmer")]

这样输出如下：putStrLn $ toWgc $ solve
["farmer","cabbage","goat","wolf"]----[]
["cabbage","wolf"]----["farmer","goat"]
["farmer","cabbage","wolf"]----["goat"]
["cabbage"]----["farmer","goat","wolf"]
["farmer","cabbage","goat"]----["wolf"]
["goat"]----["farmer","cabbage","wolf"]
["farmer","goat"]----["cabbage","wolf"]
[]----["farmer","cabbage","goat","wolf"]

Larry, LIU Xinyu
https://sites.google.com/site/algoxy/
https://github.com/liuxinyu95/AlgoXY

[faen zhang]

在 2013年12月31日 下午3:52，Xinyu LIU <liuxi...@gmail.com>写道：

比较好看，可以写个从整数翻译

为啥不能用int中的bit位表示呢？ 

[Xinyu LIU]

注意到这个解实际上正是用了4个bit表示。

Larry, LIU Xinyu
https://sites.google.com/site/algoxy/
https://github.com/liuxinyu95/AlgoXY

2013/12/31 faen zhang <zhan...@gmail.com>

在 2013年12月31日 下午3:52，Xinyu LIU <liuxi...@gmail.com>写道：

比较好看，可以写个从整数翻译

为啥不能用int中的bit位表示呢？ 

--
 
---
您收到此邮件是因为您订阅了 Google 网上论坛的“TopLanguage”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 pongba+un...@googlegroups.com。
要查看更多选项，请访问 https://groups.google.com/groups/opt_out。