Segundo Trabalho de P. A. A.

Aluno: Mateus Conrad B. da Costa

Projeto e Análise de Algoritmos
Prof. Nívio Ziviani
Departamento de Ciência da Computação
Universidade Federal de Minas Gerais
Belo Horizonte - MG

Sumário

• Sumário
• Apresente pelo menos um exemplo prático (e não mais do que três) que possa ser modelado através dos seguintes problemas
• Problema do Caixeiro Viajante Assimétrico
• Heurística para o PCVA
• Bibliografia

Apresente pelo menos um exemplo prático (e não mais do que três) que possa ser modelado através dos seguintes problemas

1.

Ciclo de Hamilton Considere o modelo de computação paralela em anel representado por um grafo. Os vértices representam processadores. Uma aresta ligando dois vértices a,b indica que os processadores a e b podem comunicar-se entre si diretamente. Processadores não adjascentes comunicam-se entre si através de troca de mensagens. O grafo que representa este anel é um ciclo simples.
Um outro modelo de computação paralela é o n-cubo, que contem 2ⁿ processadores e apresenta um alto grau de conectividade entre os mesmos. Um questão a ser considerada é se um n-cubo com $n\geq2$ pode simular um anel com 2ⁿ processadores, que significa perguntar ser um n-cubo contém um ciclo simples de 2ⁿ processadores. Ou ainda, desde que o n-cubo possui 2ⁿ vértices, significa perguntar se este possui um ciclo de Hamilton[5].

2.

Conjunto independente de vértices

Considere o problema de identificar localizações para um novo serviço baseado em franquias. Nem um par de franquias pode ser perto o suficiente para que acabem competindo uma com a outra. Modelando este problema como um grafo onde os vértices são possíveis localizações das franquias e as arestas indicam que estas localizações são demasiadamente próximas, o conjunto independente máximo de vértices irá fornecer o número máximo de franquias que poderão ser abertas sem que haja competição ``canibalesca'' entre qualquer par de lojas[9].

3.

Clique

Um exemplo de aplicação de clique é o seu uso na detecção de fraudes em esquemas de reembolso por mal atendimento de um determinado serviço. As requisições são encaminhadas neste sentido são representadas por vértices em um grafo. As arestas são inseridas representando similaridades suspeitas entre as requisições. A detecção de um clique grande no grafo aponta fortemente para uma fraude[9].

4.

Coloração de grafos

Uma vasta quantidade de problemas de agendamento recai sobre o problema de coloração de grafos, tipicamente na tentativa de minimizar o número de turnos sem conflitos necessários para completar uma determinada tarefa. Considere por exemplo uma situação onde é necessário agendar um conjunto de entrevistas entre duas pessoas, onde cada entrevista dura 1 hora. Todos os encontros poderiam ser marcados em horários diferentes. No entanto, seria bem menos custoso proceder com entrevistas não conflitantes simultaneamente. Construindo um grafo onde os vértices representam as pessoas e as arestas os pares de pessoas que irão compor uma entrevista, a coloração das arestas do grafo representarão o agendamento. As diferentes cores representam os diferentes horários da agenda, com todos os encontros (arestas) da mesma cor acontecendo simultaneamente[9].

5.

Problema do caixeiro viajante

Embora o problema do Caixeiro viajante esteja direta e obviamente relacionado com aplicações de transporte, sua mais importante aplicação reside na otimização de seqüencias de operações de equipamentos de manufatura. Por exemplo, Considere um braço de robô cuja função é soldar todas as conexões de uma placa de circuito impresso. O menor caminho que visita cada ponto de solda exatamente uma única vez define o caminho mais eficiente para o robô[9].

6.

Satisfabilidade

Satisfabilidade Booleana é usada na construção de uma ferramenta para análise de processadores Pipeline com o intuito de verificar um conjunto de restrições de transitividade. A ferramenta abstrai a operação do caminho de dados como sendo um conjunto de funções e predicados não interpretáveis operando sobre um conjunto de dados simbólicos.
O problema consiste em validar uma fórmula F_ver em um lógica de inequalidade com funções não interpretáveis.As funções e predicados de F_ver são então traduzidos e transformados resultando em uma fórmula proposicional Encf(F_ver) que expressa as condições de restrição de F_ver. A verificação de que não há uma associação de variáveis que satisfaça $\neg Encf(F_ver)$ garante que F_ver é universalmente válida[11].

Problema do Caixeiro Viajante Assimétrico

Dados um conjunto de cidades ${c_1 \dots c_n}, \quad n\gt 1$ e uma distância d(c_i,c_j) para cada par de cidades ,encontre o "roteiro" para todas as cidades em C cujo comprimento total seja o menor possível. Este problema é conhecido na literatura como o problema do caixeiro viajante (PCV). Uma versão um pouco diferente é o problema do caixeiro viajante assimétrico (PCVA), o qual pode ser descrito como: dados um conjunto de n cidades e distâncias para cada par de cidades, encontre um roteiro de comprimento mínimo visitando cada cidade exatamente uma vez. No caso do PCVA, a distância da cidade i para a cidade j e a distância da cidade j para a cidade i podem ser diferentes.

1.

Prove que o problema é NP-completo
Primeiro deveremos provar que o ATSP é NP. Para isso vamos construir uma versão do tipo Sim/Não ( Problema de decisão ) para o problema. Segue a versão:
Dado um conjunto de cidades ${c_1,c_2,\dots,c_m}$ e uma distância d(c_i,c_j) para cada par de cidades e d(c_i,c_j) não necessariamente igual a d(c_j,c_i), existe um percurso passando por todas as cidades uma única vez , cujo comprimento total do percurso e menor que um determinado k. Provaremos que este problema é NP apresentando um algoritmo polinomial para verificar se um roteiro válido é uma solução para o problema.
Seja $S={s_1,s_2,s_3\dots s_m}$uma suposta solução para uma dada instância G(V,E) do ATSP e d[v_i,v_j] a distância entre v_i e v_j para quaisquer $v_i,v_j \in V$. O seguinte algoritmo polinomial é capaz de verificar se o conjunto S é uma solução para o problema:

Procedimento ChecaSolucao(G,S,d)

$Percurso \leftarrow0$
Para todo i de 1 ate m-1 faça

$Percurso\leftarrow Percurso+ d[s_i,s_{i+1}]$

$Percurso\leftarrow Percurso + d[s_m,s_1]$
Se Percurso < k então

S é um percurso mínimo

Senão

S não é um percurso mínimo

Fim do Procedimento

Assim fica provado que o ATSP é NP

Para provar que o problema do Caixeiro viajante assimétrico (ATS) é um problema NP-Completo vamos verificar que existe uma transformação polinomial do problema do ciclo de hamilton (HC) em um grafo direcionado, que é NP-Completo[2], para o ATS. Ou seja, devemos provar que ${\it HC} \quad \alpha \quad{\it ATS}$
Para tanto, é necessário especificar uma função f que mapeia cada instância de HC em uma instância correspondente para o ATS e verificar que esta função satisfaz as seguintes propriedades de uma transformação polinomial:

As seguintes propriedades para f devem ser satisfeitas:

