MAC0323 2018: guloso x shortest paths no EP07

Oi,

Teria alguma explicação de exatamente o porquê de um algoritmo guloso não funcionar nesse EP? No video linkado na aba do EP, é brevemente mencionado que não funciona para o método alternativo de resolução, mas, dado que cada "vértice" da matriz criada age como o vetor distTo[i][j], eu não consigo entender bem qual a propriedade que não permite um guloso funcionar.

Outra coisa, também no tópico shortest paths: qual a diferença do código para a menor distância mostrado na última aula e o algoritmo de dijkstra? Especificamente, por que não seguir a ordem proposta pelo algoritmo de dijkstra (a casa do vetor distTo[i] com menor valor sofre "relaxation") não interfere no resultado?

Re: guloso x shortest paths no EP07

por José Coelho de Pina (admin) - sexta-feira, 22 jun. 2018, 23:58

Oi Gabriel,

eu não consigo entender bem qual a propriedade que não permite um guloso funcionar.

Hmm.
Veja se ajuda.
Imagine um caminho bem barato que te leve a um beco onde para sair você tem que pagar os tubos.

qual a diferença do código para a menor distância mostrado na última aula e o algoritmo de dijkstra?

O código na última aula só funciona para grafos acíclicos.
Os vértices de grafos acíclicos podem ser ordenados topologicamente em tem linear, ou seja, O(V+E) (para vetor de listas de adjacência).
Em seguida o algoritmo examina os vértices nessa ordem topológica consumindo tempo O(V+E).
Assim, o consumo de tempo total do algoritmo é O(V+E).

por que não seguir a ordem proposta pelo algoritmo de dijkstra (a casa do vetor distTo[i] com menor valor sofre "relaxation") não interfere no resultado?

Se os pesos nos arcos do digrafo são não-negativos, podemos também usar Dijkstra.
A razão para preferirmos o algoritmo que usa a ordenação topológica é consumo de tempo.
O consumo de tempo de Dijkstra em que a fila priorizada é implementada com min-heaps é O(E lg V) (versus O(V + E)).

Dijkstra pode ser usado para qualquer digrafo em que os pesos nos arcos são não-negativos.

O algoritmo da aula passada pode ser usado apenas para digrafos acíclicos (já que usa ordenação topológica), não importando se há pesos negativos ou não.

Re: guloso x shortest paths no EP07

por Gabriel Araujo - sábado, 23 jun. 2018, 21:18

Oi Professor,

Sobre a questão do guloso, eu ainda não entendi por que não funciona. Digo, o método mostrado no vídeo faz a mesma coisa que o vetor disTo[], não? por que não funcionaria? Entendi bem sua explicação do porque não usar o dijkstra e o porquê desse algoritmo funcionar, mas surgiu outra dúvida: no ep, é utilizada ordem topológica? por que, me parece que não percorremos o todos os vértices do grafo implícito gerado, então isso pode ser considerado uma ordem topológica?

Re: guloso x shortest paths no EP07

por José Coelho de Pina - domingo, 24 jun. 2018, 13:12

Oi Gabriel,

Muito bom você ter perguntado!

Sobre a questão do guloso, eu ainda não entendi por que não funciona

Antes de mais nada temos que ver se estamos falando do mesmo algoritmo guloso.
A denominação algoritmo guloso é muitas vezes usada para paradigmas diferentes de algoritmos.

Digamos que um algoritmo guloso é um algoritmo que não se arrepende de suas decisões.
No caso do caminho mínimo de um determinado vértice origem s a um vértice destino t, o algoritmo é iterativo.
No início de cada iteração temos um caminho (como o algoritmo ativo na DFS).
No início da primeira iteração, o caminho é composto apenas do vértice origem s.
Cada iteração consiste em:

pegar o vértice v que é ponta final do caminho;
examinar todos os arcos v-w saindo do vértice v;
selecionar o vértice o arco v-w mais leve/curto/barato saindo de v;
inserir w no final do caminho;
começar nova iteração (com w no papel de v).

O algoritmo pára quando chegamos ao vértice destino t.

É isso que você está considerando como guloso?