grafos eulerianos-carteiro chinês

7/15/2019 grafos eulerianos-carteiro chinês

http://slidepdf.com/reader/full/grafos-eulerianos-carteiro-chines 1/50

GRAFOS EULERIANOS E OPROBLEMA DO CARTEIRO CHINÊS

(PCC)

Leandro Freitas Martins

Rennan Aquino Neri

DISCIPLINA DE OTIMIZAÇÃO



INTRODUÇÃODiversos problemas práticos são abordados em relação ao

roteamento de arcos. Dentre eles podem ser citados:

a entrega de cartas,a coleta de lixo doméstico,a fiscalização de linhas de ônibus,a inspeção de redes elétricas,Nebulização (fumacê) no combate à dengue,Limpeza das ruasPintura de linhas no centro das ruas

Patrulhamento da polícia

A redução de custos desses problemas faz com que sejamotimizadas.



OBJETIVO

•O objetivo é descrever o método de cobertura dearcos através do Problema do Carteiro Chinês (PCC),de forma a determinar uma rota de custo mínimo, paraque todos os arcos do grafo sejam percorridos aomenos uma vez.



INTRODUÇÃO

• Caminhos que usam todos os vértices outodas as arestas de um grafo sãogeralmente chamados de percursos;

• Uma grande variedade de problemas

práticos podem ser vistos como umpercurso num grafo• Eles se dividem em duas categorias:

– Problemas do tipo euleriano – Problemas do tipo hamiltoniano



INTRODUÇÃO

• Problemas do tipo euleriano: requeremque cada aresta seja percorrida pelomenos uma vez.

• Problemas do tipo hamiltoniano: requerem

que cada vértice seja percorrido pelomenos uma vez.• Exemplos clássicos de otimização: o

problema do carteiro chinês e o problemado caixeiro viajante





Caminho Euleriano

• Leonhard Euler, que foi um matemático e físico suíço,em 1736, provou que não existia caminho que possibilitassetais restrições. Euler transformou os caminhos em retas esuas intersecções em pontos criando possivelmente oprimeiro grafo da história;

• Então percebeu que só seria possível atravessar ocaminho inteiro passando uma única vez em cada ponte sehouvessem no máximo dois pontos de onde saia um

número ímpar de caminhos;

• Em 1873, Carl Hierholzer mostrou que um grafo cujo todosos vértices têm grau par é euleriano.



Grafos Eulerianos

• Um percurso euleriano é um percurso que

contém todos as arestas do grafo• Um circuito euleriano é um percurso

euleriano fechado

• Um grafo euleriano é um grafo quecontém um circuito euleriano

• Um circuito euleriano no grafo é

<u,v,t,u,w,t,z,w,x,y,z,u>

w

zu t

v

y

x



Caminho Euleriano

• Um grafo conexo G é um

Grafo Euleriano se esomente se todos os seusvértices são grau par.

Caminho Euleriano

• Baseado no grau dos vérticesdo grafo: existe um caminhoEuleriano em um grafo se:

• Existem 2 vértices de grauímpar (inicia em um vérticeímpar e termina em outrovértice ímpar)



Problemas Eulerianos

• As pontes de Königsberg: é possível fazer um percurso atravessando todas aspontes, sem repetir nenhuma?



Problemas Eulerianos

• Euler percebeu que só seria possívelatravessar o caminho inteiro passandouma única vez em cada ponte sehouvessem exatamente dois pontos de

onde saíssem um número ímpar decaminhos.



O Problema do Carteiro Chinês

• O matemático chinês Meigu Guanintroduziu o problema em 1962: – Achar o caminho fechado mais curto que

percorra todas as arestas de um grafo pelo

menos uma vez. – É o problema do carteiro que quer entregar a

correspondência numa rede de ruas e retornar ao escritório central o mais rápido possível.




• Definição: um circuito do carteiro em umgrafo G é um caminho fechado que usacada aresta de G pelo menos uma vez

• Definição: em um grafo com peso nasarestas, um circuito ótimo do carteiro é umcircuito do carteiro cujo peso total das

arestas é mínimo




• A idéia é duplicar arestas nos vértices de grauímpar, fazendo com que o grafo tenha umcircuito euleriano.

• O ponto chave do algoritmo é descobrir asarestas de caminho mais curto entre osvértices de grau ímpar




• Exemplo: achar o circuito ótimo do carteirono grafo abaixo:

ca

d

b

e f

6

3

6

7

532

g h i10 5

45 6

O grafo não tem um circuito euleriano (existem vértices de grau

ímpar), então é necessário repetir arestas no circuito.