(a)

A instância f(G) de uma instância qualquer G do ciclo de Hamilton tem de ser obtida em tempo polinomial por uma algoritmo determinístico;

(b)

Se X é solução para HC então f(X) é solução para o ATS;

Para definir a função f, suponha que o grafo direcionado G(V,E) com número de vértices igual a m seja uma instância de HC direcionado. A instância correspondente do ATS possui um conjunto de cidades C igual ao número de vértices de G. Para qualquer par de cidades c_i,c_j, a distância d[i,j]entre elas é definida como:

d[i,j]=

$1 \qquad se \quad e_{c_i,c_j} \in E,$
$2 \qquad se \quad e_{c_i,c_j} \notin E.$

O seguinte algoritmo implementa a função f:

Procedimento ObtemInstanciadoATS(G,G')

Para cada $v \in V$

$V' \leftarrow v$

Para cada i de 1 até m

Para cada j de 1 até m

se $(v_i,v_j) \in E$

$d[v_i,v_j] \leftarrow1$

senão se $i \neq j$

$d[v_i,v_j]\leftarrow2$

Fim procedimento

O limite B do percurso desejado para o ATS é m. Ou seja, nunca existirá um percurso na instância f(G) para o ATS com comprimento menor que m. Apara atender a segunda condição, devemos mostrar que G possui um ciclo de Hamilton se e somente se existe um percurso passando por todas as cidades tal que o comprimento total do percurso não seja maior que B. Segue a prova:
Primeiro, Suponhamos que ${v_1,v_2,v_3 \dots v_m}$ seja um ciclo Hamiltoniano para G. Então ${v_1,v_2,v_3 \dots v_m}$ será também um percurso passando por todas as cidades em f(G) que possui comprimento total igual a B=m. Dado que o custo do percurso de uma cidade a par uma cidade b quaisquer de f(G) é igual a 1 ou 2 e desde que exatamente m destas cidades são usadas para computar o comprimento total do percurso, o fato de que B=m implica que cada par de cidades visitadas (v_i,v_i+1) sucessivamente deve ter o custo $c_i \rightarrow v_{i+1}=1$. Pela definição de f(G), segue que $(v_i,v_{i+1}),\quad 1 \leq i \leq m \quad e \quad (v_m,v_1)$ são todas arestas de G e também que $(v_1,v_2,v_3 \dots v_m)$ é um ciclo hamiltoniano de G.

  

Figura: Exemplo de uma Instância do Ciclo de Hamilton

  

Figura: Instância do ATS gerada a partir de uma Instância do HC (figura 1)

2.

(a)

Implemente um algoritmo capaz de obter a solução ótima para este problema.
- Apresentação da solução
Conforme verificado no item anterior, o PCVA é um problema NP-completo o que implica que não existe um algoritmo Deterministico polinomial conhecido que forneça uma solução ótima para o mesmo. Um algoritmo que forneça uma solução ótima para este problema deve percorrer todas as possíveis soluções afim de verificar qual a solução ótima, que é um percurso de menor custo possível. Pora tanto, o algoritmo deve montar todos os possíveis caminhos a partir de uma dada cidade passando por todas as cidades uma única vez e retornando a cidade de origem, e computar seus custos. O menor custo vai sendo armazenado e comparado com o custo de cada novo percurso encontrado.
O algoritmo de busca em profundidade em grafos (Depth First Search -DFS), pode pode ser adaptado para determinar uma solução ótima do PCVA. O algoritmo DFS é um esquema de visita a todos os nós de um grafo em profundidade que visita todos os nós alcançaveis a partir de um nó inicial seguindo uma ordem de visita recursiva (em profundidade). Por exemplo, suponha uma execução do grafo da figura 2 iniciado a partir do vértice A. O DFS irá então visitar o vértice B que é adjacente a A. Antes de Visitar os demais nós Adjacentes a A, DFS irá visitar os vértices adjacentes a B e assim recursivamente até visitar todos os vértices. O procedimento DFS usa um esquema de cores para determinar quais vértices não foram visitados (BRANCO), quais já foram visitados (CINZA) e quais vertices já tiveram seu conjunto de vértices adjacentes todos visitados (PRETO). O algoritmo DFS é apresentado a seguir: - Fonte: Cormen: Introduction to Algorithms[1].

Procedimento DFS(G)

para todo $v \in V$

$Cor[u]\leftarrow BRANCO$
$Pred[u]\leftarrow nil$

para todo $u \in V$

Se $Cor[u] \neq BRANCO$

Visita(u)

Fim do Procedimento DFS
Procedimento Visita(u)

Para cada $v \in adj[u]$

Se $Cor[u] \neq BRANCO$

$Pred[v]\leftarrow u$
$Cor[v]\leftarrow CINZA$
Visita(v)

Cor[u]=PRETO

Fim do Procedimento Visita

Avaliando o comportamento do algoritmo DFS, vemos que um vértice qualquer r, pintado de preto não será mais alcançado em uma busca através de um outro vértice v da lista de adjancência de um vértice qualquer s. Assim este algoritmo vai eliminando vértices alcançaveis e sua complexidade de tempo fica = O(V+E). Para fazer com que o mesmo visite um vértice t, quantas vezes este for alcançado a partir de um vértice inicial s, passando por vértices intermediários diferentes, basta que ao término da lista de adjacências de cada vértice, estes passem a ter novamente a cor branca. Assim, se o mesmo vértice t, for adjacente a um outro vertice que não seja o seu predecessor atual, ele será novamente visitado.
Além desta alteração, é necessário fazer com que o algoritmo compute o custo do percurso construído, verifique quando um novo percurso foi concluído e compare o custo do novo percurso com o custo do menor percurso obtido até então. Além disso, para computar o percurso, uma cidade de partida é definida, dado que o percurso é um ciclo e portanto a partida poderá se dar de qualquer cidade dentro do percurso encontrado. O algoritmo é apresentado a seguir:

Procedimento PCVA(G, ci)

para todo $u \in V$

$Cor[u]\leftarrow BRANCO$
$Pred[u]\leftarrow nil$

$visitas\leftarrow 1$
$MenorRota\leftarrow \phi$
$MenorCusto\leftarrow \infty$
$rota\leftarrow \phi$
$custo\leftarrow 0$
Visita(ci)

Fim do procedimento PCVA

Procedimento Visita(u)

$cor[u]\leftarrow CINZA$
$Rota \cup u$
Para cada $v \in adj[u]$

Se $Cor[u] \neq BRANCO$

$visitas \leftarrow visitas+1$
custo=custo+peso(u,v)
$Pred[v]\leftarrow u$
Visita(v)

$Cor[u]\leftarrow BRANCO$
Se visitas = |V|

$custo\leftarrow custo+peso(u,ci)$
Se custo<menorcusto

$MenorCusto \leftarrow custo$
$MenorRota \leftarrow Rota$
$custo\leftarrow custo-peso(u,ci)$

custo=custo-peso(Pred[u],u)
$rota\leftarrow rota - {u}$
$visitas\leftarrow visitas - 1$

Fim do procedimento Visita

- Complexidade de tempo do procedimento Visita
A complexidade de tempo do algoritmo será da pela complexidade do procedimento Visita. Considerando número de rotas que serão construídas por Visita teremos a seguinte equação de recorrência:

f'(2) = 2
f'(n) = (n-1)*f'(n-1)

Resolvendo a equação teremos que f'(n) = (n-1)!.
Considerando que para a montagem de cada rota Visita realiza exatamente n atribuições para a computação do custo da rota, temos que a complexidade de Visita considerando o número de atribuições de custo é:
f(n)= n* f'(n-1). Portanto f(n)=n*(n-1)! = n!,

f(n)=O(n!)

- Implementação da solução

O algoritmo foi implementado com base no algoritmo de busca em profundidade em grafos. O programa esta composto de três partes. A saber: - main.c

/*  Projeto e análise de algoritmos
    Prof. Nívio Ziviani  \\
    Trabalho prático 2 : Implementação do
    problema do Caixeiro viajante assimétrico



- Descrição do problema
Construir um programa que forneca uma solução
ótima para o problema do Caixeiro viajante assimétrico.
Uma instância para o problema do caixeiro viajante é dada
por um conjunto de cidades C e uma função d(ci,cj) que fornece
o custo do desolocamento entre as cidades ci e cj. A definição
deste problema implica em que sempre haja uma rota ligando duas
cidades quaisquer de C. No problema do caixeiro viajante assimetrico
o custo entre Ci e cj  pode nao ser o mesmo que o entre cj e ci.
Uma solução ótima para este problema é um percurso Composto por
todas as cidades do conjunto C  um única vez cujo custo total
seja o menor possível.

- Autor: Mateus Conra Barcellos da Costa -
  DCC - UFMG - mcosta@dcc.ufmg.br
- Desenvolvido em julho de 2002
- Ultima atualização: 10/07/2002
- Linguagem/sistema: C - compilador: CGG - Linux
-  Modulos do programa: main.c module.c


 main.c - modulo principal do programa

- Objetivo do modulo: utilizar a função  {\it VisitaEmProfundidade}
para encontrar uma solução ótima para uma instância qualquer
do problema do Caixeiro Viajante assimétrico, tomando como
dados de entrada o arquivo entrada

Como utilizá-lo: o programa utiliza um makefile para
que seja compilado e executado usando o camando make.
a saida é gerada em um arquivo chamado saida

a função main abre um arquivo de entrada chamado entrada que
contem os dados de uma instância  do problema.
Os dados da instância  devem ser apresentados no seguinte formato:

n
-1 d0_1 d0_2 .. d0_n-1
d1_0 -1 d1_2  .. d1_n-1
 .
 .
 .
dn-1_0  dn-1_1 ..  -1



onde:

- dij representa o custo do desolocamento entre as cidades i e j.
 Por exemplo, dn-1_1 representa o custo do deslocamento entre a
 cidades n-1 e a cidade 1. - A diagonal principal deve ter o valor
 -1 que indica tambem sem conexão - O valor 0 indica que o custo é
 tão baixo que tende a zero

 Tempo de execução: O programa executa em tempo proporcional a n!
As maiores instâncias cujo programa conseguiu resolver foram:
12 cidades sem utilizar técnicas de Brench and Bound (podas) e
20 cidades  podando a arvore de solucoes quando o custo de um percurso
nao concluido ja atinge um valor maior que o  menor custo encontrado até
então.
Maiores informações encontram-se na documentação do
trabalho prático II

#include<stdio.h>
#include <stdlib.h>
#include  "module.h"


/* a matriz de adjacencia tem como objetivo representar
o grafo que modela a disposicao das cidades e suas ligacoes
a posicao a[i][j] contem o peso do  vertice que liga i a j.
Se for -1 (SEM_CONEX)  é que nao ha ligacao entre os vértices
(cidades) i e j. O peso representa a distância entre as cidades
i e j. Como o problema é assimétrico, ha uma diferenca entre os
pesos i,j e j,i.*/

/* definição de variaveis globais do programa */

int n=0; // numero de vertice do grafo: numero de cidades
FILE *fp;

int ma[MAX][MAX]; /* matriz de adjascencia: Guarda
os custos de deslocamentos ntre as cidades */

/* Os arranjos Cor e Pred são usado na montagem
dos percurso pela função isita que esta baseado
no algoritmo de busca em profundidade em grafos*/

int cor[MAX];
int pred[MAX];

/* Variaveis para armanzenamento de percursos
e custos dos percursos*/
int menorrota[MAX], rota[MAX];


int custo,menorcusto;

int visitas; /* Contará o numero de visitas a cidades
durante a construção de um novo percurso */

/* Função main -
Objetivo: imprimir na saida o menor custo para uma
instancia do PCVA Descrição: Le o arquivo de dados
contendo uma instancia do PCVA através da função LeMatriz
inicializa variáveis de menorcusto e menorrota e encontra
uma solução otima para a instância lida através da chamada
da função VisitaEmProfundidade */

main(){

  int i;
  /* tenta abrir o arquivo de dados:   entrada*/
  if(!(fp = fopen("entrada","r"))) {
    printf("Problemas com a abertura do  arquivo\n");
    return 0;
  }

  /* Tenta Ler a instância do problema e armazena na matriz ma*/
  n=LeMatriz(fp,ma);

  fclose(fp);
  /*verifica se houve algum problema na leitura dos dados*/
  if (n==0){
    printf("Problemas com a leitura dos dados\n");
    return 0;
  }

  /* inicializa o menorcusto com um valor alto (INF)inito */
  menorcusto=INF;
  custo=0;
  for(i=0;i<n;i++){
    rota[i]=0;
    menorrota[i]=0;
  }
  /* chama o procedimento para encontrar a
   melhor solução: menor custo */
  VisitaEmProfundidade(ma,n);
  /*imprime o menor custo*/
  printf("%d",menorcusto);
}

- module.c

/* module.c -

 Implementa as funções:
   LeMatriz, Print Matriz, Visita e VisitaEmProfundidade
   usadas na solução do
   problema do caixeiro viajante assimétrico
 Linguagem de Programação/SO/Compilador: C/Linux/GCC
 Data da última alteração: 15/07/2002
 Autor: Mateus Conrad B. da Costa
*/
#include "module.h"

extern int ma[MAX][MAX];
extern int cor[MAX];
extern int pred[MAX];
extern int menorrota[MAX];
extern int  rota[MAX];
extern int custo;
extern int menorcusto;
extern int visitas;

/* Função LeMatriz -
Objetivo: Ler os valores da matriz de adjacências
Parâmetros de entrada:
FILE *fp  -  ponteiro para um arquivo de entrada
ma[][MAX] - Arranjo bidimensional para armazenar a mtriz em memória */

int LeMatriz(FILE *fp,int ma[][MAX]) {

  int register i,j;
  int n=0;

    fscanf(fp,"%d", &n);
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
        fscanf(fp, "%d", &ma[i][j]);
   return n;
  }

/* Função PrintMatriz -
Objetivo: Imprime uma matriz quadrada na saida padrão
Parâmetros de entrada:
 ma[][MAX] - Arranjo bidimensional para armazenar a mtriz em memória
 n - dimensão da matriz */

 void PrintMatriz(int ma[][MAX], int n){
  int register i,j;
    for(i=0;i<n;i++){
      for(j=0;j<n;j++)
        printf("%3d ",ma[i][j]);
      printf("\n");
    }
 }

/*Funcao: Visita -
Objetivo: Encontra uma solução ótima para o problema do
caixeiro viajante assimétrico para um conjunto de
n cidades.

- Descrição: a funçao  visita   todas as cidades do grafo a
partir da cidade u montanto recursivamente todos os percursos
possíveis que cobrem todas as ciaddes um unica vez. Ao concluir
um novo percurso, Visita verifica se o percurso encontrado é
menor que o menor percurso encontrado até então. Em caso
afirmativo, o novo percurso é armazenado e o menor percurso
atualizado. Quando Visita termina, o menor percurso estará
armazenado na variável menorrota e o custo deste percurso
estará armazenado na variável menorcusto. Este procedimento
e uma modificação do algoritmo de busca em profundidade em
Grafos. Fonte: Cormen: An Introduction to Algorithms
Ordem de complexidade: O(n!)
Parâmetros de entrada: u - Cidade de inicio do
percurso  ma[][MAX] - Arranjo bidimensional que armazena a
matriz de adjacências entre as cidades A diagonal principal
e as posições relativas a cidades (i,j) sem conexão deverão
ter o valor -1 n - número de cidades

*/
void Visita(int u, int ma[][MAX],int n){
int v,i;
  cor[u]=CINZA; /* pinta u de cinza para evitar
                a construção de um ciclo no  percurso*/
  rota[visitas]=u; // a cidade u é incluida no percurso
  for(v=0;v<n;v++)
   if(ma[u][v]!=SEM_CONEX)
     if(cor[v]==BRANCO){ /* para todas as cidades adjacentes
                           a u e de cor branca*/
        visitas++;  /* incremento o número de cidades visitadas*/
        custo=custo+ma[u][v]; /*Contabilizo o custo da proxima visita*/
        pred[v]=u;  /* especifico quem é a cidade que entecede a próxima */
                    /*   visita*/
        Visita(v,ma,n);  /* visito a nova cidade v*/

     }

  cor[u]=BRANCO; /* se a cidade u não tiver mais nem
                    uma cidade adjacente que */
                 /*não tenha sido  visitada retorno a
                    cor dela para branco*/

/*Se nem todas as cidades foram visitada ou nao  existe
um conexao da última  cidade ate a primeira entao apago
a ultima cidade do percurso*/


   if(( visitas<n-1) ||(ma[u][0]==SEM_CONEX)){
        rota[visitas]=0;
   }

/*Se  todas as cidades foram visitada e
existe uma conexao da última cidade ate a
primeira entao contabilizo o custo da
conexao entre a ultima cidade e a primeira*/


  if (( visitas ==n-1) && (ma[u][0]!=SEM_CONEX)){
     //rota[visitas]=u;
     custo=custo+ma[u][0];

     /*Se o custo do percurso encontrado for menor que
      o menor  custo, copio a nova rota para menorrota
      e atualizo o menorcusto
     */

   if(custo<menorcusto){
      menorcusto=custo;
      memcpy(menorrota,rota,n*sizeof(int));

   }
   custo=custo-ma[u][0];
 }
 /* decremento o número de visitas e o custo
    para procurar outro percurso */
 visitas--;
 custo=custo-ma[pred[u]][u];
 }

/*Funcao: VisitaEmProfundidade
Objetivo: Inicializa os arranjos de Cores e
de predecessores para cidades e chama o procedimento
Visita para encontrar uma solução ótima para o problema
do caixeiro viajante assimétrico a partir da cidade n.
Parâmetros de entrada: bidimensional que armazena
a matriz de adjacências entre as cidades n - número de cidades

*/

void VisitaEmProfundidade(int ma[][MAX],int n){
  int register i,j,k;

   // inicializa vetores de cores e  precedentes
  for (i=0;i<n;i++){
    cor[i]=BRANCO;
    pred[i]=0;
  }
  visitas=0;
  Visita(0,ma,n); // encontrar a menor rota a partir  da cidade 0

}

- module.h

/* module.h possui as constantes utilizadas no modulo
module.c e os protótipos das funções implementadas neste modulo*/

#include<stdio.h>
#include <stdlib.h>
#define MAX 100
#define BRANCO 0 /* cores para pintura dos vertices na
construcao dos percursos */
#define CINZA  1
#define PRETO  2
#define SEM_CONEX -1  // sem conexao entre cidades
#define INF 1000000 // um valor muito grande

int LeMatriz(FILE *fp,int ma[][MAX]);

void PrintMatriz(int ma[][MAX], int n);

void Visita(int u, int ma[][MAX],int n);

void VisitaEmProfundidade(int ma[][MAX],int n);

(b)

Informe o tamanho do maior problema que você conseguiu obter a solução ótima.
O tamanho do maior problema cuja solução foi encontrada através do algoritmo apresentado sem a utilização de técnicas de podas (Branch and bound) foi com 15 cidades.
A seguir são apresentados parte dos testes realizados:

n:7
Custo da menor rota: 36
Vertices da rota:
   0    2    1    5    3    4    6
n: 8
Custo da menor rota: 33
Vertices da rota:
   0    2    1    7    3    4    5    6
n: 10
Custo da menor rota: 94
Vertices da rota:
   0    1    8    3    7    2    6    5    4    9
n:12
Custo da menor rota: 109
Vertices da rota:
   0   10    1    8    3    7    2   11    5    6
   4    9
n: 15
Custo da menor rota: 118
Vertices da rota:
   0   10   13    6    5   14    3    7    2   11
   12    1    8    4    9

(c)

Comente o resultado indicando o motivo da limitação e faca uma estimativa do tempo necessário no caso de termos uma entrada 10 vezes maior que a do maior problema que voce resolveu.
A limitação do problema vem do crescimento abrupto do tempo de execução cuja ordem de complexidade é n! onde o n representa o número de cidades. A maior instância do problema resolvida foi com 15 cidades. O programa foi executada em um computador com a seguinte configuração:

vendor_id	: GenuineIntel
model name	: Pentium III (Coppermine)
cpu MHz		: 730.976
cache size	: 256 KB
Memory          : 512Mbytes

O tempo de execução foi obtido com o uso do time, através da seguinte linha de comando:

sh -c "time ./cv " 2> ts15 &

Os tempos obtidos foram os seguintes:

real    4170m22.107s
user    2075m6.490s
sys     1m13.470s

O tempo em que o programa esteve executando é o user time, portanto foi de 2075m6.490s= 124506.49s.
Para estimar o tempo de uma instância do problema 10 vezes maior temos que:
T = n! * c
c = 124506.49/ 15!
c = 9.52121514704187 * 10^-8
Portanto, para executar uma instância 10 vezes maior teremos um tempo total igual a:

$T = 150! * c = 150! * 9.52121514704187 * 10^{-8} \quad segundos$
$T = (5.71338395644585* 10^{262}) * 9.52121514704187 * 10^{-8} \quad segundos$
$T = 5.43983578669783*10^{255} \quad segundos$
$T = 1.724960612220226* 10^{239} \quad \mbox{ bilhões} \quad de \quad anos!!$

Heurística para o PCVA

1.

Implemente uma heurística (ou aproximação) que resolva este problema eficientemente e produza ``boas'' soluções sob o ponto de vista prático.
O algoritmo de aproximação implementado é baseado no algortimo de Jonhson-McGeogh que utiliza uma heurística construtiva (Vizinho mais Próximo) para determinar um percurso inicial e depois aplica o esquema de busca local 3-Opt[12][13].
Heurísticas de busca local (Local Search) são tipicamente definidas em termos de uma estrutura de vizinhança, onde um percurso B é vizinho de uma percurso A se este pode ser obtido a partir de A através de uma perturbação ou movimento. Estes esquemas partem de uma heurística construtiva para gerar um percurso inicial e depois, repetidamente tenta procura um movimento que produza uma solução melhor. Se este é encontrado o movimento é realizado para a obtenção efetiva do melhor resultado. O processo continua até que não exista tal movimento.
A heurística 3-Opt consiste na obtenção de todos os percursos através da delição de 3 arcos e a permutação dos três caminhos resultantes.
Seguindo o algoritmo de Johnson-McGeoch foi construida uma implementação utilizanda a heurística vizinho mais próximo para construir o percurso inicial. Esta heurística foi testada iniciando a partir de cada cidade. Posteriormente foi aplicado o procedimento relativo ao 3-opt. A complexidade do vizinho mais próximo é O(N²) A complexidade de tempo do 3-Opt é O(N³) conforme Codenotti[12], onde N é o número de cidades da instância do problema. Assim, a complexidade da herística implementada é Max(O(N²),O(N³))=O(N³).
Conforme já mencionado, a implementação segue o seguinte algoritmo:

1. Obter uma percurso inicial Aplicando a Heurística do vizinho mais próximo para cada cidade, selecionando a que for de menor custo
2. Aplicar a heurística de busca local 3-Opt sobre o percurso inicial

Implementação da Heurística
A implementação da heurística é apresentada no programa hdef.c. O programa possui apenas um módulo que é apresentado a seguir: Não forama utilizadas estruturas de dados especiais, sendo que a matriz de adjacências foi implementada estaticamente.

/*
 DCC-UFMG - Doutorado em Ciência da Computação
   -Projeto e Analise de Algoritmos
   -Prof. Nívio Ziviani - 1 semestre de 2002
   - Trabalho Prático 2
   - Item: Implementação da Heurística para
    o Problema do Caixeiro Viajante Assimétrico

- Descrição do problema:
Construir um programa que forneca uma solução
aproximada da ótima (Heurística) para o problema do Caixeiro viajante
assimétrico. Uma instância para o problema do caixeiro viajante é dada
por um conjunto de cidades C e uma função d(ci,cj) que fornece
o custo do desolocamento entre as cidades ci e cj. A definição
deste problema implica em que sempre haja uma rota ligando duas
cidades quaisquer de C. No problema do caixeiro viajante assimetrico
o custo entre Ci e cj  pode nao ser o mesmo que o entre cj e ci.
Uma solução ótima para este problema é um percurso Composto por
todas as cidades do conjunto C  um única vez cujo custo total
seja o menor possível.

- Autor: Mateus Conra Barcellos da Costa -
  DCC - UFMG - mcosta@dcc.ufmg.br
- Desenvolvido em julho de 2002
- Ultima atualização: 24/07/2002
- Linguagem/sistema: C - compilador: CGG - Linux
-  Modulos do programa: hdef.c

Breve descrição da Heurística:

- Constroi um percurso inicial Utilizando uma aproximação com o vizinho mais
próximo e procurando a cidade inicial que forneça a melhor aproximação;
- Aplica-se posteriormente o algoritmo 3OPT (busca local) na tentativa de
obter um percurso "vizinho" ao caminho inicial  com custo menor.


Funcionamento do programa:
Compilação: O programa deve ser compilado utilizando o gcc:
"gcc hdef.c -o hdef"
Execucao: ./hdef
Na execução o programa solicita o nome do arquivo de entrada que contenha a
matriz de adjacências do grafo represetativo das cidades e ligações. O arquivo
deve estar no seguinte formato:
n
-1 d0_1 d0_2 .. d0_n-1
d1_0 -1 d1_2  .. d1_n-1
 .
 .
 .
dn-1_0  dn-1_1 ..  -1

onde:

- dij representa o custo do desolocamento entre as cidades i e j.
 Por exemplo, dn-1_1 representa o custo do deslocamento entre a
 cidades n-1 e a cidade 1. - A diagonal principal deve ter o valor
 -1 que indica tambem sem conexão - O valor 0 indica que o custo é
 tão baixo que tende a zero.
O resultado do programa e o custo e o percurso
encontrado pela aproximação. Este
resultado é armazenado em uma arquivo chamado sDef.
- Complexidade de Tempo: O(n^3) - n é o número de cidades
Restrição: A Heurísitca só se aplica a instâncias com n > 6 -  Este restrição
não cria nenhum impedimento dado que a heurísitca visa determinar soluções
para instâncias impossíveis de serem resolvidas pelo algoritmo da solução
ótima
*/

#include<stdio.h>
#define MAX 500  // tamanho máximo da instância do problema
#define BRANCO 0
#define CINZA  1
#define PRETO  2
#define NULL 0
#define TRUE 1
#define INF 1000000   // um valor arbitrariamente grande (INFinito)
#define FALSE 0
#define SEM_CONEX -1

int n=0; // numero de vertice do grafo: numero de cidades
FILE *fp;

int  ma[MAX][MAX]; // matriz de adjacencia
int cor[MAX];  // arranjo de cores para controle de visitação ãs cidades
//int pred[MAX];
// int td[MAX],tf[MAX];
int  menorrota[MAX], rota[MAX];
/* arranjos para armazenamento de percursos */
int custo,menorcusto;
int visitas;
int C;
/*
Função LeMatriz -  le uma matriz de n posicoes de um arquivo de entrada
Parâmetros:
FILE *fp - Um ponteiro para um arquivo,
int ma[][MAX] -  Matriz de adjacência
Valor de retorno: retorna o valor de n */
int LeMatriz(FILE *fp,int ma[][MAX]);
void PrintMatriz(int ma[][MAX], int n);
int ObtemVizMaisProx(int u, int ma[][MAX],int n);
void MontaRota(int u, int ma[][MAX],int n);
void organiza(int *r, int *c, int ma[][MAX], int n);


int LeMatriz(FILE *fp,int ma[][MAX]) {

int register i,j;
int n=0;

    fscanf(fp,"%d", &n);
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
        fscanf(fp, "%d", &ma[i][j]);
   return n;
  }

 /*Função  ImprimeMatriz - Imprime uma matriza na saida padrão
 Parâmetros:
  -int ma[][MAX] - a matriz a ser impressa
  -int n  - dimensão da matriz */
 void PrintMatriz(int ma[][MAX], int n){
  int register i,j;
    for(i=0;i<n;i++){
      for(j=0;j<n;j++)
        printf("%6d ",ma[i][j]);
      printf("\n");
    }
 }
/*Função  ObtemVizMaisProx - determina qual o vértice mais próximo
  dado um vertice de entrada u
  Parâmetros:
  - int  u - vértice de origem
  - int ma[][MAX] - matriz de adjacências
  - int n - número de cidades

  - valor de retorno: int - vértice mais próximo

*/
  int ObtemVizMaisProx(int u, int ma[][MAX],int n){
 int v,dm,vm;
   dm=INF;
    for (v=0;v<n;v++){
    /* percorre todos os adjacentes de u e verifica qual o de menor custo */
        if (ma[u][v]!=SEM_CONEX)
           if(cor[v]==BRANCO){
              if (ma[u][v]<dm){
                   vm=v;
                   dm=ma[u][v];
              }
           }
     }
        return vm;
}
/* Função MontaRota  - Implementacao da heurísitca construtiva do
vizinho mais próximo
Parâmtros:
- int u Cidade de origem do roteiro
-  int ma[][MAX] - Matriz de adjacencia
- int n - número de cidades
-Descrição: A função procura a proxima cidade da rota levando em conta
apenas o custo imediato entre a ciadade anterior e a próxima. A próxima cidade
é exatamente a menor distânte da cidade atual*/

void MontaRota(int u, int ma[][MAX],int n){

int v,i,a,b;

  if(visitas<n-1) {

   a=SEM_CONEX; // inicializo a com um valor de vértice inválido
   a=ObtemVizMaisProx(u, ma,n); /* a recebe um vértice adjacente
   a u (se existir) que é o mais próximo de u e não visitado*/
    if(a!=SEM_CONEX) { /* Se existe um vértice adjacente não visitado*/
      visitas++; /* incremento o numero de visitas*/
      rota[visitas]=a; /*adiciono a no percurso */
      cor[a]=CINZA;  /*pinto a de CINZA: Visitado!*/
      custo+=ma[u][a]; /* Contabilizo o custo*/
      MontaRota(a,ma,n); /*reinicio enquanto não completar as rotas */
   }
 }

 else{
   custo=custo+ma[rota[visitas]][C];
    /* se acbaou, somo o custo do final até a
                                         cidade inicial */
 }
}


/* Função Organiza -  Implementação do 3-opt para procurar
por um caminho melhor tomando como base um percurso inicial
Parâmetros -
-int *r - Ponteiro para o percurso  que será verificado,
pondendo ser
modificado
- int *c -  Custo que será avaliado - pode ser modificado
- ma[][MAX] - Matriz de adjacência
- int n - Número de cidades
- Descrição:  Este  esquema do 3-Opt consiste em desagregar
o percurso em três arestas indepedentes, começando da aresta
r[0],r[1] saltando para r[2],r[3] e   depois para r[4][5].
Com a desagregação desta aresta, um novo percurso precisa
é montado ligando o ínicio de uma desagregação com o fim de
outra não coincidentes.   Depois de montado o novo percurso,
o custo deste e comparado com o do   anterior.
  Se for menor, o custo anterior é substituido e o processo volta ao
  estado inicial
  Se não for menor, uma nova desagregação é testada,
  mantendo as duas primeiras e tentando com a aresta r[5][6].
  O algoritmo segue assim iterativamente, até não haverem mais novas
  alternativas. */

void Organiza(int *r, int *c, int ma[][MAX], int n){
int register i,j,k,t;
int aux, rc[MAX], novarota, cust;


novarota=FALSE;
i=0;
  memcpy(rc,r,n*sizeof(int)); /*copio a rotac inicial para o arranjo auxiliar
rc*/
  while(i<n-4){  /* este laco e controlado pelo valor de i que volta
  a valer 0 sempre que uma solução melhor é encontrada*/
    for(j=i+2;j<n-2;j++){ /*O segundo e terceiros lacos podem ser interrompidos
sempre que uma solução melhor e encontrada*/
     if (novarota)
       break;
    for(k=j+2;k<n;k++) {
       /*rearranjo ligando o inicio de um rompimento  ao fim de outro
          ligo r[i] com r[j+1]
               r[j] com r[k+1]
               r[k] com r[i+1]
       */
       cust=0;
       /* monto um  possível novo caminho */
       aux=rc[i+1];
       rc[i+1]=rc[j+1)];
       rc[j+1]=aux;
       aux=rc[j];
       rc[j]=rc[k];
       rc[k]=aux;
      /* calculo o custo do novo caminho */
       for(t=0;t<n-1;t++)
          cust+=ma[rc[t]][rc[t+1]];
       cust+=ma[rc[n-1]][rc[0]];
       /* verifico se o novo caminho é melhor*/
       if (cust< *c){/* se o rearranjo e melhor altero a rota original e
                      recomeço  o processo */

          memcpy(r,rc,n*sizeof(int));
          *c=cust;
          novarota=TRUE;

          break;
       }else{ /* se o caminho é pior, descarto voltando a melhor rota ate o
               momento */

           memcpy(rc,r,n*sizeof(int));
       }



     }
   }
   i++;
   if (novarota){ /*Se uma nova rota é encontrada recomeço com i=0 */
     i=0;
     novarota =FALSE;
    }
   }
 }

