三只大老虎和三只小老虎过河

         ABCabc<    
---Aa--> BCbc>Aa
<-- A--- ABCbc<a
---bc--> ABC>abc
<-- c--- ABCc<ab
---AB--> Cc>ABab
<--Aa--- ACac<Bb
---Cc--> Aa>BCbc
<--Bb--- ABab<Cc
---AB--> ab>ABCc
<-- c--- abc<ABC
---ac--> b>ABCac
<-- B--- Bb<ACac
---Bb--> >ABCabc
按有限状态机的思路写了个，深度优先遍历.代码好像比楼主的复杂多了，就不贴了
---Bb--> 表示 Bb坐船往右边划 
Aa>BCbc  表示Aa在左边，BCbc在右边，>表示船在右边，<表示船在左边

这个好像是最优问题吧，利用最优控制和遗传算法或者蚁群算法都应该可以求出，不好意思，上学没好好学呀！

还不如叫斑马母子或者角马母子

这是典型的图论搜索问题。建立一个“图”，每个节点是一个状态（每只老虎在哪侧，船在哪侧）
两个节点之间有边，边表示一个状态调走一只或几只老虎，可以转换到另一个状态。
初始状态是6只老虎都在原侧，终结状态就是6只老虎都被转移到对侧。
解法就是找到从初始状态到终结状态的一条路径（最好是最短路径）。

状态分合法状态和非法状态。非法状态就是会有老虎被吃掉。因此搜索的时候，需要避免走到非法状态。
转移需要满足：最多转移两只老虎，而且必须有一只会划船。

这样用简单的BFS就可以了。

最优解法可能有多个，都是13步。

我的实现

module Main where

import List
import Maybe
import Text.Printf

main = putStrLn $ prettyPrintPath $ fromJust $ bfs

data Tiger = BigA | BigB | BigC | SmallA | SmallB | SmallC
            deriving (Show,Eq,Ord)
-- SmallC can drive boat

-- A helper logical function:  a implies b
implies :: Bool -> Bool -> Bool
implies a b = (not a) || b


data State = State Place [Tiger]    deriving (Show,Eq)
data Trans = Trans [Tiger]          deriving (Show,Eq)
data Place = Local | Remote         deriving (Show,Eq)

allTigers = [BigA,BigB,BigC,SmallA,SmallB,SmallC]
bigTigers = [BigA,BigB,BigC]
smallTigers = [SmallA,SmallB,SmallC]
driverTigers = [BigA,BigB,BigC,SmallC]

startingState = State Local allTigers
finalState = State Remote []


-- A state is valid if both side of river is valid
stateValid :: State -> Bool
stateValid (State _ tigers) = localStateValid tigers &&
                              localStateValid (allTigers\\tigers) where

    -- A state is valid on one side of river means
    -- Either there are no big tigers or all small tigers are protected by their mothers
    localStateValid tigers = (noBigTiger tigers) || (allProtected tigers)

    noBigTiger tigers = all (`notElem` tigers) bigTigers

    allProtected tigers = all protected (zip smallTigers bigTigers)
        where protected (small,big) = (small `elem` tigers) `implies` (big `elem` tigers)


-- A transition is valid if there is at most 2 tigers on the boat
-- and at least one of them can drive the boat.
transValid :: Trans -> Bool
transValid (Trans tigers) = length tigers <=2 && any (`elem` tigers) driverTigers


-- Find all possible transition from one state,
-- no matter whether the target state is valid.
findAllTrans :: State -> [Trans]
findAllTrans (State place tigers) = map Trans (if place==Local
                                      then allTransLocal tigers
                                      else allTransLocal (allTigers\\tigers)
                                      ) where

    allTransLocal :: [Tiger] -> [[Tiger]]
    allTransLocal tigers = 
        let (drivers,others) = partition (`elem` driverTigers) tigers
        in [[one] | one <- drivers] ++
           [[one,another] | one <- drivers, another <- others] ++
           anyTwo drivers
        where anyTwo [] = []
              anyTwo [x] = []
              anyTwo (x:xs) = [[x,another] | another <- xs] ++ anyTwo xs

-- Actually perform one transition on a state, return the target state.
-- Tiger lists are sorted for easy comparison.
doTrans :: State -> Trans -> State
doTrans (State Local tigers) (Trans goTigers) = State Remote (sort (tigers\\goTigers))
doTrans (State Remote tigers) (Trans comeTigers) = State Local (sort (tigers++comeTigers))


-- Breadth first search.
-- Search from the initial state to the final state
bfs :: Maybe [(State,Trans,State)]
bfs = bfs' [startingState] [] []

