65
Faculdade de Filosofia, Ciências e Letras de Mandaguari Departamento de Informática APOSTILA DA DISCIPLINA ANÁLISE DE ALGORITMOS Profa. Camilla Brandel Martins Mandaguari, 2004

Apostila Análise de Algoritmos

Embed Size (px)

DESCRIPTION

analise de algoritmos

Citation preview

Page 1: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari Departamento de Informática

APOSTILA DA DISCIPLINA ANÁLISE DE ALGORITMOS

Profa. Camilla Brandel Martins

Mandaguari, 2004

Page 2: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 2 Curso: Informática Disciplina: Análise de Algoritmos Ementa da Disciplina

Estudo de conceitos e análise da complexidade de algoritmos.

Programa: 1. Introdução 1.1 Objetivo da Disciplina 1.2 Medidas de Desempenho de Algoritmos 2. Teoria dos Grafos 2.1. Introdução 2.2. Sucessores e Antecessores de um Grafo Dirigido 2.3. Representação de Grafos em um Computador 2.4. Caminho e Conexidade 2.5. Localização de Centros 2.6. Algoritmos e problemas clássicos com grafos 2.7. Busca em Grafos 2.8. Fluxo em rede 3.Complexidade de Algoritmos 3.1.Definições 3.2. Notação O, Omega e Theta 3.3. Crescimento assintótico de funções 4. Análise da Complexidade de Algoritmos 4.1 Estimativas de Tempo de Execução 4.2. Regras para Análise de Algoritmos 4.3. Relações de recorrência 5. Técnicas de Projeto de Algoritmos 5.1 Algoritmos de Ordenação 5.1.1 Algoritmos de Ordenação por inserção 5.1.2 Algoritmos de Ordenação por seleção 5.1.3 Algoritmos de Ordenação por troca 5.2 Algoritmo da Força Bruta 5.3 Algoritmo Minmax 5.4 Algoritmo dividir e conquistar 5.5 Algoritmo Guloso 6. Teoria da Complexidade 6.1. Tipos de Problemas 6.2. Classes de Problemas 6.2.1. Problemas P, NP e NP-Completos Previsão de Avaliações: 1o. Bimestre – Uma prova escrita valendo 7,0 e um trabalho valendo 3,0 2o. Bimestre – Uma prova escrita valendo 7,0 e um trabalho valendo 3,0 3o. Bimestre – Uma prova escrita valendo 7,0 e um trabalho valendo 3,0 4o. Bimestre – Uma prova escrita valendo 7,0 e um trabalho valendo 3,0

Page 3: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 3 Curso: Informática Disciplina: Análise de Algoritmos

ÍNDICE 1 INTRODUÇÃO ................................................................................................................................ 5

1.1 OBJETIVO DA DISCIPLINA ........................................................................................................... 5 1.2 MEDIDAS DE DESEMPENHO DE ALGORITMOS .............................................................................. 5

2 TEORIA DOS GRAFOS .................................................................................................................. 7 2.1 INTRODUÇÃO ............................................................................................................................. 7

2.1.1 Representação Gráfica ......................................................................................................... 8 2.1.2 Representação Matemática ................................................................................................... 8 2.1.3 Definições Básicas ................................................................................................................ 8 2.1.4 Tipos de Grafos .................................................................................................................... 9

2.2 SUCESSORES E ANTECESSORES DE UM GRAFO DIRIGIDO ............................................................ 12 2.3 REPRESENTAÇÃO DE GRAFOS EM UM COMPUTADOR .................................................................. 12

2.3.1 Matriz de Adjacência .......................................................................................................... 12 2.3.2 Matriz de Custo .................................................................................................................. 13 2.3.3 Matriz de Incidência ........................................................................................................... 13 2.3.4 Lista de Arestas .................................................................................................................. 14 2.3.5 Estrutura de Adjacência ...................................................................................................... 14

2.4 CAMINHO E CONEXIDADE ........................................................................................................ 15 2.4.1 Caminho ............................................................................................................................. 15 2.4.2 Cadeia ................................................................................................................................ 15 2.4.3 Comprimento ...................................................................................................................... 15 2.4.4 Caminho Simples x Trajetória ............................................................................................. 16 2.4.5 Grafo Conexo ..................................................................................................................... 16 2.4.6 Caminhos abertos e fechados .............................................................................................. 16 2.4.7 Circuito e Ciclo .................................................................................................................. 16 2.4.8 Algoritmo de Goodman ....................................................................................................... 17

2.5 LOCALIZAÇÃO DE CENTROS (EM GRAFOS NÃO VALORADOS) ...................................................... 18 2.5.1 Distância ............................................................................................................................ 18 2.5.2 Pista ................................................................................................................................... 19 2.5.3 Excentricidade .................................................................................................................... 19 2.5.4 Raio ................................................................................................................................... 19 2.5.5 Centro ................................................................................................................................ 19 2.5.6 Centro de um grafo dirigido ................................................................................................ 20 2.5.7 Localização de Centros de Emergência ............................................................................... 20

2.6 ALGORITMOS E PROBLEMAS CLÁSSICOS COM GRAFOS ................................................................ 23 2.6.1 Algoritmo de Floyd ............................................................................................................. 23 2.6.2 Algoritmo de Dijkstra ......................................................................................................... 28 2.6.3 Grafos de Euler .................................................................................................................. 30 2.6.4 Problema do Carteiro Chinês.............................................................................................. 30 2.6.5 Caminho e Circuito Hamiltoniano....................................................................................... 34 2.6.6 Problema do Caixeiro Viajante ........................................................................................... 34

2.7 BUSCA EM GRAFO .................................................................................................................... 44 2.7.1 Algoritmo Básico ou Busca Geral ....................................................................................... 44 2.7.2 Busca em Profundidade ...................................................................................................... 46 2.7.3 Busca em Largura .............................................................................................................. 49

2.8 FLUXO EM REDE ...................................................................................................................... 53 3 EFICIÊNCIA E CORRETUDE DE ALGORITMOS ................................................................... 54

3.1 DEFINIÇÕES ............................................................................................................................. 54 3.1.1 O que é um algoritmo?........................................................................................................ 54 3.1.2 Instâncias de execução de algoritmos .................................................................................. 55 3.1.3 Avaliação de Algoritmos ..................................................................................................... 55

3.2 NOTAÇÃO O, OMEGA E THETA ................................................................................................. 57 3.2.1 Notação O .......................................................................................................................... 57

3.3 CRESCIMENTO ASSINTÓTICO DE FUNÇÕES ................................................................................. 59

Page 4: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 4 Curso: Informática Disciplina: Análise de Algoritmos 4 ANÁLISE DA COMPLEXIDADE DE ALGORITMOS ............................................................... 60

4.1 ESTIMATIVAS DE TEMPO DE EXECUÇÃO .................................................................................... 60 4.2 REGRAS PARA ANÁLISE DE ALGORITMOS .................................................................................. 60 4.3 RELAÇÕES DE RECORRÊNCIA .................................................. ERRO! INDICADOR NÃO DEFINIDO.

Page 5: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 5 Curso: Informática Disciplina: Análise de Algoritmos

1 Introdução

1.1 Objetivo da Disciplina Nesta altura do curso, a maioria dos alunos já deve ter compreendido que o

desenvolvimento de algoritmos é uma atividade fundamental da computação. Assim, esta é mais uma disciplina que irá ajudá-lo a aprimorar suas habilidades de programação.

Nas disciplinas de engenharia de software, aprende-se vários métodos e procedimentos que devem ser adotados para produzir um software eficiente e de qualidade, utilizando o menor tempo possível e a menor quantidade possível de recursos. A disciplina Análise de Algoritmos está, portanto, relacionada com a engenharia de software, pois um de seus objetivos é a produção de softwares eficientes. A diferença é que a engenharia se preocupa com diversos aspectos do software, como o paradigma utilizado, qual é a melhor linguagem de preocupação, como montar uma equipe de programadores, etc. Já a análise de algoritmos se preocupa unicamente com uma atividade: a codificação.

Assim, o objetivo final desta disciplina é fazer com que os alunos produzam não apenas códigos que funcionem, mas que sejam também eficientes. Para isso, vamos estudar alguns tipos de problemas que podem ser resolvidos computacionalmente. Em seguida, vamos ver como a abordagem adotada para resolver pode influenciar, levando a um algoritmo mais ou menos eficiente.

Em longo prazo, espera-se que o aluno consiga naturalmente compreender quais estruturas e técnicas são mais adequadas para cada problema e as utilize de forma a produzir programas o mais eficientes possível.

"Ao verificar que um dado programa está muito lento, uma pessoa prática pede uma máquina mais rápida ao seu chefe.

Mas o ganho potencial que uma máquina mais rápida pode proporcionar é tipicamente limitado por um fator de 10, por razões técnicas ou econômicas.

Para obter um ganho maior, é preciso buscar melhores algoritmos. Um bom algoritmo, mesmo rodando em uma máquina lenta,

sempre acaba derrotando (para instâncias grandes do problema) um algoritmo pior rodando em uma máquina rápida. Sempre."

- S. S. Skiena, The Algorithm Design Manual

1.2 Medidas de Desempenho de Algoritmos Uma possível definição para algoritmo é a de que um algoritmo é um método para

resolver uma classe de problemas utilizando um computador. A complexidade de um algoritmo seria então o custo de se utilizar o algoritmo para resolver um desses problemas, sendo que custo pode ser medido em tempo de processamento, armazenamento, ou outra unidade de medida (Wilf, 1994).

Os programas utilizados nos computadores domésticos geralmente executam rapidamente. Mas quem já compilou um grande programa sabe que o tempo gasto nessa atividade pode ser bastante longo. Quem já tentou fazer um programa para calcular o valor de pi () sabe que atualmente essa é uma tarefa impossível. O estudo do montante de esforço computacional necessário para executar alguma computação é chamado de estudo da complexidade.

Page 6: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 6 Curso: Informática Disciplina: Análise de Algoritmos

Um dos fatores que influencia o tempo de processamento é o volume de dados. Não é difícil perceber que calcular a soma de 2 números é mais rápido do que fazer a soma de 2000 números. Assim, uma das medidas para se verificar a complexidade de um algoritmo é o tempo de execução em relação ao volume de dados.

Por exemplo, suponha que você escreveu um pequeno programa que pede ao usuário para digitar quantos nomes ele quiser. Em seguida, o programa apresenta os nomes em ordem alfabética. Ao executar o programa e digitar 100 nomes, você percebe que o programa demorou 1 segundo. Ao digitar 1000 nomes, você percebe que ele demorou 9 segundos (quando, por uma regra de 3 simples, você pudesse achar que ele iria demorar 10 segundos). O que isso quer dizer?

Bom, isso quer dizer que não é assim tão simples prever quanto tempo o programa demorará para executar quando você utilizar grandes volumes de dados. Assim, para que possamos prever o seu comportamento com grandes volumes, é preciso analisar o algoritmo e fazer alguns cálculos.

Para aprender a fazer esses cálculos, naturalmente tomaremos alguns problemas computacionais como exemplo. E como vários dos problemas clássicos da computação envolvem o uso de grafos, iniciaremos o curso estudando teoria dos grafos.

Page 7: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 7 Curso: Informática Disciplina: Análise de Algoritmos

2 Teoria dos Grafos

2.1 Introdução Os grafos, ou problema em grafos, são estudados há muitos anos. Já em 1736, Euler

descreveu o seguinte problema: Dada a configuração abaixo1, tendo um rio com duas ilhas, duas margens e 7 pontes, é possível passar por todas as pontes sem repetir nenhuma? Como provar?

Para resolver esse problema, Euler o representou com o grafo ilustrado na Figura 1.

Com essa representação, e considerando as propriedades do grafos que serão apresentadas mais tarde nesse curso, é possível resolver facilmente esse problema.

Figura 1 . Representação gráfica do problema de Euler

Esse tem sido considerado o primeiro problema do que hoje chamamos de teoria

dos grafos. No entanto, até o fim do século 19 houve poucos trabalhos na área. Por exemplo, em 1847, Kirchhoff utilizou modelos de grafos no estudo de circuitos elétricos. Em 1857, Cayley utilizou grafos na química orgânica. Em 1859, Hamilton inventou um jogo que consistia na busca de um percurso fechado envolvendo todos os vértices de um dodecaedro regular, de tal modo que cada um deles fosse visitado uma única vez. Para mais exemplos, consulte, por exemplo, Boaventura Neto, 1996.

1 Figura retirada do site http://www.inf.ufpr.br/~andre/Disciplinas/BSc/CI065/michel/Intro/intro.html

Page 8: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 8 Curso: Informática Disciplina: Análise de Algoritmos

2.1.1 Representação Gráfica Visualmente, os grafos são representados por um conjunto de pontos e um conjunto

de linhas ou setas ligando esses pontos. Exemplos:

2.1.2 Representação Matemática Um grafo G é definido como G(V,A) onde V é um conjunto finito e não vazio de

vértices e A um conjunto finito de pares de V, isto é, A (VxV). Os elementos de A são chamados de arestas do grafo.

2.1.3 Definições Básicas Laço – uma aresta que incide com um único vértice é chamada de laço. Orientação – é a direção para a qual uma seta aponta. Se a aresta não tiver seta, diz-se

que ela não tem orientação Incidente – Diz-se que uma aresta é incidente com os vértices que ela liga (não importa

a orientação). Vértices Adjacentes – dois vértices são adjacentes se estão ligados por uma aresta. Vértice isolado – Um vértice é dito isolado se não existe aresta incidente sobre ele. Arestas paralelas – Duas arestas incidentes nos mesmos vértices (não importa a

orientação). Ou seja, se a1 = (v,w) e a2 = (v,w), então as arestas a1 e a2 são paralelas.

Laço no vértice A A aresta a3 incide no vértice C e no vértice D.

Os vértices A e B são adjacentes. os vértices C e D também são adjacentes.

Vértice E isolado. As arestas a1 e a2 são paralelas

E

a3 C D

Vértices – são os “pontos”, ou nós Arestas – são as linhas ou setas, ou arcos.

A B

v1 v2

a1

a2

Page 9: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 9 Curso: Informática Disciplina: Análise de Algoritmos

2.1.4 Tipos de Grafos

2.1.4.1 Grafo Rotulado Um grafo é dito rotulado quando seus vértices e/ou arestas são distinguidos uns dos

