Questões

1. 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. Bin packing

      Resposta:

      • Um dos exemplos mais simples que podem ser imaginados é o problema de otimizar a carga de caminhões no transporte de materiais: dados o volume e o peso de cada unidade a transportar e a capacidade de cada caminhão, maximizar a carga em cada caminhão para minimizar a quantidade de caminhões a ser utilizada;

      • Um problema curioso pode ser visto em ambientes de processamento paralelo ou distribuído, onde se dispõe de um certo número de processadores com uma determinada capacidade (relacionada à carga de trabalho que podem executar) e uma certa quantidade de trabalhos a serem executados, cada um com uma estimativa de custo de processamento associada. Dessa forma, o subsistema de controle de tarefas pode alocar os trabalhos para cada processador, evitando a sobrecarga de alguns deles.

      $\Box$

   2. Cobertura de vértices (vertex cover)

      Resposta:

      • Suponha que um indivíduo esteja planejando suas atividades para o ano seguinte. Embora tenha vários objetivos em mente (participar de cursos ou conferências, por exemplo), alguns deles não podem ser feitos ao mesmo tempo, pois os horários conflitam. A intenção, então, é escolher o maior conjunto de atividades que possam ser feitas sem que haja qualquer conflito. Ou, remodelando: Ele deseja desistir do menor número possível de atividades. Ora, se modelarmos a situação através de um grafo onde cada vértice representa uma atividade e cada aresta representa um conflito, o problema da cobertura de vértices pode ser utilizado para escolher o menor conjunto possível de atividades que representem algum conflito.

      $\Box$

   3. Mochila (knapsack)

      Resposta:

      • Dado que uma série de encomendas precisam ser distribuídas, cada uma com uma prioridade associada, e dado que o meio de transporte - um caminhão, por exemplo - possui capacidade limitada (de volume ou de peso), um sistema pode modelar esta situação como o problema da mochila: Carregar ao máximo o caminhão, tentando respeitar da melhor forma as prioridades das encomendas.

      $\Box$

   4. Subset sum

      Resposta:

      • Existem alguns estudos acerca do ``problema da compensação bancária'': Um banco deve compensar valores que saem com valores que entram. Entretanto, esses valores são fixos (correspondem às movimentações bancárias) e deve-se procurar subconjuntos de entradas e saídas que se anulem mutuamente, para não gerar pendências de débito ou crédito entre os bancos. Na realidade, este problema de casamento nada mais é do que uma maneira diferente de formular o problema de subset sum;

      • Alguns pesquisadores sugerem o uso do problema do subset sum - ou melhor, da sua característica de ser $\mathcal{NP}$-completo - para construir sistemas de criptografia. Por exemplo: Armazenar ou transportar senhas em texto puro (plain text) é considerada prática pouco segura, pois um hacker, tendo acesso ao sistema de arquivos ou ao canal de comunicação, poderá muito facilmente obtê-las. Uma alternativa é descrita a seguir: Dado um conjunto fixo de números inteiros $C$, uma função pode ser construída de modo a receber como entrada uma palavra-chave - uma senha - e retornar um subconjunto $S$ de $C$. Assim, bastaria armazenar ou transportar a soma dos elementos de $S$. Embora o valor dessa soma possa tornar-se público, é muito difícil reconstituir os elementos originais de $S$ apenas com base nesse valor. Um sistema de segurança poderá ser construído com confiabilidade suficiente para assegurar que o único meio de reconstituir o subconjunto $S$ seja digitando novamente a senha que o originou.

      $\Box$

   5. Problema do caixeiro viajante

      Resposta:

      • Uma rede de computadores pode ser modelada como um grafo completo ponderado: um pacote de dados pode partir de qualquer nó com destino a outro, e essa operação possui um custo (tempo) associado. Determinadas aplicações, em particular em ambientes de processamento distribuído, podem estabelecer que pacotes de controle devem partir de um determinado nó - um servidor, por exemplo -, viajar por cada nó da rede e retornar ao ponto de origem. Neste cenário, determinar qual a seqüência mais rápida de nós diminuirá o tempo total da viagem do pacote.

      • Os aparelhos de inserção de componentes em circuitos impressos são programados para montar uma série de componentes. Se cada ponto de inserção for modelado como um vértice de um grafo completo e for considerado que a distância entre dois pontos é o peso associado a cada aresta, então deve-se buscar a seqüência de movimentos que minimize a distância total percorrida, o que diminui o tempo de fabricação de cada circuito. O fato de que o caminho é um ciclo fechado advém do fato de que o sistema de inserção sempre retornará a uma posição inicial após a montagem de cada placa.

      $\Box$