/*Função Main -  Resolve o problema do caixeiro viajante assimétrico
 utilizando o algoritmo de aproximação proposto*/
main(){

  int i;
  char s[20];

  printf("Digite o nome do arquivo de entrada: ");
  scanf("%s",s);
  if(!(fp = fopen(s,"r"))) {
    printf("Problemas com a abertura do  arquivo\n");
    return 0;
  }
  n=LeMatriz(fp,ma);
  fclose(fp);

  if (n==0){
    printf("Problemas com a leitura dos dados\n");
    return 0;
  }
   custo=0;

   menorcusto=100000;
   /* aplica a heurística do vizinho mais proximo a partir de cada cidade para
   encontrar o melhor percurso inicial*/
   for(C=0;C<n;C++){

     rota[0]=C;
     for(i=0;i<n;i++){
       rota[i]=0;
       cor[i]=BRANCO;
     }
     visitas=0;
     custo=0;
     cor[C]=CINZA;
     rota[0]=C;
       MontaRota(C,ma,n);
       if (custo<menorcusto){
          menorcusto=custo;
          memcpy(menorrota,rota,n*sizeof(int));
       }

   }

   /* Aplico a heuritica  3-Opt - sobre a solução inicial encontrada*/
   if(!(fp = fopen("sDef","w"))) {
      printf("Problemas com a abertura do  arquivo\n");
    return 0;
  }

   fprintf(fp,"\nCusto da menor rota antes de organizar: %d\n", menorcusto);
   fprintf(fp,"\nVertices da rota: antes de organizar\n");
   for(i=0;i<n;i++)
      fprintf(fp," %d ",menorrota[i]);

   /*Organiza a melhor rota obtida */

   Organiza(menorrota, &menorcusto, ma, n);
   fprintf(fp,"\nCusto da menor rota: %d\n", menorcusto);
   fprintf(fp,"\nVertices da rota:\n");
   for(i=0;i<n;i++)
      fprintf(fp, " %d ",menorrota[i]);

  fclose(fp);
 }