outros por rótulos (que pode ser um nome, um número ou conjunto de letras ou números. Caso contrário o grafo é não rotulado.

Nos exemplos abaixo, o primeiro grafo não tem nenhum rótulo. O segundo grafo possui rótulos nos vértices e o terceiro grafo possui rótulos nas arestas.

x1 a1 a2 x2 x3

Grafo não rotulado Grafo rotulado Grafo rotulado

Exemplo 1 – Represente graficamente um grafo definido matematicamente como segue: Grafo G(V,A), onde V = {v1,v2,v3,v4} e A = {(v1,v2),(v2,v3),(v3,v3),(v3,v1)}. Há varias formas gráficas semelhantes de se representar esse grafo, mantendo as definições, pois a posição dos vértices no espaço é irrelevante. Vou fazer de duas formas diferentes.

v1 v4

v2 v3

2.1.4.2 Subgrafos

Seja G(V,A) um grafo. Um subgrafo G’ de G é um grafo G’(V’,A’), tal que V’ V e A’ A.

Grafo G Grafo G’

2.1.4.3 Ordem A ordem de um grafo é definida por |V| = n. Ou seja, a ordem de um grafo é o número de vértices.

v1 v2

v3 v4

Page 10: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 10 Curso: Informática Disciplina: Análise de Algoritmos

2.1.4.4 Grafos simples, completos e multígrafos Multígrafo – grafo que contém arestas paralelas ou aços Grafo simples – grafo que não contém nenhum par de arestas paralelas ou laços. Grafo completo – um grafo simples será completo quando existir uma aresta entre

cada par de seus vértices. Exemplos de grafos completos de 2, 3 e 4 vértices: n Um grafo completo com n vértices possui m = 2 arestas ou (n-1)! Um grafo completo de n vértices é denominado cliques.

2.1.4.5 Grafo Complementar

Um grafo G é dito complementar de G se possui a mesma ordem de G e se uma aresta (v,w) G, então (v,w) G e vice-versa. Exemplo: Grafo G Grafo G a a b d b d c c

No caso de grafos dirigidos, o grafo complementar G será aquele que possui os mesmos vértices de G, possui todas as arestas não presentes em G e possui o reverso das arestas de G. Por exemplo: Grafo G Grafo G a a b d b d c c

2.1.4.6 Grafo Bipartite Se G(V1 V2,A) é tal que, para V1 V2 = e para toda aresta (vi,vj) A, tem-se que vi V1 e vj V2, então o grafo é denominado bipartite. Ou seja, o grafo pode ser dividido logicamente em dois conjuntos de vértices, tal que toda aresta começa no vértice de um dos conjuntos e termina no vértice do outro conjunto.

Page 11: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 11 Curso: Informática Disciplina: Análise de Algoritmos V1 = {a.,b} a c V2 = {c,d,e} d b e

2.1.4.7 Grafo Dirigido Um grafo é chamado de dirigido (ou dígrafo) se suas arestas possuem orientação.

Caso contrário o grafo é não dirigido. Em termos leigos: será dirigido se suas arestas forem “flechas” que apontam o vértice inicial e final de cada aresta.

2.1.4.8 Grafos Isomorfos Dois grafos são isomorfos se coincidirem os vértices de suas representações

gráficas, preservando as adjacências das arestas. Em outras palavras, são isomorfos se têm a mesma representação matemática, mas são representados diferentemente graficamente.

Formalmente pode-se dizer que G1(V1,A1) e G2(V2,A2) são isomorfos se satisfizerem as seguintes condições: 1) |V1| = |V2| = n. 2) Existe uma função bijetora f: V1 V2, tal que (v,w) A1 ((f(v),f(w)) A2 v,w

V1.

a a’ a a’ b b’ c c’ c’ b c b’

2.1.4.9 Grau e Grafos Regulares O grau de um vértice v V denotado por gr(v) = número de arestas incidentes a v

(sendo que um laço equivale a duas arestas). Um grafo é dito regular de grau r se todos os vértices possuem grau r. Ou seja, todos

os vértices possuem o mesmo grau. Teorema 1 – A soma dos graus dos vértices de um grafo é igual a duas vezes o número

de arestas. Teorema 2 – Em qualquer grafo existe sempre um número par de vértices de grau

ímpar.

2.1.4.10 Grafo Valorado Seja pi um número associado a cada aresta e qj um número associado a cada vértice

de um grafo G(V,A). Então G é denominado de grafo valorado e o número pi é chamado de custo da aresta e o número qj é chamado de custo do vértice.

Custo da aresta pode significar distância, altitude, capacidade, fluxo etc.

Page 12: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 12 Curso: Informática Disciplina: Análise de Algoritmos

Custo do vértice pode significar capacidade, entradas, etc.

10km 8km 16km

2.2 Sucessores e Antecessores de um Grafo Dirigido Formalmente, os vértices sucessores e antecessores de um grafo dirigido são

definidos da seguinte forma: v é sucessor de w <=> (w,v) A v é antecessor de w <=> (v,w) A

Os conjuntos de todos os vértices sucessores e antecessores de um dos vértices de um grafo são formalmente definidos da seguinte forma: +(v) = {w/(v,w) A --> conjunto de sucessores de v -(v) = {w/(w,v) A --> conjunto de antecessores de v

Exemplo: b a d c +(a) = {b,c} +(b) = {c} +(c) = {d} +(d) = { } -(a) = { } -(b) = {a} -(c) = {a,b} -(d) = {c}

2.3 Representação de Grafos em um Computador Para que um grafo seja armazenado em um computador, é necessário definir dois aspectos:

Quais informações devem ser consideradas Como armazenar as informações no computador, ou seja, definir a estrutura de

dados que será utilizada. A estrutura de dados é particularmente importante, pois a eficiência de um

algoritmo que irá trabalhar sobre o grafo vai depender da escolha certa de como representar o grafo.

De uma forma geral, pode-se representar um grafo utilizando matrizes ou listas, como veremos a seguir.

2.3.1 Matriz de Adjacência Dado um grafo G(V,A), a matriz de adjacência A = [aij] é uma matriz n x n tal que aij = 1 se e somente se existe (vi, vj) Aj 0 caso contrário

Exemplo:

Page 13: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 13 Curso: Informática Disciplina: Análise de Algoritmos a2 a4 a1 a3 a2 a3 a1 a4 b c a d

1 2 3 4 1 0 1 0 0 2 1 0 1 1 3 0 1 0 1 4 0 1 1 0 j 1 2 3 4 1 1 1 0 0 i 2 0 0 1 0 3 0 0 0 1 4 0 1 0 0 j 1 2 3 4 1 0 2 0 0 i 2 0 0 1 0 3 0 0 0 1 4 0 1 0 0

2.3.2 Matriz de Custo Um grafo valorado pode ser representado por uma matriz de custo w = {wij}, onde wij = custo da aresta, se (vi, vj) A caso (vi, vj) A (ou seja, caso não exista aresta)

Exemplo: a2 2 a3 1 8 5 a1 a4

j 1 2 3 4 1 1 i 2 1 2 5 3 2 8 4 5 8

2.3.3 Matriz de Incidência Dado um grafo G(V,A) de n vértices e m arestas a matriz de incidência de G é denotada por B = [bij] é uma matriz n x m definida por: bij = 1 se vi é vértice de aj 0 caso contrário

Page 14: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 14 Curso: Informática Disciplina: Análise de Algoritmos

Se o grafo G for orientado (dígrafo), então poderá ser definida como: 1 se vi for vértice inicial de aj (ou se existir um laço no vértice vi) bij = -1 se vi for vértice final de aj 0 se o vértice vi não pertence à aresta aj

Exemplo: 2 b 3 a c d 1 4 e 1 a 2 b 3 d c 4

arestas a b c d e 1 1 0 0 0 1 2 1 1 0 1 0 vértices 3 0 1 1 0 0 4 0 0 1 1 0 arestas a b c d 1 1 0 0 0 2 -1 1 0 -1 vértices 3 0 -1 1 0 4 0 0 -1 1

2.3.4 Lista de Arestas

Pode-se representar um grafo em um computador utilizando-se duas listas de vértices, representando as arestas do grafo. As listas podem ser vetores simples. A primeira lista contém os vértices de início de cada aresta. A segunda lista contém os vértices onde cada uma delas termina. Por exemplo: v2 v3 v5 L1 = (v2,v3,v3,v4,v5,v5) L2 = (v1,v2,v5,v3,v2,v4) v1 v4

2.3.5 Estrutura de Adjacência Um grafo pode ser representado por uma lista de vértices e, para cada vértice da lista, é associada uma lista dos seus respectivos sucessores. Exemplo: 2 1 3

5 4

1 3

1 3 2

3 -

4 3 5

5 1 2 3

Page 15: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 15 Curso: Informática Disciplina: Análise de Algoritmos

2.4 Caminho e Conexidade 2.4.1 Caminho Formalmente temos o seguinte:

Definição: seja G(V,A) um grafo. Então define-se um caminho de G como sendo uma seqüência de arestas da forma (u,v),(v,w),(w,x),...,(y,z), onde cada aresta pertence ao grafo G.

O caminho denotado acima é definido, também, como o caminho entre u e z e pode ser representado por: u v w x ... y z.

O exemplo abaixo mostra um caminho entre d e c. O caminho é denotado por d a b c.

a b c d e 2.4.2 Cadeia

Definição: uma cadeia é uma seqüência de arestas de um grafo G, tal que qualquer par de arestas subseqüentes possuem um vértice de incidência comum. Ao contrário da definição de caminho, uma cadeia ignora a orientação das arestas.

Portanto, todo caminho é uma cadeia, porém a recíproca nem sempre é verdadeira. Veja o seguinte exemplo:

b A seqüência a b c d é um caminho, também uma cadeia.

a c A seqüência a b d c é uma cadeia, mas não é um caminho. d

2.4.3 Comprimento Definição: o número de arestas k que compõem um caminho (ou cadeia) é denominado de comprimento do caminho (ou da cadeia). Exemplo. b

O caminho a b c d é um caminho entre ‘a’ e ‘d’ de comprimento igual a 3

a c d

Caminho: segue a orientação Cadeia: não precisa seguir a orientação

Page 16: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 16 Curso: Informática Disciplina: Análise de Algoritmos

2.4.4 Caminho Simples x Trajetória Definição: se os vértices de um caminho (ou cadeia) forem distintos (com exceção do vértice inicial e o vértice final), então a seqüência recebe o nome de caminho simples (ou cadeia simples). Se as arestas da seqüência forem distintas, então a seqüência recebe o nome de trajeto ou trajetória. Exemplo: 2 3 1 4 A seqüência 1 2 3 4 5 é um caminho simples. A seqüência 1 2 3 4 2 é uma trajetória. A seqüência 1 2 3 4 2 1 é apenas uma seqüência.

6 5

2.4.5 Grafo Conexo Definição: um grafo G é conexo se existe pelo menos um caminho (ou cadeia) entre qualquer par de vértices de G. Caso contrário o grafo é desconexo. Exemplo: a) Grafo conexo b) Grafo desconexo

Todo grafo desconexo é composto por subgrafos conexos chamados de componentes. Por exemplo, o grafo b) é um grafo desconexo composto por 2 componentes.

2.4.6 Caminhos abertos e fechados Um caminho em G é denominado fechado se o vértice final é o mesmo que o vértice inicial. Caso contrário, o caminho é denominado aberto. Exemplo: b c Caminho aberto: b d c e a Caminho fechado: b d c e b e d

De forma semelhante a um caminho fechado, uma cadeia fechada de um grafo é uma cadeia de G tal que a aresta inicial e a aresta final possuem um vértice de incidência em comum, ou em outras palavras, se o vértice inicial e o vértice final se confundem.

2.4.7 Circuito e Ciclo Um circuito é um caminho simples fechado. Um ciclo é uma cadeia simples fechada. Exemplo:

Page 17: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 17 Curso: Informática Disciplina: Análise de Algoritmos b c Circuito: a b c d a a Ciclo: d c b d d

Um grafo que não contém nenhum ciclo é chamado de “grafo acíclico”.

2.4.8 Algoritmo de Goodman Esse algoritmo verifica se um grafo é conexo e identifica seus componentes no caso

de ser desconexo. A idéia consiste em reduzir cada componente a um único ponto. Nesse algoritmo necessitamos da definição de fusão de dois vértices Fusão – Dados dois vértices u e v adjacentes de um grafo G, a fusão de v com u é feita eliminando-se a aresta (v,u) e em seguida tornando v e u um único vértice. O vértice resultante desta fusão é um vértice w adjacente a todos os vértices anteriormente adjacentes a u e/ou v. Exemplo: a b a b Após a fusão de u e v u v w

O procedimento consiste da escolha de um vértice inicial v0 e a fusão de um vértice com ele. Isto é repetido até que não reste qualquer vértice adjacente a v0. Caso reste algum vértice não adjacente a v0, então novo vértice v0 é selecionado e o processo é repetido. Se no final o grafo resultante for apenas um vértice, então o grafo é conexo. Caso contrário, o número de vértices representará o número de componentes do grafo. Entrada: grafo G(V,A) Saída: variável c contendo o número de componentes. P0. [inicialize] H G; c 0; P1. [Gere a próxima componente] Enquanto H 0 faça Selecione um vértice v0 H; Enquanto v0 for adjacente a algum vértice u H faça H grafo resultante da fusão de u com v0. Remova v0, isto é, faça H H – v0; c c + 1; P2.[Teste do Tipo de conexidade] Se c>1 então G é desconexo. Senão G é conexo.

Page 18: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 18 Curso: Informática Disciplina: Análise de Algoritmos Exemplo: a b f e 1o. passo: escolher um vértice.

Vértice d. Fusão de d com e. c d

a b

f Vértice d. Fusão de d com c. c d a b

f Vértice d. Fusão de d com b. d a

f Vértice d. Fusão com a. d

d f

2.5 Localização de Centros (em grafos não valorados)

2.5.1 Distância Dados dois vértices v e w pertencentes ao grafo G(V,A), denomina-se distância

entre v e w, o comprimento do menor caminho entre dois vértices v e w. No caso da não existência desse caminho, considera-se a distância infinita.

Notação: d(v,w) = distância entre os vértices v e w = comprimento do menor caminho entre v e w Denotamos por D(G) a matriz de distâncias de um grafo, onde dij=(vi,vj) Em um grafo conexo, distância é uma métrica, isto é, para todo vértice de G(V,A)

tem-se que: i) d(u,v)>=0 com d(u,v)=0 se e somente se u=v. ii) d(u,v) = d(v,u) ocorre apenas quando o grafo é não orientado; iii) d(u,v) + d(v,w) >= d(u,w)

Page 19: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 19 Curso: Informática Disciplina: Análise de Algoritmos

2.5.2 Pista Uma pista (xi,xj) ou (ij) ou ij é um caminho de comprimento mínimo entre xi e xj, ou seja, um caminho de comprimento igual a d(xi,xj). Por exemplo, considere o grafo abaixo: b f a c g d e Qual a distância entre a e g? d(a,g) = 3, (a,g) = (a,b,f,g) (a,e) = (a,b,f,e) ou (a,c,d,e)

