Algoritmo da Arvore Geradora Minima - Conectando Nos de Forma Eficiente

1 Profª Dra Stella Jacyszyn Bachega Algoritmo da Árvore Geradora Mínima 2 Trata de conectar os nós de uma rede direta ou indiretamente usando o comprimento total mais curto de ramos conectores Aplicação típica pavimentação de estradas rurais que ligam várias cidades minimização do comprimento total da estrada pavimentada Árvore Geradora Mínima Etapas Conjunto de nós da rede N 1 2 n Ck conjunto de nós que foram conectados permanentemente na iteração k Ck conjunto de nós que ainda terão que ser conectados permanentemente após a iteração k Etapa 0 Faça C0 O e C0 N Etapa 1 Comece com qualquer nó i no conjunto não conectado C0 e faça C1 i o que dá como resultado C1 N i Faça k 2 Etapa geral k Selecione um nó j no conjunto não conectado Ck1 que dê o arco mais curto até um nó no conjunto conectado Ck1 e elimineo de Ck1 isto é Ck Ck1 j Ck Ck1 j 3 Etapas Se o conjunto de nós não conectados Ck1 for vazio PARE Caso o contrário faça k k 1 e repita a etapa A Midwest TV Cable Company está em vias de fornecer serviços por cabo a cinco novas áreas onde estão em desenvolvimento de projetos residenciais A figura a seguir mostra as possíveis conexões de TV entre as cinco áreas As extensões em milhas dos cabos são mostradas em cada arco Determine a rede mais econômica Exemplo 4 Exemplo C0 C0 1 2 3 4 5 6 Exemplo Iteração 1 C1 1 C1 2 3 4 5 6 5 Exemplo Iteração 2 C2 1 2 C2 3 4 5 6 Exemplo Iteração 3 C3 1 2 5 C3 3 4 6 6 Exemplo Iteração 4 C4 1 2 4 5 C4 3 6 Exemplo Iteração 5 C5 1 2 4 5 6 C5 3 7 Exemplo Iteração 6 C6 1 2 3 4 5 6 C6 Exemplo Iteração 6 Comprimento total 16 milhas Rede mais econômica 12 13 24 25 46 ou 12 24 25 34 46 8 Pratique Resolva o mesmo exemplo começando pelo nó 5 ao invés de iniciar pelo nó 1 e mostre que o algoritmo produz a mesma solução Algoritmo para Resolução do Problema de Caminho Mínimo 9 Determina o caminho mais curto entre um destino e uma origem em uma rede de transporte Alguns algoritmos para resolução Algoritmo de Dijkstra desenvolvido para determinar o caminho mais curto entre o nó de origem e qualquer outro nó da rede Algoritmo de Floyd é mais abrangente pois permite a determinação do caminho mais curto entre quaisquer dois nós da rede Problema de Caminho Mínimo Algoritmo de Dijkstra Seja ui a distância mais curta do nó de origem 1 ao nó i e defina se dij 0 como o comprimento do arco i j Então o algoritmo define o rótulo para um nó imediatamente posterior j como uj i ui dij i dij 0 O rótulo para o nó inicial é 0 o que indica que o nó não tem nenhum predecessor Tipos de rótulos temporário é modificado se for possível encontrar uma rota mais curta até um nó permanente se não for possível encontrar nenhuma rota melhor 10 Etapa 0 Rotule o nó de origem nó 1 com o rótulo permanente 0 Determine i 1 Etapa i a Calcule os rótulos temporários ui dij i para cada nó j que puder ser alcançado partindo do nó i contanto que j não seja permanentemente rotulado Se o nó j já estiver rotulado com uj k passando por um outro nó k e se ui dij uj substitua uj k por ui dij i b Se todos os nós tiverem rótulos permanentes PARE Caso contrário selecione o rótulo ur s cuja distância ur é a mais curta entre todos os rótulos temporários empates são resolvidos arbitrariamente Determine i r e repita a etapa i Algoritmo de Dijkstra A rede a seguir dá as rotas possíveis e seus comprimentos em milhas entre a Cidade 1 nó 1 e quatro outras cidades nós 2 a 5 Determine os caminhos mais curtos entre a Cidade 1 e cada uma das outras quatro cidades Exemplo Algoritmo de Dijkstra 11 Iteração 0 Designe o rótulo permanente 0 ao nó 1 Exemplo Algoritmo de Dijkstra Iteração 1 Os nós 2 e 3 podem ser alcançados com base no nó 1 último nó rotulado permanentemente Assim a lista de nós rotulados temporários e permanentes fica Iteração 2 Os nós 4 e 5 podem ser alcançados com base no nó 3 e a lista de nós fica Exemplo Algoritmo de Dijkstra 12 Iteração 3 Os nós 2 e 5 podem ser alcançados com base no nó 4 A lista de nós fica Exemplo Algoritmo de Dijkstra Iteração 4 Só o nó 3 pode ser alcançado com base no nó 2 Contudo o nó 3 tem um rótulo permanente e não pode ser rotulado novamente A nova lista de rótulos permanece a mesma da iteração 3 exceto que o rótulo no nó 2 agora é permanente Isso deixa o nó 5 com o único rótulo temporário Como o nó 5 não leva a outros nós seu status é convertido em permanente e o processo termina Exemplo Algoritmo de Dijkstra 13 Exemplo Algoritmo de Dijkstra Resposta Rota desejada 1 3 4 2 Comprimento total 55 milhas O caminho mais curto entre o nó 1 e qualquer outro nó da rede é determinado começando no nó de destino desejado e percorrendo a rota inversa a partir desse ponto usando a informação dada pelos rótulos permanentes No exemplo 2 554 4 403 3 301 1 Qual é a rota mais curta do nó 1 inicial ao nó 2 final Exemplo Algoritmo de Dijkstra Representação dos cálculos do algoritmo na rede 14 Pratique A rede abaixo dá as distâncias em milhas entre pares de cidades 1 2 3 4 5 6 7 e 8 Use o algoritmo de Dijkstra para achar o caminho mais curto entre as cidades 4 e 8 Resposta do Pratique Use o algoritmo de Dijkstra para achar o caminho mais curto entre as cidades 4 e 8 8 86 6 65 5 34 4 64 Caminho 4 5 6 8 ou 4 6 8 Distância total 8 milhas 15 Bibliografia Básica ARENALES M ARMENTANO V MORABITO R YANASSE H H Pesquisa Operacional para cursos de engenharia Rio de Janeiro Campos 2006 HILLIER F S LIEBERMAN G J Introdução à Pesquisa Operacional São Paulo McGrawHill 2006 TAHA H A Pesquisa Operacional uma visão geral São Paulo Pearson Prentice Hall 2008 Bibliografia Complementar ANDRADE E L Introdução à Pesquisa Operacional Métodos e Modelos para Análise de Decisões Rio de Janeiro LTC 2004 COLIN E C Pesquisa Operacional 170 aplicações em Estratégia Finanças Logística Produção Marketing e Vendas Rio de Janeiro LTC 2007 LACHTERMACHER G Pesquisa operacional na tomada de decisões Rio de Janeiro Campus 2007 MOREIRA D A Pesquisa Operacional Curso Introdutório São Paulo Thomson Learning 2007 PRADO D Teoria das Filas e da Simulação 3ª ed Editora INDG Tecnologia e Serviços Ltda 2006