Procura Informada

Na última secção, abordámos a procura cega, uma abordagem que explora todo o espaço de procura sem qualquer indicação do quão longe se encontra dos nós-objetivo. No entanto, se soubermos, de antemão, informações úteis sobre o objetivo, fará todo o sentido usá-las a nosso favor, por forma a conseguir (idealmente) procuras mais eficientes. É aqui que entram as estratégias de procura informada, abordagens que, de um modo geral, se baseiam na procura melhor primeiro, uma estratégia de procura que recorre a uma função de avaliação, f(n)f(n), para escolher a ordem de expansão dos nós.

A função de avaliação é modelada como uma estimativa do custo entre um nó, nn, e o objetivo. Por norma, poderá ser constituída por algumas componentes principais (correspondendo à soma/composição/etc. destas):

  • g(n)g(n), o custo do caminho percorrido desde o estado inicial até nn;
  • h(n)h(n), uma estimativa do custo do melhor caminho desde nn até ao objetivo;
  • h(n)h^*(n), o custo real do melhor caminho desde nn até ao objetivo, isto é, a estimativa exata.

Dizemos que h(n)h(n) é uma função heurística.

Função Heurística

Uma função heurística estima o quão perto um dado estado está do nó objetivo mais próximo: podemos pensar nela como uma espécie de detetor de metais, que apita cada vez mais alto à medida que nos aproximamos de um objetivo.

Note-se que, acima, foi utilizada a palavra estimativa: funções heurísticas não são necessariamente representações fiéis do custo real de um nó ao objetivo, mas sim aproximações que fazemos, idealmente por defeito.

Se estivermos num nó objetivo, a função heurística deve ser nula (h(n)=0h(n) = 0, portanto).

Funções heurísticas ajudam-nos, portanto, a decidir que caminho tomar (ou seja, que nó escolher), procurando minimizar os custos até ao objetivo.

Procura Melhor Primeiro (Genérica)

Tal como referido mais acima, a procura melhor primeiro corresponde a uma estratégia baseada na ideia de função de avaliação, que mapeia cada nó a uma estimativa: o quão perto estará do objetivo mais próximo. Seguindo esta abordagem, vamos sempre tentar expandir o nó com o menor valor de f(n)f(n) na fronteira, já que idealmente será esse nó que nos aproximará, de forma ótima, do objetivo (com algumas exceções, que vamos ver mais à frente). A fronteira em si tem os nós ordenados de forma crescente (através de uma min priority queue) segundo a respetiva função de avaliação.

Se pensarmos bem, acaba por ter uma lógica igual à da procura custo uniforme, onde aqui ff corresponde ao custo do caminho percorrido nessa procura: podemos, portanto, recorrendo à notação gg exposta mais acima, afirmar que, na procura custo uniforme, temos

f(n)=g(n).f(n) = g(n).

Isto é, na procura custo uniforme, a função de avaliação foca-se exclusivamente no caminho percorrido até agora, sem se preocupar com o caminho para a frente. Se pensarmos bem, faz então sentido que se encaixe nas procuras cegas, já que de facto não há informação útil que usemos sobre o objetivo: apenas sabemos coisas sobre o que está para trás.

Procura Gananciosa

Se na procura custo uniforme tínhamos f(n)=g(n)f(n) = g(n), isto é, a função de avaliação focava-se exclusivamente no caminho percorrido para trás, a procura gananciosa olha precisamente para o oposto: para o caminho que falta percorrer, sem se preocupar com o caminho percorrido até agora (procurando, portanto, expandir sempre o nó que aparenta estar mais próximo do objetivo). Dizemos, assim, que na greedy search se tem

f(n)=h(n).f(n) = h(n).
Exemplo - Procura Gananciosa, Arad-Bucareste

Voltemos a pegar no exemplo de Arad-Bucareste, considerando como função heurística a distância em linha reta do nó atual ao objetivo (Bucareste):