Conjunto de Testes Foram realizados testes utilizando as matrizes disponíveis no site TSPLIB[16]. Para a instância de teste utilizada para comparação das heurística, RBG443 com 443 cidades foi obtido como resultado um percurso de peso = 2860 que é 5.14% pior que o ótimo (2720). Nos testes também pode ser observado que o limite superior para a solução não é justo. A tabela abaixo resume a realização dos testes:

 

Instância n Ótimo Heurística Limite superior

br17.atsp 17 39 40 80.5

ftv33.atsp 33 1286 1457 3257.49

ftv53.atsp 53 6905 8462 19822.41

ft70.atsp 70 38673 41815 118717.42

ftv64.atsp 64 1839 2202 5547.73

rbg443.atsp 443 2720 2860 11958.19

A seguir são apresentados os resultados dos testes realizados.

Teste: br17.atsp.gz   - Melhor resultado: 39
Limite superior da heuristica: 80.5
Custo da menor rota antes da busca local: 56

Custo da menor rota: com a busca local: 40
Vertices da rota:
3  4  5  6  14  15  0  11  10  9  1  13  2  12  7  8  16

*******************************************************************

Teste: ftv33.atsp.gz   - Melhor resultado: 1286
Custo da menor rota antes da busca local: 1504
Limite superior da heuristica: 3257.49
Custo da menor rota com a busca local: 1457

