Home

Exemplo de redução:

• Encontrar o caminho de produto mínimo em um grafo.
  • Mas conhecemos o Dijkstra para achar o caminho de menor soma.
  • Então vamos transformar o nosso problema original em um problema que sabemos resolver. Nesse caso, podemos usar uma propriedade de produtos para transformar em um somatório simples (Veja a resposta marcada como correta para mais detalhes).
  • Exemplo: Caminho A: (4, 4, 4). Caminho B: (2, 2, 15). Logo, soma(A) = 12 e soma(B) = 19. Se simplesmente somarmos, o menor caminho seria o A, mas está errado pois ele dá o maior produto. Mas podemos fazer o log(v[i], e) de cada caminho, fazendo então: Caminho A: (1.39, 1.39, 1.39). Caminho B: (0.69, 0.69, 2.71). Agora aplicamos Dijkstra e encontraremos o menor caminho como sendo o Caminho B, pois: soma(A) = 4.16 e soma(B) = 4.09. Para obter o produto, basta fazer e^4.09 = 60, que é justamente o valor do produto dos valores originais.