Cidade Distância a Bucareste Cidade Distância a Bucareste
Arad 366366 Mehadia 241241
Bucareste 00 Neamt 234234
Craiova 160160 Oradea 380380
Drobeta 242242 Pitesti 100100
Eforie 161161 Rimnicu Vilcea 193193
Fagaras 176176 Sibiu 253253
Giurgiu 7777 Timisoara 329329
Hirsova 151151 Urziceni 8080
Iasi 226226 Vaslui 199199
Lugoj 244244 Zerind 374374

Note-se que temos na tabela acima a distância em linha reta entre nós e o objetivo, não a distância real! É apenas uma estimativa, utilizada aqui como heurística.

Seguindo uma abordagem greedy, partindo de Arad e procurando atingir Bucareste, a árvore de procura resultante iria evoluir como se mostra abaixo:

A procura gananciosa não nos deu a solução ótima - em vez de seguir por Fagaras e depois para Bucareste, o caminho ótimo passaria por Rimnicu Vilcea, Pitesti e só depois por Bucareste. Esta procura não garante, portanto, otimalidade.

Como foi possível observar no exemplo acima, a greedy search não garante otimalidade. Mais ainda, podemos também afirmar que não é completa: infelizmente, esta abordagem não está imune a entrar em ciclos. Basta pensar, e olhando para o mapa da Roménia novamente, no caso em que queremos ir de Iasi a Fagaras: a expansão de Iasi gera Neamt e Vaslui, e Neamt encontra-se, em linha reta, mais próximo de Fagaras que Vaslui, pelo que seguimos esse caminho. A expansão de Neamt volta a colocar Iasi na fronteira, e Iasi está mais próximo em linha reta de Fagaras que Vaslui, pelo que voltamos a expandir Iasi - entramos, portanto, num ciclo infinito, e fica o caldo entornado.

Quanto às complexidades temporal e espacial, temos que o pior caso para ambas é exponencial, bmb^m. Note-se que, em relação à memória, basta pensar que a fronteira pode eventualmente conter todos os nós (já que temos de manter as heurísticas em memória), sendo proporcional ao número de nós dentro da fronteira e ao comprimento do maior caminho (em número de nós) percorrido.

Resta notar que, apesar da complexidade temporal exponencial da procura gananciosa, esta pode ser drasticamente reduzida utilizando uma boa heurística.

Procura A^*

Na procura custo uniforme, a heurística utilizada baseava-se exclusivamente em g(n)g(n). Já na procura gananciosa, abordada acima, recorremos unicamente a h(n)h(n), a estimativa do caminho até ao objetivo. É, então, natural que surja a ideia de combinar ambas numa única função de avaliação, em princípio mais precisa (já que terá em conta mais detalhes sobre o caminho). É precisamente essa a função de avaliação utilizada pela procura AA^*:

f(n)=g(n)+h(n).f(n) = g(n) + h(n).

A ideia-base da procura é evitar expandir caminhos que já sabemos que terão custos demasiado elevados, considerando tanto o que ficou para trás como o que ainda devemos ter de percorrer para a frente. Se pensarmos bem, ff corresponderá então ao custo total estimado da solução mais barata que passa por nn. Tal como na procura gananciosa, vamos manter a fronteira como uma min priority queue, ordenada de forma crescente pelo valor da função de avaliação de cada nó.

Exemplo - Procura AA^*, Arad-Bucareste

Voltemos a ter presente o exemplo de Arad-Bucareste, considerando novamente como h(n)h(n) a distância em linha reta do nó atual ao objetivo (Bucareste):

Cidade Distância a Bucareste Cidade Distância a Bucareste
Arad 366366 Mehadia 241241
Bucareste 00 Neamt 234234
Craiova 160160 Oradea 380380
Drobeta 242242 Pitesti 100100
Eforie 161161 Rimnicu Vilcea 193193
Fagaras 176176 Sibiu 253253
Giurgiu 7777 Timisoara 329329
Hirsova 151151 Urziceni 8080
Iasi 226226 Vaslui 199199
Lugoj 244244 Zerind 374374

