Projeto e Análise de Algoritmos
$2^{\b{o}}$ Trabalho Prático

Marcus Vinícius de Melo Rocha
mvrocha@dcc.ufmg.br
marcus@limiar.com.br http://www.limiar.com.br

20 de julho de 2002

.

CURSO DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
PROJETO E ANÁLISE DE ALGORITMOS
$1^{\b{o}}$ Semestre de 2002

Exemplos de problemas $NP$-completos:

a)

Ciclo de Hamilton: Em [22] o Circuito de Hamilton é usado para modelar Gray codes empregados em comunicação de dados e bancos de dados. Em [29], para modelar equações diferenciais.

b)

Conjunto independente de vértices: Assim como o problema da coloração de grafos, visto adiante, o problema do conjunto independente de vértices mode ser usado para modelar problemas de escalonamento de recursos. No caso de montagem de um quadro de horários, poderíamos ter como vértices as aulas a serem ofertadas. Para cada professor habilitado para duas ou mais disciplinas (aulas portanto). Teríamos uma aresta ligando as diferentes aulas para as quais ele está habilitado. O conjunto independente de vértices deste grafo mostraria quais aulas devem ofertadas em horários diferentes.

c)

Clique: Em [28], a construção de cliques é usada no modelamento de proteínas para a análise comparativa de sua estrutura. Neste modelamento, cada possível conformação de resíduo numa sequência de amino-ácido é representada por um vértice num grafo. Arestas são traçadas entre vértices que sejam mutuamente consistentes. As arestas recebem pesos conforme a interação atômicas entre os átomos representados pelos vértives. Cliques com melhores pesos representam combinações ótimas.

d)

Coloração de grafos: Em [10], o problema de construção de quadros de horários. é examinado sob diversos pontos de vista, a fim de analisar sua intratabilidade. Num dos exemplos, temos um conjunto de aulas de certas disciplinas, um conjunto de professores habilitados para uma ou mais disciplinas, e uma grade horária ao longo de uma semana. As aulas devem ser distribuídas de tal forma que um professor habilitado a duas ou mais disciplinas não seja alocado a mais de um horário num dado momento. Para tanto, cada aula é associada a um vértice. Para cada professor, traça-se uma aresta ligando as aulas das disciplinas para as quais está habilitado. Encontra-se, então, o menor valor $k$ capaz de colorir este grafo. Cada cor será atribuida a um horário na grade semanal. Este problema pode ser extendido para considerar as restrições dos estudantes, e não apenas as dos professores, impedindo, assim, que um estudante necessite estar presente em mais de um horário, num dado momento.

e)

Caixeiro Viajante - TSP: Conforme [26], uma aplicação clássica do TSP é a definição da roteamento de operação de equipamentos industriais. No caso citado, tem-se uma placa de circuito impresso, e um conjunto de furos a executar. Cada furo é associado a um dos vértices do TSP, e a distância entre dois furos é usada como o custo da aresta correspondente. O objetivo em questão é encontrar a rota de menor custo, reduzindo-se, assim, o tempo e o custo de fabricação. Outra aplicação pode ser vista em [26] e em [15]. Estas referências mostram o uso do TSP para estudos de sequenciamento genético.

f)

Satisfabilidade: Muitas das aplicações práticas da satisfabilidade estão associada à análise de expressões e circuitos lógicos, engenharia $VLSI$, otimização de consultas em bancos de dados, modelamento de circuitos, para citar apenas algumas. Uma lista bastante extensa pode ser encontrada em [17].

.

Problema do Caixeiro Viajente Assimétrico - PCVA:

Dados um conjunto de cidades $C=\{c_1,c_2,\dots,c_n\}$, e distância $d(ci,cj)$ para cada par de cidades $c_i,c_j \in C$ ($(d_j,d_j)$ pode ser diferente de $(d_j,d_j)$), encontre o ``roteiro'' para todas as cidades em $C$ cujo comprimento total seja o menor possível.

Prova de que PCVA é $NP$-Completo

.

A prova de que o PCV é $NP$-completo pode ser encontrada em [13] e [9]. Em [19] é apresentada a prova para o PCVA, similar às duas anteriores. A seguir, mostramos a prova.

1 - PCVA como problema sim/não:

Na primeira etapa da prova, transformamos o problema PCVA num problema sim/não. Para tanto, basta alterar sua formulação para: ``Dado um valor $k$, existe rota com custo menor ou igual a $k$?''

2 - PCVA como problema $NP$:

Na segunda etapa da prova, apresentamos um algoritmo não-determinístico capaz de resolver o problema em tempo polinomial.

   INT r[N], i;
   i= 1;
   r[i]= escolhe(r,0);
   SE falha() ENTAO ABORTAR;
   PARA (i=2; i<=N; i++)
     r[i]= escolhe(r,i);
     SE falha() ENTAO ABORTAR;
   FIM;

A rotina escolhe seleciona a próxima cidade do caminho. Ela recebe, como parâmetro, a lista de cidades já selecionadas ((r,0) ou (r,i)). Sendo a complexidade de escolhe $O(1)$, a complexidade total do algoritmo é $O(N)$ (polinomial, portanto).

3 - Um problema $NP$-Completo que pode ser reduzido ao PCVA:

Para completar a prova, mostramos como transformar o problema do Ciclo de Hamilton - CH - num grafo dirigido ao PCVA, e como transformar uma solução do PCVA numa solução do Ciclo de Hamilton (ambas as transformações feitas em tempo polinomial). Para tanto, seja o grafo $G=(V,E)$ um grafo dirigido, no qual se deseja encontrar um Circuito de Hamilton. Este grafo é transformado no grafo dirigido e completo $G'=(V,E')$, onde cada aresta existente no grafo original recebe peso $1$, e cada aresta acrescentada recebe peso $2$. Mais formalmente $G'=(E',V), E'=\{\langle i,j \rangle \vert i\neq j\}$ e $c(i,j)=1$ se $\langle i,j \rangle \in E;$ $c(i,j)=2$ se $\langle i,j \rangle \not \in E$.

Esta transformacão pode ser feita em tempo polinomial ($O(n^2)$) de uma forma similar ao que mostramos a seguir:

   PARA "cada vertice v de G"
     PARA "cada vertice u adjacente a v"
       SE "nao existe aresta (u,v)"
         ENTAO "Criar aresta (u,v) com peso 2"
       SE "existe aresta (u,v) sem peso atribuido"
         ENTAO "Atribuir peso 2 para a aresta"

Agora, um ciclo em $G'$ que passe por todos os $\vert V\vert$ vértices deve custar, pelo menos $\vert V\vert$. Se incluir alguma aresta de custo $2$, seu custo será maior que $\vert V\vert$. Por outro lado, um ciclo que inclua menos que $\vert V\vert$ arestas não será solução para o PCVA. Finalizando, uma solução para o PCVA selecionará necessariamente, um conjunto arestas do problema original que passará por todos os vértices de $G$, e será uma solução para o problema do Circuito de Hamilton original. Esta transformação da solução do PCVA de volta para uma solução de CH, é bastante imediata, e pode ser efetuada em tempo polinomial.

Com isto, fica demonstrado que CH $\propto$ PCVA, e que, portanto, o PCVA é um problema $NP$-completo.

.

Algoritmo exato para o PCVA:

Proposição - Implementar e analisar um algoritmo exato para a solução do PCVA.

Backtrack:

Foi implementado um algoritmo para a solução exata do problema do Caixeiro Viajante Assimétrico. Este algoritmo usou a técnica tradicional de backtrack. Foram implementadas duas versões do algoritmo. A primeira sem poda da árvore correspondente ao espaço de solução do problema. Na segunda versão foi implementado um critério simples para a poda. Note-se que a poda não reduz a exatidão do algoritmo, de vez que somente elimina trechos que, garantidamente, não levam à solução do problema.

A técnica de backtrack é derivada do algoritmo de busca em profundidade. Este algoritmo pode ser encontrado na literatura (ver [9] e [19]) sob o nome de DEPTH FIRST SEARCH - DFS. É tradicionalmente empregada para busca exaustiva no espaço de solução de problemas $NP-$completos. Ainda, segundo [19], tanto a busca em profundidade (DFS), quanto a busca em largura (BREADTH FIRST SEARCH - BFS) são casos particulares dos algoritmos conhecidos como BRANCH AND BOUND, e podem ser usadas neste tipo de pesquisa.

Resultados:

Os experimentos com o algoritmo foram efetuados num notebook Compaq Armada M700, de 400MHz, sob MsWindows, com o ambiente de desenvolvimento CygWin[11] e compilador gcc. Foi feita uma medição de tempo simplificada, baseada no tempo de execução decorrido. Embora este critério de medição seja tipicamente impreciso, especialmente se o equipamento não está dedicado à medição, foram efetuados testes que se prolongaram por vários dias, com resultados que caracterizaram de forma muito clara e inequívoca o comportamento de algoritmos exatos com busca exaustiva, quando empregados na solução de problemas $NP$-completos.

Para permitir testes com programas de diversas dimensões, foi criado um gerador de entradas de dados. Este gerador recebe um número de vértices $N$, e gera uma matriz de adjacências $N$ x $N$, preenchida com valores aleatórios.

A tabela 1 apresenta um sumário dos resultados, que podem ser vistos graficamente na figura 1. Note-se que a escala do gráfico é logarítmica, e não linear.

Table 1: Tempo de execução para busca exaustiva no PCVA

Vértices	Com poda	Sem poda
10	0	6
11	0	76
12	0	851
13	0	11240
14	1	152689
15	10
16	7
17	79
18	184
19	3586
20	766
21	1700
22	6758
23	122580

.

Estes resultados mostram, de maneira clara e inequívoca, as limitações da busca exaustiva na tentativa de solução de problemas $NP$-completos. O crescimento do tempo é exponencial, com relação à dimensão da entrada (o número de vértices, no caso). Mesmo com a poda dos ramos improdutivos da árvore de soluções, o ganho é muito pequeno. A capacidade de resolver problemas PCVA passou de 14 para 23 vértices. É um ganho enganosamente significativo, irrelevante com relação à possibilidade de resolver problemas do munto real, uma vez que, conforme se pode ver na figura 1, o crescimento do tempo continua exponencial, apesar de irregular, mesmo com a poda.

Figure 1: Tempo de execução para busca exaustiva no PCVA

Aproximação do tempo de execução para problemas arbitrariamente grandes:

Vamos, agora, estabelecer aproximações para estimar o tempo de execução dos algoritmos com e sem poda, para entradas com número arbitrário de vértices. Uma comparação entre os valores medidos e os estimados pode ser encontrada na tabela 3.3 e na figura 2. Neste gráfico fica fácil; perceber que a estimativa feita é otimista, embora ainda exponencial. Se considerarmos apenas o resultado dos experimentos sem poda, poderemos calcular, de forma aproximada e otimista, o tempo de execução do algoritmo como sendo: $T(n)= \epsilon + 10^{n-10}, n>=10$. Neste caso, se considerarmos $\epsilon = 0$, teremos, para 140 vértices, o seguinte tempo:

Table 2: Comparação entre tempo medido e estimado

Vértices	Com poda	Sem poda	Estimado com poda	Estimado sem poda
10	0	6		1
11	0	76		10
12	0	851		100
13	0	11240		1000
14	1	152689	1	10000
15	10		2
16	7		4
17	79		8
18	184		16
19	3586		32
20	766		64
21	1700		128
22	6758		256
23	122580		512

$$\begin{eqnarray*} T(n) &=& \epsilon + 10^{n-10}, n>=10, \epsilon=0\\ T(140) &=& 10^{140-10}\\ T(140) &=& 10^{130} segundos \end{eqnarray*}$$

.

Trata-se, portanto, de um número totalmente intratável de milênios, mesmo de para um problema de dimensões relativamente restritas. Se considerarmos os resultados com poda, poderemos supor, de forma otimista, que: $T(n)= 2^{n-14}, n>=14$. Sendo o maior problema resolvido com poda o de um grafo com $23$ vértices, teremos o seguinte tempo para 230 vértices:

$$\begin{eqnarray*} T(n) &=& 2^{n-14}, n>=14\\ T(230) &=& 2^{230-14}\\ &=& 2^{216}\\ &=& 16^{212}\\ T(230) &<& 10^{212} segundos \end{eqnarray*}$$

O tempo permanece intratável. Mesmo se considerarmos que o tempo real de execução seja três ordens de grandeza inferior ao tempo decorrido, e considerarmos que um milênio tem da ordem de $10^{11}$ segundos, o problema aida requer acima de $10^{190}$ milênios para ser resolvido no computador empregado nos experimentos.

Figure 2: Comparação entre tempo medido e estimado

Heurísticas para o PCVA:

O Problema do Caixeiro Viajante tem sido mais largamente estudado que o PCVA, segundo [6]. De fato, podemos encontrar diversas heurísticas, com limites inferiores de qualidade e tempo de execução satisfatórios e bem definidos em [13]. O mesmo não ocorre com o caso assimétrico, que ainda é objeto de estudos recentes, tais como [31], [32], [6] e [21].

A escolha da heurística

Antes de iniciarmos a implementação de nossa heurística, foi feita uma ampla pesquisa na literatura. Nesta pesquisa, foram de grande valia sites como [16], [8], [1] e [23], que permitiram localizar um grande número de referências e material de pesquisa. Dado o tempo exíguo para a implementação e execução de experimentos, buscamos um tipo de heurística que fosse promissora, mas não necessáriamente a melhor dentre todas, e cuja implementação não se tornasse uma tarefa desnecessariamente complexa, e com o requesito adicional de ser passível de avaliação teórica. Uma primeira sugestão de heurística foi colhida em [3], que mostra a idéia geral de um algoritmo de busca local por troca de arestas. Uma idéia atrativa, mas orientada ao PCV simétrico, que necessitava adaptação ao caso do PCVA, e sem nenhuma análise teórica apresentada. Em [6], [31], [32], encontramos fererências sobre diversas técicas de otimização empregdas para o PCVA, mas nehnuma delas com análise teórica que indicasse limites fortes de melhor ou pior caso. Em [2] é feita uma revisão de métodos de pesquisa em visinhanças amplas, mas a comparação também se baseia em resultados computacionais. Alguma análise teórica pode ser encontrada em [25], porém limitada a classes bastante específicas de heurísticas. Já em [7], encontramos alguns limites para algoritmos de aproximação $k$-opt, uma generalização do algoritmo sugerido em [3]. Feita esta pesquisa, concluímos que seria muito difícil encontar uma análise teórica ampla sobre limites superiores e inferiores das aproximações do PCVA. Nos concentramos, então, em selecionar uma heurística que permitisse uma implementação ágil, e com resultados promissores. Segundo nosso conhecimento empírico, estratégias de busca local atendem a estes requisitos. Conforme idéias colhidas em [6], [31], [32] e [3], optamos por usar busca local¹ por troca de arestas, e usamos a técnica do Vizinho Mais Próximo, conhecida como $NN$ (Nearest Neighbor), para gerar uma solução de partida. O método de busca local por troca de arestas também é conhecido como $k$-opt. Em nosso programa, usamos $NN$ para gerar a solução de partida, e usamos $3$-opt e $4$-opt reiteradamente: $3$-opt (troca de arestas 3 a 3) para um primeiro nível de otimização, $4$-opt quando a técnica $3$-opt se esgota, e retorno ao $3$-opt quando $4$-opt se esgota.

Análise da complexidade:

Numa análise superficial, o algoritmo $NN$ é $O(n^2),$3$-opt$ é $O(n^3)$ e $4$-opt é $O(n^4)$. Portanto, em princípio, nossa heurística é $O(n^4)$. Vamos examinar trechos relevantes do código de cada uma das três heurísticas empregadas isoladamente e, então, avaliar a complexidade do programa como um todo:

#define K_MAX_ADJ 500
typedef char T_NomeExp  [256];
typedef char T_DescrExp [256];
typedef int  T_MADJ     [K_MAX_ADJ+1][K_MAX_ADJ+1];

int N;                     // Nro de vertices
T_MADJ MADJ;               // Matriz de adjacências
int minC;                  // O menor custo ja encontrado para uma rota
int marca   [K_MAX_ADJ+1]; // Para controlar o caminhamento do NN
int rota    [K_MAX_ADJ+1]; // Para registrar a rota em otimizaçao
int agora;                 // Profundidade atual do NN

void NN(int v) {
  int c, i, j, cf, melhor, onde;
  c= 0;              // Ainda sem custo
  agora= 0;          // O primeiro na rota
  rota[++agora]= v;
  marca[v]= 1;       // Já foi visitado

  onde= v;
  for (i=1; i<N; i++) {   
    cf= MAXINT;
    melhor= 0;
    for (j=1; j<=N; j++) {       // Varrer cada filho
      if (j != onde) {
        if (!marca[j]) {         // Apenas os ainda não visitados
          if (MADJ[onde][j] < cf) { // Escolher o mais economico
            cf= MADJ[onde][j]; melhor= j;
          }
        }
      }
    }
    onde= melhor; marca[onde]= 1; rota [++agora]= onde; c+= cf;
  }
  minC= c + MADJ[onde][v];    // Fechar o ciclo
}

O grafo é representado por uma matriz de adjacências. Neste trecho de código, temos um for externo que varre cada um dos vértices, e um interno que varre cada um dos adjacentes ao vértice selecionado na varredura externa. Como o grafo é completo, cada vértice tem $N-1$ adjacentes. Portanto, considerando que a complexidade do trecho interno ao for mais interno é $O(1)$ (independente de $N$), temos:

$$\begin{eqnarray*} T(N) &=& \sum_{i=1}^{N}{\sum_{j=1}^{N-1}{1}} = \sum_{i=1}^{N}{(N-1)} = N^2-N\\ T(N) &=& O(N^2) \end{eqnarray*}$$

Passamos, agora, ao algoritmo $3$-opt:

int BuscaLocal_3_opt() {
  int melhora, algumaMelhora;
  int maxo1, maxo2, maxo3;
  int o1, d1, o2, d2, o3, d3;

  algumaMelhora= 0; melhora= 1;  
  maxo1= N-5; maxo2= N-3; maxo3= N-1;
  while (melhora) {
    melhora= 0;
    for (o1=1; o1<=maxo1; o1++) {
      d1= o1+1;
      for (o2=d1+1; o2<=maxo2; o2++) {
        d2= o2+1;
        for (o3=d2+1; o3<=maxo3; o3++) {
          d3= o3+1;
          if (Trocar3Arestas(o1,d1,o2,d2,o3,d3)) {
            algumaMelhora= 1;
          }
        }
      }
    }
  }
  return (algumaMelhora);
}

Para simplificar a análise, vamos considerar que o custo de Trocar3Arestas é $O(1)$ (independente de $N$) e $N > 5$. Certamente, a implementação de Trocar3Arestas é um ponto crítico no desempenho global da heurística mas, a menos que sua implementação seja totalmente descuidada e patológica, não alterará a ordem de complexidade do algoritmo, e será constante, ou ao menos aproximadamente constante, para quaisquer três arestas trocadas, independente de $N$:

$$\begin{eqnarray*} T(N) &=& \sum_{i=1}^{N-5}{\sum_{j=i+2}^{N-3}{\sum_{k=j+2}^{N-... ... O(N^3) - O(N^2) + O(N) - O(1) \\ T(N) &=& O(N^3), N>10 \end{eqnarray*}$$

Esta análise confirma que a complexidade é $O(N^3)$. Se considerarmos que a complexidade do problema original é exponencial, podemos perceber que a heurística tem potencial para encontrar soluções em tempo viável, e com desempenho comparado ao de outras heurísticas, conforme vemos em [31] e em [6].

Passamos, agora, ao algoritmo $4$-opt:

int BuscaLocal_4_opt() {
  int melhora, algumaMelhora;
  int maxo1, maxo2, maxo3, maxo4;
  int o1, d1, o2, d2, o3, d3, o4, d4;
  int trocaFeita;

  maxo1= N-7; maxo2= N-5; maxo3= N-3; maxo4= N-1;
  algumaMelhora= 0; melhora= 1;
  while (melhora) {
    melhora= 0;
    for (o1=1; o1<=maxo1; o1++) {
      d1 = o1+1;
      for (o2=d1+1; o2<=maxo2; o2++) {
        d2 = o2+1;
        for (o3=d2+1; o3<=maxo3; o3++) {
          d3 = o3+1;
          for (o4=d3+1; o4<=maxo4; o4++) {
            d4 = o4+1;
            if (Trocar4Arestas(o1,d1,o2,d2,o3,d3,o4,d4)) {
              algumaMelhora= 1;
            }
          }
        }
      }
    }
  }
  return(algumaMelhora);
}

A análise deste algoritmo é similar à anterior, e não será efetuada em detalhe, mas feita por analogia com a anáside de $3$-opt. Assim como em $3$-opt, vamos considerar que a chamada à rotina Trocar4Arestas(o1,d1,o2,d2,o3,d3,o4,d4) tem custo constante para quaisquer que sejam as arestas trocadas², e que $N > 7$. Feitas estas considerações, é fácil perceber que $4$-opt tem complexidade $O(N^4)$. Os três for externos de $4$-opt são exatamente os mesmos três de $3$opt. O que temos de novo é um for interno que varre a matriz de adjacências, em busca da quarta aresta a trocar. Ou, vendo de outra forma, temos o $3$-opt envolvido por um for externo, que repete os três for internos, de complexidade $O(N^3)$, $N-7$ vezes, com uma complexidade total $O(N^4)$.

Análise de complexidade global:

Para analisar a complexidade do programa como um todo, vamos examinar seu módulo de controle do programa, que faz uso de $NN$, $3$-opt e de $4$-opt para buscar uma solução aceitável para o PCVA.

  int j, melhora, melhora3, melhora4, vez3, vez4;
  int savRota    [K_MAX_ADJ+1]; // Para registrar a rota em otimização
  int savC, i;

//Inicializacao de NN
  for (j=1; j<=N; j++) marca[j]= 0;
  minC= MAXINT; 

//Gera a solucao NN originada em cada vertice do grafo, e
//  fica com a melhor para dar partid na otimizacao
  NN(1);                  
  for (i=2; i<=N; i++) { 
    savC= minC;
    for (j=1; j<=N; j++) marca[j]= 0;
    minC= MAXINT;
    NN(i);
    if ("MELHOR QUE ANTERIOR") {
      "SUBSTITUI ANTERIOR PELA ATUAL";
    }
  }

//Otimiza com 3_opt e 4_opt enquanto for possivel
  melhora= 1;
  while (melhora) {
    melhora= BuscaLocal_3_opt();
    if (!melhora) {
      melhora= BuscaLocal_4_opt();
      if (melhora) {
        melhora= BuscaLocal_3_opt();
      }
    }
  }
  return (minC);
}

Neste módulo, fazemos o acionamento das rotinas heurísticas. A complexidade da criação da solução de partida é $O(N^3)$. Isto ocorre porque ativamos $N$ vezes a rotina $NN$, que é de compexidade $O(N^2)$, com a finalidade de obter a melhor rota de partida. O custo deste processo certamente não é desprezível, mas a escolha de uma solução de partida adequada pode afetar muito fortemente o andamento de um algoritmo de busca local. De fato, nossos experimentos mostraram que, pelo menos em alguns casos, esta opção foi vantajosa, e permitiu encontrar uma solução ótima. Apesar disto, alguns autores, como [4] consideram que o uso de algoritmos mais robustos torna o aprimoramento da solução de partida pouco importante. É importante notar que fazemos uso reiterado das heurísticas $3$-opt e $4$-opt. Em nossos experimentos, este uso permitiu avançar o processo de otimização em situações que, de outra forma, teriam chegado a um máximo local e levado ao término do processo. A questão que surge é a de analizar o desempenho do algoritmo global, dado que o processo de iteração poderia, pelo menos hipoteticamente, se prolongar por um tempo indeterminado, uma vez que o espaço de pesquisa é exponencial. O algoritmo poderia permanecer caminhando lentamente pelo espaçco de pesquisa, evoluindo muito pouco a cada passo, levando a um tempo excessivo de processamento. Esta situação parece pouco provável porque, $3$-opt e $4$-opt são algoritmos de busca local. A tendência é atingir rápidamente um ótimo local e terminar a pesquisa neste ponto. De fato, uma das dificuldades com a busca local e algoritmos similares é impedir que isto ocorra [24]. Também é importante notar que nossa heurística opera numa estratégia de hill climbing. Ela nunca abre mão de uma solução melhor em favor de outra pior. Portanto, ainda que camhinhe lentamente no espaço de soluções do PCVA, o caminhamento terminará, no pior caso, quando o custo da rota em otimização chegar a 0. Por mais que este caminhamento possa ser lento, será polinomial, e nunca exponencial. De qualquer forma, uma solução simplista para este problema é a de limitar o número de iterações entre heurísticas, o que garante tempo polinomial para a execução do programa. No entanto ae expectativa, confirmada pelos experimentos, é que o número de iterações é muito reduzido. Segundo a literatura consultada [6] este tipo de iteração é usado frequentemente, justamente por apresentar um resultado mais efetivo. Também é importante notar que, frequentemente, algoritmos de busca local, e outros algoritmos que tendem a localizar e se limitar a ótimos locais, usam algum fator aleatório a fim de buscar uma visitação mais ampla do espaço de soluções. Esta abordagem foi evitada, como forma de simplificar a análise da complexidade do algoritmo. Uma forma simples de introduzir um fator aleatório seria sortear o vértice de partida para o algoritmo $NN$, em lugar de buscar a melhor rota $NN$ possível. Foram feitos experimentos com a heurística $5$-opt, para a troca de 5 arestas. No entanto, a complexidade da heurística, $O(N^5)$ inviabilizou completamente o prosseguimento dos experimentos. Também foram feitos experimentos alterando a ordem da aplicação das heurísticas $3$-opt e $4$-opt, sem ganhos detectados. Em conclusão, a ordem de complexidade do algoritmo é, em virtude da heurística $4$-opt, $O(N^4)$.

A melhor rota encontrada - Ótima!:

A melhor rota encontrada tem custo $2720$. Segundo documentado na TSPLIB [30], esta rota é ótima . A rota é mostrada a seguir. Se inicia no canto superior esquerdo e segue para direita. Cada linha continua na linha de baixo. O primeiro vértice é repetido no final da rota.

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

Análise de aproximação da heurística:

Em [24], encontramos a seguinte definição para heurística:

Heuristics are criteria, methods, or principles for deciding which among several alternative courses of action promises to be the most effective in order to achieve some goal. They represent compromisses between two requirements: the need to make such criteria simple and, at the same time, the desire to see them distcriminate correctly between good and bad choices.

É exatamente o caso das heurísticas implementadas. É necessário limitar a visinhança percorrida pela busca local $3$-opt e $4$- opt, a fim de evitar uma solução por demais complexa e custosa. Um experimento em particular, dentre os realizados, mostra que a definição de uma vizinhança mais ampla pode permitir a obtenção de uma solução ótima, ao custo de um tempo de processamento excessivamente longo³. Também em [24], vemos que as técnicas mais gerais para avaliação de qualidade de heurísticas são em geral, probabilísticas. Tal observação corrobora o que se verifica com relação ao PCV. No caso simétrico, em que os algoritmos tiram partido da estrutura e de peculiaridades do problema, é possível estabelecer limites teóricos bastante satisfatórios para heurísticas. O pricipal exemplo é a heurística de Cristofides para o PCV simétrico com a desigualdade triangular, que, conforme [13], garante uma aproximação de, no mínimo $3/2$ do ótimo. O mesmo não ocorre com relação ao PCVA, onde os resultados teóricos são mais frágeis, e os trabalhos de avaliação de heurísticas mais detalhados se baseiam em resultados empíricos. Em [6] e [21] temos uma comparação cuidadosa de diversas técnicas heurísticas frequentemente aplicadas ao PCVA. Em [12], avalia-se o uso do problema do assinalamento⁴ como limite superior para o PCVA. Em [6], [21] e [20], defende-se o uso do limite inferior Held-Karp⁵. Este tipo de avaliação não foi efetuado, porque exige o cálculo do limite para cada instância específica do problema. No caso de [12], é necessário resolver o problema do assinalamento (em tempo $O(N^3)$), para calcular o limite inferior do PCVA. No caso de [6], [21] e [20], é necessário converter o PCVA numa instância de PCV simétrico para, então, calcular o limite. Em [7], avaliam-se limites para heurísticas $k$-opt. Em síntese, o autor mostra que:

• No caso do PCV simétrico, $2$-opt garante obter uma rota que será, pelo menos, a média de todas as rotas possíveis.
• Em grafos que satisfaçam a desigualdade triangular, o pior caso pode chegar a $\frac{1}{4}n^{\frac{1}{2k}}$.
• Em casos mais gerais, o pior caso pode chegar a $O(\log{n})$.

Por fim, observamos que usamos as heurísticas $3$-opt e $4$-opt para melhorar o resultado da heurística $NN$ inicial. Portanto, não é possível um pior caso pior que o de $NN$. Segundo [13], o pior caso de $NN$ é ordem $O(\log{n})$, quando exista a desigualde triangular.

Resultados experimentais:

Foram efetuados diversos experimentos, com o objetivo de avaliar empiricamente a qualidade das soluções obtidas pelas heurísticas implementadas. Tanto aqui, quanto na medição anterior efetuada para o algoritmo exato (ver a seção 3), as medições de tempo se basearam no tempo decorrido para a obtenção de soluções, e não no tempo real de processamento. Conforme comentado anteriormente, esta abordagem, embora imprecisa, não prejudicou o objetivo de mostrar, na prática, a explosão exponencial; enquanto os tempos de execução das heurísticas, exceto em casos especialmente planejados, foram da ordem de segundos ou minutos, mesmo para casos de até 443 vértices extraídos da TSPLIB [30], o tempo de execução do algoritmo exato para problemas similares é simplesmente intratável. Na tabela 3 e nos gráficos 3 e 4 temos a síntese dos experimentos com problemas presentes na TSPLIB. Na tabela 3 apresentamos o nome do problema alvo, o número de vértices, o custo da rota ótima, o custo da melhor rota obtida pela heurística, o percentual da distância entre o resultado da heurística e o ótimo, o tempo decorrido do experimento, o pior caso para o algoritmo $NN$, o pior caso calculado segundo [7], e a aproximação obtida pela heurística (Custo Heurística/Custo Ótimo). O gráfico 3 apresenta a comparação entre a solução ótima e a heurística. O gráfico 4 apresenta uma comparação entre o pior caso $NN$, o pior caso [7], e a aproximação obtida pela heurística. Na tabela 4 e nos gráficos 5 e 6 temos a sítese dos experimentos com problemas aleatórios, gerados para teste, e que também foram usados na avaliação do algoritmo exato. Na tabela 4 apresentamos o número de vértices, o custo da rota ótima, o custo da melhor rota obtida pela heurística, o percentual da distância entre o resultado da heurística e o ótimo, o pior caso para o algoritmo $NN$, o pior caso calculado segundo [7], e a aproximação obtida pela heurística (Custo Heurística/Custo Ótimo). O gráfico 5 apresenta a comparação entre a solução ótima e a heurística. O gráfico 6 apresenta uma comparação entre o pior caso $NN$, o pior caso [7], e a aproximação obtida pela heurística. A avaliação destes dados e gráficos nos permite chegar às seguintes conclusões:

1. O limite de pior caso oferecido para $NN$ ($O(\log{n})$) é de pouca utilidade. Está por demais distante da aproximação mínima aceitável.
2. O limite de pior caso oferecido por [7] é uma estimativa melhor, mas ainda assim, de pouca utilidade. Mesmo o pior caso medido para o algoritmo heurístico ficou muito acima do estimado segundo [7].
3. O uso de heurísticas oferece ferramental prático para o tratamento de problemas que, de outra forma, seriam intratáveis. Ainda que a solução obtida seja aproximada, a qualidade dos resultados pode ser muito boa, adequada a situações práticas.
4. Embora uma heurística possa encontrar uma excelente solução, eventualmente uma solução ótima, é desconcertante deparar-se com uma situação em que oferecem poucas garantias reais quanto à qualidade do resultado obtido.
5. Em problemas aleatórios, o comportamento da heurística foi pior que nos cados extraídos da TSPLIB. Acreditamos que isto se deva ao conceito de visinhança empregado pela heurística. De qualquer forma, seria interessante avaliar o comportamento da heurística frente a problemas aleatórios de maiores dimensões.

Por fim, o experimento que foi capaz de encontrar a solução ótima para o problema $rbg443$ da TSPLIB usou uma versão modificada do algoritmo, com tempo de execução $O(N^5)$. Ao contrário da versão do algoritmo usado em todos os outros experimentos, esta versão modificada efetuou a iteração de otimizações $3$-opt e $4$-opt para todas as $N$ rotas de partida do algoritmo $NN$, e escolheu a melhor dentre as $N$ rotas otimizadas.

Table 3: Avaliação de $3$-opt e $4$-opt para problemas da TSPLIB

Problema	N	Ótimo	Heurística	% Erro	Tempo (s)	$NN$	Chandra	Aprox
br17	17	39	39	0,00%	0	0,10	0,40	1,00
ft53	53	6905	7441	7,76%	0	0,00	0,48	0,93
ft70	70	38673	40212	3,98%	1	0,00	0,51	0,96
ftv33	34	1286	1489	15,79%	0	0,00	0,45	0,86
ftv35	36	1473	1667	13,17%	0	0,00	0,45	0,88
ftv38	39	1530	1744	13,99%	0	0,00	0,46	0,88
ftv44	45	1613	1705	5,70%	0	0,00	0,47	0,95
ftv47	48	1776	2023	13,91%	0	0,00	0,48	0,88
ftv55	56	1608	1862	15,80%	1	0,00	0,49	0,86
ftv64	65	1839	2056	11,80%	0	0,00	0,50	0,89
ftv70	71	1950	2184	12,00%	0	0,00	0,51	0,89
ftv170	171	2755	3135	13,79%	13	0,00	0,59	0,88
kro124	100	36230	41261	13,89%	1	0,00	0,54	0,88
p43	43	5620	5662	0,75%	0	0,00	0,47	0,99
rbg323	323	1326	1337	0,83%	85	0,01	0,65	0,99
rgb358	358	1163	1172	0,77%	154	0,01	0,67	0,99
rbg403	403	2465	2466	0,04%	208	0,00	0,68	1,00
rbg443	443	2720	2727	0,26%	298	0,00	0,69	1,00
rbg48p	48	14422	15419	6,91%	0	0,00	0,48	0,94

Table 4: Avaliação de $3$-opt e $4$-opt para problemas aleatórios

N	Ótimo	Heurística	% Erro	NN	Chandra	Aproxa
10	66	73	10,61%	0,05	0,37	0,90
11	89	89	0,00%	0,04	0,37	1,00
12	63	71	12,70%	0,06	0,38	0,89
13	70	96	37,14%	0,05	0,38	0,73
14	73	108	47,95%	0,05	0,39	0,68
15	75	86	14,67%	0,05	0,39	0,87
16	57	70	22,81%	0,07	0,40	0,81
17	68	79	16,18%	0,06	0,40	0,86
18	75	97	29,33%	0,06	0,40	0,77
19	80	114	42,50%	0,05	0,41	0,70
20	59	83	40,68%	0,07	0,41	0,71
21	64	73	14,06%	0,07	0,42	0,88
22	67	76	13,43%	0,07	0,42	0,88

Figure 3: Avaliação de $3$-opt e $4$-opt para problemas da TSPLIB

Figure 4: Avaliação da aproximação de $3$-opt e $4$-opt para problemas da TSPLIB

Figure 5: Avaliação de $3$-opt e $4$-opt para problemas aleatórios

Figure 6: Avaliação da aproximação de $3$-opt e $4$-opt para problemas aleatórios

Bibliography

1

http://www.acm.org/portal

2

Ahuja, R. K., Ergun, Ö., Orlin, J.B., Punnen, A.P., A survey of very large-scale neiborhood search techniques, Discrete Applied Mathematics 123 P73-102, 2002.

3

Aho, A., Hopcroft, J., Ullman, J., Data Structures and Algorithms, Addison-Wesley Publishing Company, 1983.

4

Ascheuer, N., Jünger, M., Reinelt, G., A Branch & Cut Algorithm for the Assimetric Travelling Salesman Problem with Precendence Constraints, Report No.98.323, Institut für Informatik, Universität zu Köln 1998.

5

Carr, R., Vempara, S., Towards a 4/3 aproximation for the Asymetric Traveling Salesman Problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms February, 2000.

6

Cirasella, J., Johnson, D.S., McGeoch, L.A., Zhang, W., The Assymetric Traveling Salesman Problem: Algorithms, Instance Generators, ans Tests, ALENEX 2001 Proceedings, Springer Lecture Notes in Computer Science 2153, pp. 32-59, 2001.

7

Chandra, B., Karloff, H., Tovey, C., New Results on the Old $k$-Opt Algorithm for the TSP, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, Arlington, Virginia, United States, 1994 .

8

http://citeseer.nj.nec.com/cs

9

Cormen, T., Leiserson, C., Rivest, R., Introduction to Algorithms, Addison-Wesley Publishing Company, 2001.

10

Cooper, T. B., Kingst, J. H., The complexity of Timetable Construction Problems, Practice and Theory of Automated Timetabling, Springer, 1983 - 283-295.

11

http://www.cygwin.com/

12

Frieze, A., Sorkin, G., The probabilistic relationship between the assignment and asymetric traveling salesman problems, Symposium on Discrete Mathematics p652-660, 2000.

13

Garey, M. R., Johnson, D. S., Computers and Intractability, Freeman, 2000.

14

Glover, F., Gutin, G., Yeo, A., Zverovich, A. Construction heuristics for the asymetric TSP, To appear in European Journal of Operation Reearch, 2000.

15

http://www.inf.ethz.ch/personal/gonnet/papers/MAScoring/jcb.html

16

http://www.google.com

17

Gu, J., Purdom,P.W., Franco, J., Wah,B.W. Algorithms for the Satisfiability (SAT) Problem: a Survey, (SAT) Problem: a Survey, Preliminary version, 1996.

18

Gutin, G., Zverovich, A. Evaluation if the Contract-or-Patch Heuristic for the Asymetric TSP, Manuscript, 2000.

19

Horowitz, E., Sahni, S., Rajasekaran, S., Computers Algorithms C++, Computer Science Press, 1998.

20

Johnson, D.S., McGeoch, L.A., Ritemberg, E.E., Asymptotic Experimental Analisys for the Held-Karp Traveling Salesman Bound, ACM/SIAM Symposium on Discrete Algorithms, 1996

21

Johnson, D.S., Gutin, G., McGeoch, L.A., Yeo, A., Zhang, W., Zverovitch, A., Experimental Analysis of Heuristics for the ATSP, DRAFT (24 November 2001) of a chapter to apear in the book "The Travaling Salesman Problem and its Variations", Gutin and Punnen (eds), Kluwer Academic Publishes, 2002.

22

Kobaiash, Z., Sekiguchi, T., On a characterization of the standard Gray code by using its edge type on a hypercube, Information Processing Letters 81, p231-237, 2002/

23

http://www.periodicos.capes.gov.br

24

Pearl, J., Heuristics - Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley Publishing Company, 1984

25

Punnen, A.P., Kabadi, S. Domination analysis of some heuristics for the traveling salesman problem, Discrete Applied Mathematics 119 P117-128, 2002.

26

http://www.math.princeton.edu/tsp/apps/

27

http://www.math.princeton.edu/tsp/apps/genome.html

28

Samudrala, R., Moult, J., A Graph-theoretic Algorithm for Comparative Modeling of Protein Structure, J. Mol. Biol., Academic Press, 1998 - 279, 287-302.

29

Shariffudin, R.H., Abdullah, A.R., Hamiltonian Circuit Simulations of Elliptic partial Differencial Equation Using a Spark, Applied Mathematics Letters 14 p413-418, 2001

30

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

31

Zhang, W., Truncated Branch-and-Bound: A Case study on the Assymetric TSP, Proc. of AAAI-1993 Spring Symposium pnm AI and NP-Hard Problems, p160-199, Stanford, CA, 1993

32

Zhang, W., Depth-First Branch and Bound versos Local Search: A Case Study, Proceedings of the 17th National Conf. on Artificial Intelligence (AAAI-2000) p 930-935, Austin, TX, 2000

About this document ...

Projeto e Análise de Algoritmos
$2^{\b{o}}$ Trabalho Prático

This document was generated using the LaTeX2HTML translator Version 99.2beta8 (1.43)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -no_navigation -split 0 -discard tp2-texto

The translation was initiated by Marcus Rocha on 2002-09-25

Footnotes

... local¹

Mais detalhes sobre ténicas de busca local, heurísticas e técnicas de varredura do espaço de solução exponencial podem ser encontrados em [19] e em [24].

... trocadas²

Os mesmos comentários feitos quando à eficiência de Trocar3Arestas(o1,d1,o2,d2,o3,d3) permanecem válidos.

... longo³

Neste experimento, usamos os mesmos algoritmos básicos. Contudo, em lugar de escolher a melhor rota $NN$ como ponto de partida, executamos as otimizações $3$-opt e $4$-opt encadeadas e reiteradas para todas as rotas $NN$, e escolhemos o melhor resultado. Este experimento levou três dias para ser concluído numa CPU Pentium II 400MHz.

... assinalamento⁴

Ver [12] para uma definição do problema do assinalamento.

...Held-Karp⁵

Ver [20] para mais detalhes sobre este limite.