Vertices da rota:
16  31  27  22  8  15  29  24  9  21  10  19  4  3  28  23  12  25
26  18  2  5  11  1  0  14  30  20  6  13  17  7  32


*******************************************************************

Teste: ftv53.atsp.gz   - Melhor resultado: 6905
Custo da menor rota antes da busca local: 8584
Limite superior da heuristica: 19822.41
Custo da menor rota com a busca local: 8462

Vertices da rota:
19  18  17  16  15  52  50  51  48  49  29  28  25  26  27  7  5  8  6
9  33  31  30  0  3  2  1  41  43  42  46  45  44  34  32  21  20  39 35
40  37  36  10  12  14  13  11  38  4  22  47  23  24

*******************************************************************

Teste: ft70.atsp.gz   - Melhor resultado: 38673
Custo da menor rota antes da busca local: 41815
Limite superior da heuristica: 118717.42
Custo da menor rota com a busca local: 41815

Vertices da rota:
 21  26  35  38  39  37  63  66  64  68  65  67  69  48  43  49  47  55  51
 50  18  30  15  7  13  8  11  10  9  12  3  60  59  57  44  46  45  58  27
 22  25  24  6  0  1  5  4  23  52  54  53  20  17  16  19  41  36  42  40
 32  29  28  56  33  31  62  61  34  14  2