2.5.3 Excentricidade A excentricidade de um vértice v, denotado por e(v), é a máxima das distâncias d(v,u), isto é: e(v) = Max{d(v,u), u G} Em outras palavras, a excentricidade de um vértice v é a maior distância existente a partir de v.

2.5.4 Raio O raio de um grafo G, denotado por r(g), é o mínimo das excentricidades dos vértices de G Min(e(v)). Assim, r(G) = Min{e(v), v G}.

2.5.5 Centro O centro de um grafo G é definido pelo conjunto de vértices v tais que e(v) = r(g), isto é, centro = {v G / e(v) = r(G) }. Em uma rede de comunicação, a localização de um ponto importante (uma rede de transmissão, por exemplo) em um centro do grafo que representa a rede é, a priori, uma providência no sentido de procurar reduzir ao máximo o número de transmissões de mensagens ou de equipamentos de conexão envolvidos. Exemplo: localizar o centro do grafo abaixo. a b c e d

a b c d e e(v) a 0 1 1 2 1 2 b 1 0 1 2 2 2 c 1 1 0 1 1 1 d 2 2 1 0 1 2 e 1 2 1 1 0 2

Page 20: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 20 Curso: Informática Disciplina: Análise de Algoritmos raio = r(G) = 1 centro = {c}

2.5.6 Centro de um grafo dirigido Em um grafo dirigido, define-se excentricidade de um vértice v por es = Max{d(v,u), u G}

Define-se excentricidade de retorno de um vértice v por er = Max{d(u,v), u G}

O raio de um dígrafo G é definido por: r(G) = Min{es(v), er(v)}

Centro de um dígrafo G é definido pelo conjunto de vértices v tais que

es(v) = r(G) ou er(v) = r(G), isto é: centro = {v G / es(v) = r(G) ou er(v) = r(G)}

Por exemplo, localize o centro do grafo G abaixo: a b c e d

a b c d e es(v) a 0 1 1 2 2 2 b 3 0 1 2 2 3 c 2 3 0 1 1 3 d 2 3 3 0 1 3 e 1 2 2 3 0 3 er(v) 3 3 3 3 2

raio = r(G) = 2 centro = {a,e}

2.5.7 Localização de Centros de Emergência Aqui o interesse é determinar o centro de um grafo de tal modo que o tempo de ida e de volta seja mínimo (é o caso da localização de hospitais, polícia, bombeiro, etc). Observe que, neste caso, os vértices representam uma população e, como tal, devem ser levados em consideração. Definição: A excentricidade de saída e retorno de um vértice é definida por: esr(xi) = Max {pj [d(xi,xj) + d(xj,xi)]} onde j é o peso do vértice xj. Este peso pode ser entendido como a importância do vértice. Por exemplo, para localização de um hospital, o tamanho da população num bairro pode ser uma informação importante.

Page 21: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 21 Curso: Informática Disciplina: Análise de Algoritmos

Definição: O raio de um grafo G considerando ida e volta é definido por r(G) = Min{esr(xi)}.

Definição: O centro de emergência de um grafo G é definido pelo conjunto de

vértices v tal que esr(v) = r(G). Centro de emergência = {v G/ esr(v) = r(G)} Por exemplo, considere o seguinte dígrafo. Localize o centro de emergência do

grafo. x1 x6 x2 x5 x3 x4

D(G) x1 x2 x3 x4 x5 x6 0 1 2 3 2 3 3 0 1 2 1 2 4 3 0 1 2 3 3 2 3 0 1 2 2 1 2 3 0 1 1 2 3 4 3 0

DT x1 x2 x3 x4 x5 x6 0 3 4 3 2 1 1 0 3 2 1 2 2 1 0 3 2 3 3 2 1 0 3 4 2 1 2 1 0 3 3 2 3 2 1 0

D(G) + DT x1 x2 x3 x4 x5 x6 esr 0 4 6 6 4 4 6 4 0 4 4 2 4 4 6 4 0 4 4 6 6 6 4 4 0 4 6 6 4 2 4 4 0 4 4 4 4 6 6 4 0 6

Como o peso de cada vértice é igual a 1, então podemos calcular a excentricidade diretamente da matriz D(G) + DT(G). Portanto, o centro de emergência do grafo é formado pelo conjunto {x2,x5}.

Exercícios: 1 – Desenhe o grafo cuja matriz de adjacência é dada por: 1 2 3 4 5 6

0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0

Page 22: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 22 Curso: Informática Disciplina: Análise de Algoritmos 2 – Desenhe o grafo a partir da lista de adjacência: 3 – Localize o centro dos grafos abaixo. Para isso, determine o raio do grafo e a excentricidade dos vértices. a a b c b d e c d e f

1

1 2 4

2 4

3 2

4 2 3

Page 23: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 23 Curso: Informática Disciplina: Análise de Algoritmos

2.6 Algoritmos e problemas clássicos com grafos Existem vários algoritmos e problemas considerados “clássicos” na área de Teoria

dos Grafos. Um desses problemas é o de encontrar um caminho mínimo entre dois vértices. Existem vários algoritmos que resolvem esse problema. Um deles é o algoritmo de Floyd.

2.6.1 Algoritmo de Floyd Inicialmente, esse algoritmo faz uma matriz de custo do grafo. Ou seja, ele verifica

a distância entre cada par de vértices. Se existir uma aresta, o valor que ele coloca naquela posição da matriz é o custo da aresta. Se não existir uma aresta entre o par de vértice, ele coloca o valor .

Em seguida, ele verifica se existe um caminho de menor custo entre cada par de vértices, ao passar por um vértice intermediário. Ou seja, suponha um grafo com 5 vértices. De um modo geral, após montar a matriz de distâncias, ele fará 5 iterações:

1ª. Iteração: descobrir se há caminhos que ficam menores ao passar pelo vértice 1 2ª. Iteração: descobrir se há caminhos que ficam menores ao passar pelo vértice 2 3ª. Iteração: descobrir se há caminhos que ficam menores ao passar pelo vértice 3 4ª. Iteração: descobrir se há caminhos que ficam menores ao passar pelo vértice 4 5ª. Iteração: descobrir se há caminhos que ficam menores ao passar pelo vértice 5

Algoritmo:

Parte1 – Construir a matriz de distância e a matriz de roteamento 0, se i=j D0ij = , se não existe aresta entre o vértice i e o vértice j custo da aresta entre o vértice i e o vértice j R0ij = j, se dij < 0, caso contrário Parte2 – Verificar, para cada posição da matriz, se existe um caminho mais curto Considerando que n é o número de vértices: Para k:= 1 to n do Begin Para i:=1 to n do Begin Para j:=1 to n do Begin If (Dk-1 ik + Dk-1 kj < Dk-1 ij) then Begin Dkij := Dk-1 ik + Dk-1kj; Rkij := Rk-1ik; End End; End; End;

Page 24: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 24 Curso: Informática Disciplina: Análise de Algoritmos

Por exemplo, considerando o grafo abaixo, vamos aplicar o algoritmo de Floyd para encontrar a matriz de custo mínimo. v2 v3 v1 v5 v4

O primeiro passo, então, é construir as matrizes de distância e a matriz de roteamento:

v1 v2 v3 v4 v5 v1 0 5 3 v2 0 3 v3 0 5 v4 1 1 0 1 v5 1 1 0

v1 v2 v3 v4 v5 v1 1 2 0 4 0 v2 0 2 3 0 0 v3 0 0 3 0 5 v4 1 2 0 4 5 v5 0 2 0 4 5

Agora, então, o algoritmo fará várias iterações para tentar verificar se existe um

caminho mais curto entre cada pares de vértices. No início temos: K=1, i=1, j=1 se D011 + D011 < D011? 0 + 0<0? Não! K=1, i=1, j=2 se D011 + D012 < D012? 0 + 5 < 5? Não! K=1, i=1, j=3 se D011 + D013 < D013? 0 + < ? Não! K=1, i=1, j=4 se D011 + D014 < D014? 0 + 3 < 3? Não! K=1, i=1, j=5 se D011 + D015 < D015? 0 + < ? Não!

O significado aqui é o seguinte. Para ir do vértice 1 para qualquer outro, o caminho fica mais curto se eu passar primeiro pelo vértice 1?

Como j chegou em n, que é igual a 5 (número de vértices), então a execução sai do laço. Então i é incrementado para 2. Temos então: K=1, i=2, j=1 se D021 + D011 < D021? + 0 < ? Não! K=1, i=2, j=2 se D021 + D012 < D022? + 5 < 0? Não! K=1, i=2, j=3 se D021 + D013 < D023? + < 3? Não! K=1, i=2, j=4 se D021 + D014 < D024? + 3 < ? Não! K=1, i=2, j=5 se D021 + D015 < D025? + < ? Não!

O significado aqui é o seguinte: na última iteração que vimos, por exemplo, o que eu estou querendo saber é se, para ir do vértice v2 ao vértice v5, é mais perto ir primeiro do v2 pro v1, e então do v1 pro v5, em vez de ir direto. Ou seja, estou verificando se utilizar o vértice 1 como intermediário encurta o caminho. Em outras palavras, para ir do vértice 2 para qualquer outro, o caminho fica mais curto se eu passar primeiro pelo vértice 1? Vimos que, para este grafo, não.

Page 25: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 25 Curso: Informática Disciplina: Análise de Algoritmos

Continuando então, i é incrementado para 3. Temos então: K=1, i=3, j=1 se D031 + D011 < D031? + 0 < ? Não! K=1, i=3, j=2 se D031 + D012 < D032? + 5 < ? Não! K=1, i=3, j=3 se D031 + D013 < D033? + < 0? Não! K=1, i=3, j=4 se D031 + D014 < D034? + 3 < ? Não! K=1, i=3, j=5 se D031 + D015 < D035? + < 5? Não!

Continuando, i é incrementado para 4. Temos então: K=1, i=4, j=1 se D041 + D011 < D041? 1 + 0 < 1? Não! K=1, i=4, j=2 se D041 + D012 < D042? 1 + 5 < 1? Não! K=1, i=4, j=3 se D041 + D013 < D043? 1 + < ? Não! K=1, i=4, j=4 se D041 + D014 < D044? 1 + 3 < 0? Não! K=1, i=4, j=5 se D041 + D015 < D045? 1 + < 1? Não!

Continuando, i é incrementado para 5. Temos então: K=1, i=5, j=1 se D051 + D011 < D051? + 0 < ? Não! K=1, i=5, j=2 se D051 + D012 < D052? + 5 < 1? Não! K=1, i=5, j=3 se D051 + D013 < D053? + < ? Não! K=1, i=5, j=4 se D051 + D014 < D054? + 3 < 1? Não! K=1, i=5, j=5 se D051 + D015 < D055? + < 0? Não!

Agora, i já chegou ao valor n, ou seja, i=5. Neste caso, o loop chega ao fim. Agora, a variável k é incrementada e passa ser 2. Isso significa que agora vamos ver, para cada par de vértices, se o uso do v2 como intemediário torna o caminho mais curto. K=2, i=1, j=1 se D012 + D021 < D011? 5 + < 0? Não! K=2, i=1, j=2 se D012 + D022 < D012? 5 + 0 < 5? Não! K=2, i=1, j=3 se D012 + D023 < D013? 5 + 3 < ? Sim!!!!!!!!!! K=2, i=1, j=4 se D012 + D024 < D014? 5 + < 3? Não! K=2, i=1, j=5 se D012 + D025 < D015? 5 + < ? Não!

No momento em que eu achei um curto, então gero a minha matriz D1. Na prática, no algoritmo, é possível apenas sobrescrever os valores anteriores. A minha matriz de distâncias e a de roteamento passam a ser:

v1 v2 v3 v4 v5 v1 0 5 8 3 v2 0 3 v3 0 5 v4 1 1 0 1 v5 1 1 0

v1 v2 v3 v4 v5 v1 1 2 2 4 0 v2 0 2 3 0 0 v3 0 0 3 0 5 v4 1 2 0 4 5 v5 0 2 0 4 5

Reparem que a matriz de roteamento agora indica que, para ir do vértice v1 para o

vértice v3, é preciso primeiro passar pelo vértice v2.

Page 26: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 26 Curso: Informática Disciplina: Análise de Algoritmos

Continuando temos: K=2, i=2, j=1 se D022 + D021 < D021? 0 + < ? Não! K=2, i=2, j=2 se D022 + D022 < D022? 0 + 0 < 0? Não! K=2, i=2, j=3 se D022 + D023 < D023? 0 + 3 < 3? Não! K=2, i=2, j=4 se D022 + D024 < D024? 0 + < ? Não! K=2, i=2, j=5 se D022 + D025 < D025? 0 + < ? Não!

Continuando temos: K=2, i=3, j=1 se D032 + D021 < D031? + < ? Não! K=2, i=3, j=2 se D032 + D022 < D032? + 0 < ? Não! K=2, i=3, j=3 se D032 + D023 < D033? + 3 < 0? Não! K=2, i=3, j=4 se D032 + D024 < D034? + < ? Não! K=2, i=3, j=5 se D032 + D025 < D035? + < 5? Não!

Continuando temos: K=2, i=4, j=1 se D042 + D021 < D041? 1 + < 1? Não! K=2, i=4, j=2 se D042 + D022 < D042? 1 + 0 < 1? Não! K=2, i=4, j=3 se D042 + D023 < D043? 1 + 3 < ? Sim!!!!! K=2, i=4, j=4 se D042 + D024 < D044? 1 + < 0? Não! K=2, i=4, j=5 se D042 + D025 < D045? 1 + < 1? Não!

As matrizes passam a ser, então:

v1 v2 v3 v4 v5 v1 0 5 8 3 v2 0 3 v3 0 5 v4 1 1 4 0 1 v5 1 1 0

v1 v2 v3 v4 v5 v1 1 2 2 4 0 v2 0 2 3 0 0 v3 0 0 3 0 5 v4 1 2 2 4 5 v5 0 2 0 4 5

Continuando temos: K=2, i=5, j=1 se D052 + D021 < D051? 1 + < ? Não! K=2, i=5, j=2 se D052 + D022 < D052? 1 + 0 < 1? Não! K=2, i=5, j=3 se D052 + D023 < D053? 1 + 3 < ? Sim!!! K=2, i=5, j=4 se D052 + D024 < D054? 1 + < 1? Não! K=2, i=5, j=5 se D052 + D025 < D055? 1 + < 0? Não!

As matrizes passam a ser, então:

v1 v2 v3 v4 v5 v1 0 5 8 3 v2 0 3 v3 0 5 v4 1 1 4 0 1 v5 1 4 1 0

