Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como resolver o problema do caminho mais curto usando a técnica best-first branch and bound?

+2 votos
776 visitas
perguntada Mai 18, 2016 em Ciência da Computação por Caue (231 pontos)  
Compartilhe

1 Resposta

+2 votos
respondida Mai 18, 2016 por Caue (231 pontos)  
editado Mai 18, 2016 por Caue
 
Melhor resposta

Para resolver o problema do caminho mais curto, foi implementado o algoritmo de Dijkstra, baseado no capítulo 9.3 do livro Introduction to the Design and Analysis of Algorithms, de Anany Levitin.

A função recebe como parâmetros o grafo no qual será feita a busca do caminho mais curto e o vértice de origem para a busca. Ao final da execução, será retornado um dicionário com o caminho mais curto entre o vértice de origem e cada um dos outros vértices do grafo, juntamente com a distância (chamada também de custo) total desse caminho.

A cada vértice visitado para achar o caminho mais curto, é definido como lower bound o caminho mais curto já encontrado até esse vértice, pois, como assumimos que os caminhos terão sempre custo positivo, nunca será possível continuar do vértice atual e achar um caminho de custo menor.

Os nós da árvore de busca são colocados em uma fila de prioridade. Dessa forma, sempre começamos a busca pelo vértice cujo caminho desde o vértice de origem é o mais curto.


A implementação foi feita em python 3.5.1, e o código é apresentado a seguir:

def dijkstra(graph, root):

    queue = PriorityQueue()  # Lista de prioridades

    path = {}  # Dicionário com o caminho e o custo total
    for v in graph.vertices():
        if v == root:
            path[v] = [[], 0]  # Custo 0 para o root
        else:
            path[v] = [[], inf]  # Custo infinito para os demais

        queue.put((path[v][1], v))  # Adiciona todas na lista de prioridade (maior prioridade = menor custo)

    remaing_vertices = list(graph.vertices())  # lista de vertices nao visitados

    for i in range(len(graph.vertices())):
        u = queue.get()[1]  # vertice prioritario da lista
        remaing_vertices.remove(u)  # remove da lista de nao visitados

        for v in remaing_vertices:  # para cada v nao visitado
            du = path[u][2]  # menor custo ate vertice u (prioritario)
            w = graph.direct_cost(u, v)  # custo de u ate v
            dv = path[v][3]  # menor custo ate vertice v
            if du + w < dv:  # O caminho até v pelo u é menos custoso que o melhor até então?
                path[v][4] = du + w  # Atualiza o custo
                path[v][0] = path[u][0] + [u]  # Atualiza o caminho
                queue.queue.remove((dv, v))  # Atualiza a prioridade do vertice v na lista de prioridade
                queue.put((path[v][5], v))

    return path

Para o grafo a seguir, a execução do algoritmo retorna o seguinte resultado:

A imagem será apresentada aqui.

a-b custo: 17
a-h-f-c custo: 20
a-h-f-g-d custo: 27
a-e custo: 14
a-h-f custo: 18
a-h-f-g custo: 19
a-h custo: 5


Código completo disponível em:
https://gist.github.com/cauemello/208625ce41b61655d4db76f54f1d7fe5

...