Pesquisa marginal - Fringe search

Algoritmos de pesquisa de gráfico e árvore
Listagens
tópicos relacionados

Na ciência da computação , a busca marginal é um algoritmo de busca em gráfico que encontra o caminho de menor custo de um determinado nó inicial para um nó objetivo .

Em essência, a pesquisa marginal é um meio termo entre A * e a variante A * de aprofundamento iterativo (IDA *).

Se g ( x ) é o custo do caminho de pesquisa do primeiro nó ao atual, e h ( x ) é a estimativa heurística do custo do nó atual ao objetivo, então ƒ ( x ) =  g ( x ) +  h ( x ) , e h * é o custo real caminho para o objectivo. Considere o IDA *, que faz uma pesquisa recursiva da esquerda para a direita em profundidade primeiro a partir do nó raiz, parando a recursão assim que o objetivo for encontrado ou os nós atingirem um valor máximo ƒ . Se nenhum objetivo for encontrado no primeiro limite ƒ , o limite é então aumentado e o algoritmo pesquisa novamente. IE itera no limite.

Existem três principais ineficiências com o IDA *. Primeiro, o IDA * repetirá estados quando houver vários caminhos (às vezes não ótimos) para um nó de destino - isso geralmente é resolvido mantendo um cache dos estados visitados. IDA * assim alterado é denotado como IDA * com memória aprimorada (ME-IDA *), uma vez que usa algum armazenamento. Além disso, IDA * repete todas as operações anteriores em uma pesquisa quando itera em um novo limite, que é necessário para operar sem armazenamento. Ao armazenar os nós folha de uma iteração anterior e usá-los como a posição inicial da próxima, a eficiência do IDA * é significativamente melhorada (caso contrário, na última iteração ele sempre teria que visitar cada nó na árvore).

A pesquisa franja implementa essas melhorias no IDA * fazendo uso de uma estrutura de dados que é mais ou menos duas listas para iterar na fronteira ou franja da árvore de pesquisa. Uma lista agora armazena a iteração atual e a outra lista posteriormente armazena a próxima iteração imediata. Portanto, a partir do nó raiz da árvore de pesquisa, agora será a raiz e depois estará vazia. Em seguida, o algoritmo leva uma das duas ações: Se ƒ (cabeça) é maior do que o limite atual, remova a cabeça de agora e anexá-lo para o fim da tarde ; ou seja, salve a cabeça para a próxima iteração. Caso contrário, se ƒ (cabeça) for menor ou igual ao limite, expanda a cabeça e descarte a cabeça , considere seus filhos, adicionando-os ao início de agora . No final de uma iteração, o limite é aumentado, a lista posterior se torna a lista now e, posteriormente, é esvaziada.

Uma diferença importante aqui entre fringe e A * é que o conteúdo das listas em fringe não precisa necessariamente ser classificado - um ganho significativo em relação a A *, que requer a manutenção frequentemente cara da ordem em sua lista aberta. Diferentemente de A *, entretanto, a franja terá que visitar os mesmos nós repetidamente, mas o custo de cada visita é constante em comparação com o tempo logarítmico do pior caso de classificação da lista em A *.

Pseudo-código

Implementando ambas as listas em uma lista duplamente vinculada, onde os nós que precedem o nó atual são a parte posterior e todos os outros são a lista agora . Usando uma matriz de nós pré-alocados na lista para cada nó na grade, o tempo de acesso aos nós na lista é reduzido a uma constante. Da mesma forma, uma matriz de marcadores permite que a pesquisa de um nó na lista seja feita em tempo constante. g é armazenado como uma tabela hash, e uma última matriz de marcador é armazenada para pesquisa em tempo constante se um nó foi ou não visitado antes e se uma entrada de cache é válida. 

init(start, goal)
    fringe F = s
    cache C[start] = (0, null)
    flimit = h(start)
    found = false

    while (found == false) AND (F not empty)
        fmin = ∞
        for node in F, from left to right
            (g, parent) = C[node]
            f = g + h(node)
            if f > flimit
                fmin = min(f, fmin)
                continue
            if node == goal
                found = true
                break
            for child in children(node), from right to left
                g_child = g + cost(node, child)
                if C[child] != null
                    (g_cached, parent) = C[child]
                    if g_child >= g_cached
                        continue
                if child in F
                    remove child from F
                insert child in F past node
                C[child] = (g_child, node)
            remove node from F
        flimit = fmin

    if reachedgoal == true
        reverse_path(goal)

Pseudocódigo reverso. 

reverse_path(node)
    (g, parent) = C[node]
    if parent != null
        reverse_path(parent)
    print node

Experimentos

Quando testado em ambientes baseados em grade típicos de jogos de computador, incluindo obstáculos intransponíveis, a franja superou A * em cerca de 10 a 40 por cento, dependendo do uso de ladrilhos ou octeis. Outras melhorias possíveis incluem o uso de uma estrutura de dados que se presta mais facilmente aos caches.

Referências

links externos