Missionários em segurança com canibais

O intuito desse trabalho é gerenciar o uso do barco para que todos os missionários da paróquia do Frei Sardinha consiga atravessar o rio em segurança na companhia dos queridos indígenas Caetés. Mas para garantir a segurança de todos, principalmente dos missionários, existem algumas regras que devem ser respeitadas.

Primeiramente, o problema considera duas margens do rio: a margem inicial (esquerda) e a margem de destino (direita). Todos os indivíduos começam na margem inicial e devem ser transportados para a margem de destino.

O transporte é realizado por meio de um barco, que possui capacidade limitada, podendo transportar no máximo um número fixo de pessoas por travessia.

Regras

As regras que regem o problema são as seguintes:

• O barco deve sempre transportar pelo menos uma pessoa, o barco nunca se desloca sozinho.
• Em nenhuma das margens do rio pode haver um número de indígenas maior que o de missionários, caso exista pelo menos um missionário presente naquela margem. Caso contrário, os missionários seriam colocados em risco.

Índice

1. Como usar
2. Definições iniciais
3. Validação
4. BFS - Busca em Largura
5. DFS - Busca em Profundidade
6. DLS - Busca em Profundidade Limitada
7. Playground

Como usar

com todas as células compiladas é possível utilizar no final do arquivo o playground, todos os 3 cenários estão prontos com métricas para serem retornados, é possível configurar o número de missionários, de canibais e o tamanho do barco em todos os algorítmos, no de Busca por Profundidade limitada também é possível definir, o limite inicial e o limite máximo.

Definições iniciais

from time import perf_counter
from collections import deque

# possibilita que os parâmetros possam ser redefinidos conforme necessidade do cenário
def set_initial_state(missionaries=3, cannibals=3, boat="left"):
    state = {
        "left": (missionaries, cannibals),
        "right": (0, 0),
        "boat": boat
    }
    return state
initial_state = set_initial_state()

#melhora a qualidade de exibição das métricas e estatísticas
def print_metrics(metrics):
    match(metrics):
        case {"tipo": "dls", "sucesso": False}:
            print(f"❌ Tempo de execução: {metrics['tempo_de_execução']:.6f} s")
        case _:
            print("\n📊 MÉTRICAS DE EXECUÇÃO")
            print("=" * 35)
        
            print(f"Sucesso: {'✅' if metrics['sucesso'] else '❌'}")
        
            print(f"Tempo de execução: {metrics['tempo_de_execução']:.6f} s")
        
            print(f"Estados verificados: {metrics['estados_verificados']:,}".replace(",", "."))
            print(f"Nós gerados: {metrics['nodes_gerados']:,}".replace(",", "."))
            print(f"Nós expandidos: {metrics['nodes_expandidos']:,}".replace(",", "."))
        
            print(f"Tamanho máximo da {metrics['estrutura']}: {metrics['tamanho_maximo_estrutura']:,}".replace(",", "."))
        
            profundidade = metrics["profundidade_solucao"]
            if profundidade is not None:
                print(f"Profundidade da solução: {profundidade}")
            else:
                print("Profundidade da solução: —")
        
            print("=" * 35)

Validação

A validação consiste em verificar em cada margem, se há mais canibais que missionarios.

def is_valid(state):
    left_missionaries, left_cannibals = state["left"]
    right_missionaries, right_cannibals = state["right"]

    if min(left_missionaries, left_cannibals, right_missionaries, right_cannibals) < 0:
        return False

    if left_missionaries > 0 and left_cannibals > left_missionaries:
        return False

    if right_missionaries > 0 and right_cannibals > right_missionaries:
        return False

    return True

Função sucessor

É listado todos os movimentos possíveis de acordo com a quantidade de lugares no barco, por meio da soma do valor dos index, é possível comparar quantas pessoas de cada cultura cabe no espaço do barco.

def possible_moves(boat_capacity):
    moves = []
    
    for m in range(boat_capacity + 1):
        for c in range(boat_capacity + 1):
            total = m + c
            
            if 1 <= total <= boat_capacity:
                moves.append((m, c))
    
    return moves

possible_moves(2) # Um exemplo de uso com o máximo de duas pessoas no barco

[(0, 1), (0, 2), (1, 0), (1, 1), (2, 0)]

Com isso, podemos finalmente criar a função que aplica os movimentos:

def apply_move(state, move):
    missionaries, cannibals = move
    left_missionaries, left_cannibals = state["left"]
    right_missionaries, right_cannibals = state["right"]

    if state["boat"] == "left":
        return {
            "left": (left_missionaries - missionaries, left_cannibals - cannibals),
            "right": (right_missionaries + missionaries, right_cannibals + cannibals),
            "boat": "right"
        }
    else:
        return {
            "left": (left_missionaries + missionaries, left_cannibals + cannibals),
            "right": (right_missionaries - missionaries, right_cannibals - cannibals),
            "boat": "left"
        }

# Test
initial_state = set_initial_state(3, 3)
new_state = apply_move(initial_state, (2, 1))
print(new_state)
print("Válido?", is_valid(new_state))

{'left': (1, 2), 'right': (2, 1), 'boat': 'right'}
Válido? False

Explicação da função sucessor

A função sucessor é responsável por gerar, a partir de um estado atual, todos os próximos estados possíveis que podem ser alcançados em uma única travessia do barco. Para isso, ela combina três etapas já definidas anteriormente:

1. Obtém todos os movimentos possíveis por meio da função possible_moves() (combinações de missionários e canibais que cabem no barco).
2. Aplica cada movimento ao estado atual com a função apply_move(state, move), produzindo um novo estado candidato.
3. Valida esse novo estado com is_valid(new_state), descartando automaticamente estados que violam as regras do problema.

Ao final, a função retorna uma lista de pares (movimento, novo_estado). Essa estrutura é essencial para os algoritmos de busca (como o BFS), pois permite explorar o espaço de estados de forma sistemática, mantendo apenas transições válidas e seguras.

def successors(state, boat_capacity):
    result = []

    for move in possible_moves(boat_capacity):
        new_state = apply_move(state, move)

        if is_valid(new_state):
            result.append((move, new_state))

    return result

def is_goal(state):
    return state["left"] == (0, 0)

BFS - Busca em Largura

