食人者与传教士问题python-人工智能算法
Cannibals and missionaries problem python -artificial intelligence algorithm
我正在尝试解决 python 中的 cannibals and missionaries problem（有一些额外的标准，但主要思想是 classic ）。
因此，在 class Graph 中，我初始化状态（食人者的数量、传教士的数量、船上的可用座位、食物单位（如果有，传教士可以喂食食人者）食人者多于传教士），等等
然后我的方法 genereazaSuccesori 无法正常工作，因为我做错了什么，我不知道是什么。所以这个方法应该为一个节点（参数nodCurent）生成后继者。
根据我在 Pycharm 中调试时看到的情况，主要问题是我的程序在执行第三个 for 之前以某种方式退出（我在 listaSuccesori 中追加，因此数组返回是空的。
有谁知道我的代码哪里做错了吗？特别是为什么我的代码不执行第三个 for?
即使 link 在 python 中实现了这个问题的完整示例也会对我有帮助（但是有食物的那个也有食物，因为这里的事情变得更加混乱，基本的很漂亮简单）。
谢谢！
solver.py:
import math
class NodParcurgere:
def __init__(self, info, parinte):
self.info = info
self.parinte = parinte # parintele din arborele de parcurgere
def obtineDrum(self):
l = [self];
nod = self
while nod.parinte is not None:
l.insert(0, nod.parinte)
nod = nod.parinte
return l
def afisDrum(self): # returneaza si lungimea drumului
l = self.obtineDrum()
for nod in l:
print(str(nod))
return len(l)
def contineInDrum(self, infoNodNou):
nodDrum = self
while nodDrum is not None:
if (infoNodNou == nodDrum.info):
return True
nodDrum = nodDrum.parinte
return False
def __repr__(self):
sir = ""
sir += str(self.info) + "\n"
return (sir)
def __str__(self):
sir = ""
sir += str(self.info) + "\n"
return (sir)
class Graph: # graful problemei
def __init__(self, numeFisier):
f = open(numeFisier, "r")
textFisier = f.read()
infoFisier = textFisier.split("\n")
for i in infoFisier:
date_citite = i.split("=");
print(date_citite);
if date_citite[0] == "N1":
Graph.N1 = int(date_citite[1]); # N1 canibali,
if date_citite[0] == "N2":
Graph.N2 = int(date_citite[1]); # N2 misionari
if date_citite[0] == "Nr":
Graph.Nr = int(date_citite[
1]); # La fiecare Nr deplasari cu barca (de la un mal la celalalt) un loc din barca se va degrada
if date_citite[0] == "MalInitial":
Graph.MalInitial = date_citite[1];
if date_citite[0] == "MalFinal":
Graph.MalFinal = date_citite[1];
if date_citite[0] == "M":
Graph.M = int(date_citite[1]);
f.close();
canibali_mal_opus = 0
misionari_mal_opus = 0
pozitie_barca_mal_opus = 0
pozitie_barca_mal_initial = 1
nr_unitati_hrana_opus = 0
nr_unitati_hrana_initial = 0
numar_deplasari = 0;
f = open(numeFisier, "r")
textFisier = f.read()
infoFisier = textFisier.split("\n")
for i in infoFisier:
date_citite = i.split("=");
#print(date_citite);
if date_citite[0] == "K":
nr_unitati_hrana_initial = int(date_citite[1])
self.start = (
Graph.N1, Graph.N2, canibali_mal_opus, misionari_mal_opus, pozitie_barca_mal_initial,
nr_unitati_hrana_initial,
nr_unitati_hrana_opus, numar_deplasari);
# TODO care e starea finala buna?
self.scopuri = [(0, 0, 0, 0, 0, 0, 0, 0)]
#print("stare initiala", self.start);
# nr canibali pe mal initial si pe mal opus
# nr misionari mal initial si mai opus
def genereazaSuccesori(self, nodCurent):
def test_conditie(mis, can):
return mis == 0 or mis >= can
listaSuccesori = []
barca = nodCurent.info[4]
if barca == 1:
canMalCurent = nodCurent.info[0]
misMalCurent = nodCurent.info[1]
canMalOpus = int(Graph.N1) - int(canMalCurent)
misMalOpus = int(Graph.N2) - int(misMalCurent)
hranaMalCurent = nodCurent.info[5]
hranaMalOpus = nodCurent.info[6]
else:
canMalOpus = nodCurent.info[0]
misMalOpus = nodCurent.info[1]
canMalCurent = Graph.N1 - canMalOpus
misMalCurent = Graph.N2 - misMalOpus
hranaMalCurent = nodCurent.info[6]
hranaMalOpus = nodCurent.info[5]
maxMisionariBarca = min(int(Graph.M - nodCurent.info[7] % 3), misMalCurent)
for misBarca in range(0,maxMisionariBarca + 1):
if misBarca == 0:
maxCanibaliBarca = min(Graph.M - nodCurent.info[7] % Graph.Nr, canMalCurent)
minCanibaliBarca = 1 # pt ca barca nu merge singura
else:
maxCanibaliBarca = min(Graph.M - nodCurent.info[7] % 3 - misBarca, canMalCurent,
misBarca + nodCurent.info[5] * 2)
minCanibaliBarca = 0
for canBarca in range(minCanibaliBarca, maxCanibaliBarca + 1):
minHrana = math.ceil(nodCurent.info[0] - nodCurent.info[1] / 2)
maxHrana = min(nodCurent.info[5], Graph.M - misBarca - canBarca)
for hrana in range(minHrana, maxHrana):
hranaBarca = hrana;
canMalCurentNou = canMalCurent - canBarca
misMalCurentNou = misMalCurent - misBarca
canMalOpusNou = canMalOpus + canBarca
misMalOpusNou = misMalOpus + misBarca
nodCurent_list = list(nodCurent.info);
nodCurent_list[7] = nodCurent_list[7]+1;
nodCurent.info = tuple(nodCurent_list)
hranaNou = hranaMalCurent - hranaBarca;
hranaOpus=0;
if(canBarca > misBarca):
hranaOpus = hranaOpus + hranaBarca - canBarca/2;
else:
hranaOpus = hranaOpus + hranaBarca;
if not test_conditie(misMalCurentNou, canMalCurentNou):
continue
if not test_conditie(misMalOpusNou, canMalOpusNou):
continue
if barca == 1: # testul este pentru barca nodului curent (parinte) deci inainte de mutare
infoNodNou = (canMalCurentNou, misMalCurentNou, 0)
else:
infoNodNou = (canMalOpusNou, misMalOpusNou, 1)
if not nodCurent.contineInDrum(infoNodNou):
listaSuccesori.append(NodParcurgere(infoNodNou, nodCurent))
print("lista succesori",listaSuccesori)
return listaSuccesori
def testeaza_scop(self, nodCurent):
return nodCurent.info in self.scopuri;
def __repr__(self):
sir = ""
for (k, v) in self.__dict__.items():
sir += "{} = {}\n".format(k, v)
return (sir)
def breadth_first(gr):
global nrSolutiiCautate
# in coada vom avea doar noduri de tip NodParcurgere (nodurile din arborele de parcurgere)
c = [NodParcurgere(gr.start, None)]
continua = True # variabila pe care o setez la false cand consider ca s-au afisat suficiente solutii
while (len(c) > 0 and continua):
# print("Coada actuala: " + str(c))
# input()
nodCurent = c.pop(0)
if gr.testeaza_scop(nodCurent):
print("Solutie:")
nodCurent.afisDrum()
input()
nrSolutiiCautate -= 1
if nrSolutiiCautate == 0:
continua = False
lSuccesori = gr.genereazaSuccesori(nodCurent)
c.extend(lSuccesori)
def depth_first(gr):
# vom simula o stiva prin relatia de parinte a nodului curent
df(NodParcurgere(gr.noduri.index(gr.start), gr.start, None))
def df(nodCurent):
global nrSolutiiCautate, continua
if not continua:
return
print("Stiva actuala: " + "->".join(nodCurent.obtineDrum()))
input()
if gr.testeaza_scop(nodCurent):
print("Solutie: ", end="")
nodCurent.afisDrum()
nrSolutiiCautate -= 1
if nrSolutiiCautate == 0:
continua = False
lSuccesori = gr.genereazaSuccesori(nodCurent)
for sc in lSuccesori:
df(sc)
#############################################
def dfi(nodCurent, adancime):
global nrSolutiiCautate, continua
if not continua:
return
print("Stiva actuala: " + "->".join(nodCurent.obtineDrum()))
input()
if adancime == 1 and gr.testeaza_scop(nodCurent):
print("Solutie: ", end="")
nodCurent.afisDrum()
nrSolutiiCautate -= 1
if nrSolutiiCautate == 0:
continua = False
return
if adancime > 1:
lSuccesori = gr.genereazaSuccesori(nodCurent)
for sc in lSuccesori:
dfi(sc, adancime - 1)
def depth_first_iterativ(gr):
for i in range(1, gr.nrNoduri + 1):
if nrSolutiiCautate == 0:
break
print("-----------\nAdancime maxima: ", i)
dfi(NodParcurgere(gr.noduri.index(gr.start), gr.start, None), i)
gr = Graph("input.txt")
nrSolutiiCautate = 4
breadth_first(gr)
nrSolutiiCautate = 4
continua = True
# depth_first(gr)
nrSolutiiCautate = 4
continua = True
# depth_first_iterativ(gr)
input.txt:
N1=4
N2=4
K=2
M=2
Nr=3
MalInitial=vest
MalFinal=est
实际输出：
['N1', '4']
['N2', '4']
['K', '2']
['M', '2']
['Nr', '3']
['MalInitial', 'vest']
['MalFinal', 'est']
['']
lista succesori []
为了找出究竟是什么阻止了您看似描述的 for 循环的进入，我在第 126 行提供的脚本中插入了一个简单的 print 语句：
第 124 到 127 行现在改为 （保持原始缩进）：
minHrana = math.ceil(nodCurent.info[0] - nodCurent.info[1] / 2)
maxHrana = min(nodCurent.info[5], Graph.M - misBarca - canBarca)
print(f"minHrana: {minHrana}, maxHrana: {maxHrana}")
for hrana in range(minHrana, maxHrana):
我的输出是：
['N1', '4']
['N2', '4']
['K', '2']
['M', '2']
['Nr', '3']
['MalInitial', 'vest']
['MalFinal', 'est']
['']
minHrana: 2, maxHrana: 1
minHrana: 2, maxHrana: 0
minHrana: 2, maxHrana: 1
minHrana: 2, maxHrana: 0
minHrana: 2, maxHrana: 0
lista succesori []
要使range(start, stop)非空，必须满足条件start < stop。
然而，无论是由于输入还是其他原因，我们观察到 范围 是空的。因此，您的 for 循环恰好执行了 0（换言之：零）次。
我正在尝试解决 python 中的 cannibals and missionaries problem（有一些额外的标准，但主要思想是 classic ）。
因此，在 class Graph 中，我初始化状态（食人者的数量、传教士的数量、船上的可用座位、食物单位（如果有，传教士可以喂食食人者）食人者多于传教士），等等
然后我的方法 genereazaSuccesori 无法正常工作，因为我做错了什么，我不知道是什么。所以这个方法应该为一个节点（参数nodCurent）生成后继者。
根据我在 Pycharm 中调试时看到的情况，主要问题是我的程序在执行第三个 for 之前以某种方式退出（我在 listaSuccesori 中追加，因此数组返回是空的。
有谁知道我的代码哪里做错了吗？特别是为什么我的代码不执行第三个 for?
即使 link 在 python 中实现了这个问题的完整示例也会对我有帮助（但是有食物的那个也有食物，因为这里的事情变得更加混乱，基本的很漂亮简单）。
谢谢！
solver.py:
import math
class NodParcurgere:
def __init__(self, info, parinte):
self.info = info
self.parinte = parinte # parintele din arborele de parcurgere
def obtineDrum(self):
l = [self];
nod = self
while nod.parinte is not None:
l.insert(0, nod.parinte)
nod = nod.parinte
return l
def afisDrum(self): # returneaza si lungimea drumului
l = self.obtineDrum()
for nod in l:
print(str(nod))
return len(l)
def contineInDrum(self, infoNodNou):
nodDrum = self
while nodDrum is not None:
if (infoNodNou == nodDrum.info):
return True
nodDrum = nodDrum.parinte
return False
def __repr__(self):
sir = ""
sir += str(self.info) + "\n"
return (sir)
def __str__(self):
sir = ""
sir += str(self.info) + "\n"
return (sir)
class Graph: # graful problemei
def __init__(self, numeFisier):
f = open(numeFisier, "r")
textFisier = f.read()
infoFisier = textFisier.split("\n")
for i in infoFisier:
date_citite = i.split("=");
print(date_citite);
if date_citite[0] == "N1":
Graph.N1 = int(date_citite[1]); # N1 canibali,
if date_citite[0] == "N2":
Graph.N2 = int(date_citite[1]); # N2 misionari
if date_citite[0] == "Nr":
Graph.Nr = int(date_citite[
1]); # La fiecare Nr deplasari cu barca (de la un mal la celalalt) un loc din barca se va degrada
if date_citite[0] == "MalInitial":
Graph.MalInitial = date_citite[1];
if date_citite[0] == "MalFinal":
Graph.MalFinal = date_citite[1];
if date_citite[0] == "M":
Graph.M = int(date_citite[1]);
f.close();
canibali_mal_opus = 0
misionari_mal_opus = 0
pozitie_barca_mal_opus = 0
pozitie_barca_mal_initial = 1
nr_unitati_hrana_opus = 0
nr_unitati_hrana_initial = 0
numar_deplasari = 0;
f = open(numeFisier, "r")
textFisier = f.read()
infoFisier = textFisier.split("\n")
for i in infoFisier:
date_citite = i.split("=");
#print(date_citite);
if date_citite[0] == "K":
nr_unitati_hrana_initial = int(date_citite[1])
self.start = (
Graph.N1, Graph.N2, canibali_mal_opus, misionari_mal_opus, pozitie_barca_mal_initial,
nr_unitati_hrana_initial,
nr_unitati_hrana_opus, numar_deplasari);
# TODO care e starea finala buna?
self.scopuri = [(0, 0, 0, 0, 0, 0, 0, 0)]
#print("stare initiala", self.start);
# nr canibali pe mal initial si pe mal opus
# nr misionari mal initial si mai opus
def genereazaSuccesori(self, nodCurent):
def test_conditie(mis, can):
return mis == 0 or mis >= can
listaSuccesori = []
barca = nodCurent.info[4]
if barca == 1:
canMalCurent = nodCurent.info[0]
misMalCurent = nodCurent.info[1]
canMalOpus = int(Graph.N1) - int(canMalCurent)
misMalOpus = int(Graph.N2) - int(misMalCurent)
hranaMalCurent = nodCurent.info[5]
hranaMalOpus = nodCurent.info[6]
else:
canMalOpus = nodCurent.info[0]
misMalOpus = nodCurent.info[1]
canMalCurent = Graph.N1 - canMalOpus
misMalCurent = Graph.N2 - misMalOpus
hranaMalCurent = nodCurent.info[6]
hranaMalOpus = nodCurent.info[5]
maxMisionariBarca = min(int(Graph.M - nodCurent.info[7] % 3), misMalCurent)
for misBarca in range(0,maxMisionariBarca + 1):
if misBarca == 0:
maxCanibaliBarca = min(Graph.M - nodCurent.info[7] % Graph.Nr, canMalCurent)
minCanibaliBarca = 1 # pt ca barca nu merge singura
else:
maxCanibaliBarca = min(Graph.M - nodCurent.info[7] % 3 - misBarca, canMalCurent,
misBarca + nodCurent.info[5] * 2)
minCanibaliBarca = 0
for canBarca in range(minCanibaliBarca, maxCanibaliBarca + 1):
minHrana = math.ceil(nodCurent.info[0] - nodCurent.info[1] / 2)
maxHrana = min(nodCurent.info[5], Graph.M - misBarca - canBarca)
for hrana in range(minHrana, maxHrana):
hranaBarca = hrana;
canMalCurentNou = canMalCurent - canBarca
misMalCurentNou = misMalCurent - misBarca
canMalOpusNou = canMalOpus + canBarca
misMalOpusNou = misMalOpus + misBarca
nodCurent_list = list(nodCurent.info);
nodCurent_list[7] = nodCurent_list[7]+1;
nodCurent.info = tuple(nodCurent_list)
hranaNou = hranaMalCurent - hranaBarca;
hranaOpus=0;
if(canBarca > misBarca):
hranaOpus = hranaOpus + hranaBarca - canBarca/2;
else:
hranaOpus = hranaOpus + hranaBarca;
if not test_conditie(misMalCurentNou, canMalCurentNou):
continue
if not test_conditie(misMalOpusNou, canMalOpusNou):
continue
if barca == 1: # testul este pentru barca nodului curent (parinte) deci inainte de mutare
infoNodNou = (canMalCurentNou, misMalCurentNou, 0)
else:
infoNodNou = (canMalOpusNou, misMalOpusNou, 1)
if not nodCurent.contineInDrum(infoNodNou):
listaSuccesori.append(NodParcurgere(infoNodNou, nodCurent))
print("lista succesori",listaSuccesori)
return listaSuccesori
def testeaza_scop(self, nodCurent):
return nodCurent.info in self.scopuri;
def __repr__(self):
sir = ""
for (k, v) in self.__dict__.items():
sir += "{} = {}\n".format(k, v)
return (sir)
def breadth_first(gr):
global nrSolutiiCautate
# in coada vom avea doar noduri de tip NodParcurgere (nodurile din arborele de parcurgere)
c = [NodParcurgere(gr.start, None)]
continua = True # variabila pe care o setez la false cand consider ca s-au afisat suficiente solutii
while (len(c) > 0 and continua):
# print("Coada actuala: " + str(c))
# input()
nodCurent = c.pop(0)
if gr.testeaza_scop(nodCurent):
print("Solutie:")
nodCurent.afisDrum()
input()
nrSolutiiCautate -= 1
if nrSolutiiCautate == 0:
continua = False
lSuccesori = gr.genereazaSuccesori(nodCurent)
c.extend(lSuccesori)
def depth_first(gr):
# vom simula o stiva prin relatia de parinte a nodului curent
df(NodParcurgere(gr.noduri.index(gr.start), gr.start, None))
def df(nodCurent):
global nrSolutiiCautate, continua
if not continua:
return
print("Stiva actuala: " + "->".join(nodCurent.obtineDrum()))
input()
if gr.testeaza_scop(nodCurent):
print("Solutie: ", end="")
nodCurent.afisDrum()
nrSolutiiCautate -= 1
if nrSolutiiCautate == 0:
continua = False
lSuccesori = gr.genereazaSuccesori(nodCurent)
for sc in lSuccesori:
df(sc)
#############################################
def dfi(nodCurent, adancime):
global nrSolutiiCautate, continua
if not continua:
return
print("Stiva actuala: " + "->".join(nodCurent.obtineDrum()))
input()
if adancime == 1 and gr.testeaza_scop(nodCurent):
print("Solutie: ", end="")
nodCurent.afisDrum()
nrSolutiiCautate -= 1
if nrSolutiiCautate == 0:
continua = False
return
if adancime > 1:
lSuccesori = gr.genereazaSuccesori(nodCurent)
for sc in lSuccesori:
dfi(sc, adancime - 1)
def depth_first_iterativ(gr):
for i in range(1, gr.nrNoduri + 1):
if nrSolutiiCautate == 0:
break
print("-----------\nAdancime maxima: ", i)
dfi(NodParcurgere(gr.noduri.index(gr.start), gr.start, None), i)
gr = Graph("input.txt")
nrSolutiiCautate = 4
breadth_first(gr)
nrSolutiiCautate = 4
continua = True
# depth_first(gr)
nrSolutiiCautate = 4
continua = True
# depth_first_iterativ(gr)
input.txt:
N1=4
N2=4
K=2
M=2
Nr=3
MalInitial=vest
MalFinal=est
实际输出：
['N1', '4']
['N2', '4']
['K', '2']
['M', '2']
['Nr', '3']
['MalInitial', 'vest']
['MalFinal', 'est']
['']
lista succesori []
为了找出究竟是什么阻止了您看似描述的 for 循环的进入，我在第 126 行提供的脚本中插入了一个简单的 print 语句：
第 124 到 127 行现在改为 （保持原始缩进）：
minHrana = math.ceil(nodCurent.info[0] - nodCurent.info[1] / 2)
maxHrana = min(nodCurent.info[5], Graph.M - misBarca - canBarca)
print(f"minHrana: {minHrana}, maxHrana: {maxHrana}")
for hrana in range(minHrana, maxHrana):
我的输出是：
['N1', '4']
['N2', '4']
['K', '2']
['M', '2']
['Nr', '3']
['MalInitial', 'vest']
['MalFinal', 'est']
['']
minHrana: 2, maxHrana: 1
minHrana: 2, maxHrana: 0
minHrana: 2, maxHrana: 1
minHrana: 2, maxHrana: 0
minHrana: 2, maxHrana: 0
lista succesori []
要使range(start, stop)非空，必须满足条件start < stop。
然而，无论是由于输入还是其他原因，我们观察到 范围 是空的。因此，您的 for 循环恰好执行了 0（换言之：零）次。