食人族和传教士问题python人工智能算法

Question

我正在尝试用python解决cannibals and missionaries problem（使用一些附加标准，但主要思想是经典标准）

因此，在类Graph中，我初始化状态（食人者的数量、传教士的数量、船上的可用座位、食物单位（如果食人者比传教士多，传教士可以喂养食人者），等等

然后我有一个方法genereazaSuccesori，该方法不起作用，因为我做错了什么，我不知道是什么。所以这个方法应该为一个节点（参数nodCurent）生成后续节点

从我在Pycharm中调试时看到的情况来看，主要问题是，我的程序在执行第三个for（我在listaSuccesori中追加）之前以某种方式退出，因此返回的数组是空的

有人知道我的代码做错了什么吗？特别是为什么我的代码不执行第三个

即使是一个用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 []

Answer 1

为了找出到底是什么阻止了您似乎描述的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 []

要使^{}为非空，它必须满足条件start < stop

然而，无论是由于输入还是其他原因，我们观察到的是范围为空。因此，您的for循环被精确执行0次（换句话说：零次）