Existem gráficos para os quais um * não pode ser admissível?

Question

Wikipedia afirma que "em gráficos infinitos com um fator de ramificação finito e Custos de borda que são limitados a partir de zero $ (D (x, y)> \ Varepsilon> 0 $ para alguma fixa $ \ VAREPSILON $ ), A * é garantido para terminar apenas se existe uma solução. "

Isso significa que, se eu tiver um gráfico, não há admissível A * que existe para este gráfico? Quando alguém diz que um * não é admissível, isso significa que sua heurística não é admissível, certo?

Além disso, é correto dizer que uma heurística só é admissível em relação a um gráfico - não é geralmente admissível?

Por exemplo, se eu tiver um gráfico infinito que tenha um fator de ramificação finito, e o custo de cada borda é metade do custo da borda Precedendo (algo assim: $ gol \ \ {_ {c= 2}} Start \ righttarrow _ {_ {c= 1}} Q1 \ righttarrow_ {_ {c= 1/2}} q_2 \ righttarrow ... $ ), a heurística e, portanto, o * é necessariamente inadmissível como não existe nenhuma fixa $ \ epsilon> 0 $ que é menor que o custo de qualquer borda?

Para generalizar, o $ epsilon $ restrição é garantir que não há caminho infinito que é convergente total de custos, garantindo assim a rescisão?

Qualquer esclarecimento é apreciado. Obrigado!

Answer 1

a função heurística $ h: v \ longrightarrow \ mathbb {r} _ {\ geq 0} $ é * uma entrada para a matemática $ a ^ * $ algoritmo. Se a função é admissível , em seguida, $ a ^ * $ algoritmo dá a solução; No entanto, como você observou para gráficos infinitos, os pesos da borda devem ter um limite inferior positivo.

O ponto da função heurística é encontrar o caminho mais curto no mínimo de tempo , i.e. Abaixe a complexidade computacional; Porque você está tomando decisões informadas com base em uma heurística (daí o nome).

Lembre-se da função heurística é admissível se $ h (v) $ é sempre menor que (ou igual a) o verdadeiro caminho custa para o nó da meta.

Há sempre uma admissível $ h $ nomeadamente $ h (v)= 0 $ para todos $ v $ . Nesse caso extremo, torna-se Algoritmo de Dijkstra .

Retornando ao exemplo que você deu se você conectar a entrada $ a ^ * (g, h) $ onde $ G $ é uma descrição da $ g $ e $ h= 0 $ < span class="contentor de matemática"> $ a ^ * $ não parou (série geométrica $ r= 2 \ implica \ sum_i r ^ i= { 1-r ^ {n + 1}} {1-r}} \ leq 2 $ para todas as somas parciais finitas). Mas vamos ver se podemos contornar isso; Vamos tentar: \ begin {equation} h (v)=begin {casos} 3 & \ text {\} v= q_1 \\ 0 & \ text {else} { casos} \ end {equation} como você pode ver $ h $ é admissível (porque $ D (Q_1 , \ texto {goal})= 3 $ no nariz) e $ a ^ * $ escolherá "meta" como seu primeiro nó (porque é Duas escolhas são $ f (q_1)= 4 $ ou $ f (\ text {goal})= 2 $ ).