*******************************************************************

Teste: ftv64.atsp.gz   - Melhor resultado:  1839
Custo da menor rota antes da busca local: 2202
Limite superior da heuristica:  5547.732422
Custo da menor rota com a busca local: 2202

Vertices da rota:
 30  53  31  62  52  51  24  25  63  29  32  54  28  27  26  21  48  49  22
 59  23  35  20  19  46  45  10  60  15  0  61  1  37  3  14
 47  5  7  8  40  41  9  42  11  12  43  44  36  39  6  57  58  34  56  64  38
 2  4  18  17  16  13  50  55  33

*******************************************************************

Teste: rbg443.atsp.gz  - Melhor resultado:  2720
Custo da menor rota antes da busca local: 3858
Limite superior da heuristica:  11958.195
Custo da menor rota com a busca local: 2860

Vertices da rota:
349  332  342  283  272  301  242  210  118  6  65  25  403
365  405  230  240  67  98  362  379  11  52  75  152  321  123  291
241  378 398  364  128  139  131  352  196  212  221  141  211  48
47  143  142 97 88 154  72  18  17  3  404  311  103  30  33  32
249  171  36 370  22  278 271 38  337  49  312  56  208  24  325
238  59  435 295  219  130 188  440 37 150  76  29  63  425  232  202
176  410 383  408  186 183  68  50 296 168 268  234  109  107  214
226  423 148  167 61  236  330 314  308  363 10 205 58  220  185  39
114  8  83 93  96 71  200 284  122 198  34  134 120 15 341  127  54
233  235 19  1  125 438 274  373 371  345 184  146 145 307 20  305
264  313 137  78  13 2  21 318 316  133 57  12 317  178 9 149 156
407  353  136 62  329 73  361 334  60 266  263 231  189 86 199 80 181
172  237 151  85  306 193  45 388 155  108 302  157 23  385 158 105
323  159 389  381 160  84  413 395  161 138  304 162  94 228  163 153
422 166 87  427 328  275 303  279  357 258 191  164 124  239 174  14
368 412 170 112 70  46 336  227 53  27  262 169 175  222 43  99 344
287 254  253 207  252 298 250 415  369 113  180  64 391 110  129 251
376 375 374 310 245 351  82 333 288 273  270 66  74  315 190 104 286
203 91 41 165  419 277 326 293  92 393 335 179 126  0  377 195 182
439 194 79 147  81  26 115 430  418 358  300 229 201 119  117  44
348 429 35 204 347  248 16 7  246 319  224  215 411 132 42 392  28
216 95 350 55 290  260  187 209  116 255  213 77  431  217 294 420
111  223  144 356 100 173  121 276  101 281  269 177  285 225  331
289 434 414 402  4 247 297 192 102 322  243  359 421 372 309  257
197  140 135 327  31  292 382 261 441 437  339 265  256  340 343 244
424 346 436 417 390 282  40 299 360 106  394 259  218 367  354  324
206  384 69 387 90 396  397 355 399 320 401  380  51 406  366 280
267  5 400 338 386  89 416  432 409 433 428  426 442
*******************************************************************