v1 v2 v3 v4 v5 v1 1 2 2 4 0 v2 0 2 3 0 0 v3 0 0 3 0 5 v4 1 2 2 4 5 v5 0 2 2 4 5

Page 27: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 27 Curso: Informática Disciplina: Análise de Algoritmos

Repetindo então o processo para k=3, k=4 e k=5, no final teremos as duas seguintes matrizes:

v1 v2 v3 v4 v5 v1 0 4 7 3 4 v2 10 0 3 9 8 v3 7 6 0 6 5 v4 1 1 4 0 1 v5 2 1 4 1 0

v1 v2 v3 v4 v5 v1 1 4 4 4 4 v2 3 2 3 3 3 v3 5 5 3 5 5 v4 1 2 2 4 5 v5 4 2 2 4 5

Assim, a matriz da esquerda indica qual será o custo mínimo pra ir de um vértice a outro, enquanto a matriz da direita mostra qual é o caminho que deverá ser percorrido para ir de um vértice a outro com o custo mínimo. Por exemplo: Para ir do vértice v1 para o vértice v2, o caminho mais curto, de custo 4, é passando

pelo vértice v4. Ou seja, v1-v4-v2. Para ir do vértice v1 para o vértice v3, o caminho mais curto, de custo 7, é passando

pelo vértice v4. No entanto, vemos na matriz de roteamento que não podemos ir direto do v4 para o v3, é preciso passar pelo vértice v2. Assim, a rota então é v1-v4-v2-v3.

Olhando apenas para essa matriz, responda:

a) Qual é a rota de custo mínimo entre o vértice v1 e o vértice v5? b) Qual é a rota de custo mínimo entre o vértice v4 e o vértice v3? c) Qual é a rota de custo mínimo entre o vértice v5 e o vértice v1?

Exercício – Utilizando o algoritmo de Floyd, encontre a matriz de custo mínimo e a matriz de roteamento para o grafo abaixo:

Page 28: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 28 Curso: Informática Disciplina: Análise de Algoritmos

2.6.2 Algoritmo de Dijkstra O algoritmo de Dijkstra é semelhante ao de Floyd. Inicialmente, o usuário também

deve entrar com a matriz de custo do grafo. No entanto, este algoritmo considera que o grafo tem um vértice inicial. Assim, ele só calcula o caminho mínimo do vértice inicial para todos os outros. Portanto, o usuário deve definir em seguida qual é o vértice inicial.

O algoritmo gera então dois vetores simples: 1)uma matriz de rota e 2)uma matriz de custo mínimo. Leia (Custo[ ]); //ler matriz de custo Leia (vert); //ler vértice inicial Para i = 1 .. n faça // n é o número de vértices Begin Rota[i] = vert; // Rota do vértice inicial até o vértice i Dist[i] = Custo[vert,i] // Custo inicial do vértice inicial até o vértice i End Para a = 1.. n faça Para todo k +(a) //Para todo vértice k que é sucessor do vértice a Begin P = mín(D[k], D[a]+Custo[a,k]); If (P < D[k]) Then Begin Rota[k] = a; Dist[k] = P; End

Só lembrando que os vértices sucessores de a serão aqueles que têm um valor de custo diferente de 0 (ou seja, não é o próprio vértice) e diferente de (ou seja, não existe aresta entre eles e, portanto, o vértice não é um sucessor). Considere por exemplo o seguinte grafo: 1 2 2 3 10 7 3 8 5 4 5 4

Inicialmente, o algoritmo solicita que o usuário entre a matriz de custo do grafo. 1 2 3 4 5

1 0 2 10 2 0 3 7 3 0 4 4 0 5 8 5 0

Page 29: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 29 Curso: Informática Disciplina: Análise de Algoritmos

Em seguida, pergunta qual é o vértice inicial. Vamos considerar que o vértice inicial é o vértice 1. Temos então: Vert = 1 Rota[1,1,1,1,1]. Dist[0,2, ,,10]

Ou seja, inicialmente ele inicializa todas as posições do vetor Rota com o vértice inicial. Em seguida, coloca o custo das arestas do vértice inicial para todas as outras. Quando a aresta não existe, o valor é colocado. a = 1, k=1 vértice 1 não é sucessor de 1 k=2 D[2] x D[1] + Custo[1,2] 2 x 0+2 p=2. p < D[k]?? 2 <2 ? Não! k=3 vértice 3 não é sucessor de 1 k=4 4 não é sucessor de 1 k=5 D[5] x D[1] + Custo[1,5] 10 x 0+10 p=10 p < D[k]? 10 < 10? Não! a = 2, k=1 vértice 1 não é sucessor de 2 k=2 vértice 2 não é sucessor de 2 k=3 D[3] x D[2] + Custo[2,3] x 2+3 p=5 p<D[k]? 5<? Sim!! Rota[3]=2, Dist[3]=5 Rota[1,1,2,1,1] e Dist[0,2,5, ,10] k=4 4 não é sucessor de 2 k=5 D[5] x D[2] + Custo[2,5] 10 x 2+7 p=9 p < D[k]? 9 < 10? Sim! Rota[5]=2, Dist[5]=9 Rota[1,1,2,1,2] e Dist[0,2,5, ,9] a = 3, k=1 vértice 1 não é sucessor de 3 k=2 vértice 2 não é sucessor de 3 k=3 vértice 3 não é sucessor de 3 k=4 D[4] x D[3] + Custo[3,4] x 5+4 p=9 p < D[4]? 9 < ? Sim! Rota[4]=3, Dist[4]=9 Rota[1,1,2,3,2] e Dist[0,2,5, 9,9] k=5 vértice 5 não é sucessor de 3 a = 4, k=1 vértice 1 não é sucessor de 4 k=2 vértice 2 não é sucessor de 4 k=3 vértice 3 não é sucessor de 4 k=4 vértice 4 não é sucessor de 4 k=5 vértice 5 não é sucessor de 4 a = 5, k=1 vértice 1 não é sucessor de 5 k=2 vértice 2 não é sucessor de 5 k=3 D[3] x D[5] + Custo[5,3] 5 x 9+8 p=5 p < D[3]? 5 < 5? Não! k=4 D[4] x D[5] + Custo[5,4] 9 x 9+5 p=9 p < D[4]? 9 < 9? Não! k=5 vértice 5 não é sucessor de 5

Assim, no final temos: Rota[1,1,2,3,2] e Dist[0,2,5,9,9].

Page 30: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 30 Curso: Informática Disciplina: Análise de Algoritmos

Exercício 1 – Para o mesmo grafo, repita o procedimento acima, mas considerando que o vértice inicial é o vértice 2.

Exercício 2 – Para o seguinte grafo, aplique o algoritmo “passo a passo”, de forma a descobrir a matriz de rota e a matriz de custo mínimo. Considere que o vértice 1 é vértice inicial. Determine então a pista do vértice 1 para todos os outros vértices 2 1 3 10 1 3 2 9 4 6 5 7 5 2 4

2.6.3 Grafos de Euler Define-se um caminho de Euler como sendo um caminho fechado passando uma

única vez por cada aresta do grafo (percorrendo todas as arestas do grafo). Todos os grafos que admitem um caminho de Euler são chamados de grafos de Euler. TEOREMA: Um grafo conexo G (simples, não orientado) é um grafo de Euler se e somente se todos os seus vértices são de grau par. TEOREMA: Um dígrafo G contém um circuito de Euler se e somente se os graus de entrada e saída de cada vértice forem iguais.

Exemplos: a) Não é grafo de Euler b)Não é grafo de Euler c) Grafo de Euler

2.6.4 Problema do Carteiro Chinês A noção de grafos de Euler e caminhos de Euler são utilizadas quando é necessário

atender seqüencialmente a um conjunto de usuários, sendo que todos devem ser atendidos. Exemplo são: entrega de correio, coleta de lixo, etc.

O problema do carteiro chinês consiste em encontrar um caminho que passe por TODAS AS ARESTAS do grafo G(V,A) pelo menos uma vez, de preferência uma única vez. Há dois tipos de solução para esse problema: Solução 1 – Quando o grafo é de Euler. Nesse caso, o caminho pode ser achado (e

também seu respectivo custo). Para isso, utiliza-se o algoritmo de Fleury. Solução 2 – Quando o grafo não é de Euler. Nesse caso, algumas arestas terão que ser

repetidas e utiliza-se um algoritmo diferente.

Page 31: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 31 Curso: Informática Disciplina: Análise de Algoritmos

2.6.4.1 Algoritmo de Fleury Este algoritmo parte do pressuposto de que G é um grafo de Euler. Para executar o algoritmo, deve-se iniciar em qualquer vértice v e atravessar as

arestas de maneira arbitrária, seguindo as seguintes regras: Regra 1 – Apague a aresta que foi visitada e, se algum vértice ficar isolada, apague-o

também. Regra 2 – Em cada estágio, use uma ponte (istmo) somente se não houver alternativa.

Isto é, nunca atravesse uma aresta se essa aresta divide o grafo em duas componentes (excluindo o vértice isolado.

Observação: uma ponte (istmo) é uma aresta do grafo G cuja remoção divide o grafo G em duas componentes conexas de ordem maior que 1. Por exemplo, no exemplo abaixo, a aresta d é uma ponte.

b c e f a d g

Vamos considerar, por exemplo, o grafo abaixo e aplicar o algoritmo de Fleury, considerando o vértice 6 como vértice inicial (que, conseqüentemente, deve ser também o vértice final.

1 2 3 a b c d e f g h i 4 5 6 7 Pode-se iniciar o algoritmo por qualquer aresta que saia do vértice 6. Por exemplo,

as arestas d, e, h, i. Conforme a implementação, pode-se deixar a escolha aleatória, ou pegar sempre o primeiro vértice, conforme a ordem em que o usuário digitou. Por exemplo, vamos iniciar pela aresta d, que deve então ser removida. Temos então a configuração da Figura 2.

Em seguida a única aresta possível que pode ser removida é a c. Ao removermos a aresta c, o vértice 2 fica isolada, sendo removido. Temos então a configuração da Figura 3.

Figura 2

Figura 3 O processamento está agora no vértice 5. Como a aresta h é uma ponte, não se pode

escolhê-la. Pode-se então passar pela aresta b ou g. Vamos percorrer a aresta b, gerando então a configuração da Figura 4.

1 2 3

4 5 6 7

a b c e f g h i

4 5 6 7

1 3

a b e f g h i

Page 32: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 32 Curso: Informática Disciplina: Análise de Algoritmos

Em seguida, a única opção é percorrer a aresta a. Ao eliminarmos essa aresta, o vértice 1 fica isolado e, portanto, é também eliminado. A configuração do grafo é mostrada na Figura 5.

Figura 4

Figura 5

O processamento do algoritmo está agora no vértice 4. A única opção, portanto, é a aresta g, que é percorrida e eliminada. Como o vértice 4 ficou isolado, é também eliminado (Figura 6).

No vértice 5, a única opção é a aresta h, que é percorrida e eliminada, juntamente com o vértice 5. Temos então a configuração da Figura 7.

Figura 6

Figura 7

No vértice 6, novamente há duas opções: a aresta ‘e’ e a aresta ‘i’. Como estávamos seguindo sempre a aresta de menor ordem alfabética, vamos percorrer a aresta ‘e’, que é eliminada (Figura 8).

Em seguida, a única opção é a aresta f, que é eliminada juntamente com o vértice 3. Temos então a configuração da Figura 9.

Figura 8

Figura 9

No vértice 7, a única opção é a aresta ‘i’, que é percorrida e eliminada, juntamente com o vértice 7. Chegamos então no vértice final, que é também o final, e o algoritmo acaba.

1 3

4 5 6 7

a e f g h i

3

4 5 6 7

e f g h i

3

5 6 7

e f h i

3

6 7

e f i

3

6 7

f i

6 7 i

Page 33: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 33 Curso: Informática Disciplina: Análise de Algoritmos

6 O algoritmo de Fleury, propriamente dito, pode ser expresso da seguinte forma:

Ler grafo G(V,A) G' := G v0 := um vértice de G' C := [v0] //Inicialmente, o caminho de Euler contém só o vértice inicial v0 Enquanto A' não vazio //Ou seja, enquanto ainda existirem arestas vi := último vértice de C Se vi tem só uma aresta incidente; ai := a aresta incidente a vi em G' Senão ai := uma aresta incidente a vi em G' e que não é uma ponte Retirar a aresta ai do grafo G' Acrescentar ai no final de C vj := vértice ligado a vi por ai Acrescentar vj no final de C Retornar C

No caso do exemplo mostrado, então, as variáveis do algoritmo teriam o seguinte comportamento: A’ = {a,b,c,d,e,f,g,h,i} V’ = {1,2,3,4,5,6,7} C == [6] Figura 2 Vi:= 6 ai := d A’ = {a,b,c,e,f,g,h,i} C = [6,d] vj := 2 C = [6,d,2] Figura 3 Vi:=2 Ai:= c A’ = {a,b,e,f,g,h,i} C = [6,d,2,c] Vj:= 5 C = [6,d,2,c,5] ...

Page 34: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 34 Curso: Informática Disciplina: Análise de Algoritmos

Exercício Considere o grafo abaixo.

a) Mostre por que é um grafo de Euler. b) Aplique o algoritmo de Flery, considerando o vértice x1 como inicial. c) Aplique o algoritmo novamente, considerando o vértice x4 como inicial.

Nos itens b) e c), mostre o grafo sendo percorrido passo a passo, juntamente com o valor das variáveis do algoritmo no momento. x1

x7 x6 x2 x8 x5 x3 x4 2.6.5 Caminho e Circuito Hamiltoniano De forma resumida, um caminho que passa exatamente uma vez por cada vértice de

um grafo é chamado hamiltoniano. Se o caminho começa e termina no mesmo vértice, temos um circuito hamiltoniano. Um grafo que contém um ciclo hamiltoniano é um grafo hamiltoniano.

De forma formal: um circuito hamiltoniano em um grafo conexo G pode ser definido como um caminho simples fechado que passa em cada vértice de G exatamente uma vez. Portanto, um circuito hamiltoniano de um grafo conexo de n vértices consiste exatamente de n arestas. É possível, também, que um único grafo contenha vários caminhos hamiltonianos.

Teorema de Dirac: Uma condição suficiente, mas não necessária, para que um grafo simples G possua um ciclo hamiltoniano é que o grau de cada vértice de G seja pelo menos igual a n/2, onde n é o número de vértices.

2.6.6 Problema do Caixeiro Viajante Suponha que um caixeiro viajante tenha de visitar n cidades diferentes, iniciando e