• Solução: duplicar arestas para os vértices degrau ímpar e obter um circuito euleriano nografo

ca

d

b

e f

6

3

6

7

532

g h i

10 5

45 6



Encontre a solução para este exemplo

:



Exemplo

• Encontrar o caminho fechado de custo mínimo passando em todas as

arestas do grafo G pelo menos uma vez

• Vértices de grau ímpar: V2 e V3

• Caminho: V1-V2-V4-V3-V2-V3-V1• Custo: 5+2+3+1+1+(1) = 13

2

3

v2

v4

1v3

v1

5

1

2

3

v2

v4

1v3

v1

5

1

1





Algoritmo para achar um percurso ótimodo carteiro chinês num grafo



FIM!!



Pseudo código#include <cstdlib>

#include <iostream>

using namespace std;

struct aresta {int origem, destino, custo;

};

int main(int argc, char *argv[]){

aresta E[1000];scanf("%d%d", &nvertices, &narestas);for(int i=0; i < narestas; ++i) {

scanf("%d%d%d", &oriegemDaAresta, &destinoDaAresta,

&custoDaAresta);E[i].origem = origemDaAresta;E[i].destino = destinoDaAresta;E[i].custo = custoDaAresta;

}for (int v = 0; v < nvertices; ++v){

grauExtra[v] = 0;

}




• O algoritmo de Edmonds e Johnson usa asseguintes definições:

– Definição: um casamento em um grafo G é umsubconjunto M de arestas de G tal que nenhum

par de arestas em M tem um ponto final (vértice)em comum

x

y

v z

w

a b

c d

e f g

h

M = {a,d}, {c,b}, {e,b}, ...




• O algoritmo de Edmonds e Johnson usa asseguintes definições:

– Definição: um casamento perfeito em um grafo G éum casamento em que todo vértice de G é um

ponto final de uma das arestas de M

x

y

z

w

a b

c d

M = {a,d}, {c,b}




Entrada: Um grafo conectado G com peso nas arestasSaída: Um circuito ótimo do carteiro W

Algoritmo: Circuito Ótimo do Carteiro

Ache o conjunto S de vértices com grau ímparPara cada par de vértices u e v em S

Ache duv, o caminho mais curto entre u e v

Forme um grafo completo K com os vértices em SPara cada aresta e do grafo completo K

Atribua o peso duv para a aresta e=<u,v>

Ache um casamento perfeito M em Kcujo peso total das arestas é mínimoDuplique as arestas de G correspondentes ao casamento MConstrua um circuito euleriano W no novo grafo GW corresponde a um circuito ótimo do carteiro em G



Outros Problemas Eulerianos

• Variações do problema do carteiro chinêsaparecem em diversas aplicações:

– Coleta de lixo

– Limpeza das ruas

– Pintura de linhas no centro das ruas

– Patrulhamento da polícia



Grafos Hamiltonianos

• Definição: um caminho hamiltoniano em umgrafo G é um caminho simples que contémtodos os vértices de G.

• Definição: um ciclo hamiltoniano é um

caminho hamiltoniano fechado

• Definição: um grafo hamiltoniano é um grafoque tem um ciclo hamiltoniano

w

zu t

v

y

x




• Não existe uma regra simples (como para osgrafos eulerianos) para caracterizar um grafocomo hamiltoniano

• O problema de saber se um grafo qualquer é

hamiltoniano é NP-completo

• Um algoritmo de tempo polinomial pararesolver o problema não é conhecido




• Não existe um algoritmo que funcione paraqualquer grafo, mas: – Existem condições suficientes para um grafo ser

hamiltoniano que se aplicam a uma grande classe

de grafos – Existem algumas regras básicas que ajudam a

identificar grafos que não são hamiltonianos



Grafos Não Hamiltonianos

• As regras são baseadas na observação que umciclo hamiltoniano deve conter exatamenteduas arestas incidentes em cada vértice

• A estratégia para aplicar as regras é iniciar a

construção de um ciclo hamiltoniano emostrar que em algum ponto as regras secontradizem




• Regras para grafos não-hamiltonianos: – Se um vértice v tem grau 2, todas as arestas

incidentes em v devem fazer parte de qualquerciclo hamiltoniano

– Durante a construção, nenhum ciclo pode serformado até todos os vértices terem sido visitados

– Se durante a construção, duas arestas incidentesem um vértice v são necessárias, todas as outrasarestas incidentes podem ser apagadas




• Exemplo:

v

w

h

x

a

f

e

d

c

g

b

Regra 1

Regra 2

Regra 3




• Exemplo

a

d

v

b

e

w

c

f

x

Regra 1

Regra 3

Regra 1




• Teorema (Ore, 1960): Seja G um grafo simplesde n vértices, onde n ≥ 3, tal que deg(x) +

deg(y) ≥ n para cada par de vértices não

adjacentes x e y. Então G é hamiltoniano

y

w

u

v

x

f l




• Corolário (Dirac 1952): Seja G um grafosimples com n vértices, onde n ≥ 3, tal que

deg(v) ≥ n/2 para cada vértice v. Então G é

hamiltoniano

y

wv

x

z

f l




• Exercício: identifique se o grafo abaixo é ou

não hamiltoniano

w

zu t

v

y

x

G f H il i





não hamiltoniano

w

z

u

t

v

y

x

s

G f H il i





não hamiltoniano

w

z

u

t

v

y

x

s

O bl d C i i i j



O Problema do Caixeiro Viajante

• O problema do caixeiro viajante consiste em

minimizar o custo de um caixeiro viajante quedeseja percorrer n cidades, visitando cadacidade apenas uma vez, e retornar para casa.

w

zu

t

v

10 9

5 6

7

11

6

9

107

O P bl d C i i Vi j



O Problema do Caixeiro Viajante

• Dantzig, Fulkerson e Johnson foram os

primeiros a encontrar uma solução ótimausando 49 cidades em 1954 – Branch and Bound – Cutting planes

• Crowder e Padberg conseguiram uma soluçãoótima para o problema usando 318 cidadesem 1980 – Branch and Bound – Facet-defining inequalities

H í ti A i õ



Heurísticas e Aproximações

• Definição: uma heurística é um procedimento

que ajuda na tomada de uma decisão quandoexistem múltiplas alternativas

• Heurísticas são aplicadas quando é impossível

avaliar todas as possibilidades. É o que faz,por exemplo, o jogador de xadrez

H í ti A i õ




• Definição: um algoritmo heurístico é um

algoritmo cujos passos são guiados por umaheurística.

• Um algoritmo heurístico abdica da garantia de

achar a melhor solução, para que uma soluçãopossa ser encontrada rapidamente

• A heurística mais simples para o caixeiroviajante é a do vizinho mais próximo




• Segundo (BARR et al., 2001), MétodosHeurísticos, também chamados algoritmosaproximativos, procedimentos inexatos,

algoritmos incorretos, ou simplesmenteheurísticos são usados para identificar boassoluções aproximadas para cada problema em

menos tempo que os algoritmos exatos(quando este existir).



Heurísticas Construtivas

Heurísticas ConstrutivasAs Heurísticas de métodos construtivosiniciam, sem nenhum resultado, a solução de

um problema e constroem passo a passo umasolução viável. Apresentam algoritmosgulosos, os quais, devido a enxergaremapenas o que está mais próximo do objetivo

desejado, são também chamados dealgoritmos míopes.



Heurísticas Construtivas

• Quando se trata de solucionar o PCV, asvariações desta classe de algoritmo, que seapresentam com maior destaque, são:

• o vizinho mais próximo;• a inserção mais próxima;• a inserção mais distante;• a inserção mais barata;

• a inserção pelo maior ângulo;• o método das economias.

H í ti PCV



Heurísticas para o PCV

Entrada: um grafo completo com pesos nas arestas

Saída: uma seqüência de vértices que formam um ciclo hamiltoniano

Algoritmo: Vizinho mais próximoInicie em qualquer vértice vrótulo(v) = 0i = 0Enquanto existirem vértices não rotulados

i = i + 1Percorra a aresta de menor custo que une v a

um vértice não rotulado wrótulo(w) = iv = w





• O algoritmo do vizinho mais próximo é rápido

e fácil de implementar

• As vezes ele produz resultados muito bons,podendo inclusive achar o ótimo, como no

exemplo abaixo se iniciarmos em s

w

zu

s

v

10 9

5 6

7

11

6

9

107





• Entretanto, em geral, o algoritmo do vizinho

mais próximo pode achar ciclos hamiltonianosruins (com custo elevado)

u

vs

t

2

1

2

1

1

1000000




Aplicações do PVC



Aplicações do PVC

• Seqüenciamento de tarefas:

– Suponha n tarefas que devem ser processadasnuma única máquina

– O tempo necessário para processar a tarefa j

depois da tarefa i é cij

– Como as tarefas devem ser seqüenciadas de formaa minimizar o tempo de processamento?

– A solução é um caminho hamiltoniano de customínimo no grafo

Documents

grafos eulerianos-carteiro chinês