我写了一个 Python 脚本来解决 "Fox, goose and bag of beans puzzle" .我在 ABM(基于代理的模型)中编写了代码。每一件需要运过河的东西都是一个 Passenger 对象。河边的两 block 土地也是空间物体。
代码运行良好，解决了原来的问题。但是，一旦我尝试初始化对象(例如 peaman2、fox2)，就会发生无限循环。我的意思是我只初始化了。我从来没有把它们放在实际的模拟中。因此，如果取消注释行 num 170(#fox2 = Passenger('fox', 'rooster'))，就会发生无限循环。有趣的是你可以初始化额外的 Cereal 或公鸡，但不能初始化农民或狐狸。我认为这可能是由于随机模块，所以我尝试用
设置种子random.seed(some_int)
但是并没有解决任何问题。
这是有趣的部分；该代码在 Windows 10 Python 2.7.4 上运行良好。我试过另一台 Mac，但它也会有无限循环。 是 Mac 问题还是 Python 问题？我的代码有什么问题？
没有错误的代码
from sets import Set
import random
from itertools import *
class Passenger(object):
""" Anything that gets on board on the boat.
Assumed that there could be multiple captains """
def __init__(self, species, food=None, is_captain=False):
self.species = species
self.food = food
self.is_captain = is_captain
def eat(self, something):
return self.food == something.species
def __str__(self):
return "I am %s" % self.species
class Space(object):
"""docstring for """
def __init__(self, name, residents=[]):
self.name = name
self.residents = residents
self.captains = self.update_captains()
def num_residents(self):
return len(self.residents)
## e.g. send_off([traveller1, traveller2])
def send_off(self, passengers):
''' Remove the passengers who left for the other land.
It means that the number of captains in the land is changed. '''
self.residents = list(Set(self.residents) - Set(passengers))
self.captains = self.update_captains()
## e.g. welcome([sailing_captain, traveller])
def welcome(self, passengers):
''' Append newcomers '''
self.residents += passengers
self.captains = self.update_captains()
def update_captains(self):
return [r for r in self.residents if r.is_captain]
def pick_a_captain(self):
''' Pick a captain randomly '''
return random.choice(self.captains)
def print_resident_species(self):
''' Simply print out every species in the land.
For debug purpose '''
for r in self.residents:
print r.species
def get_resident_species(self):
''' e.g. Returns "fox, grain,"
"fox, grain, peasant" '''
species = [r.species for r in self.residents]
return ', '.join(species)
def __str__(self):
return self.name + ": " + self.get_resident_species()
''' Stand-alone functions '''
def get_captains(residents):
return [r for r in residents if r.is_captain]
def is_peaceful_pair(pair):
''' e.g. is_peaceful_pair([fox, rooster]) => False '''
p1 = pair[0]
p2 = pair[1]
return not p1.eat(p2) and not p2.eat(p1)
def is_peaceful(residents):
''' e.g. is_peaceful([fox, rooster, grain]) => False '''
for pair in list(permutations(residents, r=2)):
if not is_peaceful_pair(pair):
return False
return True
def select_traveller(from_):
for t in from_.residents:
## Figure out if the rest of the residents will get along
if is_peaceful(list(Set(from_.residents) - Set([t]))):
from_.send_off([t])
return t
return None
def get_sailing_captain(from_):
sailing_captain = from_.pick_a_captain()
from_.send_off([sailing_captain])
return sailing_captain
## e.g. travel_to_destination(korea, japan)
## If succeeds, return passengers. If not, return None(stop the simulation)
def travel_to_destination(from_, to):
'''
Randomly pick one traveller and figures out whether the rest will be safe.
Loop until find one and if not, this simulation should end.
'''
if len(from_.captains) == 0:
## No captain, no simulation
print "There is no captain who can sail a boat :("
return None
sailing_captain = get_sailing_captain(from_)
## Shuffle the residents list so that you always get a random traveller
random.shuffle(from_.residents)
traveller = select_traveller(from_)
if traveller != None:
passengers = [sailing_captain, traveller]
to.welcome(passengers)
return passengers
else:
return None
## e.g. travel_back(japan, korea):
##
def travel_back(from_, to):
sailing_captain = get_sailing_captain(from_)
## Shuffle the residents list so that you always get a random traveller
if is_peaceful(from_.residents):
to.welcome([sailing_captain])
return [sailing_captain]
else:
traveller = select_traveller(from_)
passengers = [sailing_captain, traveller]
to.welcome(passengers)
return passengers
def get_passenger_name(passengers):
return tuple(p.species for p in passengers)
def print_land_info(lands):
for l in lands:
print l
peasant = Passenger('human', is_captain=True)
''' IF I UNCOMMENT THE NEXT LINE OUT, THE INFINITE LOOP HAPPENS!!! '''
#fox2 = Passenger('fox', 'rooster')
fox = Passenger('fox', 'rooster')
rooster = Passenger('rooster', 'grain')
#rooster2 = Passenger('rooster', 'grain')
grain = Passenger('grain')
#grain2 = Passenger('grain')
korea = Space('Korea', [peasant, fox, rooster, grain])
japan = Space('Japan')
POPULATION = korea.num_residents()
CAPTAIN = get_captains(korea.residents)
i = 1
while True:
print "Loop", i
passengers = travel_to_destination(korea, japan)
if passengers == None:
print "The journey can't be continued"
break
if japan.num_residents() == POPULATION:
print "Everyone has crossed the river safely!"
print_land_info([japan, korea])
break
else:
print "Korea ---> Japan", get_passenger_name(passengers)
print_land_info([japan, korea])
passengers = travel_back(japan, korea)
print "Japan ---> Korea", get_passenger_name(passengers)
print_land_info([japan, korea])
print "========================"
i += 1
无限循环代码
from sets import Set
import random
from itertools import *
class Passenger(object):
""" Anything that gets on board on the boat.
Assumed that there could be multiple captains """
def __init__(self, species, food=None, is_captain=False):
self.species = species
self.food = food
self.is_captain = is_captain
def eat(self, something):
return self.food == something.species
def __str__(self):
return "I am %s" % self.species
class Space(object):
"""docstring for """
def __init__(self, name, residents=[]):
self.name = name
self.residents = residents
self.captains = self.update_captains()
def num_residents(self):
return len(self.residents)
## e.g. send_off([traveller1, traveller2])
def send_off(self, passengers):
''' Remove the passengers who left for the other land.
It means that the number of captains in the land is changed. '''
self.residents = list(Set(self.residents) - Set(passengers))
self.captains = self.update_captains()
## e.g. welcome([sailing_captain, traveller])
def welcome(self, passengers):
''' Append newcomers '''
self.residents += passengers
self.captains = self.update_captains()
def update_captains(self):
return [r for r in self.residents if r.is_captain]
def pick_a_captain(self):
''' Pick a captain randomly '''
return random.choice(self.captains)
def print_resident_species(self):
''' Simply print out every species in the land.
For debug purpose '''
for r in self.residents:
print r.species
def get_resident_species(self):
''' e.g. Returns "fox, grain,"
"fox, grain, peasant" '''
species = [r.species for r in self.residents]
return ', '.join(species)
def __str__(self):
return self.name + ": " + self.get_resident_species()
''' Stand-alone functions '''
def get_captains(residents):
return [r for r in residents if r.is_captain]
def is_peaceful_pair(pair):
''' e.g. is_peaceful_pair([fox, rooster]) => False '''
p1 = pair[0]
p2 = pair[1]
return not p1.eat(p2) and not p2.eat(p1)
def is_peaceful(residents):
''' e.g. is_peaceful([fox, rooster, grain]) => False '''
for pair in list(permutations(residents, r=2)):
if not is_peaceful_pair(pair):
return False
return True
def select_traveller(from_):
for t in from_.residents:
## Figure out if the rest of the residents will get along
if is_peaceful(list(Set(from_.residents) - Set([t]))):
from_.send_off([t])
return t
return None
def get_sailing_captain(from_):
sailing_captain = from_.pick_a_captain()
from_.send_off([sailing_captain])
return sailing_captain
## e.g. travel_to_destination(korea, japan)
## If succeeds, return passengers. If not, return None(stop the simulation)
def travel_to_destination(from_, to):
'''
Randomly pick one traveller and figures out whether the rest will be safe.
Loop until find one and if not, this simulation should end.
'''
if len(from_.captains) == 0:
## No captain, no simulation
print "There is no captain who can sail a boat :("
return None
sailing_captain = get_sailing_captain(from_)
## Shuffle the residents list so that you always get a random traveller
random.shuffle(from_.residents)
traveller = select_traveller(from_)
if traveller != None:
passengers = [sailing_captain, traveller]
to.welcome(passengers)
return passengers
else:
return None
## e.g. travel_back(japan, korea):
##
def travel_back(from_, to):
sailing_captain = get_sailing_captain(from_)
## Shuffle the residents list so that you always get a random traveller
if is_peaceful(from_.residents):
to.welcome([sailing_captain])
return [sailing_captain]
else:
traveller = select_traveller(from_)
passengers = [sailing_captain, traveller]
to.welcome(passengers)
return passengers
def get_passenger_name(passengers):
return tuple(p.species for p in passengers)
def print_land_info(lands):
for l in lands:
print l
peasant = Passenger('human', is_captain=True)
peasant2 = Passenger('human', is_captain=True)
''' IF I UNCOMMENT THE NEXT LINE OUT, THE INFINITE LOOP HAPPENS!!! '''
fox2 = Passenger('fox', 'rooster')
fox = Passenger('fox', 'rooster')
rooster = Passenger('rooster', 'grain')
#rooster2 = Passenger('rooster', 'grain')
grain = Passenger('grain')
#grain2 = Passenger('grain')
korea = Space('Korea', [peasant, fox, rooster, grain])
japan = Space('Japan')
POPULATION = korea.num_residents()
CAPTAIN = get_captains(korea.residents)
i = 1
while True:
print "Loop", i
passengers = travel_to_destination(korea, japan)
if passengers == None:
print "The journey can't be continued"
break
if japan.num_residents() == POPULATION:
print "Everyone has crossed the river safely!"
print_land_info([japan, korea])
break
else:
print "Korea ---> Japan", get_passenger_name(passengers)
print_land_info([japan, korea])
passengers = travel_back(japan, korea)
print "Japan ---> Korea", get_passenger_name(passengers)
print_land_info([japan, korea])
print "========================"
i += 1
编辑: 我 updated code根据@hamstergene 的建议。我修复了
中的错误travel_back(...)
并添加
__eq__ and __hash__
到乘客()。但是，我不确定问题是否已完全解决。
最佳答案
无限循环的原因是您的算法中的错误:travel_back 没有进行随机洗牌，而是选择了第一个不安全的乘客。如果那恰好是刚刚到达的那一个，它就变成空操作，无限期地重复。如果您在那里添加随机洗牌，程序将始终终止:
def travel_back(from_, to):
sailing_captain = get_sailing_captain(from_)
## Shuffle the residents list so that you always get a random traveller
if is_peaceful(from_.residents):
to.welcome([sailing_captain])
return [sailing_captain]
else:
random.shuffle(from_.residents) # <---
# ....
“神秘”依赖于创建额外对象的原因是集合和字典依赖于 __hash__ 和 __eq__ 操作，它们的默认实现(在自定义类中) 只需使用对象的内存地址。
在你的例子中，分配一个额外的对象会改变后续分配的内存地址，这反过来会改变对象在 list(Set(...)-Set(...)) 之后排序的方式 send_off 中的操作，并影响 travel_back 将选择的乘客。如果不进行混洗，它将始终是同一个对象:要么是好的选择(无循环)，要么是坏的选择，具体取决于它们的内存地址。
添加散列/相等运算符将消除是否拥有一个额外对象的神秘依赖性，并使您的程序的行为更具确定性:它要么总是陷入无限循环(如果您没有修复 travel_back 还没有)，或者从不:
class Passenger(object):
# [...skipped...]
def __eq__(self, other):
return self.species == other.species
def __hash__(self):
return self.species.__hash__()
关于python - Mac OS X 10.10.3 上 Python 2.7.9 中的神秘无限循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31156337/