A procura AA^* que, partindo de Arad procura o caminho mais barato até Bucareste, cria uma árvore de procura como a seguinte:

Note-se que os valores indicados ao lado de cada estado na árvore correspondem a ff, sendo a soma de gg (o caminho até agora percorrido) e hh (a estimativa do caminho por percorrer).

Podemos notar algo relevante: estados a representar a mesma cidade podem ser adicionados mais do que uma vez à fronteira (temos, por exemplo, Sibiu e Bucareste a ser adicionadas duas vezes). Para além disso, chegámos, através desta abordagem, ao caminho ótimo de Arad a Bucareste, algo que não se tinha verificado na abordagem greedy: não é indicativo, contudo, da otimalidade geral da procura; como vamos ver à frente, a procura AA^* não é ótima.

Infelizmente, não podemos garantir a otimalidade da procura AA^*. Como contra-exemplo, observe-se a seguinte árvore de procura (onde DD e GG são ambos estados objetivo):

Aqui, GG é o objetivo ótimo, com custo caminho igual a 77. Temos, contudo, que o seu pai (CC) nunca é explorado, já que BB tem menor valor de ff, 88, e depois um dos seus filhos também tem menor valor de ff - esse filho vai passar no teste objetivo, pelo que acabamos por não pesquisar o resto da árvore, ficando sem passar por GG.

Quando é que uma procura pode ser ótima?

Parecia estar tudo a correr bem, mas voltámos a apercebermo-nos que se calhar ter uma procura ótima não é assim tão fácil. Há, contudo, uma maneira de garantir que AA^* é ótima: recorrer a heurísticas admissíveis.

Heurísticas Admissíveis

Dizemos que uma heurística é admissível se, para todo o nó nn da árvore de procura, se verificar que

h(n)h(n).h(n) \leq h^*(n).

Dito de outra forma, heurísticas admissíveis são sempre otimistas, estimando sempre por defeito o custo de atingir o objetivo. Uma heurística admissível é, por exemplo, a utilizada em Arad-Bucareste no exemplo acima, onde hh corresponde à distância em linha reta de cada nó ao destino: temos, claro, que a distância em linha reta é sempre o melhor caso, mas que, geralmente, h(n)<h(n)h(n) < h^*(n) (os caminhos têm por norma curvas e afins).

Utilizar uma heurística admissível torna AA^* ótima em procura em árvore - podem ler a prova detalhada aqui.

Voltando ao exemplo de Arad-Bucareste, podemos agora perceber melhor a utilidade das garantias que heurísticas admissíveis nos dão: há uma situação em que temos a possibilidade de ir para Bucareste (já está na fronteira), mas que optamos por passar por Pitesti, visto ter um valor de função de avaliação menor. A lógica acaba por ser bastante simples: se existe a possibilidade de fazer um caminho mais curto por ali, vou primeiro verificar se, de facto, consigo ou não antes de me contentar com o que já tenho.

Note-se que foi referido acima que utilizar heurísticas admissíveis só torna AA^* ótima na procura em árvore: na procura em grafo, não adicionamos à fronteira estados por onde já passámos, pelo que podemos eventualmente perder o caminho mais curto até ao objetivo. De seguida, encontra-se um exemplo de uma situação onde podemos verificar isso mesmo:

A admissibilidade da heurística não garante, portanto, que AA^* seja ótima na procura em grafo, visto que um nó pode ser descartado se já estiver sido explorado no passado - estamos a perder possíveis caminhos mais curtos só por já ter explorado um mais caro anteriormente.

Podemos, contudo, garantir a otimalidade da procura AA^* em grafo, através de uma segunda restrição às heurísticas: estas devem ser consistentes.

Heurísticas Consistentes