Com o auxílo de uma fila, o algorítmo percorre linha por linha da arvore, mantendo o mesmo nível na busca por uma solução, tende a percorrer a árvore toda e só para quando encontra um resultado, o resultado tende a ser o mais curto em passos.

from collections import deque
from time import perf_counter

def solve_bfs(initial_state, boat_capacity, optimized=False):
    start_time = perf_counter()

    def state_to_key(state):
        return (state["left"], state["right"], state["boat"])

    initial_key = state_to_key(initial_state)

    queue = deque([{
        "state": initial_state,
        "path": [],
        "movements": [(0, 0)],
        "path_keys": {initial_key}
    }])

    visited = {initial_key} if optimized else None

    generated_nodes = 1
    expanded_nodes = 0
    max_queue_size = 1

    while queue:
        max_queue_size = max(max_queue_size, len(queue))

        node = queue.popleft()
        expanded_nodes += 1

        state = node["state"]
        path = node["path"]
        movements = node["movements"]
        path_keys = node["path_keys"]

        if is_goal(state):
            end_time = perf_counter()
            solution = path + [state]

            success_metrics = {
                "sucesso": True,
                "tempo_de_execução": end_time - start_time,
                "estados_verificados": len(visited) if optimized else generated_nodes,
                "nodes_gerados": generated_nodes,
                "nodes_expandidos": expanded_nodes,
                "tamanho_maximo_estrutura": max_queue_size,
                "estrutura": "fila",
                "profundidade_solucao": len(solution) - 1,
                "tipo": "bfs",
                "otimizado": optimized
            }

            return solution, movements, success_metrics

        for move, new_state in successors(state, boat_capacity):
            state_key = state_to_key(new_state)

            if optimized:
                # Evita revisitar estados já descobertos globalmente
                if state_key in visited:
                    continue
            else:
                # Evita apenas ciclos dentro do caminho atual
                if state_key in path_keys:
                    continue

            queue.append({
                "state": new_state,
                "path": path + [state],
                "movements": movements + [move],
                "path_keys": path_keys | {state_key}
            })

            if optimized:
                visited.add(state_key)

            generated_nodes += 1

    end_time = perf_counter()

    failed_metrics = {
        "sucesso": False,
        "tempo_de_execução": end_time - start_time,
        "estados_verificados": len(visited) if optimized else generated_nodes,
        "nodes_gerados": generated_nodes,
        "nodes_expandidos": expanded_nodes,
        "tamanho_maximo_estrutura": max_queue_size,
        "estrutura": "fila",
        "profundidade_solucao": None,
        "tipo": "bfs",
        "otimizado": optimized
    }

    return None, None, failed_metrics

def scenario_bfs(missionaries = 3, cannibals = 3, boat_size = 2, optimized = True):
    initial_state = set_initial_state(missionaries, cannibals)
    solution, movements, metrics = solve_bfs(initial_state, boat_size, optimized)
    
    if solution and movements:
        
        total_steps = len(movements) - 1  # ignorando (0,0)
        print(f"Resolvido em {total_steps} passos.")
    
        if total_steps > 20:
            print("Solução muito longa, não será exibida.")
        else:
            print("\nGabarito da travessia:")
            boat_side = "left"
        
            for step, move in enumerate(movements[1:], start=1):
                missionaries, cannibals = move
                origin = "esquerda" if boat_side == "left" else "direita"
                destination = "direita" if boat_side == "left" else "esquerda"
        
                missionaries_label = "missionário" if missionaries == 1 else "missionários"
                cannibals_label = "canibal" if cannibals == 1 else "canibais"
        
                print(
                    f"Passo {step}: levar {missionaries} {missionaries_label} e "
                    f"{cannibals} {cannibals_label} da margem {origin} para a margem {destination}."
                )
        
                boat_side = "right" if boat_side == "left" else "left"
    else:
        print("Nenhuma solução encontrada")
    
    print_metrics(metrics)
scenario_bfs()

Resolvido em 11 passos.

Gabarito da travessia:
Passo 1: levar 0 missionários e 2 canibais da margem esquerda para a margem direita.
Passo 2: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 3: levar 0 missionários e 2 canibais da margem esquerda para a margem direita.
Passo 4: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 5: levar 2 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 6: levar 1 missionário e 1 canibal da margem direita para a margem esquerda.
Passo 7: levar 2 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 8: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 9: levar 0 missionários e 2 canibais da margem esquerda para a margem direita.
Passo 10: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 11: levar 0 missionários e 2 canibais da margem esquerda para a margem direita.

📊 MÉTRICAS DE EXECUÇÃO
===================================
Sucesso: ✅
Tempo de execução: 0.000140 s
Estados verificados: 15
Nós gerados: 15
Nós expandidos: 15
Tamanho máximo da fila: 3
Profundidade da solução: 11
===================================

---

DFS - Busca em Profundidade

A busca em profundidade explora um caminho até o fim antes de voltar (backtracking) para tentar alternativas. Aqui, usamos uma pilha para controlar os estados pendentes e também evitamos revisitar estados já explorados.

from time import perf_counter

def solve_dfs(initial_state, boat_capacity, optimized=False):
    start_time = perf_counter()

    def state_to_key(state):
        return (state["left"], state["right"], state["boat"])

    initial_key = state_to_key(initial_state)

    stack = [{
        "state": initial_state,
        "path": [],
        "movements": [(0, 0)],
        "path_keys": {initial_key}
    }]

    visited = {initial_key} if optimized else None

    generated_nodes = 1
    expanded_nodes = 0
    max_stack_size = 1

    while stack:
        max_stack_size = max(max_stack_size, len(stack))

        node = stack.pop()
        expanded_nodes += 1

        state = node["state"]
        path = node["path"]
        movements = node["movements"]
        path_keys = node["path_keys"]

        if is_goal(state):
            end_time = perf_counter()
            solution = path + [state]

            success_metrics = {
                "sucesso": True,
                "tempo_de_execução": end_time - start_time,
                "estados_verificados": len(visited) if optimized else generated_nodes,
                "nodes_gerados": generated_nodes,
                "nodes_expandidos": expanded_nodes,
                "tamanho_maximo_estrutura": max_stack_size,
                "estrutura": "pilha",
                "profundidade_solucao": len(solution) - 1,
                "tipo": "dfs",
                "otimizado": optimized
            }

            return solution, movements, success_metrics

        for move, new_state in successors(state, boat_capacity):
            state_key = state_to_key(new_state)

            if optimized:
                # Evita revisitar estados já explorados globalmente
                if state_key in visited:
                    continue
            else:
                # Evita ciclos apenas no caminho atual
                if state_key in path_keys:
                    continue

            stack.append({
                "state": new_state,
                "path": path + [state],
                "movements": movements + [move],
                "path_keys": path_keys | {state_key}
            })

            if optimized:
                visited.add(state_key)

            generated_nodes += 1

    end_time = perf_counter()

    failed_metrics = {
        "sucesso": False,
        "tempo_de_execução": end_time - start_time,
        "estados_verificados": len(visited) if optimized else generated_nodes,
        "nodes_gerados": generated_nodes,
        "nodes_expandidos": expanded_nodes,
        "tamanho_maximo_estrutura": max_stack_size,
        "estrutura": "pilha",
        "profundidade_solucao": None,
        "tipo": "dfs",
        "otimizado": optimized
    }

    return None, None, failed_metrics

