MacOSX10.10.3上Python2.7.9中的神秘无限循环

Question

我编写了一个Python脚本来解决"Fox, goose and bag of beans puzzle"。我用ABM（基于代理的模型）编写代码。每一件需要运送过河的东西都是一个乘客的物品。河边还有两块陆地是太空物体。在

代码运行良好，可以解决原始问题。但是，一旦我尝试初始化对象（例如peasant2、fox2），就会发生无限循环。我是说我只是初始化了。我从来没有把它们放在实际的模拟中。因此，如果取消对行num 170（#fox2=Passenger（'fox'，'rooster'）的注释，就会发生无限循环。有趣的是，你可以初始化额外的谷物或公鸡，但不能初始化农民或狐狸。我想这可能是由于随机模块，所以我试着用

random.seed(some_int)

但这并没有解决任何问题。在

有趣的是，代码在Windows10Python2.7.4上运行良好。我试过用另一个Mac，但它也有无限循环。 是Mac问题还是Python问题？我的密码怎么了？在

无误编码

^{pr2}$

具有无限循环的代码

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

---

编辑： 我根据@hammergene的建议。我把窃听器修好了

travel_back(...)

并补充道

__eq__ and __hash__

致乘客（）。不过，我不确定这个问题是否完全解决了。在

Answer 1

无限循环的原因是算法中的一个错误：travel_back不是随机洗牌，而是选择第一个不安全的乘客。如果它恰好是刚刚到达的那个，它就变成了no op，它会被无限期地重复。如果在此处添加随机随机洗牌，程序将始终终止：

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__和{}操作，它们的默认实现（在自定义类中）只是使用对象的内存地址。在

在您的例子中，分配一个额外的对象会改变后续分配的内存地址，这反过来又会改变对象在send_off操作后的排序方式，并影响到travel_back将选择哪一个。如果不进行洗牌，它将始终是同一个对象：要么是好的选择（没有循环），要么是坏的，这取决于它们的内存地址。在

添加散列/相等运算符将消除是否有一个额外对象的神秘依赖性，并使程序的行为更具确定性：它要么总是陷入无限循环（如果尚未修复travel_back），要么永远不会：

^{pr2}$