Please enable JavaScript.

Coggle requires JavaScript to display documents.

Dynamic programming, Approximation Algorithms for the Traveling Salesman…

- - - - Entre os subconjuntos que não incluem o i-ésimo item, o valor de um subconjunto ótimo é, por definição, F (i - 1, j).
        
        Assim, o valor de uma solução ótima entre todos os subconjuntos viáveis dos primeiros i itens é o máximo desses dois valores. Obviamente, se o iº item não couber na mochila, o valor de um subconjunto ótimo selecionado dos primeiros i itens é o mesmo que o valor de um subconjunto ótimo selecionado dos primeiros i - 1 itens.
      - Entre os subconjuntos que incluem o i-ésimo item (portanto, j - wi ≥ 0), um subconjunto ótimo é composto deste item e um subconjunto ótimo dos primeiros i - 1 itens que se encaixa na mochila de capacidade j - wi. O valor de tal subconjunto ótimo é vi + F (i - 1, j - wi).
- - - - Um algoritmo de aproximação de tempo polinomial é considerado um algoritmo de aproximação c, onde c ≥ 1, se a razão de precisão da aproximação que ele produz não excede c para qualquer instância do problema em questão:
        r(sa) ≤ c
        
        The performance ratio serves as the principal metric indicating the quality of the approximation algorithm. We would like to have approximation algorithms with RA as close to 1 as possible. Unfortunately, as we shall see, some approximation algorithms have infinitely large performance ratios (RA = ∞). This does not
        necessarily rule out using such algorithms, but it does call for a cautious treatment of their outputs. There are two important facts about difficult combinatorial optimization problems worth keeping in mind. First, although the difficulty level of solving most such problems exactly is the same to within a polynomial-time transformation of one problem to another, this equivalence does not translate into the realm of approximation algorithms. Finding good approximate solutions is much easier for some of these problems than for others. Second, some of the problems have special classes of instances that are both particularly important for real-life applications and easier to solve than their general counterparts. The traveling salesman problem is a prime example of this situation.
  - - - Greedy algorithm for the discrete knapsack problem:
        
        1 - Compute the value-to-weight ratios ri = vi/wi, i = 1, . . . , n, for the items given.
        
        2 - Sort the items in nonincreasing order of the ratios computed in Step 1. (Ties can be broken arbitrarily.)
        
        3 - Repeat the following operation until no item is left in the sorted list: if the current item on the list fits into the knapsack, place it in the knapsack and proceed to the next item; otherwise, just proceed to the next item.
        
        Greedy algorithm for the continuous knapsack problem:
        
        1 - Compute the value-to-weight ratios vi/wi, i = 1, . . . , n, for the items given.
        
        2 - Sort the items in nonincreasing order of the ratios computed in Step 1. (Ties can be broken arbitrarily.)
        
        3 - Repeat the following operation until the knapsack is filled to its full capacity or no item is left in the sorted list: if the current item on the list fits into the knapsack in its entirety, take it and proceed to the next item; otherwise, take its largest fraction to fill the knapsack to its full capacity and stop.
        
        Approximation Schemes: For this problem, unlike the traveling salesman problem, there exist a with any predefined accuracy level: polynomial-time approximation schemes, which are parametric families of algorithms that allow us to get approximations s(k) with any predefined accuracy level: f (s∗)/f (sa(k)) ≤ 1 + 1/k for any instance of size n, where k is an integer parameter in the range 0 ≤ k < n. The first approximation scheme was suggested by S. Sahni in 1975 [Sah75]. This algorithm generates all subsets of k items or less, and for each one that fits into the knapsack it adds the remaining items as the greedy algorithm would do (i.e., in nonincreasing order of their value-to-weight ratios). The subset of the highest value obtained in this fashion is returned as the algorithm’s output.
- - - - Nearest-neighbor algorithm: it is based on the nearest-neighbor heuristic: always go next to the nearest unvisited city.
        
        1 Choose an arbitrary city as the start.
        
        2 Repeat the following operation until all the cities have been visited:go to the unvisited city nearest the one visited last (ties can be broken arbitrarily).
        
        3 Return to the starting city.
      - Multifragment-heuristic algorithm: Another natural greedy algorithm for the traveling salesman problem considers it as the problem of finding a minimum-weight collection of edges in a given complete weighted graph so that all the vertices have degree 2.
        
        1 Sort the edges in increasing order of their weights. (Ties can be broken arbitrarily.) Initialize the set of tour edges to be constructed to the empty set.
        
        2 Repeat this step n times, where n is the number of cities in the instance being solved: add the next edge on the sorted edge list to the set of tour edges, provided this addition does not create a vertex of degree 3 or a cycle of length less than n; otherwise, skip the edge.
        
        3 Return the set of tour edges.
      - Minimum-Spanning-Tree–Based Algorithms: There are approximation algorithms for the traveling salesman problem that exploit a connection between Hamiltonian circuits and spanning trees of the same graph. Since removing an edge from a Hamiltonian circuit yields a spanning tree, we can expect that the structure of a minimum spanning tree provides a good basis for constructing a shortest tour approximation. Here is an algorithm that implements this idea in a rather straightforward fashion.
  - - - Christofides Algorithm
        Local Search Heuristics