De Arad para Bucareste
Problema
Imagine um agente passando féria na Romênia. O agente está em Arad e precisa ir para Bucareste.
- Estado Inicial: Arad
- Estado Final: Bucareste
- Espaço de estados: Todos os caminhos possíveis
- Ações: Passar de uma cidade para outra (ex. Arad até Sibiu)
- Solução: O caminho do estado atual até o estado final como melhor solução
Montando uma Árvore de Busca
Para montar uma árvore de busca usando o mapa da Romênia como exemplo:
Nó Raiz: O nó raiz da árvore seria Arad, o ponto de partida.
Nós Filhos: Os nós filhos de qualquer nó na árvore representam os possíveis movimentos ou caminhos a partir daquela cidade. Por exemplo, a partir de Arad, pode-se ir para Zerind, Sibiu ou Timisoara, conforme as conexões disponíveis no mapa.
Custo de Caminho: Cada aresta da árvore (ou seja, o caminho de uma cidade para outra) terá um custo associado, que geralmente representa a distância entre as cidades.
Montando o Grafo e Heurística
# Grafo das conexões entre as cidades. O valor representa a distância real entre elas.
grafo = {
'Arad': [('Zerind', 75), ('Timisoara', 118), ('Sibiu', 140)],
'Zerind': [('Arad', 75), ('Oradea', 71)],
'Timisoara': [('Arad', 118), ('Lugoj', 111)],
'Sibiu': [('Arad', 140), ('Oradea', 151), ('Fagaras', 99), ('Rimnicu Vilcea', 80)],
'Oradea': [('Zerind', 71), ('Sibiu', 151)],
'Lugoj': [('Timisoara', 111), ('Mehadia', 70)],
'Fagaras': [('Sibiu', 99), ('Bucareste', 211)],
'Rimnicu Vilcea': [('Sibiu', 80), ('Pitesti', 97), ('Craiova', 146)],
'Mehadia': [('Lugoj', 70), ('Drobeta', 75)],
'Drobeta': [('Mehadia', 75), ('Craiova', 120)],
'Craiova': [('Drobeta', 120), ('Rimnicu Vilcea', 146), ('Pitesti', 138)],
'Pitesti': [('Rimnicu Vilcea', 97), ('Craiova', 138), ('Bucareste', 101)],
'Bucareste': [('Fagaras', 211), ('Pitesti', 101), ('Giurgiu', 90)]
}
# Função heurística: distância em linha reta de cada cidade até Bucareste
heuristica = {
'Arad': 366,
'Bucareste': 0,
'Craiova': 160,
'Drobeta': 242,
'Fagaras': 178,
'Giurgiu': 77,
'Lugoj': 244,
'Mehadia': 241,
'Oradea': 380,
'Pitesti': 98,
'Rimnicu Vilcea': 193,
'Sibiu': 253,
'Timisoara': 329,
'Zerind': 374
}
Busca Gulosa
Criar um algoritmo em Python, aplicando a Busca Gulosa
def busca_gulosa(grafo, heuristica, inicio, objetivo):
visitados = set() # Conjunto para manter o controle das cidades já visitadas
visitar = [(inicio, 0, [inicio])] # Lista de prioridades com cidades a serem visitadas, começando com a cidade inicial
while visitar:
# Ordena a lista de visitar pela heurística da cidade destino
visitar.sort(key=lambda x: heuristica[x[0]])
cidade_atual, custo_atual, caminho_atual = visitar.pop(0)
if cidade_atual == objetivo:
print(f”Caminho encontrado até {cidade_atual} com custo total de {custo_atual}”)
print(“Caminho:”, ” -> “.join(caminho_atual))
return
if cidade_atual not in visitados:
visitados.add(cidade_atual)
# Adiciona vizinhos à lista de visitar
for vizinho, custo in grafo[cidade_atual]:
if vizinho not in visitados:
# Atualiza o caminho com o vizinho atual
novo_caminho = caminho_atual + [vizinho]
visitar.append((vizinho, custo_atual + custo, novo_caminho))
print(“Caminho não encontrado”)
return
# Chamada da função
busca_gulosa(grafo, heuristica, ‘Arad’, ‘Bucareste’)
Busca A*
Criar um algoritmo em Python, aplicando a Busca A*