凤逆天下小说全集免费:人工智能野人传教士过河

第一次俩个野人过河，留下一个野人，回一个野人
第二次一野人一传教士过河，留下一个传教士，回一个野人
第三次俩个教士过河，回一个野人
剩下的就好办了...
(错)
*************************************************************************
汗。。。火星微生物说得对哈，我差点就闹出人命了
试一试：(x:野人,o:传教士)
第一次俩个野人过河，留下一个野人，回一个野人（ xxooo｜x ）
第二次俩个野人过河，留下一个野人，回一个野人(xooo|xx)
第三次俩个传教士过河,回一个野人,一传教士(xxoo|xo)
第四次俩个传教士过河（xx|xooo）........
大家看看，有没有问题（这几天脑袋发昏），欢迎指教：）

 
 
 
三对三有解。
我用 Python 写了搜寻答案的程序。
要知道其它组合有没有解，只要改一改 “mCOUNT, cCOUNT = 3, 3” 这一行然后运行就知道了。
有空的话我会译成 Java 贴上来。

'''
Solve the Missionaries And Cannibals Puzzle by trying all legal moves.

The puzzle imposes two constraints:
    1) Relative headcount: missionaries must be >= cannibals at any point.
    2) Boat capacity: max is two.
'''

def comb( items, r ):
    '''Returns all combinations of elements in items taken r at a time.'''
    if r == 0:
        yield ( )   # Returns tuple to enable direct conversion to set.
    else:
        for i in xrange( len( items ) ):
            for subComb in comb( items[ i + 1 : ], r - 1 ):
                yield ( items[ i ], ) + subComb

# Simply represent the elements of the puzzle by characters.
MISSIONARY, CANNIBAL, BOAT = 'm', 'c', 'B'

mCOUNT, cCOUNT = 3, 3

# Constraint #2: boat capacity.
nMAXCROSSER = 2
nMINCROSSER = 1

class RiverSide:
    '''Represents the state of a riverside.'''
    def __init__( self, men = [ ], boat = [ ] ):
        self.men = men
        self.boat = boat

    def __eq__( self, other ):
        self.men.sort( ); other.men.sort( )
        return self.men == other.men and self.boat == other.boat

    def __repr__( self ):
        return 'BOAT' + `self.boat`.ljust( 8 ) + 'MEN' + `self.men`

    def _xferBoat( self, otherSide ):
        '''To be called only by xferMen( ).'''
        otherSide.boat.append( self.boat.pop( ) )

    def xferMen( self, otherSide, menList ):
        for man in menList:
            otherSide.men.append( self.men.pop( self.men.index( man ) ) )
        # Nice to automate boat xfer here.
        self._xferBoat( otherSide )

    # Constraint #1: relative headcount.
    def fatal( self ):
        '''Returns true iff the cannibals outnumbers missionaries.'''
        mCount = self.men.count( MISSIONARY )
        return mCount and mCount < self.men.count( CANNIBAL )

class RiverScene:
    '''Represents the state of a riverscene.'''
    def __init__( self, sourceSide = RiverSide( ), targetSide = RiverSide( ) ):
        self.source = sourceSide
        self.target = targetSide

    def __eq__( self, other ):
        return self.source == other.source and self.target == other.target

    def __repr__( self ):
        return `self.source` + '\n' + `self.target`

    def fatal( self ):
        return self.source.fatal( ) or self.target.fatal( )

def solve( firstScene, finalScene ):
    '''Returns a list of solution steps if solution's found; else returns None.'''
    def solutionSteps( takenSteps ):
        '''
        The solution searching recursive workhorse function.
        Takes a list containing the first scene and returns a list of
        solution steps leading to the final scene if solution was found.
        Optimizations done:
            1) elimination of equivalent combinations of men to be moved
            2) maximization of headcount to move from source
               (minimization for the reverse direction)
        '''
        lastStep = takenSteps[ - 1 ]
        if lastStep == finalScene: return takenSteps

        from copy import deepcopy
        newStep = deepcopy( lastStep )

        # To enable moving of both direction to share the same chunk of code.
        start, stop, step = nMAXCROSSER, nMINCROSSER - 1, -1
        src, dst = newStep.source, newStep.target
        if dst.boat:
            start, stop, step = nMINCROSSER, nMAXCROSSER + 1, 1
            src, dst = dst, src

        for nCrosser in range( start, stop, step ):
            for men in set( comb( src.men, nCrosser ) ):
                src.xferMen( dst, men )
                if not newStep.fatal( ) and newStep not in takenSteps:
                    takenSteps.append( newStep )
                    sol = solutionSteps( takenSteps )
                    if sol:
                        return sol
                    else:
                        takenSteps.pop( )
                # Rewind before trying next move.
                dst.xferMen( src, men )

    takenSteps = [ firstScene ]
    return solutionSteps( takenSteps )

# Setup.
men =  [ MISSIONARY ] * mCOUNT + [ CANNIBAL ] * cCOUNT
boat = [ BOAT ]
source = RiverSide( men, boat )
target = RiverSide( )
firstScene = RiverScene( source, target )
finalScene = RiverScene( target, source )

print '\nTrying to solve puzzle of', mCOUNT, 'missionaries and', cCOUNT, 'cannibals...\n'
solutionSteps = solve( firstScene, finalScene )
if solutionSteps:
    print 'Solution found:\n\n'
    for step in solutionSteps:
        print step, '\n'
else:
    print 'No solution found.'
 
 
 

LEO_KING11，你的第二次一野一传过到对岸时是二野一传，要闹人命的。

我认为唯一的解决是那三个传教士乘两个野人过河时合力把留下的那个野人推进河里，然后就真的好办了。

好吧，传教士做不出那种事，所以他们应该合力促使那个野人皈依基督，不必杀人也能解决问题。

呵呵。 说真的，我也不认为三野三传能有解。

是不是你搞错了，根本就没有答案的，我编程试了一下，遍历所有组合没有可能的。

除非船上的人到了岸边的话，没有算进去。

处理一下上下船，用一下启发式搜索应该可以的。