Dynamic programming

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.

A programação dinâmica é uma técnica para resolver problemas com subproblemas sobrepostos. Normalmente, esses subproblemas surgem de uma recorrência relacionando a solução de um determinado problema às soluções de seus subproblemas menores. Em vez de resolver subproblemas sobrepostos repetidamente, a programação dinâmica sugere resolver cada um dos subproblemas menores apenas uma vez e registrar os resultados em uma tabela a partir da qual uma solução para o problema original pode então ser obtida.

Principle of optimality: Em termos um tanto diferentes de sua formulação original, ele diz que uma solução ótima para qualquer instância de um problema de otimização é composta de soluções ótimas para suas subinstâncias

Coin-row problem: Há uma fileira de n moedas cujos valores são alguns
inteiros positivos c1, c2, ..., cn, não necessariamente diferentes. O objetivo é coletar a quantidade máxima de dinheiro sujeito à restrição de que duas moedas adjacentes na linha inicial não possam ser coletadas.

Change-making problem: Dê o troco para o valor n usando o número mínimo de moedas de denominações d1 <d2 <... <dm. Para as denominações de moedas usadas nos Estados Unidos. Considera-se um algoritmo de programação dinâmica para o caso geral, assumindo a disponibilidade de quantidades ilimitadas de moedas para cada uma das m denominações d1 <d2 <... <dm onde d1 = 1.

Coin-collecting problem: Várias moedas são colocadas em células de um tabuleiro n × m, não mais do que uma moeda por célula. Um robô, localizado na célula superior esquerda do tabuleiro, precisa coletar o máximo de moedas possível e trazê-las para a célula inferior direita. Em cada etapa, o robô pode mover uma célula para a direita ou uma célula para baixo de sua localização atual. Quando o robô visita uma célula com uma moeda, ele sempre pega a moeda. O algoritmo deve encontrar o número máximo de moedas que o robô pode coletar e um caminho que ele precisa seguir para fazer isso.

knapsack problem: dados n itens de pesos conhecidos w1, ..., wn e valores
v1, ..., vn e uma mochila de capacidade W, encontre o subconjunto mais valioso dos itens que cabem na mochila. suponha que todos os pesos e a capacidade da mochila sejam inteiros positivos; os valores dos itens não precisam ser inteiros.

considere uma instância definida pelos primeiros i itens, 1 ≤ i ≤ n, com pesos w1, ..., wi, valores v1, ..., vi e capacidade da mochila j, 1 ≤ j ≤ W. Seja F (i , j) ser o valor de uma solução ótima para essa instância, ou seja, o valor do subconjunto mais valioso dos primeiros i itens que cabem na mochila de capacidade j. Podemos dividir todos os subconjuntos dos primeiros i itens que cabem na mochila de capacidade j em duas categorias: aqueles que não incluem o i-ésimo item e aqueles que incluem.

Entre os subconjuntos que não incluem o i-ésimo item, o valor de um subconjunto ótimo é, por definição, F (i - 1, j).

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).

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.

Memory function: A abordagem direta top-down para encontrar uma solução para tal recorrência leva a um algoritmo que resolve subproblemas comuns mais de uma vez e, portanto, é muito ineficiente (normalmente, exponencial ou pior). A abordagem de programação dinâmica clássica, por outro lado, funciona de forma bottom up: ela preenche uma tabela com soluções para todos os subproblemas menores, mas cada um deles é resolvido apenas uma vez. Um aspecto insatisfatório dessa abordagem é que as soluções para alguns desses subproblemas menores geralmente não são necessárias para se obter uma solução para o problema fornecido. Uma vez que esta desvantagem não está presente na abordagem de cima para baixo, é natural tentar combinar os pontos fortes das abordagens de cima para baixo e de baixo para cima. O objetivo é obter um método que resolva apenas os subproblemas necessários e que o faça apenas uma vez. Esse método existe; é baseado no uso de funções de memória.

Esse método resolve um determinado problema de maneira top-down, mas, além disso, mantém uma tabela do tipo que seria usada por um algoritmo de programação dinâmica bottom-up. Inicialmente, todas as entradas da tabela são inicializadas com um símbolo especial "nulo" para indicar que ainda não foram calculadas. Depois disso, sempre que um novo valor precisa ser calculado, o método verifica primeiro a entrada correspondente na tabela: se essa entrada não for “nula”, ela é simplesmente recuperada da tabela; caso contrário, é calculado pela chamada recursiva cujo resultado é então registrado na tabela.

