busca a estrela

main.py

from Nos import NOS, INICIO, FINAL, TABELA_DE_CUSTOS


def calcula_distancia(i, j):
    if i < j:
        return TABELA_DE_CUSTOS[i][j]
    else:
        return TABELA_DE_CUSTOS[j][i]

#Função para testar qual a custo do nó n para o nó final
def retorna_funcao_h(destino: int, nodes: list):
    """
    essa funcao retorna outra funcao que calcula o h de um no

    Isso mesmo, uma funcao que retorna outra funcao
    """
    def h(n):
        # funcao recursiva
        # funcao original: nao mais em uso
        def caminhar1(posicao:int, visitados: list, distancia_percorrida: float) -> float:
            adjacentes = nodes[posicao]
            distancias = []
            visitados.add(posicao)
            if posicao == destino:
                return distancia_percorrida
            # TODO: a distancia entre os nos deve ser variavel, e nao cte 1
            distancia_percorrida += 1
            for novo_pos in adjacentes:
                if novo_pos == destino:
                    return distancia_percorrida
                if novo_pos not in visitados:
                    try:
                        distancias.append(
                            caminhar(novo_pos, set(visitados), distancia_percorrida)
                        )
                    except Exception: #pylint: disable=broad-except
                        pass

            # retornar a menor distancia
            return min(distancias)

        # funcao modificada: usa a tabela de custos
        def caminhar2(posicao:int, visitados:list, distancia_percorrida:float)->float:
            # nao ha mais necessidade de caminhar, uma vez que temos uma tabela de custos
            distancia_percorrida += calcula_distancia(posicao,destino)
            return distancia_percorrida


        # funcao modificada: usa a tabela de custos
        def caminhar(posicao:int, visitados:list, distancia_percorrida:float)->float:
            adjacentes = nodes[posicao]
            distancias = []
            visitados.add(posicao)
            if posicao == destino:
                return distancia_percorrida
            distancia_percorrida += calcula_distancia(posicao, destino)
            for novo_pos in adjacentes:
                if novo_pos == destino:
                    return distancia_percorrida
                if novo_pos not in visitados:
                    try:
                        distancias.append(
                            caminhar(novo_pos, set(visitados), distancia_percorrida)
                        )
                    except Exception: #pylint: disable=broad-except
                        pass

            # retornar a menor distancia
            return min(distancias)

        try:
            return caminhar(n,set(), 0)
        except Exception: #pylint: disable=broad-except
            return None

    return h

def retorna_caminho(destino: int, nodes: list, funcao_h):
    """
    essa funcao retorna outra funcao que imprime o caminho percorrido

    Isso mesmo, uma funcao que retorna outra funcao
    """
    def calcular_caminho(n):
        # f eh a soma de g + h
        # ou seja, a posicao do inicio + posicao pro fim
        def calculo_f(pos, g_anterior):
            valor = funcao_h(pos)
            if not valor:
                raise Exception('Não há caminho para determinado destino')
            return g_anterior + valor

        pos = n
        g = 0
        caminho_percorrido = [pos] # comecando pela posicao inicial
        try:
            while True:
                menor = 999999
                idx_menor = -1
                adjacentes = nodes[pos]

                # loop entre os adjacentes
                for caminho in adjacentes:
                    if caminho == destino:
                        # adicionar o destino e acaba o loop
                        caminho_percorrido.append(caminho)
                        # break
                        return caminho_percorrido

                    # ignora nos ja visitados
                    if caminho in caminho_percorrido:
                        continue

                    # _TODO: acho que esse + 1 nao deve ser cte. Deve variar de acordo com
                    # a tabela de custos
                    # heuristica = calculo_f(caminho, g)
                    ultimo_g = calcula_distancia(caminho, caminho_percorrido[-1])
                    heuristica = calculo_f(caminho, ultimo_g)

                    # guardar o menor custo (o menor caminho)
                    # guardar o adjacente com menor custo
                    if heuristica < menor:
                        menor = heuristica
                        idx_menor = caminho

                if idx_menor != -1:
                    pos = idx_menor

                    caminho_percorrido.append(idx_menor)

                    # _TODO: acho que esse + 1 nao deve ser cte. Deve variar de acordo com
                    # a tabela de custos
                    g += calcula_distancia(caminho_percorrido[-1], caminho_percorrido[-2])
                    continue
                else:
                    break
        except Exception: #pylint: disable=broad-except
            return []

        return caminho_percorrido
    return calcular_caminho

def main():
    funcao_h = retorna_funcao_h(FINAL, NOS)

    print("h de INICIO = {}".format(funcao_h(INICIO)))

    calcular_caminho = retorna_caminho(FINAL, NOS, funcao_h)

    # printar caminho
    caminhos = calcular_caminho(INICIO) # recebe a lista para ser transformada em string
    texto = ''
    for i in range(len(caminhos)):
        passagem = caminhos[i]
        if i != 0:
            texto += ' => '
        texto += str(passagem)

    print(texto)

if __name__ == "__main__":
    main()

Nos.py

import numpy as np

# Variável onde seu índice representa a posíção no labirinto
# E seu valor representa os possíveis lugares para se mover
# em outras palavras, a tabela de adjacencia
NOS = [
    [1],#nó 0
    [0, 2, 4, 3],#nó 1
    [1],#nó 2
    [1, 5],#nó 3
    [1, 7],#nó 4
    [3, 6],#nó 5
    [7, 5],#nó 6
    [6, 4],#nó 7
]

INICIO: int = 0
FINAL: int = 7


# a tabela de custos diz quanto custo para ir de uma estacao a outra
# é uma matriz iXj onde i eh a origem e o j o destino e o valor o custo

# usando None pq so precisamos de metade da matriz (1X2 == 2X1)
TABELA_DE_CUSTOS = np.array([
    #0,      1,      2,      3,      4,     5,     6,      7,
    [0,      1,      1,      1,      1,     1,     1,      1,      ], # 0
    [None ,  0,      1,      4,      22,     1,     1,      1,     ], # 1
    [None ,  None,   0,      1,      1,     1,     1,      1,      ], # 2
    [None ,  None,   None,   0,      1,     1,     1,      1,      ], # 3
    [None ,  None,   None,   None,   0,     1,     1,      1,      ], # 4
    [None ,  None,   None,   None,   None,  0,     1,      1,      ], # 5
    [None ,  None,   None,   None,   None,  None,  0,      1,      ], # 6
    [None ,  None,   None,   None,   None,  None,  None,   0,      ], # 7
])

# XX,YY = np.meshgrid(np.arange(TABELA_DE_CUSTOS.shape[1]),np.arange(TABELA_DE_CUSTOS.shape[0]))
# TABELA_DE_CUSTOS_FLAT = np.vstack((TABELA_DE_CUSTOS.ravel(),XX.ravel(),YY.ravel())).T