Heurísticas de Busca no Roteamento da Romênia

Exemplo 1 Utilizando a heurística de distância em linha reta DLR para o problema de roteamento da Romênia Romania with step costs in km Busca A A estrela É a técnica de busca mais amplamente conhecida Tenta minimizar o custo total da solução combinando Busca Gulosa econômica porém não é completa nem ótima Busca de Custo Uniforme Dijkstra ineficiente porém completa e ótima Estratégia Avalia a combinação de duas funções fn gn hn Técnicas de Busca Estratégias de Busca Cega ou Exhaustiva não utiliza informações sobre o problema para guiar a busca BUSCA SEM INFORMAÇÃO Estratégias de Busca Heurística busca informada utiliza informações específicas do domínio para ajudar na decisão BUSCA COM INFORMAÇÃO Busca de melhor escolha Busca Gulosa Deriva da busca em árvore porém o nó é selecionado para expansão levando em consideração uma função de avaliação fn Estratégia onde gn é o custo real da origem até o nó n Distância de n nó atual ao nó inicial hn é a distância em linha reta do objetivo até o nó n distância estimada de n nó atual ao final A expande o nó de menor valor de fn na fronteira do espaço de estados Lista de Nós abertos nós que foram gerados e sofreram a aplicação da função heurística mas que ainda não foram examinados isto é seus sucessores não foram gerados Lista de Nós fechados nós que já foram examinados Precisamos manter estes nós na memória se quisermos efetuar uma busca em grafo em vez de árvore já que sempre que um novo nó é gerado precisamos verificar se ele já foi gerado antes Exemplo 2 Utilizando a função heurística fn gn hn para o problema de roteamento da Romênia Exemplo 2 a The initial state b After expanding Arad c After expanding Sibiu d After expanding Rimnicu Vilcea e After expanding Fagaras f After expanding Pitesti Straightline distance to Bucharest Arad 366 Bucharest 0 Craiova 160 Drobeta 242 Eforie 161 Fagaras 178 Giurgiu 77 Hirsova 151 Iasi 226 Lugoj 244 Mehadia 241 Neamt 234 Oradea 380 Pitesti 98 Rimnicu Vilcea 193 Sibiu 253 Timisoara 329 Urziceni 80 Vaslui 199 Zerind 374 Descrição do Algoritmo A Passo 0 Criar um grafo de busca G inicialmente contendo somente o nó de partida S Passo 1 inicializar uma lista chamada OPEN com o nó de partida S e uma lista chamada CLOSED com Ø OPEN é a lista de nós ainda não selecionados para expansão enquanto CLOSED é a lista dos nós já expandidos Passo 2 LOOP Se OPEN Ø Então FIM e retornar Falha Passo 3 tomar um nó de OPEN com o menor f Chamar este nó de N Retirálo de OPEN e colocálo em CLOSED Passo 4 Se N é o nó buscado Então FIM e fornecer a solução percorrendo os ponteiros de N a S Passo 5 Expandir N gerando o conjunto de nós sucessores e adicionar estes nós no grafo G Passo 6 Para cada membro M de SUCESSORES Se M não pertence a OPEN CLOSED Então adicionar M em OPEN Se M pertence a OPEN executar Passo 6 open Se M pertence a CLOSED executar Passo 6 closed Exercício 1 Um viajante de vendas deve partir da cidade A e retorna a mesma após percorrer todas as cidades um única vez Encontrar a rota de menor custo utilizando o algoritmo de busca Gulosa Exercício 2 Robótica Móvel No ambiente mostrado o robô deve partir de S e chegar em G Usando o algoritmo A descreva passo a passo como ficam as listas OPEN CLOSED SUCESSORES e o resultado final do melhor caminho Desenhe a árvore Suponha que greta1 e gdiagonal15 O custo h é a diferença entre as coordenadas linha e coluna do nó atual e a meta ObsX obstáculo Por exemplo h entre os pontos S e G vale 41 31 5