Tidsperiode

Al´em de melhorar a complexidade da heur´ıstica de ordena¸c˜ao por inser¸c˜ao ´otima (em rela¸c˜ao a uma implementa¸c˜ao direta por meio do algoritmo de Kadane), os algoritmos de consulta do Cap´ıtulo 3 tamb´em levam a uma implementa¸c˜ao eficiente de um algoritmo de subida de colina (hill climbing) para o problema SMSP. O algoritmo de subida de colina ´e um tipo de busca local, e portanto funciona partindo de uma solu¸c˜ao inicial e iterativamente passando da solu¸c˜ao corrente a outra melhor, at´e que nenhuma solu¸c˜ao melhor que a corrente seja encontrada; al´em disso, em cada itera¸c˜ao apenas a chamada vizinhan¸ca da solu¸c˜ao corrente —que normalmente ´e um subconjunto restrito do espa¸co de solu¸c˜oes completo— ´e considerada na busca por melhores solu¸c˜oes. No caso particular do algoritmo de subida de colina (na vers˜ao de subida mais ´ıngreme), a busca por melhores

solu¸c˜oes em cada itera¸c˜ao necessariamente examina a totalidade da vizinhan¸ca da solu¸c˜ao corrente, e a melhor solu¸c˜ao desse conjunto ´e escolhida (31, ➜4.1.1).

A estrat´egia de busca por subida de colina pode ser facilmente utilizada no problema SMSP. Dadas uma matriz m× n A e um ´ındice i ∈ [0 .. n − 1], n´os podemos definir a vizi- nhan¸ca de A como o conjunto das matrizes que resultam do reposicionamento da coluna A[i] em A. Logo, a seguinte estrat´egia ´e essencialmente um algoritmo de subida de colina para o problema SMSP: partindo de uma matriz de entrada, selecione uma coluna da matriz corrente e a reposicione, escolhendo, dentre todas as posi¸c˜oes poss´ıveis para essa coluna, uma que minimize o custo da matriz resultante; em seguida, caso a opera¸c˜ao de reposicionamento tenha levado a uma solu¸c˜ao de melhor valor, repita o processo, seleci- onando nova coluna. Atente para o fato de que a referida opera¸c˜ao de reposicionamento de coluna pode ser implementada primeiramente removendo-se a coluna selecionada A[i] da matriz corrente A, obtendo-se uma matriz A′, e em seguida inserindo-se a coluna A[i] na matriz A′ por meio do algoritmo de inser¸c˜ao ´otima para matrizes; em consequˆencia dos nossos resultados anteriores (➜3.3), a opera¸c˜ao em quest˜ao pode ser implementada de forma a executar em tempo O(m ⋅ n), isto ´e, em tempo linear sobre o tamanho de A.

4.3.1

Estrat´egias de Escolha de Coluna

Observe que, no algoritmo de subida de colina descrito acima, a vizinhan¸ca de uma solu¸c˜ao apenas est´a definida quando ´e escolhida uma coluna da matriz para a opera¸c˜ao de reposicionamento, o que abre espa¸co para diferentes estrat´egias de escolha dessa coluna. Neste trabalho n´os concebemos, implementamos e avaliamos duas tais estrat´egias. A pri- meira delas ´e simplesmente a escolha sucessiva de todas as colunas da matriz ao longo das itera¸c˜oes do algoritmo de busca, segundo uma ordem circular na qual cada coluna ocorre exatamente uma vez (agendamento round-robin); essa ordem ´e definida aleatoria- mente no in´ıcio do algoritmo e utilizada at´e o fim da sua execu¸c˜ao. Essa estrat´egia tem caracter´ısticas positivas, como a simplicidade de implementa¸c˜ao, a variedade das colunas escolhidas e a rapidez de execu¸c˜ao; observe que esta ´ultima caracter´ıstica ´e importante, pois a opera¸c˜ao de reposicionamento da coluna escolhida, embora tenha complexidade linear, j´a ´e por si s´o custosa para um algoritmo de busca, onde itera¸c˜oes mais r´apidas implicam numa maior parcela explorada do espa¸co de solu¸c˜oes.

A segunda estrat´egia de sele¸c˜ao de coluna que n´os implementamos para o algoritmo de subida de colina possui um crit´erio de escolha mais elaborado que o da primeira, e tem como objetivo selecionar a coluna que tenha o maior potencial para diminuir o valor da matriz corrente. A estrat´egia consiste em associar a cada coluna da matriz uma penaliza¸c˜ao, e ent˜ao escolher uma das colunas mais penalizadas, realizando desempates aleat´orios. O valor de penaliza¸c˜ao atribu´ıdo a cada coluna ´e diferente no problema SMSP e na sua varia¸c˜ao de m´aximo. No caso do problema SMSP, cada elemento da matriz recebe uma penaliza¸c˜ao, e a penaliza¸c˜ao de cada coluna ´e a soma das penaliza¸c˜oes dos

