4. Teori
4.4 Eksisterende empirisk forskning på modellene
Para facilitar o problema de obter uma implementa¸c˜ao mais r´apida da opera¸c˜ao de in- ser¸c˜ao ´otima para matrizes, n´os investigamos primeiramente uma simplifica¸c˜ao do pro- blema para matrizes de uma linha apenas, e al´em disso exclu´ımos subsequˆencias circulares de considera¸c˜ao. Mais precisamente, n´os consideramos o problema de, dados um n´umero real x e uma sequˆencia A de n n´umeros reais, encontrar um ´ındice p ∈ [0 .. n] que mi- nimize MS(A(x→p)). Observe que esse problema ´e facilmente resolvido em tempo Θ(n2)
por meio do algoritmo de Kadane: basta utilizar o algoritmo para computar MS(A(x→p))
para cada p ∈ [0 .. n], e ent˜ao escolher um ´ındice p que minimize o valor em quest˜ao. N´os buscamos, entretanto, uma solu¸c˜ao mais r´apida, e de fato conseguimos obter um algoritmo linear relativamente simples para o problema. Esse algoritmo ´e descrito num artigo de nossa coautoria (9, 30).
O nosso segundo passo rumo a uma implementa¸c˜ao eficiente da opera¸c˜ao de inser¸c˜ao ´otima para matrizes foi voltar a considerar o caso de matrizes com v´arias linhas, mas ainda excluindo subsequˆencias circulares de considera¸c˜ao. Em outras palavras, n´os bus- camos uma solu¸c˜ao eficiente para o problema de, dadas uma matriz real m × n M e um vetor-coluna X de m n´umeros reais, encontrar um ´ındice p ∈ [0 .. n] que minimize ∑m−1
onde M′ = M(X→p). Observe que o algoritmo linear mencionado no par´agrafo anterior
n˜ao leva a uma solu¸c˜ao para o problema em quest˜ao, pois um ´ındice p que minimize a soma m´axima de uma linha qualquer de M′ n˜ao necessariamente minimiza a soma ou o m´aximo das somas m´aximas de todas as linhas de M′. Observe tamb´em que, assim como no caso da opera¸c˜ao de inser¸c˜ao ´otima original, o problema em quest˜ao pode ser resolvido pela estrat´egia geral do Algoritmo 1; como antes, por´em, a dificuldade consiste em conse- guir computar rapidamente a soma m´axima de cada linha de cada matriz resultante das poss´ıveis inser¸c˜oes de X em M . N´os obtivemos, entretanto, um algoritmo que, dados um n´umero real x e uma sequˆencia A de n n´umeros reais, computa MS(A(x→p)) para todos
os ´ındices do intervalo [0 .. n] coletivamente em tempo Θ(n). Esse algoritmo pode ent˜ao ser utilizado no c´alculo de cada linha da matriz C da vers˜ao n˜ao-circular do Algoritmo 1, levando a uma solu¸c˜ao Θ(m ⋅ n) (isto ´e, linear) para o problema aqui em quest˜ao. N´os ressaltamos ainda que o algoritmo que obtivemos na verdade realiza em tempo linear a seguinte tarefa mais geral: dadas sequˆencias A e Y de n e n + 1 n´umeros reais, respectiva- mente, computar o valor MS(A(Y [p]→p)) para cada p ∈ [0 .. n]. O algoritmo em quest˜ao ´e descrito num artigo de nossa autoria (10).
O nosso ´ultimo passo na obten¸c˜ao de uma implementa¸c˜ao eficiente da opera¸c˜ao de inser¸c˜ao ´otima para matrizes consistiu em estender o algoritmo anunciado no par´agrafo anterior de forma a computar a soma m´axima circular de inser¸c˜oes. Na verdade, n´os obtivemos um resultado ainda mais geral, envolvendo dois algoritmos complementares. O primeiro algoritmo, de pr´e-processamento, recebe uma sequˆencia A de n n´umeros reais e computa um certo conjunto de dados auxiliares em tempo Θ(n). O segundo algoritmo, de consulta, recebe um n´umero real x e um ´ındice p ∈ [0 .. n] e, utilizando os dados auxiliares computados pelo primeiro algoritmo, calcula MS(A(x→p)) ou MCS(A(x→p)) em tempo de pior caso O(1). Naturalmente, esses algoritmos generalizam aqueles citados nos par´agrafos anteriores. Al´em disso, eles levam ao Algoritmo 2, que ´e um refinamento do Algoritmo1que executa em tempo Θ(m⋅n), e que portanto implementa a opera¸c˜ao de inser¸c˜ao ´otima para matrizes na melhor complexidade de tempo poss´ıvel. N´os remetemos o leitor ao artigo do Apˆendice A, onde os algoritmos de pr´e-processamento e de consulta s˜ao apresentados.
Algoritmo 2: Algoritmo de inser¸c˜ao ´otima para matrizes (vers˜ao ´otima)
Entrada: Uma matriz real m × n M e um vetor-coluna X com m n´umeros reais Sa´ıda: Uma matriz M(X→p) tal que p∈[0 .. n] e p minimiza custo(M(X→p))
para i de 0 a m − 1 fa¸ca 1 Pr´e-processar M[i] 2 para j de 0 a n fa¸ca 3
C[i, j] ← Consultar MCS(M[i](X[i]→j))
4
retorne M(X→p), p/ algum p∈[0 .. n] que minimize ∑m−1
i=0 C[i, p] ou maxiC[i, p].
3.4 2-Aproxima¸c˜ao para a Vers˜ao Escalar e N˜ao-circular de SMSP
O artigo (9,30) mencionado na se¸c˜ao anterior apresenta tamb´em resultados para a vers˜ao escalar e n˜ao-circular do problema SMSP, isto ´e, para o problema de, dada uma sequˆencia Ade n n´umeros reais, encontrar uma permuta¸c˜ao A′ de A que minimizeMS(A′). Primei-ramente, ´e demonstrado que esse problema ´e fortemente NP-dif´ıcil, por redu¸c˜ao a partir do problema de 3-PARTIC¸ ˜AO; em seguida, ´e apresentado um algoritmo 2-aproximativo O(n log n) para o problema. Dada uma sequˆencia A de n n´umeros reais, a primeira parte do algoritmo em quest˜ao consiste no c´alculo, em tempo O(n log n), de um limite inferior L ≥ 0 para o valor OPT = min{MS(A′) ∶ A′ ´e permuta¸c˜ao de A}. A segunda parte do algoritmo consiste na obten¸c˜ao, em tempo O(n), de uma permuta¸c˜ao A′ de A tal que MS(A′) ≤ L + M, onde M = max{0, maxn−1
i=0 A[i]} (observe que M ≤ OPT, da´ı o fator de
aproxima¸c˜ao). O ´unico desses resultados que ´e utilizado diretamente nesta tese ´e o limite inferior L, cujo c´alculo ´e apresentado no Algoritmo 3; n´os remetemos o leitor `a se¸c˜ao 5 do artigo que foi citado para uma demonstra¸c˜ao de que o Algoritmo 3´e correto.
Algoritmo 3: C´alculo de limite inferior (9, 30, ➜5). Entrada: Uma sequˆencia A de n n´umeros reais
Sa´ıda: Um limite inferior L≥ 0 para OPT = min{MS(A′) ∶ A′ ´e permuta¸c˜ao de A} se A[i] ≥ 0 para todo i ent˜ao
1
retorne sum(A)
2 M ← max{A[i] ∶ 0 ≤ i < n} 3 se M ≤ 0 ent˜ao 4 retorne 0 5
B ← multiconjunto {−A[i] ∶ A[i] < 0}
6
P ← sequˆencia resultante da ordena¸c˜ao de B em ordem crescente
7
x ← max{sum(A), M}
8
se P[i] ≤ x para todo i ent˜ao
9 retorne x 10 i ← min{i ∶ P[i] > x} 11 b ← sum(A) + ∑j≥i(P[j] − x) 12 enquanto x< b fa¸ca 13 se b< P[i] ent˜ao 14 retorne b 15 y ← x 16 x ← P[i] 17
se P[j] = x para todo j ≥ i ent˜ao
18 retorne x 19 k ← i 20 i ← min{j ∶ P[j] > x} 21
b ← b − (n − k)(x − y) ; // ´E o mesmo que: b ← sum(A) + ∑j≥i(P[j] − x)
22
retorne x