PESQUISA OPERACIONAL

Disciplina: Teoria dos Grafos

BUSCA EM GRAFOS

CAPÍTULO 7 - Algoritmo da Matriz de Custo Geral

 

Professor: Altamir A. R. Araldi

Apostila de um Curso de Mestrado! 

  

Curso Completo (Apostila)

 

 

Algoritmo da Matriz de Custo Geral

 

AUTORES: Ford, Moore, Bellman

 

DATA: em torno de 1950

 

NOMENCLATURA:

                :  label do vértice xi depois de k+1 iterações.

       S       :  conjunto de todos os vértices cujos caminhos mais curtos atuais desde s são de Cardinalidade k.

       Ti      :  conjunto de vértices para os quais os caminhos mais curtos atuais dede s são de Cardinalidade k e no qual um arco xi existe.

 

FUNDAMENTOS:

É um método iterativo baseado na designação de labels nos vértices. No final da iteração k, os labels representam os valores dos caminhos mais curtos destes que contêm k+1 ou menos arcos.

 

OBSERVAÇÃO: Diferente de Dijstra, nenhum label pode ser considerado permanente no processo até que todos os sejam.

 

ALGORITMO CONCEITUAL

Passo 1: INICIALIZAÇÃO

   - calcular           para todo xi ≠ s

   - S=Γ(s), k=1, l’(s)=0,

   - l’(xi)=C(s,xi) para xi ∈ S

   - l’(xi)=0 para xi ∉ S

 

Passo 2: ATUALIZAÇÃO DOS LABELS

   a. Determinar vértices cujos labels podem ser modificados → xi ∈ Γ(s), xi ≠ s

   b. Determinar Ti=           ∩ S para xi ∈ Γ(s), xi ≠ s

   c. Atualizar os labels

 

 

 

Passo 3: TESTE DE FINALIZAÇÃO

  

 

 

 

Passo 4: ATUALIZAÇÃO DE S

 

 

Passo 5: INCREMENTO DE K

   k=k+1 Volte ao Passo 2.

 

 

OBSERVAÇÃO: Este algoritmo pode ser usado para Cij=0, desde que não exista no grafo um Circuito cujo Custo seja Negativo.

  A partir de 11 Set de 2020

Você é o Visitante de Número

(48) 8410.6510 /  faleconosco@ensinoeinformacao.com  /  Florianópolis - SC - Brasil

  • w-facebook
  • Twitter Clean
  • w-googleplus

® 2003 - 2018 Todos os direitos Reservados, ensinoeinformacao.com

Temos Uma versão desta Revista Especificamente para SmartPhones: Versão mais Enxuta somente com Vídeo Aulas e Eventos