Алгоритм AStar в Python - PullRequest
Новая
       19

Алгоритм AStar в Python

0 голосов
/ 01 декабря 2019

Проблема, которую необходимо решить, - это склад, на который прибывает ряд ящиков, у этих ящиков есть день входа и день выхода. Ящики хранятся в кучах, которые имеют не более MAXSIZE ящиков. Необходимо убедиться, что невозможно хранить коробку с выходным днем ​​после даты, указанной ниже. Я попытался решить эту проблему в python, выполнив следующие функции: 

class Bcolors:
    HEADER = '\033[95m'
    OKBLUE = '\033[94m'
    OKGREEN = '\033[92m'
    WARNING = '\033[93m'
    FAIL = '\033[91m'
    ENDC = '\033[0m'
    BOLD = '\033[1m'
    UNDERLINE = '\033[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

Эта функция отвечает за создание списка ящиков в соответствии с порядком прибытия на склад. 

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)

Эта функция используется в качестве отладки, печатая последнее состояние в качестве аргумента и имея возможность выбирать между зеленым цветом или выводом предупреждения со вторым аргументом функции. 

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

Эта функция рассчитывает стоимость узла в соответствии с его состоянием, чтобы алгоритм AStar мог выбрать следующий узел с наименьшей стоимостью. Цель состоит в том, чтобы использовать как можно меньше батарей, следовательно, используется функция расчета стоимости. 

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

Эта функция получает в качестве входных данных список состояний и возвращает список узлов, новый узел для каждого состояния доставляется какаргумент. 

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

Эта функция отвечает за создание всех возможных состояний для размещения следующего блока в соответствии с прошлым текущим узлом в качестве аргумента. Проблема заключается в том, что, например, при получении в качестве входных данных узла, состояние которого следующее: 

#####################################################################
# 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
#####################################################################

Я надеюсь получить в качестве выходных данных два состояния в списке, соответствующих двум возможным состояниям размещенияполе в стеке 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
#####################################################################

Но вместо этого я получаю следующий список функций: 

#####################################################################
# 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
#####################################################################

Тело выполнения файлавыглядит следующим образом: 

#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)

Я хотел бы знать, как решить проблему функции, отвечающей за создание возможных состояний, на основе узла, полученного в качестве параметра, который соответствует узлу, посещаемому алгоритмом AStar.

...