O caixeiro viajante é np completo

Faculdade de Ciências Humanas, Saúde, Exatas e Jurídicas de Teresina

Turma: Ciência da Computação Período: 4º - ManhãDisciplina: Projet0 e Análise de AlgoritmosDocente: Francisco José Discentes: Adson Ferrett

Igor MonteiroMarcelo KelleWhallysson Estevam

Copyright 2013.1

1 Introdução;

2 Tipos de Problema;

2.1 A Classe P de problemas;

2.2 A Classe NP de problemas;

2.2 A Classe NP-Completo de problemas;

2.2 A Classe NP-Difícil de problemas.

3 Problema do caixeiro viajante;

3.1 Algoritmos de força bruta;

3.2 Implementação.

4 O Problema do caixeiro viajante é NP-Completo;

5 Conclusão;6 Referências.

Copyright 2013.1

O problema do caixeiro viajante é um problema que tenta determinar a menor rota para percorrer uma série de cidades, retornando à cidade de origem. Ele é um problema de otimização NP-Completo inspirado na necessidade dos vendedores em realizar entregas em diversos locais percorrendo o menor caminho possível, reduzindo o tempo necessário para a viagem e os possíveis custos com transporte e combustível.

3

Nos anos de 1800, problemas relacionados com o PCV começaram a ser desenvolvidos por dois matemáticos: o escocês William Rowan Hamilton e o britânico Thomas Penyngton Kerkman. A forma geral do PCV parece ter sido, pela primeira vez, estudada por matemáticos nos anos de 1930 em Harvard e Viena. O problema foi posteriormente estudado por HasslerWhitney e Merril Flood em Princeton.

4

Para compreender o problema abordado neste trabalho, é necessário conhecer a classe de problemas NP-Completos. Para melhor compreender essa classe e também as classes P e NP, segue uma definição básica de cada uma delas.

fig 1.

5

6

2.1 A Classe P de problemas

A classe NP de problemas é o conjunto de todos os problemas de decisão para os quais existem verificadores polinomiais. Esta classe corresponde à classe dos problemas que poderíamos chamar "razoáveis".

É importante lembrar que todo problema pertencente à classe P também pertence à classe NP, uma vez que se um problema pode ser resolvido em tempo polinomial, ele pode ser igualmente verificado em tempo polinomial.

7

2.2 A Classe NP de problemas

A classe NP-Completo é o conjunto de todos os problemas completos em NP, portanto, NP-Completo é a classe dos problemas mais "difíceis" de NP.

Esta classe de problemas é alvo de longos estudos e pesquisa durante as últimas décadas, pois ela está no centro de um dos impasses mais famosos dentro da computação.

8

2.3 A Classe NP-Completo de problemas

Um problema NP-Difícil pode também estar em NP, mas não necessariamente. Os problemas contidos nesta classe são ditos ao menos tão difíceis quanto os problemas mais difíceis de NP e não é possível resolvê-los na exatidão, a menos que P = NP. Ou seja, um algoritmo polinomial que encontra a solução exata para um problema NP-Difícil implica P = NP.

9

2.4 A Classe NP-Difícil de problemas

O PCV consiste em, dado um grafo completo G(V,E), com n vértices, obter um ciclo hamiltoniano de custo mínimo, isto é, deseja-se, a partir de um vértice inicial, passar por todos os demais vértices do grafo uma única vez e então retornar ao vértice inicial. Cada aresta que liga um par de vértices do grafo possui um custo c(i, j) que determina o quanto se gasta para ir de i até j. Esse custo pode ter diversos significados, de acordo com a aplicação desejada.

10

Algoritmos de força bruta são uma forma de se encontrar a solução ótima para um problema de otimização através do teste exaustivo de todos os elementos de seu domínio. Considerando o PCV, que é o problema estudado neste trabalho, um algoritmo de força bruta consiste em testar todas as permutações possíveis entre os vértices de uma instância e escolher o ciclo hamiltoniano de menor custo.

11

3.1 Algoritmos de força bruta

12

3.2 Implementação

A seguir, o pseudocódigo que descreve a implementação feita para o algoritmo de força bruta.

Força Bruta(Ciclo[n], int pos)

1. SE pos == n

2. Calcule o custo do ciclo

3. SE custo < custo mínimo

4. ENTÃO custo mínimo = custo

5. SENÃO FAÇA

6. PARA j = pos até n

7. Troca (ciclo[], pos, j)

