python - Python中的AStar算法(AStar algorithm in Python)

Question

The problem to be solved is a warehouse to which a series of boxes are arriving, these boxes have an entry day and an exit day.

(要解决的问题是一系列箱子到达的仓库，这些箱子有入库日和出库日。)

The boxes are stored in piles which have at most MAXSIZE boxes.

(盒子被堆放在堆里，最多有MAXSIZE个盒子。)

It has to be fulfilled that it is not possible to store a box with an exit day after the one below.

(必须满足的是，不可能在下一个出口日之后的一天存放一个箱子。)

I have tried to solve this problem in python by performing the following functions:

(我试图通过执行以下功能来解决python中的此问题：)

class Bcolors:
    HEADER = '33[95m'
    OKBLUE = '33[94m'
    OKGREEN = '33[92m'
    WARNING = '33[93m'
    FAIL = '33[91m'
    ENDC = '33[0m'
    BOLD = '33[1m'
    UNDERLINE = '33[4m'

class Caja:
    def __init__ (self, id, entrada, salida):
        self.id = id
        self.entrada = entrada
        self.salida = salida

    def to_string (self):
        return "Caja(" + str(self.id) + "," + str(self.entrada) + "," + str(self.salida) + ")"

class Pila:
    def __init__ (self, cajas, disponible, total):
        self.cajas = cajas
        self.disponible = disponible
        self.total = total

class Estado:
    def __init__ (self, pilas, cajaColocada):
        self.pilas = pilas
        self.cajaColocada = cajaColocada

class Nodo:
    def __init__ (self, estado, posibilidades, visitado, coste):
        self.estado = estado
        self.posibilidades = posibilidades
        self.visitado = visitado
        self.coste = coste

    def __lt__(self, other):
        return self.coste < other.coste

def crea_cajas():
    cajas = []

    cajas.append(Caja(9,1,17))
    cajas.append(Caja(10,1,17))
    cajas.append(Caja(11,1,17))
    cajas.append(Caja(12,1,17))
    cajas.append(Caja(13,1,17))
    cajas.append(Caja(14,1,17))
    cajas.append(Caja(15,1,17))
    cajas.append(Caja(16,1,17))
    cajas.append(Caja(17,1,17))
    cajas.append(Caja(18,1,17))
    cajas.append(Caja(19,1,17))
    cajas.append(Caja(20,1,17))
    cajas.append(Caja(3,1,18))
    cajas.append(Caja(4,1,18))
    cajas.append(Caja(5,1,18))
    cajas.append(Caja(6,1,18))
    cajas.append(Caja(7,1,18))
    cajas.append(Caja(8,1,18))
    cajas.append(Caja(1,1,19))
    cajas.append(Caja(2,1,19))

    return cajas

This function is in charge of creating the list of boxes according to the order of arrival at the warehouse.

(此功能负责根据到达仓库的顺序创建箱子列表。)

def imprime_estado(estado, type):
    global MAXSIZE, MAXPILAS;

    if type == 1:
        print(Bcolors.OKGREEN + "#####################################################################")
    else:
        print(Bcolors.WARNING + "#####################################################################")
    print("# Caja colocada en este estado:" + str(estado.cajaColocada))
    print("# Coste del estado:" + str(calcula_coste(estado)))
    for i in range(MAXPILAS):
        disponible = estado.pilas[i].disponible
        if disponible == MAXSIZE:
            print("# PILA " + str(i))
            print("# - NONE")
        else:
            print("# PILA " + str(i))
            for j in range(MAXSIZE - estado.pilas[i].disponible):
                print("# - " + estado.pilas[i].cajas[j].to_string())
    print("#####################################################################" + Bcolors.ENDC)

This function is used as a debug, printing the last state as an argument and being able to select between the green or warning output with the second argument of the function.

(此函数用作调试，将最后一个状态作为参数打印，并可以在绿色或警告输出与函数的第二个参数之间进行选择。)

def calcula_coste(estado):
    global MAXSIZE, MAXPILAS;
    coste = 0

    for i in range(MAXPILAS):
        if estado.pilas[i].disponible == MAXSIZE:
            continue
        coste = coste + 1 + (MAXSIZE/(MAXSIZE - estado.pilas[i].disponible))

    return coste

This function calculates the cost of the node according to its state so that the AStar algorithm can select the next lowest cost node.

(此功能根据其状态计算节点的成本，以便AStar算法可以选择下一个成本最低的节点。)

The objective is to use as few batteries as possible, hence the cost calculation function.

(目的是使用尽可能少的电池，因此具有成本计算功能。)

def genera_nodos(estados):
    numero_estados = len(estados)
    nodos = []

    for i in range(numero_estados):
        nodos.append(Nodo(estados[i],None,0,calcula_coste(estados[i])))

    return nodos

This function receives as input a list of states and returns a list of nodes, a new node for each state delivered as an argument.

(该函数接收状态列表作为输入，并返回节点列表，每个状态的新节点作为参数传递。)