encerrando sua viagem na primeira cidade. Suponha, também, que não importa a ordem com que as cidades são visitadas e que de cada uma delas pode-se ir diretamente a qualquer outra. Assim, o problema do caixeiro viajante consiste em descobrir a rota que torna mínima a viagem total.

O custo pode ser expresso em termos de dinheiro, distância, etc. Na prática, trata-se de achar um circuito hamiltoniano de custo mínimo para o grafo representando o problema.

Page 35: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 35 Curso: Informática Disciplina: Análise de Algoritmos

2.6.6.1 Complexidade do problema O problema do caixeiro viajante nos mostra que alguns problemas computacionais

ainda são difíceis de serem resolvidos computacionalmente, mesmo com os computadores potentes que temos atualmente.

Para entender isso, devemos notar que um mesmo grafo pode conter diversos caminhos hamiltonianos. Ou seja, conforme as arestas percorridas, teremos caminhos diferentes, com custos diferentes. Assim, não basta achar um circuito hamiltoniano, deve-se achar um de “custo mínimo”.

Suponha então que existem 4 cidades a serem percorridas, A, B, C e D, como demonstrado pelo grafo abaixo.

Supondo que de cada cidade pode-se ir diretamente a qualquer outra, então, só

saindo de A existem seis rotas possíveis:

ABCDA (custo 18) ABDCA (custo 16) ACBDA (custo 14) ACDBA (custo 16) ADBCA (custo 15) ADCBA (custo 18)o

Assim, não basta apenas achar uma rota qualquer, deve-se ainda encontrar a de menor custo, neste caso a de custo 14. Ou seja, o melhor procedimento, teoricamente, é encontrar todas as possíveis rotas e, em seguida, verificar qual delas tem o menor custo. Mas embora isso pareça simples, na prática nem sempre é possível.

Considere novamente este exemplo. Além das 6 rotas iniciando pela cidade A, temos ainda seis possibilidades começando com B, mais seis possibilidades começando com C e mais seis iniciando com D. Ou seja são 24 combinações, ou (n!), onde n é o número de cidades. Supondo que eu considere apenas uma cidade inicial, por exemplo a cidade A, temos as 6 combinações acima, ou (n-1)!.

Se eu criar um algoritmo para encontrar todas as rotas, ele vai executar perfeitamente com grafos com poucos vértices, como esse acima. No entanto, conforme o número de grafos cresce, o tempo para encontrar todas as rotas pode ser impraticável.

Suponha um computador que seja capaz de fazer 1 bilhão de somas por segundo e um grafo com 20 cidades. Assim, esse computador gastará 19 adições para calcular uma rota qualquer, apenas concatenando cidades aleatórias. Portanto, se em 1 segundo ele consegue fazer 1 bilhão de adições e para cada rota eu preciso apenas de 19 adições, portanto em cada segundo é possível calcular aproximadamente 53 milhões de rotas por segundo (1bilhão/19).

Embora isso possa parecer razoável à primeira vista, vamos ver então quantas rotas existem com 20 cidades. Considerando apenas uma cidade inicial, então são (n-1)! rotas possíveis, ou seja, 19!, que equivale a 121 645 100 408 832 000, ou 121 “quadrilhões”.

A B

C D

2 4

3 5

4

6

Page 36: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 36 Curso: Informática Disciplina: Análise de Algoritmos

1 segundo -------------- 53 milhões de rotas x -------------- 121 645 100 408 832 000 rotas X = 121 645 100 408 832 000 = 2.3 x 109 segundos

53.000.000

Ora, se em 1 segundo eu calculo 53 milhões de rotas, para calcular esse número de rotas eu preciso de 2.3 x 109 segundos, o que equivale a aproximadamente 73 anos.

A tabela a seguir demonstra o tempo que demora para calcular todas as rotas necessárias considerando grafos com 5, 10, 15, 20 e 25 cidades.

Cidades(n) Rotas por segundo Número de rotas( n - 1 )! Tempo para o cálculo

5 250 milhoes 24 insignificante

10 110 milhoes 362 880 0.003 seg

15 71 milhoes 87 bilhoes 20 min

20 53 milhoes 1.2 x 1017 73 anos

25 42 milhoes 6.2 x 1023 470 milhoes de anos Esse problema demonstra, portanto, que mesmo com os computadores potentes

existentes atualmente, para alguns problemas não basta conseguir fazer um algoritmo para resolver um problema. O algoritmo deve ser eficiente.

2.6.6.2 Aplicações

Algumas aplicações práticas de algoritmos que resolvem o problema do caixeiro-viajante são as seguintes: Programação de operações de máquinas em manufatura (Finke e Kusiak, 1985) Programação do movimento de ferramentas de corte (Chauny et al., 1987) Problemas de roteamento de veículos (Bodin et al., 1983) Solução de problemas de seqüenciamento de uma forma geral (Whitley et al, 1991) Solução de problemas de programação (Salomon et al, 1997) Distribuição de tarefas em plantas industriais (Salomon et al, 1997) Trabalhos administrativos (Laporte et al, 1996) Minimização do tempo que um robô industrial gasta para soldar a carcaça de um

automóvel Diminuição do tempo ou combustível na distribuição diária de um jornal produzido

numa grande cidade.

2.6.6.3 Tipos de soluções Em grafos pequenos, é possível achar vários (ou todos) os circuitos hamiltonianos

e, em seguida, pegar aquele com o menor custo. No entanto, com grafos muito grandes não

Page 37: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 37 Curso: Informática Disciplina: Análise de Algoritmos

é possível encontrar todos os circuitos hamiltonianos. Assim, existem dois tipos de solução para este problema: Solução 1 – Métodos exatos. Encontram a melhor solução, ou seja, de custo mínimo. Solução 2 – Métodos aproximados (heurísticas). Geram soluções satisfatórias, mas sem garantias de que aquele circuito hamiltoniano é o melhor possível.

Embora existam métodos exatos, eles não são muito eficientes, devido à dificuldade mostrada anteriormente. Assim, normalmente são utilizados os métodos aproximados. Alguns exemplos de soluções são as seguintes: Heurística greedy (algoritmo guloso) Vizinho mais próximo Inserção mais próximo Inserção mais distante Inserção mais econômica K-opt ou K-melhoramento “Simulated Annealing” Algoritmos Genéticos Busca Tabu Heurística Clarke-Wright 1. ALGORITMO VIZINHO MAIS PRÓXIMO

O algoritmo consiste basicamente dos seguintes passos: Escolher um vértice i qualquer e iniciar a rota. Repetir os seguintes passos até incluir todos os vértices

o Procure, considerando apenas os vértices j ainda não incluídos na rota, aquele que seja o mais próximo do último vértice considerado.

o Acrescente o vértice ao roteiro Acrescentar o primeiro vértice selecionado ao final da rota

Pode-se observar que, embora esse algoritmo funcione para grafos onde todos os

vértices têm ligação com todos os vértices, pode não funcionar caso contrário. Considere por exemplo o seguinte grafo.

Aplicando o algoritmo, temos: 1. Escolher, por exemplo, o vértice ‘a’. 2. O vértice mais próximo é o ‘e’. Portanto a rota fica ‘a e’. 3. A partir do vértice ‘e’, o mais próximo é o ‘f’. A rota, portanto, fica ‘a e f’. 4. A partir do vértice ‘f’, o mais próximo é o b. A rota, portanto, fica ‘a e f b’. 5. A partir do vértice ‘b’, o único vértice possível é o ‘c’. A rota, portanto, fica ‘a e f b c’

4 5

4 5

2 2 4 3 4

a

b

c

d e

f

3

Page 38: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 38 Curso: Informática Disciplina: Análise de Algoritmos

6. A partir do vértice ‘c’, o único vértice possível é o ‘d’. A rota, portanto, fica ‘a e f b c d’. 7. Como todos os vértices foram inseridos, agora deveria-se acrescentar primeiro vértice (a) ao final da rota. No entanto, não há uma ligação direta entre ‘d’ e ‘a’ e, portanto, essa rota não é válida.

Assim, pudemos perceber que esse algoritmo nem sempre encontra uma solução válida. Além disso, vale lembrar que, mesmo que se encontre uma solução, nem sempre ela é ótima. Por exemplo, a rota “c d e a b f c’ tem custo 21, enquanto a rota ‘f e a b c d f’ tem custo 20. 2. ALGORITMO MAIS ECONÔMICA (Inserção do mais próximo)

Este algoritmo é bastante similar ao anterior. Ou seja, inicia-se considerando um vértice inicial e buscando o vértice mais próximo. A diferença é que, a cada vez que eu procuro um novo vértice para inserir, vou escolher aquele que esteja mais perto de “qualquer um dos vértices que já façam parte do roteiro”.

Ou seja, o algoritmo consiste dos seguintes passos: 1. Escolher um vértice i qualquer. 2. Selecionar um vértice k mais próximo de i e criar um roteiro passando por k, ou seja, “i k i” (Se o grafo orientado, o vértice selecionado deve ser tal que a ida e a volta são as menores possíveis, ou seja o menor valor para dik + dki). 3. Repetir até que todos os vértices do grafo sejam inseridos:

A)Considerando o roteiro já formado, selecione um novo vértice k mais próximo de qualquer um dos vértices do roteiro

B)Considerando só as arestas que fazem parte do roteiro já formado, encontrar a aresta (x,y) do roteiro que apresenta o menor valor para (Dxk + Dky – Dxy).

C)Inserir o vértice k entre x e y.

No passo b) do item 3, se não for encontrada nenhuma aresta, o procedimento vai depender da implementação do algoritmo. O algoritmo pode a) ser finalizado ou b) procurar outro vértice k para inserir no roteiro. Exemplo: Considere o mesmo grafo do exemplo anterior, reproduzido a seguir. Vamos aplicar o algoritmo “inserção do mais próximo”. Passo 1: Escolher inicialmente o vértice ‘a’. Passo 2. Selecionamos o vértice mais próximo, que é o vértice ‘e’. Formamos então o roteiro “a e a”. Passo 3: Considerando esse roteiro, o vértice mais próximo é o vértice ‘f’. Visualmente, é fácil

perceber que tanto faz montar o roteiro da forma “afea” ou “aefa”. Mas seguindo o algoritmo, temos então:

4 5

4 5

2 2 4 3 4

a

b

c

d e

f

3

Page 39: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 39 Curso: Informática Disciplina: Análise de Algoritmos

Aresta ‘ae’ X=c, y=e, k=f Daf+ Dfe-Dae = 4 +2 -2 = 4 Aresta ‘ea’ X=e, y=a, k=f Def + Dfa - Dea = 2 + 4 -2 = 4 Como os dois roteiros têm o mesmo custo, vamos selecionar o primeiro. Temos então o roteiro “a f e a”. Considerando esse roteiro, o vértice mais próximo é o vértice ‘b’. Temos então: Aresta ‘af’ X=a, y=f, k=b Dab+ Dbf-Daf = 4 +3 -4 = 3 Aresta ‘fe’ X=f, y=e, k=b Dfb + Dbe - Dfe = 3 + - 2 = Aresta ‘ea’ X=e, y=a, k=b Déb + Dba – Dea = + 4 -2 =

Portanto, o menor roteiro é obtido inserindo-se o vértice ‘b’ entre os vértices ‘a’ e

‘f’. Portanto, o roteiro formado é “a b f e a”. Considerando esse roteiro, o vértice mais próximo é o vértice ‘d’. Temos então: Aresta ‘ab’ X=a, y=b, k=d Dad+ Ddb-Dab = + -4 = Aresta ‘bf’ X=b, y=f, k=d Dbd + Ddf - Dbf = + 4 - 3 = Aresta ‘fe’ X=f, y=e, k=d Dfd + Dde – Dfe = 4 + 4 -2 = 6 Aresta ‘ea’ X=e, y=a, k=d Ded + Dda – Dea = 4 + -2 =

Portanto, o menor roteiro é obtido inserindo-se o vértice ‘d’ entre os vértices ‘f’ e

‘e’. Portanto, o roteiro formado é “a b f d e a”. Considerando esse roteiro, o vértice mais próximo é o vértice ‘c’. Temos então: Aresta ‘ab’ X=a, y=b, k=c Dac+ Dcb-Dab = +5 -4 = Aresta ‘bf’ X=b, y=f, k=c Dbc + Dcf - Dbf = 5 + 5 - 3 = 7 Aresta ‘fd’ X=f, y=d, k=c Dfc + Dcd – Dfd = 5 + 3 -4 = 4 Aresta ‘de’ X=d, y=e, k=c Ddc + Dce – Dde = 3 + -4 = Aresta ‘ea’ X=e, y=a, k=c Dec + Dca – Dea = + -2 =

Portanto, o menor roteiro é obtido inserindo-se o vértice ‘c’ entre os vértices ‘f’ e ‘d’. Portanto, o roteiro formado é “a b f c d e a”, com um custo total de 21.

Deve-se notar que, embora este algoritmo encontre um roteiro com custo baixo, que

certamente não será o maior custo possível, pode acontecer de existir um roteiro com custo

Page 40: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 40 Curso: Informática Disciplina: Análise de Algoritmos

ainda menor. Por exemplo, neste caso um possível caminho heuleriano seria “abcdfea”, com custo 20 e outro seria “abcfdea”, com custo 24.

Exercício 1. O que é um grafo hamiltoniano? 2. Qual é a diferença entre o problema do carteiro chinês e o problema do caixeiro viajante? 3. Considere os grafos A e B abaixo. Para cada um eles, descubra um caminho hamiltoniano utilizando o algoritmo “vizinho mais próximo”. Grafo A Grafo B 4. Considere os mesmos grafos A e B da questão anterior. Para cada um eles, descubra um caminho hamiltoniano utilizando o algoritmo “inserção do mais próximo”. 3. ALGORITMO INSERÇÃO DO MAIS DISTANTE

Este algoritmo consiste dos seguintes passos: 1. Escolher um vértice i qualquer. 2. Selecionar um vértice k mais afastado de i e criar um roteiro passando por k, ou seja, “i k i” 3. Repetir até que todos os vértices do grafo sejam inseridos.

Considerando os vértices que já fazem parte do roteiro, verificar qual vértice não-inserido está mais próximo de cada vértice do roteiro. Forma-se então um conjunto Temp com vértices e suas distâncias.

Selecionar do conjunto Temp o vértice k com a maior distância. Considerando só as arestas que fazem parte do roteiro já formado, encontrar a

aresta (x,y) do roteiro que apresenta o menor valor para (Dxk + Dky – Dxy). Inserir o vértice k entre x e y.

Para exemplificar esse algoritmo, vamos considerar novamente o mesmo grafo

anterior, reproduzido abaixo:

5 4

5 2

4 3

a

b