Approximation Algorithms for NP-Hard Problems: uma abordagem diferente para lidar com problemas difíceis
de otimização combinatória, como o problema do caixeiro-viajante e o problema da mochila.

algoritmos executam uma gama em nível de sofisticação, a maioria deles é baseada em alguma heurística específica para o problema. Uma heurística é uma regra de bom senso extraída da experiência, e não de uma afirmação matematicamente comprovada. Por exemplo, ir para a cidade não visitada mais próxima no problema do caixeiro viajante é uma boa ilustração dessa noção.

Claro, se um algoritmo cuja saída é apenas uma aproximação da solução ótima real for usado, seria bom saber o quão precisa esta aproximação é:
accuracy ratio
r(sa) = f (s∗)/f (sa)

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.

Approximation Algorithms for the Traveling Salesman Problem:

1- Se P = NP, não existe algoritmo de aproximação c para o problema do caixeiro viajante, ou seja, não existe algoritmo de aproximação em tempo polinomial para este problema, de modo que para todas as instâncias f (sa) ≤ cf (s ∗) para alguns constante c.

Prova- Por meio de contradição, suponha que tal algoritmo de aproximação A e uma constante c existam. (Sem perda de generalidade, podemos assumir que c é um número inteiro positivo.) deve-se reduzir o problema do circuito hamiltoniano ao problema do caixeiro viajante.

Seja G um grafo arbitrário com n vértices. Mapeamos G para um grafo completo ponderado G, atribuindo peso 1 a cada aresta em G e adicionando uma aresta de peso cn + 1 entre cada par de vértices não adjacentes em G. Se G tem um circuito hamiltoniano, seu comprimento em G é n; portanto, é a solução exata s∗ para o problema do caixeiro viajante para G. Observe que se sa é uma solução aproximada obtida para G pelo algoritmo A, então f (sa) ≤ cn pela suposição. Se G não tiver um circuito hamiltoniano em G, o trajeto mais curto em G conterá pelo menos uma aresta de peso cn + 1 e, portanto, f (sa) ≥ f (s ∗)> cn. Levando em consideração as duas desigualdades derivadas, poderíamos resolver o problema do circuito hamiltoniano para o grafo G em tempo polinomial mapeando G para G, aplicando o algoritmo A para obter o passeio sa em G e comparando seu comprimento com cn. Como o problema do circuito hamiltoniano é NP-completo, temos uma contradição, a menos que P = NP.

⚠ Greedy Algorithms for the TSP: The simplest approximation algorithms for the traveling salesman problem are based on the greedy technique. ⚠

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.

2- O algoritmo de duas voltas na árvore é um algoritmo de 2 aproximações para o problema do caixeiro viajante com distâncias euclidianas.

Prova- Obviously, the twice-around-the-tree algorithm is polynomial time if we use a reasonable algorithm such as Prim’s or Kruskal’s in Step 1. We need to show that for any Euclidean instance of the traveling salesman problem, the length of a toursa obtained by the twice-around-the-tree algorithm is at most twice the length of the optimal tour s∗, i.e., f (sa) ≤ 2f (s∗). Since removing any edge from s∗ yields a spanning tree T of weight w(T ), which must be greater than or equal to the weight of the graph’s minimum spanning tree w(T ∗), we get the inequality f (s∗) > w(T ) ≥ w(T ∗). Coping with the Limitations of Algorithm Power This inequality implies that 2f (s∗) > 2w(T ∗) = the length of the walk obtained in Step 2 of the algorithm. The possible shortcuts outlined in Step 3 of the algorithm to obtain sa cannot increase the total length of the walk in a Euclidean graph, i.e.,
the length of the walk obtained in Step 2 ≥ the length of the tour sa. Combining the last two inequalities, we get the inequality 2f (s∗) > f (sa), which is, in fact, a slightly stronger assertion than the one we needed to prove.

Christofides Algorithm

Local Search Heuristics

Approximation Algorithms for the Knapsack Problem:

Greedy Algorithms for the Knapsack Problem We can think of several greedy approaches to this problem. One is to select the items in decreasing order of their weights; however, heavier items may not be the most valuable in the set. Alternatively, if we pick up the items in decreasing order of their value, there is no guarantee that the knapsack’s capacity will be used efficiently. Can we find a greedy strategy that takes into account both the weights and values? Yes, we can, by computing the value-to-weight ratios vi/wi, i = 1, 2, . . . , n, and selecting the items in decreasing order of these ratios.

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.