2. Problema: Dados um conjunto de cidades $C = \{c_1, c_2, \cdots, c_n\}$ e uma distância $d(c_i, c_j)$ para cada par de cidades $c_i, c_j \in C$, 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).

   O que fazer:

   1. Prove que este problema é $\mathcal{NP}$-completo.

      Resposta: Para provar que um problema é $\mathcal{NP}$-completo, deve-se provar que ele é um problema $\mathcal{NP}$ e que é $\mathcal{NP}$-difícil. As provas serão apresentadas em seguida.

      • Prova de que é $\mathcal{NP}$: Um problema é $\mathcal{NP}$ se ele pode ser verificado em tempo polinomial. Vejamos:

        Dado o problema de decisão relacionado, enunciado a seguir:

        ``Dado um grafo não orientado completo ponderado $G = (V, A)$, determinar se um certo caminho $P = \langle v_1, v_2, \cdots, v_n, v_1 \rangle$ percorre uma distância menor ou igual a um valor $k$, sendo $v_1, v_2, \cdots, v_n$ cada um dos vértices do conjunto $V$, em qualquer ordem.''

        A solução para este problema pode ser modelada pelo pseudo-código a seguir, onde $Dist$ é a matriz de adjacência:

        
        
        

        
                
        $total \leftarrow 0$;
        
        Para 
        $i \leftarrow 1$ até $n - 1$ Faça
        
        
        $total \leftarrow total + Dist[v_i, v_{i+1}]$;
        
        
        $total \leftarrow total + Dist[v_n, v_1]$;
        
        Retorne 
        $(total \leq k)$;
        

        
        
        

        De fato, este algoritmo é executado em tempo polinomial - mais especificamente, em $\Theta(n) = \Theta(\vert V\vert)$. Portanto:

        $$\mathcal{NP}$$ (1)

        
        

      • Prova de que é $\mathcal{NP}$-difícil: Para isto, deve-se tomar um problema reconhecidamente $\mathcal{NP}$-difícil e criar uma maneira de reduzi-lo polinomialmente ao PCV. Aqui, parte-se do Problema do Ciclo Hamiltoniano (PCH), reconhecidamente $\mathcal{NP}$-difícil, e será demonstrada uma redução ao PCV.

        Dada uma instância $G = (V, A)$ para o PCH, deve-se construir um grafo $G' = (V, A')$, onde, para cada aresta $(u, v) \in A'$, temos que o custo $c(u, v)$ dessa aresta é

        $$c(u, v) = \left\{ \begin{array}{ll} 0 & \text{se } (u, v) \in A \\ 1 & \text{se } (u, v) \notin A \end{array} \right.$$ (2)

        
        

        Além disto, o grafo $G'$ é completo, ou

        $$(u, v) \in A' \Longleftrightarrow u \neq v$$

        A partir deste ponto, $G'$ pode ser uma instância para o PCV: é um grafo completo, ponderado e bem definido. Para fechar a questão, deve-se provar que: (i) a redução pode ser feita em tempo polinomial; (ii) $G$ tem solução para o PCH somente se $G'$ tem solução para o PCV com custo máximo 0; e (iii) vice-versa - $G'$ tem solução para o PCV com custo máximo 0 somente se $G$ tem solução para o PCH.

        1. A redução pode ser feita em tempo polinomial: Testar todos os pares de vértice $u, v \in V$ para determinar o custo de $c(u, v)$ demanda tempo $O(\vert V\vert^2)$. Além disto, para uma implementação eficiente - digamos, por matriz de adjacências -, tanto checar a existência de $(u, v)$ em $A$ quanto armazenar o custo $c(u, v)$ demandam tempo $\Theta(1)$. Portanto, a redução tem complexidade polinomial.

        2. $G$ tem solução para o PCH somente se $G'$ tem solução para o PCV com custo máximo 0: Se for encontrada uma solução para o PCV com custo máximo 0 - e dado que não há arestas com custo negativo -, então todas as arestas do ciclo encontrado possuem custo 0. Entretanto, pela regra de formação das arestas de $G'$ apresentada em (2), nota-se que cada aresta de custo 0 em $G'$ corresponde a uma aresta existente em $G$. Portanto, se houver solução para o PCV, então existe um ciclo hamiltoniano em $G$.

        3. $G'$ tem solução para o PCV com custo máximo 0 somente se $G$ tem solução para o PCH: Se houver um ciclo hamiltoniano em $G$, então ele é formado por uma série de arestas $(u, v) \in A$. Mas, pela regra de redução definida em (2), cada uma dessas arestas torna-se uma aresta de custo 0 em $G'$, que também formam um ciclo - e, portanto, uma solução para o PCV de custo 0.

        Com base nas três provas apresentadas, deduzimos então que

        $$\mathcal{NP}$$ (3)

        
        

      Finalmente, com base nas deduções (1) e (3), concluímos que o Problema do Caixeiro Viajante é $\mathcal{NP}$-completo.

      $\Box$

   2. Implemente um algoritmo capaz de obter a solução ótima para este problema. Informe o tamanho do maior problema que você conseguiu obter a solução ótima. Comente o resultado indicando o motivo da limitação e faça uma estimativa do tempo necessário no caso de termos uma entrada 10 vezes maior que a do maior problema que voce resolveu.

      Sobre o algoritmo: O algoritmo implementado é bastante simples. Basicamente, é uma adaptação do algoritmo de pesquisa primeiro em profundidade (Depth-First Search), com duas alterações básicas:

      • Ao visitar todos os vizinhos de um determinado vértice, ele é novamente pintado de branco, para que possa ser visitado posteriormente, fazendo parte de novos caminhos. Isto impede que sejam geradas árvores com ramificações: apenas caminhos simples;

      • Quando a visita tiver chegado à sua profundidade máxima, calcula-se o custo total do ciclo obtido (arestas da árvore caminhada + aresta que liga o último ao primeiro vértice), comparando-o com o melhor resultado obtido até o momento e armazenando este ciclo, caso este seja ainda melhor.

      Maior problema resolvido: O maior problema que se conseguiu resolver possui 14 vértices e demorou pouco mais de 28 minutos para ser processado. O problema com 15 vértices foi interrompido após cerca de 3 horas, tendo sido considerado insolúvel em tempo razoável para a plataforma de execução adotada.

      É importante ressalvar que esses tempos foram conseguidos sem qualquer otimização sobre o algoritmo de força bruta. Especificamente, não foi implementada a checagem de limite de distâncias percorridas, que permite que uma determinada tentativa seja interrompida caso se perceba que ela necessariamente levará a uma solução pior do que a que foi encontrada até o momento. Isto porque uma implementação desse tipo influenciaria a cronometragem, pois é possível que a instância proposta seja particularmente boa ou ruim para esta abordagem.

      A Tabela 1 sumariza os tempos obtidos com as execuções do algoritmo adotando quantidades crescentes de vértices.

      
      

      Tabela 1: Cronometragem da execução do algoritmo de força bruta para o PCV

      Nº vértices	Tempo
      2	$<$ 1 ms
      3	$<$ 1 ms
      4	$<$ 1 ms
      5	$<$ 1 ms
      6	$<$ 1 ms
      7	$<$ 1 ms
      8	1 ms
      9	8 ms
      10	82 ms
      11	867 ms		=		0		,87''
      12	10.123 ms		=		10		,12''
      13	125.814 ms		=		2' 05		''
      14	1.694.860 ms		=		28' 15		''

      
      

      Projeção de tempo para uma entrada dez vezes maior do que a do maior problema resolvido: É muito interessante plotar os tempos obtidos em um gráfico logarítmico na ordenada, que nos dá uma boa noção do comportamento do crescimento de tempo em função do número de vértices:

      Figura 1: Plotagem logarítmica dos tempos de execução do PCV

      De fato, há uma conformação exponencial no crescimento da função de tempo. A resolução da questão proposta é feita em três passos:

      1. Tomando o eixo das ordenadas como sendo linear (usando o logaritmo do tempo), temos a seqüência de dados vista na Tabela 2;

         
         

         Tabela 2: Logaritmo dos tempos obtidos

         N^o vértices	$\log_{10}$(Tempo)
         8	0
         9	0,903089987
         10	1,913813852
         11	2,938019097
         12	4,005309237
         13	5,09972897
         14	6,22913383

         
         

      2. Usando o Método dos Mínimos Quadrados, adaptamos estes dados à equação de uma reta:
         $$e = \alpha + \beta \cdot \vert V\vert$$
         onde
         $$\alpha = \frac{\left(\sum y\right) \left(\sum x^2\right) - \left(... ...t(\sum xy\right)} {\vert V\vert \left(\sum x^2\right) - \left(\sum x\right)^2}$$
         e
         $$\beta = \frac{\vert V\vert \left(\sum xy\right) \left(\sum x\righ... ...ft(\sum y\right)} {\vert V\vert \left(\sum x^2\right) - \left(\sum x\right)^2}$$

         Dessas equações obtemos os valores de $\alpha$ e $\beta$:

         $$\begin{array}{c} \alpha = -8,447769406 \\ \beta = 1,041863387 \end{array}$$

      3. Adota-se como projeção de tempo $T_P$ a seguinte equação exponencial:
         

         $$T_P = 10^e$$

         $$= 10^{\alpha + \beta \cdot \vert V\vert}$$

         $$= 10^{-8,447769406 + 1,041863387 \cdot \vert V\vert}$$

         
         

      Para observar a veracidade da equação proposta, a Figura 2 sobrepõe a plotagem dos tempos projetados (linha sólida vermelha) aos tempos obtidos (linha tracejada azul), demonstrando uma conformação bastante adequada.

      Figura 2: Plotagem logarítmica da projeção de tempo (linha sólida) sobre os tempos obtidos (linha tracejada)

      Finalmente, o resultado da questão: Basta calcular o valor de $T_P$ para $\vert V\vert = 140$:
      

      $$T_P(140) = 10^{-8,447769406 + 1,041863387 \cdot 140}$$

      $$= 10^{123,9140008}$$

      $$= 2,5888 \cdot 10^{137}$$

      
      o que é um tempo completamente fora de qualquer ordem de grandeza imaginável pelo ser humano. Convertendo, por exemplo, este tempo em milênios, teríamos
      $$T_P(140) = 8,2035 \cdot 10^{123}$$    milênios$$$$
      - outro número igualmente impossível de ser compreendido.

   3. Implemente uma heurística (ou aproximação) que resolva este problema eficientemente e produza ``boas'' soluções sob o ponto de vista prático. Apresente uma análise de complexidade de tempo da sua heurística. Use a matriz disponível aqui: http://www.dcc.ufmg.br/$\sim$nivio/cursos/pa03/tp2/matriz-de-entrada. Imprima o caminho obtido e seu custo. As melhores soluções vão ser premiadas com pontos extras. Mais especificamente, as 5 melhores soluções que sejam até 10% piores (em termos do custo do caminho encontrado) que a melhor obtida.

      Descrição do algoritmo: O algoritmo implementado é uma simplificação do algoritmo de Christofides, com a aplicação de um algoritmo de melhoramento de resultados por permutação de vértices.

      Basicamente, o algoritmo proposto funciona da seguinte maneira:

      1. A partir do grafo ponderado fornecido como base do problema, obtém-se uma Árvore Geradora Mínima (um conjunto de arestas $A_G \subseteq A$);

      2. Usa-se os vértices de grau ímpar para obter um matching (um conjunto de arestas $A_M \subseteq A$);

      3. A partir do caminho euleriano formado pelos vértices $A_G \cup A_M$, constrói-se uma solução para o PCV realizando o caminhamento com curto-circuitos (isto é, saltando todo vértice que já tiver sido visitado).

      A diferença entre este algoritmo e o proposto por Christofides está no passo (ii). Enquanto Christofides estabelece o uso do matching mínimo, neste algoritmo deciciu-se pelo uso de um algoritmo guloso, descrito a seguir:

      1. Coleta-se o conjunto de vértices $V_I$ de grau ímpar;

      2. Coleta-se o conjunto de todas as arestas $A_I$ que liguem pares de vértices em $V_I$;

      3. Faz-se a escolha da aresta $(u, v) \in A_I$ de menor custo, onde $u, v \in V_I$;

      4. Retira-se as arestas $u$ e $v$ do conjunto $V_I$;

      5. Repete-se os passos (iii) e (iv) até que $V_I = \varnothing$.

      Este algoritmo guloso, apesar de ser executado em tempo bem menor do que o matching mínimo, evidentemente não garante a obtenção do melhor resultado possível.

      O algoritmo de melhoramento aplicado ao final consiste dos seguintes passos:

      1. A partir do melhor caminho $C$ obtido após a execução do algoritmo principal (descrito anteriormente), toma-se $k$ vértices distintos;

      2. Realiza-se todas as permutações possíveis desses vértices dentro do arranjo $C$, calculando, para cada uma das $k! - 1$ permutações¹, a nova distância total e verificando se esta é melhor do que a obtida originalmente;

      3. Repetem-se os passos anteriores para cada conjunto distinto de $k$ vértices.

      Este pequeno algoritmo de melhoramento é capaz de aprimorar sensivelmente os resultados obtidos. Para o programa escrito, adotou-se $k = 3$.

      Análise de complexidade: Um bom critério para analisar a complexidade deste algoritmo está em contabilizar o número de comparações de custos de arestas. De fato, ao observar o código-fonte do programa, é possível observar que esta operação ocorre em todas as recursões e em todos os laços relevantes da implementação.

      As rotinas do módulo priorqueue.c abstraem a comparação de chaves através de chamadas a função Compare( ). Este módulo representa a implementação padrão de heaps para filas de prioridades, portanto pode-se adotar a análise tradicional vista em Cormen [1] para as rotinas de manutenção do heap. Isto porque a operação de comparação é determinante para o tempo de execução de todas as rotinas deste módulo. Assim, temos:

      • PriorQueueMinHeapify( ): $T_{MH}(n) = O(\log_2 n)$

      • PriorQueueBuildMinHeap( ): $T_{BMH}(n) = O(n)$

      • PriorQueueExtractMin( ): $T_{EM}(n) = O(\log_2 n)$

      • PriorQueueDecreaseKey( ): $T_{DK}(n) = O(\log_2 n)$

      As rotinas do módulo heuristica.c que compõem a estrutura do algoritmo são analisadas em seqüência:

      • heuristProcuraCiclo( ): Para cada iteração do laço principal, a rotina descobre uma aresta de cor branca que liga o vértice 'u' a um vértice 'v'. A procura deste vértice é feita em $O($nSizead$)$ comparações - linhas 171-186. A aresta encontrada é pintada de cinza, e o laço principal repete-se até que não seja mais possível encontrar arestas brancas. Como a cada iteração uma aresta é pintada de cinza, então o laço principal é executado $O($nSizead$)$ vezes. Portanto, a complexidade desta rotina é
        $$T_{HPC} = O($$nSizead$$^2)$$
        O pior caso para 'nSizead' é quando todos os vértices têm grau ímpar e, portanto, o número de arestas consideradas é o dobro do número de vértices. Portanto, pode-se dizer que
        $$T_{HPC} = O(\vert V\vert^2)$$

      • heuristProcuraCicloTotal( ): Não há comparação de chaves nesta rotina, apenas chamadas a heuristProcuraCiclo( ). A primeira chamada a heuristProcuraCiclo( ) descobre um ciclo, que percorrerá pelo menos 2 vértices. Cada chamada adicional a heuristProcuraCiclo( ) adiciona um novo sub-ciclo ao ciclo original, ou seja, adiciona pelo menos 1 vértice a cada iteração (laço das linhas 219-247). Assim, no pior caso são feitas $\vert V\vert - 1$ chamadas a heuristProcuraCiclo( ). Portanto, a complexidade de heuristProcuraCicloTotal( ) é
        $$T_{HPCT} = (\vert V\vert - 1) \cdot T_{HPC} = O(\vert V\vert^3)$$

      • calcDistCaminho( ): Não há comparações feitas nesta rotina, portanto:
        $$T_{CDC} = 0$$

      • procCaminhoHeuristica( ): A linha 313 consome $T_1 = O(\log_2 \vert V\vert)$. O laço das linhas 330-355 consome: $O(1)$ comparação (linha 336) mais $O(\log_2 \vert V\vert)$ (linha 352) comparações. Como este laço é executado $\vert V\vert$ vezes, temos que o seu custo é de $O(\vert V\vert \log_2 \vert V\vert)$ comparações. O laço imediatamente externo, das linhas 316-356, engloba este custo mais $O(\log_2 \vert V\vert)$ (linha 320) e é executado no máximo $\vert V\vert$ vezes (até exaurir a fila de prioridades de vértices 'vdpq'). Portanto, o custo das linhas 316-356 é $T_2 = O(\vert V\vert \cdot (\vert V\vert \log_2 \vert V\vert + \log_2 \vert V\vert)) = O(\vert V\vert^2 \log_2 \vert V\vert)$.

        O laço das linhas 367-378 não realiza nenhuma comparação de chaves, nem o laço das linhas 391-399. Já o laço das linhas 404-419 é executado no máximo duas vezes o número de vértices ímpares, que por sua vez é no máximo o número de vértices; o único comando relevante é o da linha 405, que executa $O(\log_2 \vert V\vert)$ comparações; portanto, o máximo possível de comparações do laço é igual a $T_3 = O((\vert V\vert / 2) \cdot \log_2 \vert V\vert) = O(\vert V\vert \log_2 \vert V\vert)$.

        As linhas 433-472 correspondem a três laços aninhados, e cada iteração interna (linhas 438-469) chama 5 vezes a rotina calcDistCaminho( ); entretanto, como o seu custo em comparações é $T_{CDC} = 0$, estes laços aninhados não contam comparações.

        Finalmente, todos esses passos estão incluídos em um grande laço externo (linhas 296-476) que é executado $\vert V\vert$ vezes. Portanto, o custo total da heurística, em termos de comparações de chaves, é
        

        $$T_{PCH} = O(\vert V\vert \cdot (T_1 + T_2 + T_3))$$

        $$= O(\vert V\vert \cdot (\log_2 \vert V\vert + \vert V\vert^2 \log_2 \vert V\vert + \vert V\vert \log_2 \vert V\vert))$$

        $$= O(\vert V\vert^3 \log_2 \vert V\vert)$$

        
        

      Melhor caminho obtido: De acordo com a heurística proposta, o caminho mais curto encontrado para a instância do problema brazil58 foi:

      $\langle$20, 28, 35, 16, 25, 5, 18, 27, 13, 36, 33, 14, 45, 55, 44, 32, 7, 21, 54, 53, 1, 40, 47, 2, 34, 9, 51, 50, 46, 48, 42, 26, 4, 22, 11, 56, 23, 57, 43, 17, 0, 29, 12, 39, 24, 8, 31, 19, 52, 49, 3, 6, 30, 37, 41, 15, 10, 38, 20$\rangle$

      Este caminho percorre uma distância de 27.024 unidades - cerca de 6,41% maior do que o melhor caminho encontrado até hoje, de 25.395 unidades.

      $\Box$

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

      Resposta: Para realizar esta análise, algumas convenções serão estabelecidas:

      	$\vert PCV\vert$		é o custo do caminho ótimo do PCV;
      	$A_G$		é o conjunto de arestas que compõem a Árvore Geradora Mínima;
      	$g_i$		é cada uma das arestas pertencentes a $A_G$, com $1 \leq i \leq \vert A_G\vert$;
      	$A_M$		é o conjunto de arestas que compõem o matching;
      	$m_i$		é cada uma das arestas pertencentes a $A_M$, com $1 \leq i \leq \vert A_M\vert$.

      Considere a AGM formada pelas arestas $A_G$. A soma dos custos de cada uma destas arestas é menor do que o custo do caminho ótimo para o PCV, ou

      $$\sum_{i=1}^{\vert A_G\vert} (g_i) \leq \vert PCV\vert$$ (4)

      
      

      Analisando agora as arestas $m_i \in A_M$: Pela desigualdade de triângulos, cada aresta $m_i$ não pode ser maior do que o correspondente segmento da solução ótima para o PCV, portanto

      $$\sum_{i=1}^{\vert A_M\vert} (m_i) \leq \vert PCV\vert$$ (5)

      
      

      Ao considerar a união das arestas de $A_G$ e $A_M$, obtém-se um caminho euleriano cujo custo é

      $$\sum_{i=1}^{\vert A_G\vert}$$   Custo$$(g_i) + \sum_{i=1}^{\vert A_M\vert}$$   Custo$$(m_i) \leq 2 \cdot \vert PCV\vert$$

      Como este caminho será percorrido fazendo-se curto-circuitos, espera-se que no caso médio sejam obtidos resultados bem melhores do que $2 \cdot \vert PCV\vert$.

      $\Box$

   5. Realize testes com entradas escolhidas aleatoriamente e compare os resultados com a análise de eficiência apresentada no item anterior. Comente os resultados obtidos e discuta o quão próxima a análise teórica está da realidade.

      Testes realizados: Foi realizado um experimento com 1.000 entradas aleatoriamente geradas de instâncias com 10 vértices². Os experimentos constaram em executar a heurística e comparar seus resultados (custo total dos caminhos) com o obtido através da força bruta. Os resultados obtidos foram interessantes, pois demonstram a eficiência do algoritmo obtido:

      • Em 63,9% (quase 2/3) dos casos, a heurística foi capaz de determinar o caminho ótimo;

      • No pior caso, o caminho descoberto foi apenas 16,09% mais longo do que o caminho ótimo;

      • Os caminhos encontrados foram em média 1,44% mais longos do que os caminhos ótimos.

      Pela tabela de distribuição abaixo, é possível observar que em quase 80% dos casos a heurística apresentada é capaz de obter soluções apenas 2,5% piores em relação ao caminho ótimo:

      $$\begin{array}{\vert c\vert r\vert} \hline \text{\% pior do que o ... ...2,0\% \\ 12,5\%-15,0\% & 1,3\% \\ 15,0\%-17,5\% & 0,2\% \\ \hline \end{array}$$

      Comentários: Analisando os dados apresentados acima, é possível perceber que, no caso esperado, a expectativa é de conseguir resultados bem melhores do que o limite calculado de $2 \cdot \vert PCV\vert$ (discutido na Questão (d)). Mesmo o pior caso que ocorreu é muito distante deste limite. Os seguintes motivos podem ser apontados para este fato:

      • A análise toma por base o limite superior de $\vert PCV\vert$ para a soma das distâncias das arestas da Árvore Geradora Mínima (Eq. (4)), quando sabe-se que esta soma é menor;

      • A escolha gulosa para as arestas que compõem o matching, embora não garanta um resultado ótimo, tende a chegar a bons resultados, obtendo um conjunto de arestas cuja soma dos pesos não deve chegar perto de $\vert PCV\vert$ (limite segundo a Eq. (5));

      • O caminhamento com curto-circuitos reduz drasticamente a distância percorrida, pois vários segmentos são substituídos por uma única aresta;

      • Finalmente, o algoritmo de melhoramento final por permutação de vértices traz resultados ainda mais próximos do ideal³.

      $\Box$

   6. Submeta eletronicamente a implementação da solução ótima utilizando como entrada de dados a seguinte matriz:
      $$\begin{array}{\vert c\vert c\vert c\vert c\vert c\vert c\vert c\v... ...& 48 & 6 & 6 & - & 0 \\ \hline 8 & 8 & 48 & 6 & 6 & 0 & - \\ \hline \end{array}$$

      Resposta: O caminho mais curto encontrado é $\langle 0, 2, 1, 5, 3, 4, 6, 0 \rangle$, percorrendo uma distância de 36 unidades.

      $\Box$

   7. Apresente a documentação das implementações realizadas (veja aqui maiores detalhes sobre instruções para a entrega de trabalhos praticos: http://www.dcc.ufmg.br/$\sim$nivio/cursos/pa03/entrega).

      Resposta: Apresentada na Seção 2.

      $\Box$