c

d

e

3

a

b

c

d

e

4 3

2 4 5

2

6

4

4 5

4 5

2 2 4 3 4

a

b

c

d e

f

3

Page 41: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 41 Curso: Informática Disciplina: Análise de Algoritmos

Passo 1: escolho o vértice a Passo 2: O vértice adjacente a ‘a’ mais afastado são o ‘b’ e o ‘f’, com distância 4. Vou escolher o vértice ‘b’, por ser o primeiro. Formo então o roteiro “a b a”. Passo 3: Passo 3.1 Vértice a o mais próximo é o vértice ‘e’, com custo 2. Vértice b o mais próximo é o vértice ‘f’, com custo 3. Temp {(e,2), (f,3)} Passo 3.2. O vértice de Temp com a maior distância é o f, com distância 3. Passo 3.3. Aresta ab Daf + dfb – dab = 4+3-4 = 3 Aresta ba Dbf + dfa – dba = 3 + 4 -4 = 3 Como deu empate, escolho a primeira aresta, ‘ab’. Passo 3.4. Inserir o vértice ‘f’ no roteiro, entre a aresta ‘ab’. Roteiro: “afba”. Passo 3.1 Vértice a o mais próximo é o vértice ‘e’, com custo 2. Vértice f o mais próximo é o vértice ‘e’, com custo 2 Vértice b o mais próximo é o vértice ‘c’, com custo 5. Temp {(e,2), (e,2),(c,5)} Passo 3.2. O vértice de Temp com a maior distância é o ‘c’, com distância 5. Passo 3.3. Aresta af Dac + dcf – daf = + 5 – 4 = Aresta fb Dfc + dcb – dfb = 5 + 5 - 3 = 7 Aresta ba Dbc + dca – dba = 5 + - 4 = A aresta que acrescenta menor custo é a fb.

Page 42: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 42 Curso: Informática Disciplina: Análise de Algoritmos

Passo 3.4. Inserir o vértice ‘c’ no roteiro, entre a aresta ‘fb’. Roteiro: “afcba”. Passo 3.1 Vértice a o mais próximo é o vértice ‘e’, com custo 2. Vértice f o mais próximo é o vértice ‘e’, com custo 2 Vértice c o mais próximo é o vértice ‘d’, com custo 3 Vértice b todos os vértices adjacentes já foram inseridos. Temp {(e,2), (e,2),(d,3)} Passo 3.2. O vértice de Temp com a maior distância é o ‘d’, com distância 3. Passo 3.3. Aresta af Dad + ddf – daf = + 4 – 4 = Aresta fc Dfd + ddc – dfc = 4 + 3 - 5 = 4 Aresta cb Dcd + ddb – dcb = 3 + - 5 = Aresta ba Dbd + dda – dba = + - 4 = A aresta que acrescenta menor custo é a fc. Passo 3.4. Inserir o vértice ‘c’ no roteiro, entre a aresta ‘fb’. Roteiro: “afdcba”. Passo 3.1 Vértice a o mais próximo é o vértice ‘e’, com custo 2. Vértice f o mais próximo é o vértice ‘e’, com custo 2 Vértice d o mais próximo é o vértice ‘e’, com custo 4 Vértice c todos os vértices adjacentes já foram inseridos Vértice b todos os vértices adjacentes já foram inseridos. Temp {(e,2), (e,2),(e,4)} Passo 3.2. O vértice de Temp com a maior distância é o ‘e’, com distância 4. Passo 3.3. Aresta af Dae + def – daf = 2 + 2 – 4 = 0 Aresta fd Dfe + ded – dfd = 2 + 4 - 4 = 2 Aresta dc Dde + dec – ddc = 4 + - 3 = Aresta cb Dce + deb – dcb = + - 3 = Aresta ba Dbe + dea – dba = + 2 - 4 = A aresta que acrescenta menor custo é a af

Page 43: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 43 Curso: Informática Disciplina: Análise de Algoritmos

Passo 3.4. Inserir o vértice ‘e’ no roteiro, entre a aresta ‘af’. Roteiro final : “aefdcba”. 4. HEURÍSTICA DE MELHORAMENTO 2-OPT

Vimos que os métodos anteriores nem sempre conseguem encontrar o melhor caminho possível. Em virtude disso, este algoritmo, na verdade, não é utilizado para encontrar um caminho hamiltoniano, mas sim para “melhorar” um caminho hamiltoniano já existente.

Assim, dado um grafo e um caminho hamiltoniano nesse grafo, este algoritmo tenta melhorar esse caminho trocando duas arestas do caminho por outras duas arestas. O algoritmo é basicamente o seguinte: 1. Considere uma matriz de distâncias de um grafo e um vetor contendo o caminho inicial. 2. Selecione duas arestas do caminho: (a,b) e (c,d). 2. Verifique se existem 2 arestas alternativas (x,y) (z,w) utilizando apenas os vértices ‘a’, ‘b’, ‘c’ e ‘d’ tal que o custo d(x,y)+d(z,w) seja menor do que o custo inicial d(a,b)+d(c,d)

Por exemplo, considere o grafo abaixo:

Vamos supor que, aplicando um método qualquer, o caminho encontrado tenha sido “a b c d e a”, com custo 21. O caminho, portanto, é composto das arestas (a,b), (b,c), (c,d), (d,e) e (e,a).

Assim, escolhemos aleatoriamente as arestas (a,b) e (c,d) para serem trocadas. Vamos verificar então se as arestas (a,c) e (b,d) são melhores escolhas. D(a,b) + d(c,d) = 4 + 5 = 9 D(a,c) + d(b,d) = 1 + 4 = 5

Verificamos, assim, que as novas arestas reduzem o custo do caminho. Vamos

então, trocar as arestas, de forma que o novo caminho seja: “a c b d e a”, com custo 17. Conforme a implementação, o algoritmo pode ser aplicado várias vezes, para

verificar se não existe uma solução ainda melhor. Neste caso, por exemplo, outra alternativa, considerando o grafo original, seria trocar as arestas (e,a) e (b,c) pelas arestas (a,c) e (e,b). Vamos verificar como ficam os custos neste caso: D(e,a) + d(b,c) = 5 + 3 = 8 D(a,c) + d(e,b) = 1 + 2 = 3

Portanto, fazemos a troca e o caminho final fica: “a,c, d, e, b, a”, com custo 16. Os grafos abaixo mostram os possíveis caminhos hamiltonianos.

4 5

3

5

5 1

2

3 4

a

b

c d

e 4

4 5

5

3 4

a

b

c d

e 1 5

a

b e

4 1 2

a

b e

Page 44: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 44 Curso: Informática Disciplina: Análise de Algoritmos

5. HEURÍSTICA DE MELHORAMENTO 3-OPT2

A heurística 3-opt é praticamente idêntica à 2-opt, com a diferença de que, em vez de movermos apenas 2 arestas, movemos 3. Por exemplo, considerando o mesmo grafo anterior, poderíamos remover as arestas (a,b), (c,d) e (d,e) e inserir as arestas (a,d), (d,b) e (c,e). Neste caso o custo total seria 20, o que é mais vantajoso que os 21 iniciais. O caminho percorrido no grafo é exemplificado a seguir:

Tanto para a heurística 2-opt quanto para a 3-opt, repare que, embora algumas

arestas tenham seu sentido modificado, a heurística não considera essas mudanças no algoritmo por estarmos considerando apenas grafos não dirigidos e, portanto, o custo não é alterado. No entanto, lembre-se que ao implementar o algoritmo é necessário fazer modificações no vetor que armazena o caminho.

2.7 Busca em Grafo Até agora, vimos que os grafos podem ser utilizados ajudar a solucionar diversos

problemas, tais como encontrar o menor caminho entre dois pontos ou encontrar a melhor rota para passar por diversos pontos.

Outra possibilidade, então, é utilizar a representação na forma de grafos para a busca. Pode-se buscar um vértice específico ou um vértice que atenda a alguma características. Por exemplo, suponha que você tenha um grafo representando as cidades brasileiras e, em cada vértice do grafo, o número de habitantes. Você poderia fazer uma busca para tentar encontrar todas as cidades com menos de 5.000 habitantes. Ou então fazer uma busca para verificar se existe pelo menos alguma cidade com menos de 1.000 habitantes.

Mas qual é, então, o método mais eficiente para se fazer uma busca? Vejamos então alguns possíveis métodos:

2.7.1 Algoritmo Básico ou Busca Geral Seja G um grafo conexo.

2 Verifique novamente um exemplo de implementação da heurística 3-opt na página http://www.dcc.ufmg.br/~krusty/pcva/heuristico.htm.

4 3 4

c d 5

4

c d

4

5 5

3 3

a

b

c d

e

Page 45: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 45 Curso: Informática Disciplina: Análise de Algoritmos

1. Escolhe-se um vértice qualquer como vértice inicial. Marca-se esse vértice como já visitado.

2. Repetir os seguintes passos até que a condição seja satisfeita ou todas as arestas tiverem sido exploradas: 2.1. Selecionar um vértice já visitado v que seja incidente a alguma aresta (v,w) não visitada. 2.2. Marca-se a aresta (v,w) como visitada. 2.3. Se o vértice w ainda não tiver sido marcado, marca-se como visitado.

A condição de parada depende do objetivo do programa e, portanto, pode ser qualquer uma, tal como:

A distância percorrida é maior do que 10.000 Foi encontrado um vértice com valor 57. Foi encontrado um vértice com o nome “x”. Todos os vértices já foram percorridos.

Por exemplo, vamos supor que queremos fazer uma busca no grafo abaixo até que

todos os vértices tenham sido visitados, de modo a fazer uma contagem da soma dos valores das arestas.

1. Iniciar com o vértice a. Vértices visitados = {a}. Arestas visitadas = {} Soma = 0 2. Escolho o vértice visitado ‘a’ e (aleatoriamente) a aresta não visitada (a,b). Vértices visitados = {a,b} Arestas visitadas = {(a,b)} Soma = 4 3. Escolho (aleatoriamente) o vértice visitado ‘b’ e a aresta não visitada (b,d). Vértices visitados = {a,b,d} Arestas visitadas = {(a,b),(b,d)} Soma = 9 4. Escolho o vértice visitado ‘a’ e a aresta não visitada (a,e). Vértices visitados = {a,b,d,e} Arestas visitadas = {(a,b),(b,d),(a,e)} Soma = 14 5. Escolho o vértice visitado ‘a’ e a aresta não visitada (a,d). Vértices visitados = {a,b,d,e} Note que o vértice já tinha sido visitado Arestas visitadas = {(a,b),(b,d),(a,e),(a,d)} Soma = 21 6. Escolho o vértice visitado ‘e’ e a aresta não visitada (e,f)

d e

a b

c

4 6

6

4

5 f

5

5 5 7

Page 46: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 46 Curso: Informática Disciplina: Análise de Algoritmos

Vértices visitados = {a,b,d,e,f} Arestas visitadas = {(a,b),(b,d),(a,e),(a,d),(e,f)} Soma = 26 7. Escolho o vértice visitado ‘b’ e a aresta não visitada (b,c). Vértices visitados = {a,b,d,e,f,c} Arestas visitadas = {(a,b),(b,d),(a,e),(a,d),(e,f),(b,c)} Soma = 32 8. Como todos os vértices já foram visitados, a condição de parada é alcançada e o algoritmo sai do laço.

2.7.2 Busca em Profundidade A única diferença para o algoritmo básico é o critério para escolher o próximo

vértice a ser visitado. Neste algoritmo, considera-se a cada iteração apenas os vértices já visitados que são incidentes a alguma aresta ainda não percorrida. Escolhe-se então aquele mais recentemente visitado.

Vamos implementar esse algoritmo de forma recursiva: 1. Definir uma pilha P; 2. Escolher um vértice qualquer r para servir de vértice inicial (raiz); 3. Prof(r). Fim.

Procedimento P(v) 4. Marcar r como já visitado; 5. Colocar r na pilha P; 6. Para w +(v) (para todos os vértices w que pertencem aos sucessores de v) Se w não foi visitado então: 7. Visitar(v,w); 8. P(w); Senão se w pertence à pilha e ‘v’ e ‘w’ não são consecutivos na pilha então: 9. Visitar(v,w); Fim-para 10. Retirar v da pilha P; Fim-procedimento

Vejamos então como ficaria a busca utilizando como exemplo o mesmo grafo anterior, reproduzido a seguir:

1. Pilha P = {} 2. Vértice r = a 3. P(a).

4. Visitados = {a}

d e

a b

c

4 6

6

4

5 f

5

5 5 7

Page 47: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 47 Curso: Informática Disciplina: Análise de Algoritmos

5. Pilha P = {a} 6. +(a) = {b,d,e,f} 7. Visitar (a,b).

8. P(b). 4.Visitados = {a,b} 5. Pilha P = {a,b}

6. +(b) = {a,c,d} Vértice ‘a’ - ‘a’ já é marcado e ‘a’ e ‘b’ são consecutivos na pilha. Vértice ‘c’: 7. Visitar (b,c) 8. P(c)

4. Visitados = {a,b,c} 5. Pilha P = {a,b,c} 6. +(c) = {b,d} Vértice ‘b’ – ‘b’ já foi visitado e ‘b’ e ‘c’ são consecutivos na pilha Vértice ‘d’: 7. Visitar (c,d) 8. P(d)

4. Visitados = {a,b,c,d} 5. Pilha P = {a,b,c,d} 6. +(d) = {a,b,c,e} Vértice ‘a’ – já foi visitado mas ‘a’ e ‘d’ não são consecutivos 9. Visitar (d,a). Vértice ‘b’ – já foi visitado mas ‘b’ e ‘d’ não são consecutivos 9. Visitar (d,b) Vértice ‘c’ – já foi visitado e são consecutivos Vértice ‘e’: 7. Visitar (d,e). 8. P(e)

4. Visitados = {a,b,c,d,e} 5. Pilha P = {a,b,c,d,e} 6. +(e) = {a,d,f} Vértice ‘a’ – já visitado mas ‘a’ e ‘e’ não consecutivos 9. Visitar (e,a) Vértice ‘d’ – já visitado e são consecutivos Vértice ‘f’ – não visitado: 7. Visitar (e,f). 8. P(f).

4. Visitados = {a,b,c,d,e,f} 5. Pilha = {a,b,c,d,e,f} 6. +(f) = {a,e} Vértice ‘a’ – visitado mas não consecutivos 9. Visitar (f,a) Vértice ‘e’ – visitado mas consecutivos Como já visitei todos os sucessores de ‘f’, chego ao fim do laço ‘para’. Saindo do laço então: 10. Pilha = {a,b,c,d,e}

Page 48: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 48 Curso: Informática Disciplina: Análise de Algoritmos