2.

Apresente uma análise de complexidade de tempo da sua heurística. PAra calacular a complexidade da heurística temos que determinar a complexidade das da terminação do percurso inicial que usa a função MontaRota e a posterior busca local realizada pela função Organiza.
A função MontaRota é a implementação do Vizinho mais próximo e possui complexidade O(n²)[15]. Como a função monta rota é chamada n vezes para determinar o percurso inicial temos que este passo da heuristica possui complexidade O(n³). Resta determinar a complexidade da busca local.
Na função Organiza que realiza a busca local, se desconsiderarmos a quebra do laço inicial e considerarmos o custo das trocas = O(1), (dado que este não depende do tamanho da solução), teremos a seguinte representação dos laços em organiza:

$$f(p) = \sum_{i=0}^{n-4}\sum_{j=i+2}^{n-2}\sum_{k=j+2}^{n-1}O(1)$$

$$f(p) = \sum_{i=0}^{n-4}\sum_{j=i+2}^{n-2}\sum_{k=j+2}^{n-1}1$$

$$f(p) = \sum_{i=0}^{n-4}\sum_{j=i+2}^{n-2}(n-j-3)$$

$$f(p) = \sum_{i=0}^{n-4}\biggl(\sum_{j=i+2}^{n-2}(n-3) - \sum_{j=i+2}^{n-2}j\biggl)$$

