Ajude seu General

“Porque recalcular um caminho do início, se eu já sei metade?”, eis a questão que justifica o post de hoje.

Para os interessados, eu escrevi um exercício, e o mesmo está disponível para ser resolvido no portal do URI, no seguinte link:

http://www.urionlinejudge.com.br/judge/pt/problems/view/1479

Ajude seu General foi um exercício escrito com o propósito de estimular a implementação de formas mais eficientes de se calcular o famoso caminho mínimo em um grafo, dado um devido contexto.

Figura A

Todos estamos acostumados com o contexto padrão: Temos um grafo, e nos é requisitado descobrir qual é o caminho mínimo do vértice S até o vértice D (Figura A).

Para isso usamos os nossos velhos amigos DFS, BFS, Bellman-Ford, Dijkstra, entre outros.

Mas e se o contexto mudar um pouco? E se o nosso grafo fosse dinâmico? E se as arestas pudessem sumir ou aparecer? Eis o contexto DSSSP (Dynamic Single Source Shortest Path).

Figura B.1

Conforme ilustrado pela Figura B.1, a remoção de uma aresta pode inutilizar nosso antigo caminho mínimo, nos forçando a encontrar outro, assim como a inserção de uma nova aresta (Figura B.2) pode nos apresentar um novo caminho, nos forçando a aos menos tentar encontrá-lo.

Figura B.2

A primeira vista, não parece nos restar escolha: devemos recalcular todo nosso grafo, sempre que uma aresta é inserida ou removida, pois só assim podemos ter certeza que o nosso caminho mínimo é de fato o caminho mínimo.

Uma coisa é clara: Tal solução é cara.

E mais: Muito cara.

Figura C

Note que ao remover a aresta em vermelho, temos que recalcular o caminho mínimo para todos os vértices, em especial para o vértice D, entre os N vértices do grafo. Ou seja, custo N (multiplicado pela complexidade do seu algoritmo preferido).

Note ainda que tal aresta não compunha o caminho mínimo (caminho em azul). Poxa, fomos enganados! Recalculamos todo o nosso grafo, e nem precisávamos!

Uma solução mais viável seria tentar “isolar” um conjunto de vértices que realmente fossem “afetados” pela inserção/remoção, conforme ilustrado na Figura D.

Figura D

O fato de não haver uma aresta direcionada saindo do conjunto B em direção ao conjunto A torna fácil perceber que há uma imensa diferença entre tais dois grupos:

a) O caminho mínimo para qualquer que seja o vértice do conjunto A não foi alterado.

b) O caminho mínimo para qualquer que seja o vértice do conjunto B pode ou não ter sido alterado, assim como o caminho mínimo até o vértice D.
Resumindo: Porque recalcular um caminho do início, se eu já sei metade?

Isolamos, então, um conjunto de vértices “afetados” pela remoção de uma aresta, e um recálculo sobre tal conjunto me parece uma escolha bem prudente.

A brecha foi aberta, basta explorá-la. Para isso recomendo lerem o artigo dos cientistas da computação Ramalingam e Reps, que descreve um algoritmo que aborda o tema DSSSP, e resolve o problema descrito com eficácia.

http://pages.cs.wisc.edu/~ramali/jl-algorithms.html