Como cheguei ao fim do procedimento, volto para o ponto onde foi feita a última chamada recursiva. Ou seja, a chamada a P(f).

Neste ponto, eu estava verificando os sucessores de ‘e’. Como todos os sucessores já foram verificados, chego novamente ao fim do laço ‘para’. Então: 10. Pilha = {a,b,c,d}. Chego ao fim do procedimento e, portanto, volto para o ponto anterior onde foi feita uma chamada recursiva. Ou seja, a chamada a P(e).

Neste ponto, eu estava verificando os sucessores de ‘d’. Como todos os sucessores já foram verificados, chego novamente ao fim do laço ‘para’. Então: 10. Pilha = {a,b,c}. Chego ao fim do procedimento e, portanto, volto para o ponto anterior onde foi feita uma chamada recursiva. Ou seja, a chamada a P(d).

Neste ponto, eu estava verificando os sucessores de ‘c’. Como todos os sucessores já foram verificados, chego novamente ao fim do laço ‘para’. Então: 10. Pilha = {a,b}. Chego ao fim do procedimento e, portanto, volto para o ponto anterior onde foi feita uma chamada recursiva. Ou seja, a chamada a P(c).

Neste ponto, eu estava verificando os sucessores de ‘b’. Notem que os sucessores de ‘b’ são {a,c,d}. No entanto, quando eu estava verificando ‘c’ foi feita a chamada recursiva. Portanto, o vértice ‘d’ ainda não foi verificado. Vértice ‘d’: O vértice ‘d’ já foi visitado, e ‘d’ não pertence mais à pilha. Agora sim todos os sucessores de ‘b’ já foram verificados. Chego então ao fim do laço ‘para’. Então: 10. Pilha = {a}. Chego ao fim do procedimento e, portanto, volto para o ponto anterior onde foi feita uma chamada recursiva. Ou seja, a chamada a P(b).

Neste ponto, eu estava verificando os sucessores de ‘a’. Notem que no primeiro sucessor de ‘a’ já foi feita uma chamada recursiva. Portanto, ainda não foram verificados os vértices ‘d’, ‘e’ e ‘f’. Vértice ‘d’: O vértice já foi visitado e não pertence mais à pilha. Vértice ‘e’: O vértice já foi visitado e não pertence mais à pilha. Vértice ‘f’: O vértice já foi visitado e não pertence mais à pilha. Agora todos os sucessores de ‘a’ já foram verificados. Chego então ao fim do laço ‘para’. Então: 10. Pilha = {}. Chego ao fim do procedimento e, portanto, volto para o ponto anterior onde foi feita uma chamada recursiva. Ou seja, a chamada a P(a).

Chego finalmente, então, ao fim do programa.

Resumindo essa seqüência de passos de forma gráfica, temos:

Page 49: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 49 Curso: Informática Disciplina: Análise de Algoritmos

Vértice ‘a’ Vértice ‘b’ Vértice ‘c’ Vértice ‘d’ Vértice ‘e’ Vértice ‘f’ b a b a a a

d c d b d e

e d c f

f e

Fim

2.7.3 Busca em Largura Vimos que, na busca em profundidade, cada vez que eu encontrava um vértice não

visitado, eu pulava para ele e passava a verificar seus sucessores. Se encontrasse outro não vértice, pulava para esse outro e assim por diante.

Na busca em largura, para cada vértice selecionado eu visito todos os seus descendentes. Só então vou verificar os outros vértices. O algoritmo formal é o seguinte: 1. Escolher um vértice r qualquer como raiz. 2. Definir uma pilha P vazia. 3. Marcar r como já visitado. 4. Inserir r em P. 5. Enquanto P ≠{} (enquanto a pilha não estiver vazia)

6. v = primeiro elemento na pilha; 7. Para w +(v) faça (para todos os sucessores de v, faça)

Se w ainda não foi visitado, então: 8. visitar (v,w). 9. marcar w como já visitado; 10. Inserir w em P.

Senão, se w P, então: 11. Visitar (v,w).

Fim-para. 12. Retirar v de P;

Fim-enquanto. Fim-algoritmo.

Tomemos novamente como exemplo o grafo a seguir:

d e

a b

c

4 6

6

4

5 f

5

5 5 7

Page 50: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 50 Curso: Informática Disciplina: Análise de Algoritmos

1. Escolher o vértice ‘a’ como raiz. 2. P = {}. 3. Visitados = {a} 4. P = {a} 5. Enquanto P ≠{}: 6. v = ‘a’. (v recebe o primeiro vértice da pilha

7. Primeiro sucessor: ‘b’. 8. visitar (a,b). 9. Visitados = {a,b}. 10. P = {a,b}.

7. Segundo sucessor: ‘d’. 8. visitar (a,d). 9. Visitados = {a,b,d}. 10. P = {a,b,d}.

7. Terceiro sucessor: ‘e’. 8. visitar (a,e). 9. Visitados = {a,b,d,e}. 10. P = {a,b,d,e}.

7. Último sucessor: ‘f’: 8. visitar(a,f). 9. Visitados = {a,b,d,e,f}. 10. P = {a,b,d,e,f}

12. P = {b,d,e,f}. 6. v = ‘b’ (v recebe o primeiro vértice da pilha)

7. Primeiro sucessor: ‘a’. ‘a’ já foi visitado e não pertence à pilha. 7. Segundo sucessor: ‘c’.

8. visitar (b,c). 9. Visitados = {a,b,d,e,f,c}. 10. P = {b,d,e,f,c}.

7. Terceiro sucessor: ‘d’. ‘a’ já foi visitado mas pertence à pilha. Então:

11. visitar (b,d). 12. P = {d,e,f,c}.

6. v = ‘d’. 7. Primeiro sucessor: ‘a’. ‘a’ já foi visitado e não pertence à pilha. 7. Segundo sucessor: ‘b’. ‘b’ já foi visitado e não pertence à pilha. 7. Terceiro sucessor: ‘c’. ‘c’ já foi visitado e pertence à pilha. Então:

11. visitar (d,c). 7. Último sucessor: ‘e’.

‘e’ já foi visitado mas pertence à pilha. Então:

Page 51: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 51 Curso: Informática Disciplina: Análise de Algoritmos

11. visitar (d,e). 12. P = {e,f,c}.

6. v = ‘e’. 7. Primeiro sucessor: ‘a’.

‘a’ já foi visitado e não pertence à pilha. 7. Segundo sucessor: ‘d’. ‘d’ já foi visitado e não pertence à pilha. 7. Terceiro sucessor: ‘f’. ‘f’ já foi visitado e pertence à pilha. Então: 11. visitar (e,f). 12. P = {f,c}.

6. v = ‘f’. 7. Primeiro sucessor: ‘a’. ‘a’ já foi visitado e não pertence à pilha. 7. Segundo sucessor: ‘e’. ‘e’ já foi visitado e não pertence à pilha. 12. P = {c}.

6. v = ‘c’. 7. Primeiro sucessor: ‘b’. ‘b’ já foi visitado e não pertence à pilha. 7. Segundo sucessor: ‘d’. ‘d’ já foi visitado e não pertence à pilha. 12. P = {}.

Fim do enquanto. Fim.

Vértice ‘a’ Vértice ‘b’ Vértice ‘c’ Vértice ‘d’ Vértice ‘e’ Vértice ‘f’ b a b a a a

d c d b d e

e d Fim c f

f e

Exercício: 1 – Considerando o grafo a seguir: a) Faça uma busca geral b) Faça uma busca em profundidade c) Faça uma busca em largura O critério de parada é ter percorrido todos os vértices. Inicie pelo vértice ‘f’. d) Verifique quantas arestas foram percorridas em cada uma das buscas. Com base no resultado, decida se, para esse grafo, alguma das buscas foi mais eficiente do que as outras.

e

a

b f g

Page 52: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 52 Curso: Informática Disciplina: Análise de Algoritmos

2 – Considerando o grafo a seguir, faça uma busca em profundidade, mas mostrando em cada passo o valor das variáveis do algoritmo, como exemplificado na apostila.

d c

Page 53: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 53 Curso: Informática Disciplina: Análise de Algoritmos

2.8 Fluxo em Rede

Page 54: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 54 Curso: Informática Disciplina: Análise de Algoritmos

3 Eficiência e Corretude de Algoritmos Vimos no começo da disciplina que o objetivo da Análise de Algoritmos é

inicialmente possibilitar que o aluno aprenda algoritmos básicos e diferentes técnicas utilizadas para resolver problemas computacionalmente. Em seguida, o objetivo é que ele consiga utilizar esse conhecimento para fazer algoritmos que sejam os mais eficientes possíveis.

No entanto, para desenvolver algoritmos realmente eficientes, não basta conhecer técnicas e alternativas para problemas comuns. O programador deve ter a capacidade de prever, ao desenvolver um algoritmo, qual será o seu comportamento, quer com poucos ou com muitos dados de entrada.

A tentativa de prever o comportamento do algoritmo consiste em avaliar sua complexidade. Para isso, são feitos cálculos, que podem ser simples ou complexos. Como esses cálculos envolvem definições e notações específicas, como analisá-las, para só então vermos como proceder para analisar a complexidade de um software.

Temos então três objetivos para a análise de algoritmos: 1. Avaliar um algoritmo para verificar se ele é eficiente 2. Verificar se um algoritmo é correto ou incorreto 3. Comparar vários algoritmos (que resolvem o mesmo problema) para decidir qual é o mais eficiente.

3.1 Definições

3.1.1 O que é um algoritmo? Um algoritmo é definido pela matemática como um “processo de cálculo, ou de

resolução de um grupo de problemas semelhantes, em que se estipulam regras formais para a obtenção do resultado, ou da solução do problema”. Em computação, é comum definirmos um algoritmo como “um conjunto de passos necessários para resolver um problema”. Outra definição é a de que “um algoritmo, intuitivamente, é uma seqüência finita de instruções ou operações básicas(...), cuja execução, em tempo finito, resolve um problema computacional”(Salvetti e Barbosa, 1998).

Um algoritmo, na computação, é qualquer procedimento computacional que recebe como entrada um valor (ou conjunto de valores) e produz como saída outro valor (ou um conjunto de valores). Finalmente, então, podemos dizer que um algoritmo é uma seqüência de passos computacionais que transforma entrada em saída.

Esse, portanto, é o objeto que será estudado a partir de agora. Trechos de código só podem ser considerados algoritmos quando eu consigo definir claramente: 1) o problema, 2) os dados de entrada e 3)os dados de saída.

Por exemplo, eu posso ter um trecho de código no qual eu identifico os seguintes elementos:

Figura 10 : Exemplo de elementos de um algoritmo

Problema: Encontrar o maior e o menor valor de um vetor com n elementos. Entrada: Vetor com n elementos Saída: O elemento com o menor valor de todos e o elemento com o maior valor de todos.

Page 55: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 55 Curso: Informática Disciplina: Análise de Algoritmos

Neste caso, se o trecho tem apenas essa função, pode ser considerado um algoritmo e é possível analisá-lo individualmente.

3.1.2 Instâncias de execução de algoritmos Uma instância de um problema consiste de um conjunto de dados de entrada e saída

utilizado durante uma única execução. Por exemplo, as figuras 11 e 12 mostram diferentes instâncias da execução do mesmo algoritmo, cujo problema foi especificado na Figura 10.

Figura 11 . Exemplo de instância da execução de um algoritmo

Figura 12 . Exemplo de outra instância da execução de um algoritmo

Por esses exemplos podemos verificar que em diferentes instâncias de execução, os

dados de entrada podem ser bastante variados, podendo inclusive ter uma grande variação de volume. Ou seja, na instância apresentada na Figura 11 o vetor de entrada tinha 19 valores, enquanto na instância apresentada na Figura 12 o vetor de entrada tinha 22. Da mesma, em uma outra instância é possível que eu tenha 500 elementos de entrada.

A questão que se levanta então é: dado um algoritmo que funciona de forma eficiente para 10 elementos, ele continuará funcionando de forma eficiente para 10.000 ou mais? O algoritmo deve trabalhar corretamente sobre todas as instâncias para as quais foi projetado para solver. Portanto, um algoritmo para o qual é possível achar uma instância de dados de entrada para a qual ele não consegue achar uma resposta correta é um algoritmo incorreto. No entanto, provar o contrário, que o algoritmo é correto para qualquer instância, não é tão simples. Para isso, o algoritmo deve ser avaliado utilizando alguns critérios.

3.1.3 Avaliação de Algoritmos Algoritmos podem ser avaliados utilizando-se vários critérios. Geralmente o que

interessa é a taxa de crescimento ou espaço necessário para resolver instâncias cada vez maiores de um problema. Podemos associar um problema a um valor chamado de ‘tamanho’ do problema, que mede a quantidade de dados de entrada.

O tempo que um algoritmo necessita expresso como uma função do tamanho do problema é chamado de complexidade temporal do algoritmo. O comportamento assintótico dos algoritmos (ou funções) representa o limite do comportamento de custo quando o tamanho cresce. O comportamento assintótico pode ser definido como o comportamento de um algoritmo para grandes volumes de dados de entrada.

A complexidade temporal de um algoritmo pode ser dividida em 3 aspectos:

Problema: Encontrar o maior e o menor valor de um vetor com n elementos. Entrada: {1,34,56,32,3,54,3,356,3,2,23,78,65,32,11,1,43,356,66} Saída: Menor valor = 1 Maior valor = 356

Problema: Encontrar o maior e o menor valor de um vetor com n elementos. Entrada: {2,54,67,93,54,23,345,67,42,447,4,983,10,76,31,15,57,83,45,794,346,44} Saída: Menor valor = 2 Maior valor = 983

Page 56: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 56 Curso: Informática Disciplina: Análise de Algoritmos

1. Melhor caso – o melhor caso representa uma instância que faz o algoritmo executar utilizando o menor tempo possível. 2. Pior caso – o maior tempo demorado pelo algoritmo para executar alguma instância. 3. Caso médio – a média de tempo que o algoritmo demora para executar.

Geralmente, o mais importante é avaliar o pior caso (porque pode inviabilizar o

algoritmo) e o caso médio, porque representa como o programa vai se comportar, na prática, na maioria dos casos.

3.1.3.1 Avaliação Empírica

A forma mais simples de se avaliar um algoritmo é implementá-lo em um computador e executá-lo com várias instâncias do problema. Define-se então um critério para a eficiência, como por exemplo o tempo gasto para execução. Esse tipo de avaliação é chamada de empírica. Com base na observação, pode-se calcular o pior caso (a instância de execução que levou mais tempo), o melhor caso (a instância de execução que gastou menos tempo) e o caso médio (a média do tempo gasto em todas as instâncias de execução).

