Introdução
Seja uma sequência \(S\) de \(x\) pontos. Apresenta-se os índices da sequência \(S\), os pontos \(x\), que geram a maior variação positiva nessa sequência.
Para ilustrar apresenta-se o seguinte exemplo:
Suponha que \(x_{0} = 3\), \(x_{1} = 5\), \(x_{2} = 2\), \(x_{3} = 9\) e \(x_{4} = 10\). Logo pode-se observar que o resultado procurado é índice 2 \((x_{2} = 2)\) e o índice 4 \((x_{4}=10)\), com variação positiva de 8.
Força Bruta
A força bruta é um procedimento direto para resolver um problema tendo como base a definição deste problema e os conceitos diretamente envolvidos. Na ciência da computação, busca por força bruta ou busca exaustiva, também conhecido como gerar e testar, é uma técnica de solução de problemas trivial, porém muito geral que consiste em enumerar todos os possíveis candidatos da solução e checar cada candidato para saber se ele satisfaz o enunciado do problema.
Para aplicar busca por força bruta para uma classe específica de problemas, é preciso implementar quatro procedimentos, sendo estes: primeiro, próximo, válido, e saída. Estes procedimentos devem ter como parâmetro os dados \(P\) para a instância do problema que será resolvido, e deve fazer o seguinte:
- primeiro \((P)\): gera o primeiro candidato à solução de \(P\).
- próximo \((P, C)\): gera o próximo candidato de \(P\) depois de \(C\).
- válido \((P, C)\): checa se o candidato \(C\) é a solução de \(P\).
- saída \((P, C)\): usa a solução \(C\) de \(P\) como for conveniente para a aplicação.
O procedimento próximo também deve dizer quando não há mais candidatos à \(P\), após o \(C\) atual. Uma maneira conveniente de fazer isto é retornando um "candidato nulo", um valor de dados comum \(Λ\) que é distinto de qualquer outro candidato real. Da mesma maneira primeiro deve retornar \(Λ\) se não houver nenhum candidato para a instância \(P\).
O código força bruta para encontrar a maior variação positiva de uma sequência implementado em Python segue abaixo.
Em primeiro plano importa-se a biblioteca \(numpy\) para gerar uma distância máxima de números infinitamente pequenos, como critério de começo do algorítimo.
import numpy as np
Posteriormente, defini-se a função \(diff\_max\) e parâmetros que irão compor a iteração do processo.
def diff_max(x):
n = len(x)
dist_max = -np.inf
diff =[]
A função \(diff\_max\) possui apenas um parâmetro que corresponde a \(x\) a lista que compõe a sequência de números analisados.
Em seguida utiliza-se da iteração ao longo da sequência, um \(for\) de \(i\) que vai do primeiro elemento até o penúltimo e um \(for\) de \(j\) que vai de \(i+1\) até o último elemento. Esse intervalo garante que a iteração não ultrapasse os limites da sequência, pois realiza-se a diferença positiva entre um a um dos elementos. A primeira condicionante atribui ao \(dist\_max\) a variação do momento da iteração. Nesta condicionante cria-se uma lista de índices \(i\) e \(j\) e uma valor atribuído a diferença. A segunda condicionante encontra o máximo dessas diferenças positivas e posteriormente armazena o valor de \(diff\). No final retorna \(diff\) que é uma lista de uma lista de índices e do valor máximo encontrado.
for i in range(0,n-1):
for j in range(i+1, n):
if x[j] - x[i] == dist_max:
diff.append([[i,j], dist_max])
if x[j] - x[i] > dist_max:
dist_max = x[j] - x[i]
diff = [[i,j], dist_max]
return (diff)
A última parte do código define a lista e chama a função que calcula a distância positiva máxima entre os números \(x\) que compõem a lista que contem a sequência \(S\).
if __name__ == '__main__':
x = [5, 3, 8, 1, 9, 7, 2, 4, 6, 7, 2, 4, 6, 8, 9, 8, 7]
print(diff_max(x))
O resultado encontrado para este exemplo é:
[[3, 4], 8, [[3, 14], 8]]
O resultado mostra que a diferença entre o índice 4 e o índice 3 resultou em um valor de 8 unidades, assim como a diferença entre os índices 14 e 3.
Observa-se que o algoritmo acima tem complexidade na ordem de \(O(n^2)\), pois há uma comparação de \(n\) com \(n-1\), devido aos dois \(for\) do código. Sendo a complexidade \(O(n^2)\) assintótica.
Divisão e Conquista
A estratégia de dividir para conquistar transforma o problema em subproblemas que são similares ao problema original, então resolva-os de forma recursiva. Como a estratégia de dividir para conquistar resolve subproblemas recursivamente, cada problema deve ser menor que o problema original. O algoritmo de divisão e conquista possui três partes:
- Divida o problema em subproblemas que são menores do que problema original.
- Conquiste os subproblemas resolvendo-os recursivamente. Se estes subproblemas são menores o suficiente resolva-os como caso básico.
- Combine, concatene as soluções dos subproblemas em uma solução do problema original.
Para encontrar a maior diferença positiva entre dois números de uma sequência utilizando a estratégia de divisão e conquista. Fazer-á um código que gere um merge sort e ordena a sequência, depois o código irá comparar os primeiros números com os últimos da lista. Assim gerando a mair diferença positiva entre dois números de uma sequência.
Merge Sort
Como neste exercício usa-se divisão e conquista para ordenar, precisamos decidir quais serão nossos subproblemas. O problema completo é ordenar um array inteiro. Vamos dizer que um subproblema é ordenar um subarray. Em particular, iremos pensar em um subproblema como ordenar o subarray começando de um índice \(p\) e continuamos através do índice \(r\). Isso será conveniente para termos uma notação para um subarray, então vamos dizer que \(array[p..r] \) denota o subarray de array.
A figura abaixo Ilustra o problema:
Fonte: Khanacademy
O código em Python segue abaixo:
Em primeiro plano importa-se a biblioteca \(numpy\).
import numpy as np
Na segunda parte do código defini-se a função que irá mergiar (concatenar os subproblemas). Nessa função o algoritmo concatena os subarrays mencionados na figura acima.
def merge(x, y):
nx = len(x)
ny = len(y)
z = np.empty([nx + ny], int)
i = 0
j = 0
cont = -1;
while ((i <= nx - 1) and (j <= ny - 1)):
cont = cont + 1
if (x[i] < y[j]):
z[cont] = x[i]
i = i + 1
else:
z[cont] = y[j]
j = j + 1
if (cont < nx + ny - 1):
if (i <= nx - 1):
for k in range(cont + 1, nx + ny):
z[k] = x[i]
i = i + 1
else:
for k in range(cont + 1, nx + ny):
z[k] = y[j]
j = j + 1
return z
A função abaixo realiza-se a divisão recursivamente dos subproblemas, transformando a sequência em partes cada vez menores. Observa-se a recursividade ao ver que a função chama ela mesma, transformando uma sequência maior em pequenas subsequências, como pode ser visto na ilustração acima.
def merge_sort(a):
n = a.size
if (n > 1):
b = a[0:n // 2]
c = a[n // 2:n]
b = merge_sort(b)
c = merge_sort(c)
a = merge(b, c)
return a
Após a ordenação dos vetores, realizada pela estratégia de divisão e conquista pelo merge sort, a última função armazena os primeiros números em um vetor que se chama \(lista1\) e os últimos números em um vetor que se chama \(lista2\). Ao fazer a diferença dos vetores na \(lista2\) com os da \(lista1\) obtemos a maior diferença. Observa-se que se os números iniciais são iguais aos finais o código os armazena nas lista determinadas.
def order_diff_max(d):
control = list(d)
n = len(d)
lista1 = []
lista2 = []
classificado = merge_sort(d)
dif = classificado[n-1] - classificado[0]
for i in range(0, n):
if classificado[0] == d[i]:
lista1.append(i)
if classificado[n - 1] == d[i]:
lista2.append(i)
return [lista1, lista2, dif]
Abaixo é chamada as funções e demonstrado o resultado.
if __name__ == '__main__':
x = np.array([5, 3, 8, 1, 9, 7, 2, 4, 6, 7, 2, 4, 6, 8, 9, 8, 7])
print "Merge sort:"
print merge_sort(x)
print "order_diff_max:"
print order_diff_max(x)
Resultado:
Merge sort:
[1 2 2 3 4 4 5 6 6 7 7 7 8 8 8 9 9]
order_diff_max:
[[3], [4, 14], 8]
Observa-se que o resultado é o mesmo do encontrado no problema de força bruta, a diferença entre os índices 4 e 3 e os índices 14 e 3 da sequência apresentam 8 unidades.
A diferença deste algoritmo para o de força bruta é que como o de força bruta compara cada elemento da sequência este possui complexidade na ordem de \(O(n^2)\), já o algoritmo que usa ordenação possui menor complexidade. Observa-se que o algoritmo merge sorte possui complexidade \(O(n\ log\ n)\). Note que a relação de recorrência é :
\[T(n) = 2T\left( \frac{n}{2}\right) + O(n)\]
Com \(T(1) = 0\), sendo esse o caso 2 do Teorema Mestre. Como o código apresenta mais uma operação linear para guardar os primeiros e últimos valores da sequência e depois tirar a diferença este código possui mais uma complexidade de ordem \(n\), porém a complexidade assintótica continua a mesma que é de \(O(n\ log\ n)\).
Referências
Força Bruta .
Divisão e Conquista.
Merge Sort.