8. Força Bruta (ciclo[], pos + 1)

9. Troca (ciclo[], pos, j)13

3.2 Implementação

Os cálculos realizados no passo 2, com relação ao custo da instância, podem ser descritos da seguinte forma:

Custo(M[n][n], ciclo[n])

1. double custo = 0

2. PARA i = 1 até n-1

3. FAÇA custo = custo + M[ciclo[i]][ciclo[i + 1]]

4. custo = custo + M[ciclo[n]][ciclo[1]]

5. RETORNE custo.

14

3.2 Implementação

Voltando ao algoritmo principal, os passos 7 e 9 são responsáveis pela permutação de fato dos vértices no ciclo. Para isso, foi utilizado um algoritmo simples de troca de posições em um vetor.

Troca(ciclo[n], int i, int j)

1. int aux = ciclo [i]

2. ciclo[i] = ciclo [j]

3. ciclo[j] = aux

15

3.2 Implementação

Através da figura 2, pode-se observar um grafo que representa uma instância do PCV-Métrico e todas as permutações possíveis para a obtenção da solução.

fig 2.

16

3.2 Implementação

(i) Decisão do Caixeiro Viajante é NP

A exibição da justificativa SIM pode ser dada por uma sequência de vértices. A verificação da justificativa apresentada consiste em se verificar que cada vértice aparece na sequência apenas uma vez.

O(n) - percorrer a lista marcando os vértices, observando se já não foram marcados, verificar se contém todos os vértices,

O(1) - durante a marcação contar os vértices, e verificar se o peso total não ultrapassa o valor k,

O(n) - percorrer a lista somando-se os pesos das arestas,

O(1) - descobrir cada peso, se os dados estão em uma matriz de adjacência.

Como o algoritmo é polinomial, então o problema é da classe NP.

17

(ii) Decisão do Ciclo Hamiltoniano ∝ Decisão do Caixeiro Viajante

Seja um grafo G com n vértices para o qual queremos decidir se existe ou não um ciclo hamiltoniano. Construímos um grafo G’ a partir de G contendo todos os vértices se arestas de G. Atribuímos peso 1 a todas estas arestas.

fig. 3

18

Criamos todas as demais arestas não existentes em G’ com peso 2. É fácil notar que existe um ciclo em G’, que passa em todos os vértices exatamente uma vez, com peso no máximo n, se e somente se existe ciclo hamiltoniano em G, pois assim haveria um ciclo em G’ passando apenas por arestas de peso 1. Se não houver, um ciclo em G’ deverá passar por aresta de peso 2, o que ultrapassará o peso total n.

fig. 4

19

Logo, como

- Decisão do Caixeiro Viajante é NP;

- Decisão do Ciclo Hamiltoniano ∝ Decisão do Caixeiro Viajante;

- Decisão do Ciclo Hamiltoniano é NP-Completo;

então Decisão do Caixeiro Viajante é NP-Completo.

20

CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford.

Algoritmos: Teoria e Prática. 2 ed. Editora Campus, São Paulo. 2002.

FONSECA, Guilherme D. da. Problemas NP-Completo. Rio de Janeiro: Unirio, [2009]. 20

slides, color, Acompanha texto.

GRONER, Loiane. NP - COMPLETUDE. 2006. 42 f. Trabalho do curso de graduação em

Ciência da Computação – Unifesp, Vitória-ES.

MORAIS, José Luiz Machado. Problema do Caixeiro Viajante Aplicado ao Roteamento de

Veículos numa Malha Viária. 2010. 70 f. Trabalho de conclusão de curso – Unifesp, São José

dos Campos-SP.

O problema do caixeiro viajante é NP-Completo. Disponível em: <

http://homepages.dcc.ufmg.br/~nivio/cursos/pa03/tp2/tp22/tp22.html>. Acesso em: 16 mai.

2013, 22:40:00.

Problema do caixeiro viajante. Disponível em:

<http://www.mat.ufrgs.br/~portosil/caixeiro.html>. Acesso em: 17 mai. 2013, 16:30:00.

21

Faculdade de Ciências Humanas, Saúde, Exatas e Jurídicas de Teresina

Discentes: Adson Ferrett adson_sousa007@hotmail.com

Igor Monteiro kijigor@hotmail.comMarcelo Kelle marcelo_kcs@hotmail.comWhallysson Estevam avelino099@gmail.com

Copyright 2013.1