def genera_estados(nodo_actual, cajas_entrada):
    global MAXSIZE, MAXPILAS;
    estados_posibles = []
    caja_actual = None
    caja_siguiente = None

    if nodo_actual.estado == None:
        pilas_estado = []
        for i in range(MAXPILAS):
            cajas_pila = []
            if i == 0:
                cajas_pila.append(cajas_entrada[0])
                pilas_estado.append(Pila(cajas_pila,MAXSIZE-1,MAXSIZE))
            else:
                pilas_estado.append(Pila([],MAXSIZE,MAXSIZE))
        estados_posibles.append(Estado(pilas_estado,0))
    else:
        pilas_actual = nodo_actual.estado.pilas
        caja_actual = nodo_actual.estado.cajaColocada
        caja_siguiente = caja_actual + 1
        for i in range(MAXPILAS):
            if pilas_actual[i].disponible == 0:
                continue
            elif pilas_actual[i].disponible == MAXSIZE:
                nuevo_estado = Estado(pilas_actual,caja_siguiente)
                nuevo_estado.pilas[i].cajas.append(cajas_entrada[caja_siguiente])
                nuevo_estado.pilas[i].disponible = MAXSIZE - 1
                estados_posibles.append(nuevo_estado)
                break
            else:
                if pilas_actual[i].cajas[MAXSIZE-1-pilas_actual[i].disponible].salida < cajas_entrada[caja_siguiente].salida:
                    continue
                else:
                    nuevo_estado = Estado(pilas_actual,caja_siguiente)
                    nuevo_estado.pilas[i].disponible = pilas_actual[i].disponible - 1
                    nuevo_estado.pilas[i].cajas.append(cajas_entrada[caja_siguiente])
                    estados_posibles.append(nuevo_estado)

    for estado in estados_posibles:
        imprime_estado(estado, 2)
    return estados_posibles

This function is in charge of creating all the possible states to place the next box according to the past current node as an argument.

(该函数负责创建所有可能的状态，以根据过去的当前节点作为参数放置下一个框。)

The problem is in this function that for example when receiving as input the node whose state is the following:

(问题在于此功能，例如，当接收状态为以下状态的节点作为输入时：)

#####################################################################
# box in this state en:0
# cost :5.0
# PILE 0
# - Caja(9,1,17)
# PILE 1
# - NONE
# PILE 2
# - NONE
# PILE 3
# - NONE
# PILE 4
# - NONE
#####################################################################

I hope to receive as output two states in a list, corresponding to the two possible states of placing the box in stack 1 above the already located or placing it in stack 2:

(我希望在列表中收到两个状态作为输出，分别对应于将框放在已定位的堆栈1上方或将其放在堆栈2中的两种可能状态：)

#####################################################################
# box in this state en:1
# cost :3
# - Caja(9,1,17)
# - Caja(10,1,17)
# PILA 1
# - NONE
# PILA 2
# - NONE
# PILA 3
# - NONE
# PILA 4
# - NONE
#####################################################################
#####################################################################
# box in this state en:1
# cost :10
# - Caja(9,1,17)
# PILA 1
# - Caja(10,1,17)
# PILA 2
# - NONE
# PILA 3
# - NONE
# PILA 4
# - NONE
#####################################################################

But instead I get the following list of function:

(但是相反，我得到了以下功能列表：)

#####################################################################
# box in this state:1
# cost:8.0
# PILA 0
# - Caja(9,1,17)
# - Caja(10,1,17)
# PILA 1
# - Caja(10,1,17)
# PILA 2
# - NONE
# PILA 3
# - NONE
# PILA 4
# - NONE
#####################################################################
#####################################################################
# box in this state en:1
# cost:8.0
# PILA 0
# - Caja(9,1,17)
# - Caja(10,1,17)
# PILA 1
# - Caja(10,1,17)
# PILA 2
# - NONE
# PILA 3
# - NONE
# PILA 4
# - NONE
#####################################################################

The execution body of the file is as follows:

(文件的执行主体如下：)

#Se declaran las dos listas de nodos
nodos_posibles = []
nodos_visitados = []
estado_final = None

#Se caragan las cajas de entrada
cajas_entrada = crea_cajas()

#Se crea el nodo inicial
nodo_inicial = Nodo(None,None,1,0)
nodos_visitados.append(nodo_inicial)

#Se crean los estados desde los que se puede ir del nodo inicial
estados_posibles = genera_estados(nodo_inicial, cajas_entrada)
nodos_posibles = genera_nodos(estados_posibles)
nodo_inicial.posibilidades = nodos_posibles

#Comienza el algoritmo
while True:
    if len(nodos_posibles) == 0:
        break
    nodo_actual = nodos_posibles[0]
    imprime_estado(nodo_actual.estado, 1)
    nodos_posibles.pop(0)
    nodo_actual.visitado = 1
    if (nodo_actual.estado.cajaColocada == len(cajas_entrada)-1):
        estado_final = nodo_actual.estado
        break
    estados_posibles = genera_estados(nodo_actual, cajas_entrada)
    if len(estados_posibles) == 0:
        nodo_actual.posibilidades = None
        nodos_visitados.append(nodo_actual)
        continue
    nodos_alcanzables = genera_nodos(estados_posibles)
    for i in range(len(nodos_alcanzables)):
        #imprime_estado(nodos_alcanzables[i].estado,2)
        nodos_posibles.append(nodos_alcanzables[i])
    nodo_actual.posibilidades = nodos_alcanzables
    nodos_visitados.append(nodo_actual)

if estado_final == None:
    print("NO SE PUEDEN COLOCAR LAS PILAS CON ESA ENTRADA DE CAJAS")
else:
    print(Bcolors.OKBLUE + "ESTADO FINAL ENCONTRADO")
    imprime_estado(estado_final)

I would like to know how to solve the problem of the function in charge of creating the possible states based on the node received as parameter that corresponds to the node visited by the AStar algorithm.

(我想知道如何解决负责根据作为AStar算法访问的节点的参数接收的节点创建可能状态的功能的问题。)

  ask by mss translate from so

Answer 1

等待大神答复