$$f(p) = \sum_{i=0}^{n-4}\biggl( (n-2-i-2)*(n-3) - \frac{(n-2-i-2+1)*(n-2+i+2)}{2}\biggl)$$

$$f(p) = \sum_{i=0}^{n-4}\biggl( (n-i-4)*(n-3) - \frac{(n-i-3)*(n+i)}{2}\biggl)$$

$$f(p) = \sum_{i=0}^{n-4}\biggl(n²-7n-in +3i+12 - \frac{(n² -i²-3n -3i)}{2}\biggl)$$

$$f(p) = \frac{1}{2}\sum_{i=0}^{n-4}\biggl(n²-7n-in +3i+12 - (n²-11n-9i+24+i²+2in)\biggl)$$

$$f(p) = \frac{1}{2}\biggl(\sum_{i=0}^{n-4}(n²-11n+24) - (9+2n)\sum_{i=0}^{n-4}i + \sum_{i=0}^{n-4}i^2\biggl)$$

$$f(p) = \frac{1}{2}\biggl( (n-3)(n²-11n+24)- \frac{(9+2n)(n-3)}{2} + \frac{(n-3)(n-2)(2n-5)}{6}\biggl)$$

$$f(p) = \frac{1}{2}\biggl(\frac{ 6(n-3)(n²-11n+24)- 3(n-3)(9+2n) +(n-3)(2n²-9n+10)}{6}\biggl)$$

$$f(p) = \frac{1}{2}\biggl(\frac{ (n-3)(8n²-81n+127)}{6}\biggl)$$

$$f(p) = \frac{1}{2}\biggl(\frac{ (8n³-81n²+127n-24n²+81*3n+127*3)}{6}\biggl)$$

$$f(p) = \frac{1}{2}\biggl(\frac{4}{3}n³ - \frac{35}{2}n² + \frac{185}{3}n +\frac{127}{2}\biggl)$$

$$f(p) = \frac{2}{3}n³ - \frac{35}{4}n² + \frac{185}{6}n +\frac{127}{4}$$

Portanto, f(p) = O(n³), é a complexidade da função Organiza.

A complexidade da Heurística fica sendo então O(h)=max(O(n³),O(n³)) = O(n³).

3.

Apresente uma análise indicando o quanto a solução heurística fornecida aproxima-se do resultado ótimo(voce pode explicar resultados encontrados na literatura ou ainda apresentar sua própria demonstração).

Conforme visto, a construção da Heurística é feita em dois passos: Aplicação do Vizinho mais próximo e do 3-Opt. Considerando a qualidade da solução do vizinho mais próximo temos para o problema do Caixeiro Viajante Simétrico que

$$NN_{pcv} \leq \frac{1}{2}*lg(N+ \frac{1}{2})*SolOtima$$

Se uma instância do PCVA for transformada em uma instância do PCV, através da modificação de custos de seus vértices, poderemos estimar a qualidade da solução para o PCVA através do PCV.
Uma possível transformação de uma instância do PCVA para o PCV pode ser feita da seguinte forma: para cada par de arestas $e(v_i, v_j), \quad e(v_j, v_i), \quad$, o menor peso é completado com o valor s_i para ficar com o valor igual ao da aresta de maior peso. Temos que $S = \sum s_i$ .
Com esta transformação temos que $NN_{pcva} \leq NN_{pcv}$ e que

$Otimo_{pcv} \leq Otimo_{pcva} + S$.

Segue também que NN_pcv leq c*Otimo_pcv e ,

$NN_{pcv} \leq c(Otimo_{pcva} + S)$.

Como $NN_{pcva} \leq NN_{pcv}$, segue que:

NN_pcva leq c(Otimo_pcva + S) e portanto,

$$NN_{pcva} \leq (\frac{1}{2}*lg(N+ \frac{1}{2}))*(Otimo_{pcva} + S)$$

A solução encontrada pela heurística será portanto sempre $\leq NN_{pcva}$. Este contudo é um limite fraco para a heurística, coforme pode ser observado nos experimentos.
A segunda parte da heurística com a busca local 3-Opt tenta melhorar esta solução mas nao a piora nunca. No entanto, Após uma busca exaustiva na literatura sobre busca local não foi possível encontrar nem prever o quanto a solução será melhorada. Inclusive, em todas as referências consultadas a demonstração da eficiência deste método é sempre apresentada empiricamente.[14][13][12]. O que podemos afirmar é que para as instâncias testadas[16], os resultados obtidos foram significativamente bons.

Bibliografia

1

CORMEN H. T,Leiserson C. E., Rivest, L. R. An Introduction to Algorithms,1990.

2

MANBER U. Introduction to Algorithms A Creative Approach, Addison-Wesley, 1989.

3

KNUTH D. E. The Art of Computer Programming, Vol1: Fundamentals Algorithms, Addison Wesley: 1997.

4

http://mathworld.wolfram.com/HarmonicNumber.html.

5

JOHNSONBAUGH R. Discrete Mathematics. Fourth Edition, Prentice Hall: New Jersey, 1997.

6

GONNET G. H. Handbook of Algorithms and Data Structures. International COmputer Science Series - Addison Wesley:1984.

7

ZIVIANI N. Projeto de Algoritmos: com implementações em C e Pascal Pioneira Thonson: São Paulo, 2002.

8

http://www.dcc.ufmg.br/ nivio/cursos/pa02/pa02apr.html.

9

http://www.cs.sunysb.edu/ algorith/files/.

10

KNUTH D. E. The Art of Computer Programming, Vol2: Sorting and Searching, Addison Wesley: 1997.

11

BRYANT R. E. MELEV M. N. Boolean Satisfiability with Transitivity Constraint. Carnegie Mellon University. School of Computer Science. Pittsburgh, PA. Junho de 2000.

12

CODENOTTI. B. MANZINI G. MARGARA L. RESTA. G. Perturbation: An Eficient Technique for the Solution of Very Large Instances of the Euclidean TSP. 1993.

13

JOHNSON D. Experimental Analysis Of Heuristics For The Atsp. Url: "http://citeseer.nj.nec.com/486122.html" 2001.

14

CIRASELLA J. at All.The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators and Tests. Procedings of Lecture Notes in COmputer Science. 2001.

15

GAREY M. R. e D. S. Johnson, Computers and Intractability: A Guide to the Theory of -Completeness W. H. Freeman, 1979.

16

http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

About this document ...

Segundo Trabalho de P. A. A.

This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 trab2.tex.

The translation was initiated by Mateus Conrad Barcellos da Costa on 9/26/2002

Footnotes

...visitado.

Conforme apontado pelo Prof. Nívio Ziviani em aula aula[].

...$T = 1.724960612220226* 10^{239} \quad \mbox{ bilhões} \quad de \quad anos!!$

Obs.: Como parâmetro para avaliar esta quantia, considere que a idade do Universo é hoje estimada em 11 bilhões de anos