Dizemos que uma heurística é consistente se, para todo o nn, para todos os seus sucessores nn' gerados por ações aa se verificar a desigualdade triangular:

h(n)h(n)+c(n,a,n),h(n) \leq h(n') + c(n, a, n'),

onde c(n,a,n)c(n, a, n') corresponde ao custo associado a realizar a ação aa de nn para nn'.

De forma mais simples, uma heurística diz-se consistente se, para todo o nn, para todos os seus sucessores nn' gerados por ações aa, o custo estimado de ir de nn ao objetivo for menor ou igual ao custo real de ir de nn a nn' somado ao custo estimado de ir de nn' ao objetivo.

Teremos, portanto:

f(n)=g(n)+h(n)=g(n)+c(n,a,n)+h(n)g(n)+h(n)f(n)\begin{equation} \begin{split} f(n') &= g(n') + h(n')\\ &= g(n) + c(n, a, n') + h(n')\\ &\geq g(n) + h(n)\\ &\geq f(n) \end{split} \end{equation}

Podemos, assim, depreender que, numa heurística consistente, ff nunca decresce ao longo do caminho.

Voltemos, então, a olhar para a imagem-exemplo anterior:

Ora, notando que não é ótima, resta tentar perceber porque é que não é consistente (já que caso contrário a questão nem se colocaria). Pegando na nossa proposição inicial, h(n)h(n)+c(n,a,n)h(n) \leq h(n') + c(n, a, n'), podemos facilmente perceber que este é desrespeitado:

h(A)=74+1=c(A,B)+h(B).h(A) = 7 \nleq 4 + 1 = c(A, B) + h(B).

Como remate final, podemos dizer que toda a heurística consistente é admissível, mas não podemos afirmar o contrário.


Colocando de parte estas definições sobre heurísticas e voltando à procura AA^*, podemos afirmar que esta é completa para qualquer árvore com conjunto de estados finito. Mais ainda, é ótima para heurísticas admissíveis (como referido mais acima).

A complexidade temporal está, tal como as procuras que vamos abordar mais abaixo, dependente da heurística utilizada - contudo, e como nos costumamos focar no pior caso, podemos afirmar que esta é exponencial, O(bd)O(b^d). Adiciona-se ainda que, como AA^* acaba por consistir numa "BFS guiada por uma heurística", podemos pensar no seu pior caso como tendo uma heurística constante - nesse caso, partilha a complexidade espacial da BFS, também exponencial.

Procura IDA^*

Da mesma maneira que tínhamos, na DFSDFS, uma versão iterativa, que pesquisava a árvore em profundidade com limites que aumentavam sequencialmente, existe uma abordagem de procura AA^* que vai buscar parte da sua lógica à DFS iterativa: a procura IDAIDA^*.

Corresponde, tal como se pode esperar, a uma versão iterativa em profundidade de AA^*, onde aqui o limite, ll, baseia-se em ff (em vez dos níveis da árvore de procura).

A cada iteração, vamos procurar, usando uma DFS* todos os nós da árvore que possuam flf \leq l; caso um nó, aquando da sua geração, tenha f(n)>lf(n) > l, cortamo-lo da árvore momentaneamente. Levamos a iteração até ao fim, e, quando a acabamos, vamos atualizar o limite para o menor valor de ff entre os nós cortados na última iteração. Paramos quando vamos expandir um nó e este passa o teste objetivo - como vamos ver um pouco mais à frente, se o teste fosse feito na geração, perdíamos otimalidade.

*O valor de ff de um nó não é utilizado para escolher o próximo nó a expandir, apenas para decidir se este é cortado - a decisão de qual o nó a expandir é da DFSDFS.

O exemplo seguinte pode ajudar a consolidar ideias:

A procura IDAIDA^* partilha a completude e a complexidade temporal (O(bm)O(b^m)) com AA^*, sendo igualmente ótima para heurísticas admissíveis. Difere, contudo, quanto à complexidade espacial: uma das propriedades que herda da sua semelhança com a DFSDFS é precisamente o espaço que ocupa, linear - O(bm)O(bm) - um claro upgrade em relação ao espaço exponencial ocupado pela abordagem AA^* "normal".

Procura Melhor Primeiro Recursiva (RBFS)

Na sua essência, a RBFSRBFS acaba por procurar implementar a procura melhor primeiro em espaço linear (através da recursão). Vamos procurando expandir sempre o nó, dentro dos filhos do nó atual, que tenha menor valor de ff. Ao mesmo tempo, vamos sempre guardando recursivamente o melhor caminho alternativo ao nó atual - ou seja, o seu irmão ou antepassado com menor valor de ff. Se nenhum dos seus filhos tiver ff menor que esse valor alternativo, passamos então a explorar o nó alternativo guardado (a recursão permite-nos recuperá-lo). A procura termina assim que tentarmos expandir um nó que passa no teste objetivo.

De realçar que a função de avaliação utilizada continua a ser igual à de AA^*,

f(n)=g(n)+h(n).f(n) = g(n) + h(n).
Exemplo RBFS, Arad-Bucareste

Observe-se o exemplo seguinte:

Note-se a evolução da procura na imagem anterior:

  • ao explorar Arad, encontrámos Sibiu, Timisoara e Zerind; Sibiu é o nó com menor ff, logo vamos explorá-lo a seguir (e anotamos também que Timisoara, com f=447f = 447, é a sua alternativa);
  • ao explorar Sibiu, encontrámos Arad, Oradea, Fagaras e Rimnicu Vilcea, sendo este último o nó com menor ff, logo vamos explorá-lo a seguir (e anotamos também que Fagaras, com f=415f = 415, é a sua alternativa);
  • ao explorar Rimnicu Vilcea, encontrámos Craiova, Pitesti e Sibiu; estamos agora num impasse: o seu filho com menor valor de ff é Pitesti, com f=417f = 417, mas existe uma alternativa com ff menor. Optamos, claro, por procurar primeiro a alternativa, visto que, caso não o façamos, poderemos estar a ignorar um caminho melhor (e ainda por cima sabemos que ele existe, não faria sentido não ir lá).

Após o backtracking, atualizamos o valor de ff em Rimnicu Vilcea (para o menor valor dos seus filhos - sabemos mais sobre o custo de caminhos que partem dali, logo porque não precisar ainda mais o custo daquele caminho?). Anotamos, agora, Rimnicu Vilcea como alternativa a Fagaras e prosseguimos à respetiva expansão. Encontramos, de novo, o mesmo problema: Bucareste, com f=450f = 450, é o seu filho com menor valor de ff, sendo este valor maior que o caminho alternativo guardado anteriormente. Vamos, portanto, voltar a andar para trás e seguir em frente em Pitesti:

Note-se como, desta vez, o caminho alternativo guardado é o de Timisoara - conseguimos, recursivamente, voltar lá, ao melhor caminho alternativo por visitar, se for preciso. O próximo nó a expandir seria Bucareste (418418), que passa o teste objetivo, pelo que podemos interromper a procura - chegámos ao caminho ótimo!

No exemplo acima, podemos notar que ocorrem duas mudanças de opinião por parte do algoritmo. Estas mudanças de opinião, apesar de fulcrais para o funcionamento do algoritmo, levam a uma regeneração de nós que rapidamente se pode tornar desagradável: utilizando apenas espaço linear, o algoritmo acaba por ter de "esquecer" caminhos já expandidos, o que leva a que tenhamos que expandir nós repetidamente, acabando por afetar a complexidade temporal da procura. É, contudo, completa (para caminhos com custo crescente) e ótima (para heurísticas admissíveis), which is pretty nice.

A complexidade espacial linear deve-se a guardarmos, na pior das hipóteses, o caminho correspondente a todo um ramo, do início ao fim: caso tenhamos um caminho com profundidade dd, em que o último nó pai a ser expandido tem bb filhos, vamos ter (d1)+bd(d - 1) + bd nós em memória (já que esquecemos todos os nós que não estejam no caminho que estamos a percorrer), pelo que o espaço ocupado é dado por O(bd)O(bd). A complexidade temporal é, tal como na procura IDAIDA^*, exponencial: O(bd)O(b^d).

Heurísticas - deep-dive

Considere-se o problema 8-Puzzle, onde, dada uma configuração inicial de peças, o objetivo passa por movê-las horizontal ou verticalmente até atingir a configuração-objetivo.

Custo Ótimo = 26 passos

Temos, como propriedades calculadas à priori do problema, que a profundidade média de uma solução para este problema (dada uma configuração inicial gerada aleatoriamente) é de 2222 passos. Mais ainda, o fator de ramificação, bb, é de cerca de 33: com o canto vazio, podemos mover para lá 22 peças; com o centro vazio, podemos mover para lá 44 peças, e com qualquer outra posição vazia podemos mover para lá 33 peças (e a ramificação média acaba por ser à volta de 33). Temos, portanto, que uma árvore de procura poderá ter, no caso médio, bd=322b^d = 3^{22} estados: fazer uma procura exaustiva por todos eles seria relativamente desagradável, pelo que convém arranjarmos uma boa heurística que nos permita restringir de forma concisa certos ramos da árvore, evitando pesquisas desnecessárias.

Existem duas heurísticas admissíveis clássicas para o 8-Puzzle a que se costuma recorrer para ilustrar a utilidade de boas heurísticas:

  • uma primeira, seja ela h1h_1, que admite que qualquer peça que não esteja na posição correta precisa de pelo menos um movimento para lá chegar. Com gig_i a representar a posição correta da peça ii, e nin_i a sua posição atual, podemos definir h1h_1 tal que:

    h1(n)=i=18{1se nigi0caso contraˊrioh_1(n) = \sum_{i=1}^{8} \left\{ \begin{array}{ll} 1 & \text{se } n_i \neq g_i \\ 0 & \text{caso contrário} \end{array} \right.

    No caso do 8-Puzzle proposto acima, temos que h1(n)=8h_1(n) = 8, inicialmente. A heurística é, claro, admissível: cada jogada move apenas uma peça, pelo que, se houver inicialmente xx peças fora do sítio, pelo menos xx movimentos terão de ser feitos para chegar à configuração pretendida. Garantidamente, h1(n)h(n)h_1(n) \leq h^*(n).

  • uma segunda, seja ela h2h_2, que recorre à noção de distância de Manhattan entre uma peça e a sua localização correta, por forma a estimar o número de passos necessários até a atingir. h2h_2 pode ser definida da seguinte forma:

    h2(n)=i=18ginih_2(n) = \sum_{i=1}^{8} |g_i - n_i|

    Tal como h1h_1, h2h_2 é igualmente admissível: estamos aqui a admitir que se realizarmos uma quantidade de movimentos exatamente igual ao chão do número de movimentos requeridos para colocar todas as peças no sítio, elas ficam no sítio. Esta estimativa e o número real podem até ser iguais, mas como só movemos uma peça por jogada, a estimativa nunca ultrapassará o custo real, pelo que h2(n)h(n)h_2(n) \leq h^*(n). Note-se ainda que, para o exemplo utilizado, h2(n)h_2(n) é inicialmente 3+1+2+2+2+3+3+2=183 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18: a peça 11 precisa de 33 movimentos horizontais e/ou verticais para chegar à peça ideal, a peça 22 de apenas 11 e assim sucessivamente.

Comparar heurísticas

Seria agora interessante comparar h1h_1 e h2h_2, para procurar perceber qual das duas acaba por dar maiores ganhos de desempenho em procuras. Uma maneira bastante comum de fazer esta comparação é recorrendo a bb^*, o effective branching factor da árvore de procura, já que este acaba por ser relativamente consistente para problemas suficientemente difíceis. Dizemos que heurísticas são tanto melhores quanto mais o seu bb^* se aproximar de 11, já que dessa forma estamos efetivamente a dizer que para atingir a "solução média" do problema praticamente não temos de fazer branching (ou pouco), havendo, portanto, menos caminhos alternativos a ser explorados: com uma heurística ideal, teríamos b=1b^* = 1 e a árvore de procura seria apenas um ramo contínuo.

O livro que acompanha a cadeira apresenta uma tabela que ajuda a comparar o número total de nós gerados e o bb^* entre AA^* com cada uma das heurísticas e a DFS iterativa (esta última uma procura cega, sem heurísticas).

Como podemos observar, a procura cega torna-se rapidamente incomportável. Para além disso, apesar de h1h_1 não ser horrível, não traz qualquer benefício em comparação com h2h_2 e existe uma justificação teórica para tal acontecer.

Em primeiro lugar, vamos notar que

h1(n)h2(n)h(n),n.h_1(n) \leq h_2(n) \leq h^*(n), \forall_n.

Quando, para qualquer nó nn, podemos garantir que h2(n)h1(n)h_2(n) \geq h_1(n), afirmamos que h2h_2 domina h1h_1. Mais importante ainda, a noção de dominância traduz-se diretamente em eficiência: se h2h_2 domina h1h_1, h2h_2 nunca irá expandir mais nós que h1h_1.

Prova: Dominância     \implies Eficiência

Na procura AA^*, é garantido que todos os nós com função de avaliação menor que o custo do caminho mais barato vão ser expandidos - todos os nós tal que f(n)<Cf(n) < C^*. Tal é o mesmo que afirmar que todos os nós com h(n)<Cg(n)h(n) < C^* - g(n) serão expandidos. Ora, mas se h2h_2 domina h1h_1, então qualquer nó expandido via h2h_2 será inevitavelmente expandido por h1h_1, podendo ainda haver mais nós a ser expandidos com esta última. Assim sendo, podemos afirmar que, com h2h_2, vamos sempre expandir menos nós, garantindo portanto que h2h_2 é mais eficiente.

Heurísticas não admissíveis podem fazer sentido

Considere-se um agente GPS. Um condutor fez uma query, em que pediu ao GPS o melhor caminho para ir de Pombal a Vale de Cambra. Tenhamos em atenção o gráfico abaixo, que apresenta o comportamento de três heurísticas em relação ao mesmo problema:

Ora, a primeira coisa em que reparamos ao olhar para h3h_3 é, provavelmente, de duas uma:

  • h3h_3 pode não levar a uma procura ótima, já que há certos intervalos em que não é admissível, isto é, h3(n)>h(n)h_3(n) > h^*(n);
  • h3h_3 domina tanto h2h_2 como h1h_1, encontrando-se inclusive sempre muito mais próxima de hh^* que as outras duas.

Voltemos ao exemplo do GPS: considere-se que as duas primeiras heurísticas demoram 44 e 55 minutos, respetivamente, a responder à query proposta, e que a terceira demora 77 segundos. Com um erro associado tão baixo (h3h_3 nunca se desvia muito de hh^*), não fará mais sentido contentarmo-nos com uma resposta quase ótima mas muito rápida, em vez de uma que seja garantidamente ótima mas que seja bastante demorada? Um trajeto de 11 hora e um quarto retornado de forma praticamente instantânea parece, sem dúvida, uma proposta melhor do que um caminho que corte 22 minutos à duração da viagem, mas cuja resposta demore muito mais!

Como inventar boas heurísticas?

Página em Construção

Esta secção encontra-se atualmente incompleta.

O conteúdo será adicionado assim que possível.


Adicionamos que esta secção corresponde ao terceiro capítulo do livro que acompanha a cadeira (Solving Problems by Searching), sub-secções 3.5 e 3.6.