seus elementos. A atribui¸c˜ao de penaliza¸c˜oes aos elementos da matriz ´e feita linha-a-linha; em cada linha, a ideia ´e penalizar os elementos positivos e pontuar os elementos negativos que fa¸cam parte de uma subsequˆencia de soma m´axima, dessa forma incentivando o deslocamento de elementos que est˜ao contribuindo para o aumento da soma m´axima da linha em quest˜ao, e desestimulando o deslocamento de elementos que est˜ao contribuindo para a diminui¸c˜ao dessa soma m´axima. A fun¸c˜ao de penaliza¸c˜ao utilizada em cada linha ´e a seguinte:

1. Se todos os elementos da linha s˜ao n˜ao-negativos, ou se todos s˜ao n˜ao-positivos, ent˜ao todos recebem penaliza¸c˜ao zero, pois a soma m´axima da linha em quest˜ao independe da ordem dos seus elementos.

2. Se a linha possui tanto elementos positivos quanto negativos, e se algum elemento da linha possui soma m´axima negativa, ent˜ao cada elemento que n˜ao pertence a uma subsequˆencia de soma m´axima recebe penaliza¸c˜ao zero, e cada um dos demais ele- mentos ´e “penalizado” com o seu pr´oprio valor. Observe que n´umeros negativos que pertencem a uma subsequˆencia de soma m´axima recebem “penaliza¸c˜ao negativa”, isto ´e, s˜ao “pontuados”.

3. Finalmente, se a linha possui elementos negativos e positivos e al´em disso todos os seus elementos possuem soma m´axima n˜ao-negativa, ent˜ao os elementos s˜ao pe- nalizados da mesma forma que no item anterior, exceto se cada elemento da linha pertencer a alguma subsequˆencia de soma m´axima, caso em que todos recebem penaliza¸c˜ao zero.

No caso da varia¸c˜ao de m´aximo do problema SMSP, as penaliza¸c˜oes s˜ao calculadas de forma semelhante `aquela acima, com a diferen¸ca de que a penaliza¸c˜ao de cada ele- mento A[i, j] ´e ao final multiplicada pelo “peso” da linha A_[i], o qual n´os definimos como MCS(A_[i])/custo(A), onde custo(A) = maxm−1

j=0 MCS(A[j]). Assim, por exemplo,

se uma certa matriz A tem custo 25, se um certo elemento A[i, j] = 5 pertence a uma subsequˆencia de soma m´axima da linha A_[i], e se MCS(A_[i]) = 25, ent˜ao A[i, j] recebe 5 como penaliza¸c˜ao final; por outro lado, se MCS(A_[i]) = 5, ent˜ao A[i, j] recebe apenas 1 como penaliza¸c˜ao final. A ideia por tr´as desse c´alculo ´e, por um lado, concentrar a pena- liza¸c˜ao nas linhas de maior soma m´axima, e, por outro lado, n˜ao ignorar os elementos das demais linhas, penalizando-os proporcionalmente `a chance (heuristicamente estimada) de eles virem a influenciar o custo da matriz em itera¸c˜oes posteriores.

A nossa implementa¸c˜ao da segunda estrat´egia de sele¸c˜ao de colunas para o algoritmo de subida de colina executa em O(m⋅n), de forma que cada itera¸c˜ao da busca ´e realizada em tempo linear, como no caso da primeira estrat´egia. Entretanto, ´e ´obvio que na pr´atica a segunda estrat´egia ´e mais custosa, aumentando o tempo necess´ario para cada itera¸c˜ao e portanto diminuindo o n´umero de itera¸c˜oes que a busca pode realizar dentro de um mesmo

intervalo de tempo em rela¸c˜ao `a primeira estrat´egia. Por outro lado, a segunda estrat´egia realiza uma escolha mais criteriosa das colunas a serem reposicionadas, possuindo por- tanto potencial para a realiza¸c˜ao de itera¸c˜oes mais efetivas (em termos da diminui¸c˜ao do valor da solu¸c˜ao corrente) que aquelas da primeira estrat´egia. N´os realizamos um estudo emp´ırico de compara¸c˜ao das duas estrat´egias, o qual n´os apresentamos posteriormente neste cap´ıtulo.