O problema com esse tipo de avaliação é que o tempo gasto vai depender do computador utilizado, do compilador, da linguagem de programação, etc.

3.1.3.2 Avaliação Teórica

Na avaliação teórica, que é a que vai ser focalizada aqui, consiste em encontrar uma fórmula matemática que expresse o recurso (por exemplo, o tempo) necessário para o algoritmo executar em função do tamanho dos dados de entrada.

3.1.4 Associando uma função a um algoritmo Para encontrar uma fórmula matemática que expresse quanto tempo será necessário

para cada volume de dados de entrada, podemos utilizar primeiramente uma avaliação empírica. Para isso, deve-se montar uma tabela relacionando volumes de dados com seus respectivos tempos de execução. Considere por exemplo um programa fictício Raiz, que recebe como entrada um vetor de inteiros e devolve como saída um vetor com a raiz quadrada de cada um dos elementos do vetor. Suponha que o programa é executado várias vezes, com diferentes números de elementos de entrada, tendo seu tempo cronometrado, como apresentado na Tabela 1.

Número de elementos no vetor Tempo gasto para execução (segundos)

1 0,001 10 0,01 50 0,05 100 0,1 500 0,5 1.000 1 5.000 5 10.000 10 50.000 50 100.000 100

Tabela 1: Relação volume de dados de entrada x tempo de execução

Page 57: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 57 Curso: Informática Disciplina: Análise de Algoritmos

Se colocarmos esses valores em um gráfico (vide Gráfico 1), veremos que esses valores são representados por uma reta. Lembrando um pouco das aulas de geometria, temos que uma reta pode ser representa por uma função linear do tipo ax+b.

0

1000

2000

3000

4000

5000

6000

7000

0,001 0,01 0,05 21 3 4 5 60,1 0,5

Grafico 1

Assim, se conseguirmos encontrar uma fórmula como essa que represente o comportamento temporal do algoritmo em relação ao número de dados de entrada, então podemos saber o seu comportamento para qualquer volume de dados de entrada! Basta aplicar o valor na fórmula.

3.2 Notação O, Omega e Theta Após obter a função que representa o comportamento de um software, basta

analisá-la para termos uma medida da complexidade do software. Para isso se utiliza as três notações a seguir: O, Omega e Theta. Elas são utilizadas também para comparar funções de diferentes algoritmos.

3.2.1 Notação O Esta notação é utilizada para analisar o pior caso. Uma função g(n) é O(f(n)) se c>0 e n0 tais que g(n) <= c f(n) para n>=n0.

Explicação: uma função g(n) é da ordem de complexidade de f(n) se existe uma constante c e um valor n0 tal que para qualquer valor de n maior do que n0 g(n) é menor ou igual a c.f(n).

Isso significa que: f(n) é um limite superior para g(n) f(n) denomina assintoticamente g(n)

Propriedades:

f(n) = O(f(n)) c. f(n) = O(f(n)), c=constante O(f(n)) = O(f(n)) = O(f(n))

Page 58: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 58 Curso: Informática Disciplina: Análise de Algoritmos

O(O(f(n))) = O(f(n)) O(f(n)) = O(g(n)) = O(max(f(n),g(n)) O(f(n)) . O(g(n)) = O (f(n) . g(n))

3.2.2 Notação Esta notação é utilizada para analisar o melhor caso. Uma função f(n) = (g(n)) se existem constantes c e no, tal que c.g(n) <=f(n) para

n>=no. Isso significa que:

f(n) é um limite inferior para g(n)

3.2.3 Notação Esta notação é utilizada para analisar o caso médio. Uma função f(n) = (g(n)) se existem constantes c1, c2 e no tais que c1. g(n) <=

f(n) <= c2.g(n) para n>=no.

Page 59: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 59 Curso: Informática Disciplina: Análise de Algoritmos

A notação O é a mais utilizada, porque geralmente o mais importante é descobrir o pior caso, para saber se existe alguma possibilidade de o algoritmo falhar, isto é, não conseguir executar caso se entre com um volume de dados demasiado grande.

Fazendo uma analogia para melhor compreensão das notações, temos o seguinte, considerando que f e g são funções que representam o comportamento de dois algoritmos diferentes. F(n) = O (g(n)) f<=g F(n) = (g(n)) f>=g F(n) = (g(n)) f=g

3.3 Crescimento assintótico de funções A complexidade assintótica de um algoritmo geralmente determina o tamanho dos

problemas que poderão ser resolvidos por esse algoritmo. Assim, se um algoritmo processa dados de tamanho n em um tempo cn2 para uma constante c, então dizemos que a complexidade temporal do algoritmo é O(n2) (leia-se: da ordem de n2).

Por exemplo, suponha os cinco algoritmos abaixo:

Algoritmo Complexidade A1 n

A2 n log n A3 n2 A4 n3 A5 2n

A complexidade de tempo é o número de unidades de tempo necessárias para

processar uma entrada de tamanho n. Assim, assumindo por exemplo a unidade de tempo como sendo um millisegundo, o algoritmo A1 precisa, para processar 1000 entradas, de 1000 millisegundos, ou seja, 1 segundo. Já o algoritmo A3 precisa de 1 milhão de segundos. Enquanto o A1 consegue processar 1000 entradas em um segundo, o A5 só consegue processar 9 entradas em 1 segundo.

3.3.1 Principais Classes de Complexidade A tabela a seguir mostra as principais classes de complexidade de funções. Quanto

mais abaixo na tabela, mais complexo é o algoritmo que a função representa.

Função Nome 1 Constante log n Logarítmica log2 n Log quadrático

n Linear n log n n log n

n2 Quadrática n3 Cúbica 2n exponencial

Page 60: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 60 Curso: Informática Disciplina: Análise de Algoritmos

4 Análise da Complexidade de Algoritmos

4.1 Estimativas de Tempo de Execução Sabemos que os principais recursos ocupados por um software em execução são

espaço em disco, espaço em memória e tempo. Mas enquanto o espaço é uma questão que pode ser facilmente resolvida, o tempo que um programa gasta para executar pode inviabilizar o seu uso. Portanto, vamos focalizar na estimativa de tempo de execução.

Já vimos que o mais importante é tentar avaliar o tempo de execução para grandes volumes de dados de entrada. Para isso, vamos tentar achar uma fórmula que expresse o tempo de execução em função do volume de dados de entrada.

Dependendo da fórmula encontrada, podemos classificar e comparar a complexidade de diferentes algoritmos.

Exercícios 1. Qual é a ordem de complexidade das seguintes funções (utilize a notação O).

a) f(n) = n2 + 2 b) g(n) = 503 c) g(n) = 2 log n + n d) g(n) = 10. 2n e) f(n) = n log n + log n

2. Qual dessas funções possui a maior ordem de complexidade? 3. Arranje as seguintes expressões de acordo com a taxa de crescimento (da menor

para a maior): 4n2, n!, log3n, 3n, 20n, 2, log2n.

Vejamos então algumas regras simples para se obter essa fórmula a partir de um algoritmo.

4.1.1 Regras para Análise de Algoritmos

1 – Atribuições simples, declarações, etc Analise os exemplos de comandos a seguir:

int x=1; x= (1+y); readln( ); writeln(“Digite um número”);

Podemos facilmente notar que qualquer desses comandos, a não ser que esteja dentro de um laço, será executado uma única vez. Ou seja, são comandos que não dependem do volume de dados de entrada. Portanto, dizemos que esses comandos têm ordem de complexidade constante, ou O(1).

Page 61: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 61 Curso: Informática Disciplina: Análise de Algoritmos

2 – Laços, For-to-do, while, repeat, ... O tempo de execução de um laço é, no máximo, a soma dos tempos de execução de

todas as instruções dentro do laço (incluindo todos os testes) multiplicado pelo número de iterações. Por exemplo, considere o laço a seguir:

Para encontrar a complexidade desse trecho de código, devemos inicialmente somar o tempo de execução de todas as instruções dentro do laço. Temos portanto: O(1) + O(1) = O(1+1) = O(2).

Agora multiplicamos esse valor pelo número de iterações do laço. Como o laço vai de 1 até 10, o número de iterações é 10. Portanto, temos: O(10) x O(2) = O(10x2) = O(20). Ou seja, esse trecho de código vai demorar 20 unidades de tempo para ser executado. Como o tempo é constante, isto é, independente do volume de dados de entrada, poderíamos simplificar ainda mais e dizer que a complexidade é simplesmente O(1). 3 – Laços aninhados

Devem ser analisados de dentro para fora. O tempo total de execução de uma instrução dentro de um grupo de laços aninhados é o tempo de execução da instrução multiplicado pelo produto do tamanho de todos os laços. Exemplo:

Neste caso, só temos um comando propriamente dito, que é constante e, portanto, tem ordem O(1). Esse valor corresponde ao tempo total de execução dentro do grupo de laços. Agora é necessário, portanto, multiplicá-lo pelo produto do tamanho de todos os laços.

O primeiro laço será executado n vezes e, portanto, tem tamanho n. O mesmo vale para o segundo laço, que também será executado n vezes. Portanto, temos: O(n) . O(n) = O(n . n) = O(n2) O(1) . O(n2) = O(1. n2) = O(n2) 4 – Instruções consecutivas

Simplesmente soma-se a complexidade de cada instrução, sendo que os termos de menor ordem são ignorados. Exemplo:

For (i=1;i<=10;i++) { vetor[i]=i; O(1) vetor[i+1]=x; O(1) }

For(i=1;i<n;i++) { For(j=1;j<n,j++) { k= k+1; O(1) } }

Page 62: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 62 Curso: Informática Disciplina: Análise de Algoritmos

Se calcularmos, veremos que a ordem de complexidade do primeiro laço é O(n), enquanto a ordem de complexidade do segundo laço é O(n2). Portanto, como os dois laços são consecutivos e independentes, simplesmente soma-se a complexidade de cada instrução.

Assim, a equação que descreve a complexidade desse trecho de código seria n2 +n. No entanto, como sabemos que o mais importante é o maior tempo, podemos

simplificar essa fórmula. Vimos acima, no item Propriedades, que a soma de duas complexidades é o maior valor. Portanto:

O(n) + O(n2) = O(max(n, n2)) = O(n2)

5 – If-then-else Considere o exemplo abaixo:

O tempo de execução de um comando do tipo if-then-else nunca é maior do que o tempo de execução do teste condicional em si mais o tempo de execução da maior entre as expressões 1 e 2. Assim, se a expressão1 é O(n3) e a expressão 2 é O(n), então a complexidade é O(n3) + O(n) = O(n3).

6 – Chamadas de Função

A análise segue a mesma regra de laços aninhados: analise tudo de dentro para fora. Ou seja, para calcular a complexidade de um programa com várias funções, calcule primeiramente a complexidade de cada uma das funções e depois considere cada uma das funções como uma instrução, com a complexidade da função. 7 - Recursão

Existem dois tipos de casos. No caso de algoritmos recursivos mais simples, pode-se simular uma linearização, substituindo-se a chamada recursiva por alguns laços aninhados ou por uma outra subrotina extra e eventualmente uma pilha para controlá-la. Neste caso, o cálculo é simples e pode ser feito depois da linearização. O segundo caso é com algoritmos recursivos mais complexos, quando não é possível realizar a linearização.

for(i=1;i<n;i++){ a[i] = 0; } for (i=1;i<n;i++) { for(j = 1;j<n; j++) { a[i] = a[j] + 1; } }

If condição then expressão1; Else expressão2;

Page 63: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 63 Curso: Informática Disciplina: Análise de Algoritmos

Neste caso obtemos uma relação de recorrência que tem que ser resolvida e é uma tarefa matemática menos trivial.

Vejamos então, inicialmente, um exemplo do primeiro caso, que é mais simples. Exemplo: fatorial recursivo e fatorial linearizado:

Como podemos perceber, as duas funções fazem a mesma coisa: isto é, calculam o fatorial de n. No entanto, o primeiro algoritmo o faz de forma recursiva, já o segundo o faz de forma linear, com complexidade O(n).

Exercício: analisar a complexidade assintótica dos seguintes algoritmos:

Procedure exemplo1(var a: vetor); Begin For i:= 1 to n-1 do Begin min:= i; for j:= i+1 to m do if a[j] < a[min] then min:= j; x:= a[min]; a[min]:= a[i]; a[i] = x; end; end;

Fatorial _recursivo(n); Início Se n<= 1 então retorne 1; Senão Retorne (n* fatorial_recursivo(n-1)); Fim Fatorial_linear(n); Início Fatorial 1; Para i de 2 até n Fatorial fatorial * i; Retorne fatorial; Fim

Page 64: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 64 Curso: Informática Disciplina: Análise de Algoritmos

Procedure exemplo3(var a: vetor); Begin For i:= 1 to n do Begin For j=1 to 10 do Begin min:= i; for k:= i+1 to m do if a[k] < a[min] then min:= k; x:= a[min]; a[min]:= a[i]; a[i] = x; end; end; end;

Procedure exemplo2(var a:vetor); Begin read(x); if (x<0) a[1]:= 0; else if (x<5) a[1]:= 1; else for i:= 1 to n do begin a[i]:= i+1; end; End;

Page 65: Apostila Análise de Algoritmos

Faculdade de Filosofia, Ciências e Letras de Mandaguari 65 Curso: Informática Disciplina: Análise de Algoritmos

Bibliografia Laporte, G., Asef-Vazir, A. And Sriskandarajah, C. Some applications of the generalized traveling salesman problem. JORS 47, 1996. Salomon, M., Solomon, M., van Wassenhove, L., Dumas, Y and Dauzère-Pérès, S. Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and set-up times using the traveling salesman problem with time windows. EJOR, 100, 1997. Whitley, D., Starkwheather, T. and Shaner, D. The traveling salesman and sequence scheduling: quality solutions using genetic recombinations. Handbook of Genetics Algorithms. Edt. L. Davis van Nostrand, 1991. Bodin, L., Golden, B., Assad, A. and Ball, M. Routing and Scheduling of vechicles and crews: the state of the art. Special Issue. England: Pergamon Press, 1983. Chauny, F., Haurie, A., Wagneur, E. e Loulou, R. Punch Operations in a Flexible Manufacturing Cell a Three-Dimentional Space-Filling Curve Approach. INFOR 25(1), 1987. Finke, G and Kusiak, A. Network Approach to Modeling of Flexible Manufacturing Modules and Cells. APPII – 0399-0516. Department of Applied Mathematics Technical Report. University of Nova Scotia, Nova Scotia, Canadá, 1985.

Fontes da Internet: http://www.inf.ufpr.br/~andre/Disciplinas/BSc/CI065/michel/Intro/intro.html