def scenario_dfs(missionaries = 3, cannibals = 3, boat_size = 2, optimized = True):
    initial_state = set_initial_state(missionaries, cannibals)
    solution_dfs, movements_dfs, metrics = solve_dfs(initial_state, boat_size, optimized)
    
    if solution_dfs and movements_dfs:
        
        total_steps = len(movements_dfs) - 1  # ignorando (0,0)
        print(f"Resolvido em {total_steps} passos.")
    
        if total_steps > 20:
            print("Solução muito longa, não será exibida.")
        else:
            print("\nGabarito da travessia (DFS):")
            boat_side = "left"
        
            for step, move in enumerate(movements_dfs[1:], start=1):
                missionaries, cannibals = move
                origin = "esquerda" if boat_side == "left" else "direita"
                destination = "direita" if boat_side == "left" else "esquerda"
        
                missionaries_label = "missionário" if missionaries == 1 else "missionários"
                cannibals_label = "canibal" if cannibals == 1 else "canibais"
        
                print(
                    f"Passo {step}: levar {missionaries} {missionaries_label} e "
                    f"{cannibals} {cannibals_label} da margem {origin} para a margem {destination}."
                )
        
                boat_side = "right" if boat_side == "left" else "left"
    else:
        print("Nenhuma solução encontrada com DFS")
    
    print_metrics(metrics)
scenario_dfs()

Resolvido em 11 passos.

Gabarito da travessia (DFS):
Passo 1: levar 1 missionário e 1 canibal da margem esquerda para a margem direita.
Passo 2: levar 1 missionário e 0 canibais da margem direita para a margem esquerda.
Passo 3: levar 0 missionários e 2 canibais da margem esquerda para a margem direita.
Passo 4: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 5: levar 2 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 6: levar 1 missionário e 1 canibal da margem direita para a margem esquerda.
Passo 7: levar 2 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 8: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 9: levar 0 missionários e 2 canibais da margem esquerda para a margem direita.
Passo 10: levar 1 missionário e 0 canibais da margem direita para a margem esquerda.
Passo 11: levar 1 missionário e 1 canibal da margem esquerda para a margem direita.

📊 MÉTRICAS DE EXECUÇÃO
===================================
Sucesso: ✅
Tempo de execução: 0.000184 s
Estados verificados: 15
Nós gerados: 15
Nós expandidos: 12
Tamanho máximo da pilha: 4
Profundidade da solução: 11
===================================

---

DLS - Busca em Profundidade Limitada

A busca em profundidade limitada (Depth-Limited Search) funciona como a DFS, mas com um limite máximo de profundidade. Isso evita que a busca avance indefinidamente em ramos muito longos e permite controlar o custo de exploração.

def solve_dls(initial_state, current_depth_limit, boat_capacity, optimized=False):
    start_time = perf_counter()

    def state_to_key(state):
        return (state["left"], state["right"], state["boat"])

    initial_key = state_to_key(initial_state)

    stack = [{
        "state": initial_state,
        "path": [],
        "movements": [(0, 0)],
        "depth": 0,
        "path_keys": {initial_key}
    }]

    visited = {initial_key} if optimized else None

    generated_nodes = 1
    expanded_nodes = 0
    max_stack_size = 1

    while stack:
        max_stack_size = max(max_stack_size, len(stack))

        node = stack.pop()
        expanded_nodes += 1

        state = node["state"]
        path = node["path"]
        movements = node["movements"]
        depth = node["depth"]
        path_keys = node["path_keys"]

        if is_goal(state):
            end_time = perf_counter()
            solution = path + [state]

            success_metrics = {
                "sucesso": True,
                "tempo_de_execução": end_time - start_time,
                "estados_verificados": len(visited) if optimized else generated_nodes,
                "nodes_gerados": generated_nodes,
                "nodes_expandidos": expanded_nodes,
                "tamanho_maximo_estrutura": max_stack_size,
                "estrutura": "pilha",
                "profundidade_solucao": len(solution) - 1,
                "tipo": "dls",
                "otimizado": optimized
            }

            return solution, movements, success_metrics

        if depth >= current_depth_limit:
            continue

        for move, new_state in successors(state, boat_capacity):
            state_key = state_to_key(new_state)

            if optimized:
                # Evita revisitar estados já explorados globalmente
                if state_key in visited:
                    continue
            else:
                # Evita ciclos no caminho atual da busca em profundidade
                if state_key in path_keys:
                    continue

            stack.append({
                "state": new_state,
                "path": path + [state],
                "movements": movements + [move],
                "depth": depth + 1,
                "path_keys": path_keys | {state_key}
            })

            if optimized:
                visited.add(state_key)

            generated_nodes += 1

    end_time = perf_counter()

    failed_metrics = {
        "sucesso": False,
        "tempo_de_execução": end_time - start_time,
        "estados_verificados": len(visited) if optimized else generated_nodes,
        "nodes_gerados": generated_nodes,
        "nodes_expandidos": expanded_nodes,
        "tamanho_maximo_estrutura": max_stack_size,
        "estrutura": "pilha",
        "profundidade_solucao": None,
        "tipo": "dls",
        "otimizado": optimized
    }

    return None, None, failed_metrics