-- Inside algorithm
bfs' :: [State] -> [State] -> [(State,Trans,State)] -> Maybe [(State,Trans,State)]
bfs' [] _ _ = Nothing  -- When queue empty, fail.
bfs' (s:ss) visited transes =  -- s is current state, ss are other states.
    if s == finalState -- When final state reached, success.
    then Just (extractPath transes)
    else 
    if s `elem` visited -- If state visited or visited, discard.
    then bfs' ss visited transes
    else let newVisited = s:visited -- Otherwise mark this state visited.
             allValidTransition =   -- Find all transitions from current state (s), filtered.
                 let allTrans = findAllTrans s
                     allNewStates = map (doTrans s) allTrans
                 in filter (\(s,t,s') -> (stateValid s' && s' `notElem` newVisited))
                     (zip3 (repeat s) allTrans allNewStates) -- only keep valid and unvisited
             newFrontier = ss ++ (map (\(s,t,s') -> s') allValidTransition) -- update queue
             newTranses = allValidTransition ++ transes -- update transition tree
         in bfs' newFrontier newVisited newTranses -- next round
             

-- Given a resulting transition tree (a list of (State,Trans,State))
-- Output a path from startingState to finalState
extractPath sts = reverse $ extractPath' sts finalState
extractPath' _ curState | curState == startingState = []
extractPath' sts curState = let (prevState,trans,_) =
                                 (fromJust $ find (\(s,t,s') -> s' == curState) sts)
                            in (prevState,trans,curState):(extractPath' sts prevState)

-- Pretty print path: print all step and the final state
prettyPrintPath sts = unlines $ ((map prettyPrintStep sts) ++
                        [prettyPrintStateLine $ (\(_,_,s') -> s') $ last sts])

-- Each step consists of the old state and the transition
prettyPrintStep (s,t,s') = (prettyPrintStateLine s) ++ "\n" ++ (prettyPrintTransLine s t)

prettyPrintStateLine (State place tigers) =
    let lhs = prettyPrintTigers tigers
        rhs = prettyPrintTigers (allTigers\\tigers)
        stateLine = printf "[%6s] |            | [%6s]\n" lhs rhs :: String
    in stateLine

prettyPrintTransLine (State place oldTigers) (Trans movingTigers) =
    let moves = prettyPrintTigers movingTigers
        transLine = case place of
            Local  -> printf "           %2s --->" moves :: String
            Remote -> printf "              <--- %2s" moves :: String
    in transLine

prettyPrintTigers = map prettyPrintTiger
prettyPrintTiger tiger = case tiger of
    BigA -> 'A'
    BigB -> 'B'
    BigC -> 'C'
    SmallA -> '1'
    SmallB -> '2'
    SmallC -> '3'

写来写去都成了2只小老虎会划船了，貌似原题是只有一只小老虎会划船吧？

ab      |             A   | BCc   
ab      | A               | BCc   
b       | Aa              | BCc 
这种情况b不会被吃掉么....

这是第一版本，没有考虑主动进攻，第二版已经修正了
steps:38
ABCabc  |                 |
ACac    | Bb              |  
ACac    |             Bb  |  
ACac    |             B   | b 
ACac    | B               | b 
ABCac   |                 | b
ABC     | ac              | b  
ABC     |             ac  | b  
ABC     |             c   | ab  
ABC     | c               | ab  
ABCc    |                 | ab 
Cc      | AB              | ab   
Cc      |             AB  | ab   
Cc      |                 | ABab   
Cc      |             Aa  | Bb   
Cc      | Aa              | Bb   
ACc     | a               | Bb  
AC      | ac              | Bb   
ACa     | c               | Bb  
Aa      | Cc              | Bb   
Aa      |             Cc  | Bb   
Aa      |             c   | BCb   
Aa      |             bc  | BC   
Aa      |             b   | BCc   
Aa      |             Bb  | Cc   
Aa      | Bb              | Cc   
ABab    |                 | Cc 
ab      | AB              | Cc   
ab      |             AB  | Cc   
ab      |                 | ABCc   
ab      |             c   | ABC   
ab      | c               | ABC   
b       | ac              | ABC    
b       |             ac  | ABC    
b       |             c   | ABCa    
b       | c               | ABCa    
        | bc              | ABCa     
        |             bc  | ABCa     
        |                 | ABCabc   

http://www.blogjava.net/xmatthew/archive/2008/11/16/240766.html

这个是本人用Java的实现。

这样的题好像蛮多的啊，农民、羊、草也是这样类的问题好像

很有问题！
ACa     | Bb              | c  
ACa     |             Bb  | c  
ACa     |             B   | bc 
这一步难道B不会吃掉c？