def scenario_dls(missionaries = 3, cannibals = 3, boat_size = 2, depth_limit = 0, max_depth_limit = 500, optimized=True):

    initial_state = set_initial_state(missionaries, cannibals)
    solution_dls, movements_dls = None, None
    
    while depth_limit <= max_depth_limit:
        solution_dls, movements_dls, metrics = solve_dls(initial_state, depth_limit, boat_size, optimized)
    
        if solution_dls is None:
            print(f"depth_limit = {depth_limit}: nenhuma solução encontrada.")
            print_metrics(metrics)
            depth_limit += 1
            continue
    
        print(f"depth_limit = {depth_limit}: solução encontrada!")
        break
    
    if solution_dls is None:
        print(
            f"\nNenhuma solução encontrada até depth_limit = {max_depth_limit}."
        )
    else:
        print("\nGabarito da travessia (DLS):")
        boat_side = "left"
    
        for step, move in enumerate(movements_dls[1:], start=1):
            missionaries, cannibals = move
            origin = "esquerda" if boat_side == "left" else "direita"
            destination = "direita" if boat_side == "left" else "esquerda"
    
            missionaries_label = "missionário" if missionaries == 1 else "missionários"
            cannibals_label = "canibal" if cannibals == 1 else "canibais"
    
            print(
                f"Passo {step}: levar {missionaries} {missionaries_label} e "
                f"{cannibals} {cannibals_label} da margem {origin} para a margem {destination}."
            )
    
            boat_side = "right" if boat_side == "left" else "left"
        print_metrics(metrics)
scenario_dls()

depth_limit = 0: nenhuma solução encontrada.
❌ Tempo de execução: 0.000009 s
depth_limit = 1: nenhuma solução encontrada.
❌ Tempo de execução: 0.000037 s
depth_limit = 2: nenhuma solução encontrada.
❌ Tempo de execução: 0.000042 s
depth_limit = 3: nenhuma solução encontrada.
❌ Tempo de execução: 0.000042 s
depth_limit = 4: nenhuma solução encontrada.
❌ Tempo de execução: 0.000047 s
depth_limit = 5: nenhuma solução encontrada.
❌ Tempo de execução: 0.000053 s
depth_limit = 6: nenhuma solução encontrada.
❌ Tempo de execução: 0.000058 s
depth_limit = 7: nenhuma solução encontrada.
❌ Tempo de execução: 0.000063 s
depth_limit = 8: nenhuma solução encontrada.
❌ Tempo de execução: 0.000072 s
depth_limit = 9: nenhuma solução encontrada.
❌ Tempo de execução: 0.000077 s
depth_limit = 10: nenhuma solução encontrada.
❌ Tempo de execução: 0.000093 s
depth_limit = 11: solução encontrada!

Gabarito da travessia (DLS):
Passo 1: levar 1 missionário e 1 canibal da margem esquerda para a margem direita.
Passo 2: levar 1 missionário e 0 canibais da margem direita para a margem esquerda.
Passo 3: levar 0 missionários e 2 canibais da margem esquerda para a margem direita.
Passo 4: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 5: levar 2 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 6: levar 1 missionário e 1 canibal da margem direita para a margem esquerda.
Passo 7: levar 2 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 8: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 9: levar 0 missionários e 2 canibais da margem esquerda para a margem direita.
Passo 10: levar 1 missionário e 0 canibais da margem direita para a margem esquerda.
Passo 11: levar 1 missionário e 1 canibal da margem esquerda para a margem direita.

📊 MÉTRICAS DE EXECUÇÃO
===================================
Sucesso: ✅
Tempo de execução: 0.000079 s
Estados verificados: 15
Nós gerados: 15
Nós expandidos: 12
Tamanho máximo da pilha: 4
Profundidade da solução: 11
===================================

Playground

O playground deste notebook expõe três funções públicas para testar diferentes estratégias de busca no problema dos missionários e canibais.

Funções públicas

scenario_bfs(missionaries=3, cannibals=3, boat_size=2, optimized = True)

Executa o problema usando Busca em Largura (BFS).

Parâmetros: - missionaries: quantidade inicial de missionários na margem esquerda - cannibals: quantidade inicial de canibais na margem esquerda - boat_size: capacidade máxima do barco - optimized: capacidade de usar ou não um algorítmo otimizado que verifica se o estado já foi consultado em algum momento nessa profundidade, evitando retorno a estados já computados globalmente.

---

scenario_dfs(missionaries=3, cannibals=3, boat_size=2, optimized = True)

Executa o problema usando Busca em Profundidade (DFS).

Parâmetros: - missionaries: quantidade inicial de missionários na margem esquerda - cannibals: quantidade inicial de canibais na margem esquerda - boat_size: capacidade máxima do barco - optimized: capacidade de usar ou não um algorítmo otimizado que verifica se o estado já foi consultado em algum momento nessa profundidade, evitando retorno a estados já computados globalmente.

---

scenario_dls(missionaries=3, cannibals=3, boat_size=2, depth_limit=0, max_depth_limit=500, optimized = True)

Executa o problema usando Busca em Profundidade Limitada (DLS), tentando encontrar solução a partir de um limite inicial de profundidade.

Parâmetros: - missionaries: quantidade inicial de missionários na margem esquerda - cannibals: quantidade inicial de canibais na margem esquerda - boat_size: capacidade máxima do barco - depth_limit: limite inicial de profundidade - max_depth_limit: limite máximo de profundidade a ser testado - optimized: capacidade de usar ou não um algorítmo otimizado que verifica se o estado já foi consultado em algum momento nessa profundidade, evitando retorno a estados já computados globalmente.

Exemplos de uso

scenario_bfs()
scenario_dfs(optimized = False)

scenario_bfs(missionaries=4, cannibals=4)
scenario_dfs(4, 3, 3)
scenario_dfs(4, 3, 3, False)
scenario_dls(missionaries=3, cannibals=3, boat_size=2, depth_limit=0, max_depth_limit=20)

::: {#c717e56e-3921-46c6-9a6a-7b9a49a9eaa3 .cell editable='true' quarto-private-1='{"key":"slideshow","value":{"slide_type":""}}' tags='[]' execution_count=120}
``` {.python .cell-code}
scenario_bfs(missionaries=41)

Resolvido em 85 passos.
Solução muito longa, não será exibida.

📊 MÉTRICAS DE EXECUÇÃO
===================================
Sucesso: ✅
Tempo de execução: 0.006246 s
Estados verificados: 318
Nós gerados: 318
Nós expandidos: 318
Tamanho máximo da fila: 5
Profundidade da solução: 85
===================================

:::

scenario_dls(missionaries=5, cannibals=5, boat_size=3, depth_limit=0, max_depth_limit=20)

depth_limit = 0: nenhuma solução encontrada.
❌ Tempo de execução: 0.000011 s
depth_limit = 1: nenhuma solução encontrada.
❌ Tempo de execução: 0.000059 s
depth_limit = 2: nenhuma solução encontrada.
❌ Tempo de execução: 0.000092 s
depth_limit = 3: nenhuma solução encontrada.
❌ Tempo de execução: 0.000112 s
depth_limit = 4: nenhuma solução encontrada.
❌ Tempo de execução: 0.000135 s
depth_limit = 5: nenhuma solução encontrada.
❌ Tempo de execução: 0.000157 s
depth_limit = 6: nenhuma solução encontrada.
❌ Tempo de execução: 0.000158 s
depth_limit = 7: nenhuma solução encontrada.
❌ Tempo de execução: 0.000183 s
depth_limit = 8: nenhuma solução encontrada.
❌ Tempo de execução: 0.000194 s
depth_limit = 9: nenhuma solução encontrada.
❌ Tempo de execução: 0.000225 s
depth_limit = 10: nenhuma solução encontrada.
❌ Tempo de execução: 0.000222 s
depth_limit = 11: nenhuma solução encontrada.
❌ Tempo de execução: 0.000283 s
depth_limit = 12: nenhuma solução encontrada.
❌ Tempo de execução: 0.000307 s
depth_limit = 13: solução encontrada!

Gabarito da travessia (DLS):
Passo 1: levar 1 missionário e 1 canibal da margem esquerda para a margem direita.
Passo 2: levar 1 missionário e 0 canibais da margem direita para a margem esquerda.
Passo 3: levar 2 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 4: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 5: levar 0 missionários e 3 canibais da margem esquerda para a margem direita.
Passo 6: levar 0 missionários e 2 canibais da margem direita para a margem esquerda.
Passo 7: levar 3 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 8: levar 1 missionário e 1 canibal da margem direita para a margem esquerda.
Passo 9: levar 3 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 10: levar 0 missionários e 2 canibais da margem direita para a margem esquerda.
Passo 11: levar 0 missionários e 3 canibais da margem esquerda para a margem direita.
Passo 12: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 13: levar 0 missionários e 3 canibais da margem esquerda para a margem direita.

📊 MÉTRICAS DE EXECUÇÃO
===================================
Sucesso: ✅
Tempo de execução: 0.000208 s
Estados verificados: 25
Nós gerados: 25
Nós expandidos: 17
Tamanho máximo da pilha: 11
Profundidade da solução: 13
===================================

scenario_bfs(missionaries=30, cannibals=10, boat_size=5)

Resolvido em 19 passos.

Gabarito da travessia:
Passo 1: levar 0 missionários e 4 canibais da margem esquerda para a margem direita.
Passo 2: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 3: levar 4 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 4: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 5: levar 2 missionários e 3 canibais da margem esquerda para a margem direita.
Passo 6: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 7: levar 2 missionários e 3 canibais da margem esquerda para a margem direita.
Passo 8: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 9: levar 2 missionários e 3 canibais da margem esquerda para a margem direita.
Passo 10: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 11: levar 4 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 12: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 13: levar 4 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 14: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 15: levar 4 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 16: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 17: levar 4 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 18: levar 0 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 19: levar 4 missionários e 1 canibal da margem esquerda para a margem direita.

📊 MÉTRICAS DE EXECUÇÃO
===================================
Sucesso: ✅
Tempo de execução: 0.018128 s
Estados verificados: 496
Nós gerados: 496
Nós expandidos: 490
Tamanho máximo da fila: 43
Profundidade da solução: 19
===================================

scenario_dfs(missionaries=30, cannibals=10, boat_size=5)

Resolvido em 39 passos.
Solução muito longa, não será exibida.

📊 MÉTRICAS DE EXECUÇÃO
===================================
Sucesso: ✅
Tempo de execução: 0.004994 s
Estados verificados: 374
Nós gerados: 374
Nós expandidos: 134
Tamanho máximo da pilha: 241
Profundidade da solução: 39
===================================

50 missionários, 30 canibais, 4 posições no barco. Para a solução bfs que encontrou os 53 passos houve um tempo

scenario_bfs(50, 30, 4)

Resolvido em 53 passos.
Solução muito longa, não será exibida.

📊 MÉTRICAS DE EXECUÇÃO
===================================
Sucesso: ✅
Tempo de execução: 0.030144 s
Estados verificados: 1.378
Nós gerados: 1.378
Nós expandidos: 1.375
Tamanho máximo da fila: 38
Profundidade da solução: 53
===================================

scenario_dfs(50, 30, 4)

Resolvido em 109 passos.
Solução muito longa, não será exibida.

📊 MÉTRICAS DE EXECUÇÃO
===================================
Sucesso: ✅
Tempo de execução: 0.042929 s
Estados verificados: 1.055
Nós gerados: 1.055
Nós expandidos: 445
Tamanho máximo da pilha: 611
Profundidade da solução: 109
===================================

scenario_dls(50, 30, 4, 110)

depth_limit = 110: solução encontrada!

Gabarito da travessia (DLS):
Passo 1: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 2: levar 3 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 3: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 4: levar 1 missionário e 0 canibais da margem direita para a margem esquerda.
Passo 5: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 6: levar 3 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 7: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 8: levar 1 missionário e 0 canibais da margem direita para a margem esquerda.
Passo 9: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 10: levar 3 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 11: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 12: levar 1 missionário e 0 canibais da margem direita para a margem esquerda.
Passo 13: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 14: levar 3 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 15: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 16: levar 1 missionário e 0 canibais da margem direita para a margem esquerda.
Passo 17: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 18: levar 3 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 19: levar 3 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 20: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 21: levar 0 missionários e 4 canibais da margem esquerda para a margem direita.
Passo 22: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 23: levar 3 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 24: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 25: levar 0 missionários e 4 canibais da margem esquerda para a margem direita.
Passo 26: levar 2 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 27: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 28: levar 1 missionário e 2 canibais da margem direita para a margem esquerda.
Passo 29: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 30: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 31: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 32: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 33: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 34: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 35: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 36: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 37: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 38: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 39: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 40: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 41: levar 3 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 42: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 43: levar 0 missionários e 4 canibais da margem esquerda para a margem direita.
Passo 44: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 45: levar 3 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 46: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 47: levar 0 missionários e 4 canibais da margem esquerda para a margem direita.
Passo 48: levar 2 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 49: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 50: levar 1 missionário e 2 canibais da margem direita para a margem esquerda.
Passo 51: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 52: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 53: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 54: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 55: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 56: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 57: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 58: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 59: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 60: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 61: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 62: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 63: levar 3 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 64: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 65: levar 0 missionários e 4 canibais da margem esquerda para a margem direita.
Passo 66: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 67: levar 3 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 68: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 69: levar 0 missionários e 4 canibais da margem esquerda para a margem direita.
Passo 70: levar 2 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 71: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 72: levar 1 missionário e 2 canibais da margem direita para a margem esquerda.
Passo 73: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 74: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 75: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 76: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 77: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 78: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 79: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 80: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 81: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 82: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 83: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 84: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 85: levar 3 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 86: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 87: levar 0 missionários e 4 canibais da margem esquerda para a margem direita.
Passo 88: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 89: levar 3 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 90: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 91: levar 0 missionários e 3 canibais da margem esquerda para a margem direita.
Passo 92: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 93: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 94: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 95: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 96: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 97: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 98: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 99: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 100: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 101: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 102: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 103: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 104: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 105: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 106: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 107: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 108: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 109: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.

📊 MÉTRICAS DE EXECUÇÃO
===================================
Sucesso: ✅
Tempo de execução: 0.013942 s
Estados verificados: 1.055
Nós gerados: 1.055
Nós expandidos: 445
Tamanho máximo da pilha: 611
Profundidade da solução: 109
===================================

Abaixo é um cenário antes da inserção da otimização, considere como optimized false, mesmo não tendo esse parâmetro. Não removi devido à sua longa duração

scenario_dls(missionaries=30, cannibals=10, boat_size=5, depth_limit=0, max_depth_limit=30)

depth_limit = 0: nenhuma solução encontrada.
❌ Tempo de execução: 0.000010 s
depth_limit = 1: nenhuma solução encontrada.
❌ Tempo de execução: 0.000093 s
depth_limit = 2: nenhuma solução encontrada.
❌ Tempo de execução: 0.000810 s
depth_limit = 3: nenhuma solução encontrada.
❌ Tempo de execução: 0.005949 s
depth_limit = 4: nenhuma solução encontrada.
❌ Tempo de execução: 0.016745 s
depth_limit = 5: nenhuma solução encontrada.
❌ Tempo de execução: 0.109610 s
depth_limit = 6: nenhuma solução encontrada.
❌ Tempo de execução: 1.255668 s
depth_limit = 7: nenhuma solução encontrada.
❌ Tempo de execução: 13.024629 s
depth_limit = 8: nenhuma solução encontrada.
❌ Tempo de execução: 159.790013 s
depth_limit = 9: nenhuma solução encontrada.
❌ Tempo de execução: 1981.858470 s
depth_limit = 10: nenhuma solução encontrada.
❌ Tempo de execução: 25745.846772 s

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
Cell In[75], line 1
----> 1 scenario_dls(missionaries=30, cannibals=10, boat_size=5, depth_limit=0, max_depth_limit=30)

Cell In[57], line 7, in scenario_dls(missionaries, cannibals, boat_size, depth_limit, max_depth_limit)
      4 solution_dls, movements_dls = None, None
      6 while depth_limit <= max_depth_limit:
----> 7     solution_dls, movements_dls, metrics = solve_dls(initial_state, depth_limit, boat_size)
      9     if solution_dls is None:
     10         print(f"depth_limit = {depth_limit}: nenhuma solução encontrada.")

Cell In[47], line 31, in solve_dls(initial_state, depth_limit, boat_capacity)
     28 depth = node["depth"]
     29 path_keys = node["path_keys"]
---> 31 if is_goal(state):
     32     end_time = perf_counter()
     33     solution = path + [state]

Cell In[8], line 1, in is_goal(state)
----> 1 def is_goal(state):
      2     return state["left"] == (0, 0)

KeyboardInterrupt: 

E comparando com sua versão otimizada, é gritante a diferença.

scenario_dls(50, 30, 4)

depth_limit = 0: nenhuma solução encontrada.
❌ Tempo de execução: 0.000010 s
depth_limit = 1: nenhuma solução encontrada.
❌ Tempo de execução: 0.000094 s
depth_limit = 2: nenhuma solução encontrada.
❌ Tempo de execução: 0.000391 s
depth_limit = 3: nenhuma solução encontrada.
❌ Tempo de execução: 0.000548 s
depth_limit = 4: nenhuma solução encontrada.
❌ Tempo de execução: 0.000681 s
depth_limit = 5: nenhuma solução encontrada.
❌ Tempo de execução: 0.000745 s
depth_limit = 6: nenhuma solução encontrada.
❌ Tempo de execução: 0.000759 s
depth_limit = 7: nenhuma solução encontrada.
❌ Tempo de execução: 0.001288 s
depth_limit = 8: nenhuma solução encontrada.
❌ Tempo de execução: 0.000905 s
depth_limit = 9: nenhuma solução encontrada.
❌ Tempo de execução: 0.000823 s
depth_limit = 10: nenhuma solução encontrada.
❌ Tempo de execução: 0.000816 s
depth_limit = 11: nenhuma solução encontrada.
❌ Tempo de execução: 0.000994 s
depth_limit = 12: nenhuma solução encontrada.
❌ Tempo de execução: 0.000826 s
depth_limit = 13: nenhuma solução encontrada.
❌ Tempo de execução: 0.001118 s
depth_limit = 14: nenhuma solução encontrada.
❌ Tempo de execução: 0.000953 s
depth_limit = 15: nenhuma solução encontrada.
❌ Tempo de execução: 0.001261 s
depth_limit = 16: nenhuma solução encontrada.
❌ Tempo de execução: 0.001221 s
depth_limit = 17: nenhuma solução encontrada.
❌ Tempo de execução: 0.001510 s
depth_limit = 18: nenhuma solução encontrada.
❌ Tempo de execução: 0.001437 s
depth_limit = 19: nenhuma solução encontrada.
❌ Tempo de execução: 0.001818 s
depth_limit = 20: nenhuma solução encontrada.
❌ Tempo de execução: 0.002391 s
depth_limit = 21: nenhuma solução encontrada.
❌ Tempo de execução: 0.002101 s
depth_limit = 22: nenhuma solução encontrada.
❌ Tempo de execução: 0.002086 s
depth_limit = 23: nenhuma solução encontrada.
❌ Tempo de execução: 0.002115 s
depth_limit = 24: nenhuma solução encontrada.
❌ Tempo de execução: 0.002274 s
depth_limit = 25: nenhuma solução encontrada.
❌ Tempo de execução: 0.002714 s
depth_limit = 26: nenhuma solução encontrada.
❌ Tempo de execução: 0.002574 s
depth_limit = 27: nenhuma solução encontrada.
❌ Tempo de execução: 0.002689 s
depth_limit = 28: nenhuma solução encontrada.
❌ Tempo de execução: 0.003052 s
depth_limit = 29: nenhuma solução encontrada.
❌ Tempo de execução: 0.002839 s
depth_limit = 30: nenhuma solução encontrada.
❌ Tempo de execução: 0.003131 s
depth_limit = 31: nenhuma solução encontrada.
❌ Tempo de execução: 0.003120 s
depth_limit = 32: nenhuma solução encontrada.
❌ Tempo de execução: 0.003813 s
depth_limit = 33: nenhuma solução encontrada.
❌ Tempo de execução: 0.003401 s
depth_limit = 34: nenhuma solução encontrada.
❌ Tempo de execução: 0.003247 s
depth_limit = 35: nenhuma solução encontrada.
❌ Tempo de execução: 0.003493 s
depth_limit = 36: nenhuma solução encontrada.
❌ Tempo de execução: 0.003713 s
depth_limit = 37: nenhuma solução encontrada.
❌ Tempo de execução: 0.004030 s
depth_limit = 38: nenhuma solução encontrada.
❌ Tempo de execução: 0.004046 s
depth_limit = 39: nenhuma solução encontrada.
❌ Tempo de execução: 0.004327 s
depth_limit = 40: nenhuma solução encontrada.
❌ Tempo de execução: 0.004682 s
depth_limit = 41: nenhuma solução encontrada.
❌ Tempo de execução: 0.005057 s
depth_limit = 42: nenhuma solução encontrada.
❌ Tempo de execução: 0.004928 s
depth_limit = 43: nenhuma solução encontrada.
❌ Tempo de execução: 0.005136 s
depth_limit = 44: nenhuma solução encontrada.
❌ Tempo de execução: 0.005073 s
depth_limit = 45: nenhuma solução encontrada.
❌ Tempo de execução: 0.004984 s
depth_limit = 46: nenhuma solução encontrada.
❌ Tempo de execução: 0.005323 s
depth_limit = 47: nenhuma solução encontrada.
❌ Tempo de execução: 0.005684 s
depth_limit = 48: nenhuma solução encontrada.
❌ Tempo de execução: 0.005530 s
depth_limit = 49: nenhuma solução encontrada.
❌ Tempo de execução: 0.005655 s
depth_limit = 50: nenhuma solução encontrada.
❌ Tempo de execução: 0.006048 s
depth_limit = 51: nenhuma solução encontrada.
❌ Tempo de execução: 0.005826 s
depth_limit = 52: nenhuma solução encontrada.
❌ Tempo de execução: 0.005806 s
depth_limit = 53: nenhuma solução encontrada.
❌ Tempo de execução: 0.006348 s
depth_limit = 54: nenhuma solução encontrada.
❌ Tempo de execução: 0.006586 s
depth_limit = 55: nenhuma solução encontrada.
❌ Tempo de execução: 0.006490 s
depth_limit = 56: nenhuma solução encontrada.
❌ Tempo de execução: 0.006197 s
depth_limit = 57: nenhuma solução encontrada.
❌ Tempo de execução: 0.006599 s
depth_limit = 58: nenhuma solução encontrada.
❌ Tempo de execução: 0.006940 s
depth_limit = 59: nenhuma solução encontrada.
❌ Tempo de execução: 0.006850 s
depth_limit = 60: nenhuma solução encontrada.
❌ Tempo de execução: 0.007062 s
depth_limit = 61: nenhuma solução encontrada.
❌ Tempo de execução: 0.007239 s
depth_limit = 62: nenhuma solução encontrada.
❌ Tempo de execução: 0.007492 s
depth_limit = 63: nenhuma solução encontrada.
❌ Tempo de execução: 0.007730 s
depth_limit = 64: nenhuma solução encontrada.
❌ Tempo de execução: 0.007881 s
depth_limit = 65: nenhuma solução encontrada.
❌ Tempo de execução: 0.008100 s
depth_limit = 66: nenhuma solução encontrada.
❌ Tempo de execução: 0.008247 s
depth_limit = 67: nenhuma solução encontrada.
❌ Tempo de execução: 0.008244 s
depth_limit = 68: nenhuma solução encontrada.
❌ Tempo de execução: 0.012894 s
depth_limit = 69: nenhuma solução encontrada.
❌ Tempo de execução: 0.008819 s
depth_limit = 70: nenhuma solução encontrada.
❌ Tempo de execução: 0.009804 s
depth_limit = 71: nenhuma solução encontrada.
❌ Tempo de execução: 0.009103 s
depth_limit = 72: nenhuma solução encontrada.
❌ Tempo de execução: 0.010007 s
depth_limit = 73: nenhuma solução encontrada.
❌ Tempo de execução: 0.010173 s
depth_limit = 74: nenhuma solução encontrada.
❌ Tempo de execução: 0.010181 s
depth_limit = 75: nenhuma solução encontrada.
❌ Tempo de execução: 0.010383 s
depth_limit = 76: nenhuma solução encontrada.
❌ Tempo de execução: 0.010945 s
depth_limit = 77: nenhuma solução encontrada.
❌ Tempo de execução: 0.010355 s
depth_limit = 78: nenhuma solução encontrada.
❌ Tempo de execução: 0.010259 s
depth_limit = 79: nenhuma solução encontrada.
❌ Tempo de execução: 0.010515 s
depth_limit = 80: nenhuma solução encontrada.
❌ Tempo de execução: 0.011150 s
depth_limit = 81: nenhuma solução encontrada.
❌ Tempo de execução: 0.011137 s
depth_limit = 82: nenhuma solução encontrada.
❌ Tempo de execução: 0.011117 s
depth_limit = 83: nenhuma solução encontrada.
❌ Tempo de execução: 0.011531 s
depth_limit = 84: nenhuma solução encontrada.
❌ Tempo de execução: 0.011348 s
depth_limit = 85: nenhuma solução encontrada.
❌ Tempo de execução: 0.011762 s
depth_limit = 86: nenhuma solução encontrada.
❌ Tempo de execução: 0.011960 s
depth_limit = 87: nenhuma solução encontrada.
❌ Tempo de execução: 0.012075 s
depth_limit = 88: nenhuma solução encontrada.
❌ Tempo de execução: 0.012329 s
depth_limit = 89: nenhuma solução encontrada.
❌ Tempo de execução: 0.012165 s
depth_limit = 90: nenhuma solução encontrada.
❌ Tempo de execução: 0.012429 s
depth_limit = 91: nenhuma solução encontrada.
❌ Tempo de execução: 0.013023 s
depth_limit = 92: nenhuma solução encontrada.
❌ Tempo de execução: 0.012750 s
depth_limit = 93: nenhuma solução encontrada.
❌ Tempo de execução: 0.013372 s
depth_limit = 94: nenhuma solução encontrada.
❌ Tempo de execução: 0.013518 s
depth_limit = 95: nenhuma solução encontrada.
❌ Tempo de execução: 0.012993 s
depth_limit = 96: nenhuma solução encontrada.
❌ Tempo de execução: 0.013484 s
depth_limit = 97: nenhuma solução encontrada.
❌ Tempo de execução: 0.013710 s
depth_limit = 98: nenhuma solução encontrada.
❌ Tempo de execução: 0.013647 s
depth_limit = 99: nenhuma solução encontrada.
❌ Tempo de execução: 0.013573 s
depth_limit = 100: nenhuma solução encontrada.
❌ Tempo de execução: 0.012908 s
depth_limit = 101: nenhuma solução encontrada.
❌ Tempo de execução: 0.014278 s
depth_limit = 102: nenhuma solução encontrada.
❌ Tempo de execução: 0.013434 s
depth_limit = 103: nenhuma solução encontrada.
❌ Tempo de execução: 0.014552 s
depth_limit = 104: nenhuma solução encontrada.
❌ Tempo de execução: 0.014070 s
depth_limit = 105: nenhuma solução encontrada.
❌ Tempo de execução: 0.014313 s
depth_limit = 106: nenhuma solução encontrada.
❌ Tempo de execução: 0.014622 s
depth_limit = 107: nenhuma solução encontrada.
❌ Tempo de execução: 0.014777 s
depth_limit = 108: nenhuma solução encontrada.
❌ Tempo de execução: 0.015450 s
depth_limit = 109: solução encontrada!

Gabarito da travessia (DLS):
Passo 1: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 2: levar 3 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 3: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 4: levar 1 missionário e 0 canibais da margem direita para a margem esquerda.
Passo 5: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 6: levar 3 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 7: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 8: levar 1 missionário e 0 canibais da margem direita para a margem esquerda.
Passo 9: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 10: levar 3 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 11: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 12: levar 1 missionário e 0 canibais da margem direita para a margem esquerda.
Passo 13: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 14: levar 3 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 15: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 16: levar 1 missionário e 0 canibais da margem direita para a margem esquerda.
Passo 17: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 18: levar 3 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 19: levar 3 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 20: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 21: levar 0 missionários e 4 canibais da margem esquerda para a margem direita.
Passo 22: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 23: levar 3 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 24: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 25: levar 0 missionários e 4 canibais da margem esquerda para a margem direita.
Passo 26: levar 2 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 27: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 28: levar 1 missionário e 2 canibais da margem direita para a margem esquerda.
Passo 29: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 30: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 31: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 32: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 33: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 34: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 35: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 36: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 37: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 38: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 39: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 40: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 41: levar 3 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 42: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 43: levar 0 missionários e 4 canibais da margem esquerda para a margem direita.
Passo 44: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 45: levar 3 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 46: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 47: levar 0 missionários e 4 canibais da margem esquerda para a margem direita.
Passo 48: levar 2 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 49: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 50: levar 1 missionário e 2 canibais da margem direita para a margem esquerda.
Passo 51: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 52: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 53: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 54: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 55: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 56: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 57: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 58: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 59: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 60: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 61: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 62: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 63: levar 3 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 64: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 65: levar 0 missionários e 4 canibais da margem esquerda para a margem direita.
Passo 66: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 67: levar 3 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 68: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 69: levar 0 missionários e 4 canibais da margem esquerda para a margem direita.
Passo 70: levar 2 missionários e 1 canibal da margem direita para a margem esquerda.
Passo 71: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 72: levar 1 missionário e 2 canibais da margem direita para a margem esquerda.
Passo 73: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 74: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 75: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 76: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 77: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 78: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 79: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 80: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 81: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 82: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 83: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 84: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 85: levar 3 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 86: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 87: levar 0 missionários e 4 canibais da margem esquerda para a margem direita.
Passo 88: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 89: levar 3 missionários e 1 canibal da margem esquerda para a margem direita.
Passo 90: levar 4 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 91: levar 0 missionários e 3 canibais da margem esquerda para a margem direita.
Passo 92: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 93: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 94: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 95: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 96: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 97: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 98: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 99: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 100: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 101: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 102: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 103: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 104: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 105: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 106: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 107: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.
Passo 108: levar 2 missionários e 0 canibais da margem direita para a margem esquerda.
Passo 109: levar 4 missionários e 0 canibais da margem esquerda para a margem direita.

📊 MÉTRICAS DE EXECUÇÃO
===================================
Sucesso: ✅
Tempo de execução: 0.005872 s
Estados verificados: 1.055
Nós gerados: 1.055
Nós expandidos: 445
Tamanho máximo da pilha: 611
Profundidade da solução: 109
===================================

Uma lógica para o algorítmo DLS é iniciar no nó que contém o resultado, seria então garantido ter uma resposta e talvez fosse até rápido, porém, se o tempo no limite 10 foi de 25745s(aproximadamente 7 horas), mesmo estando na profundidade de nó correto, ele teria que testar vários caminhos de 109 nós pra algum deles ser o correto, o que ainda pode gerar um tempo muito grande no algorítmo não otimizado.