Prova para o algoritmo solução do problema das caixas

Problema retirado do teste 8 do professor Carlos Brito, da disciplina de Contrução e Análise de Algoritmos (CAnA).

Problema:

Temos n caixas C1,…,Cn. Cada caixa Ci é utilizada Ki vezes e possui peso Pi. (Se i <> j podemos ter Ki<>Kj e Pi <> Pj).

As caixas devem ser organizadas em uma pilha <Ci1, Ci2,…,Cin> . O esforço realizado para utilizar a caixa Cij nesta pilha é definido por:

Eij = Kij * Somatorio {t=j até n} Pit

ou seja, o número de vezes que a caixa é utilizada multiplicado pela soma do seu peso com os pesos das caixas que estão acima dela na pilha.

O custo C da solução <Ci1, Ci2,…,Cin> é dado por

Max{Ei1, Ei2, … , Ein}

ou seja, o esforço máximo entre todas as caixas na pilha:

O problema consiste em encontrar uma solução para o problema que tenha custo mínimo.

Dado o algoritmo:

Organizar as caixas em ordem crescente de acordo com o número de vezes Ki que elas são utilizadas.

Pergunta-se, se o algoritmo está correto. Se sim, mostrar a prova de corretude. Se não, mostrar um contra exemplo e estimar a diferença entre a sua solução e a solução ótima, no pior caso.

Solução:

O algoritmo está correto.

Prova 1:

Essa foi a prova que a Cibele fez na aula de monitoria bem mais fácil.

Com duas caixas:Primeiro provamos que para uma instância do problema com duas caixas A e B ordenar é a melhor maneira.
Podemos organizar uma pilha com duas caixas A e B de duas maneiras:

Duas Pilhas
Pela definição do problema, o custo da maneira 1 é o maior desses custos:

  • KA*PA
  • KB*(PA+PB)

Se organizarmos as caixas da maneira 2, o custo será o maior desses custos:

  • KB*PB
  • KA*(PB+PA)

Queremos saber qual dessas duas maneiras de organizar as caixas é a melhor. Vamos supor, que KA ≥ KB, ou seja que a maneira 1 esta ordenada. Se isso é verdadeiro então KA*(PB+PA) é o maior termo de todos. Então a maneira 1 nos dá um custo menor que a da meneira 2 porque não importa qual dos termos foi o maior, ele será menor ou igual a KA*(PB+PA).

Analogamente, poderiamos ter escolhido KB ≥ KA. E então a maneira 2 seria a melhor, mas de toda forma esta seria a pilha estaria ordenada por K.

Então já está provado que para uma pilha de dois elementos, ordena-los nos dá o menor custo.

Com várias caixas:

Vamos observar uma pilha com muitos elementos. Vamos supor duas caixas A e B consecutivas no seu interior:

Duas Pilhas

Vamos supor que KA ≥ KB. Ou seja a pilha 1 não está ordenada pela ordem do algoritmo (pela ordem do algoritmo os Ks maoires ficam no topo da pilha). Vamos construir uma outra pilha idêntica a ela, a pilha 2, mas vamos trocar A e B de posição. Vamos análisar o custo dessas duas pilhas, há três lugares para se investigar.

Os elementos que estavam acima de B na pilha 1 continuaram em suas mesmas posições na pilha 2. Observe que suas funções de custo também continuaram iguais já que na hora de calcular o custo de uma caixa tudo o que importa é quem está acima da caixa, não importando como elas estão arranjadas. Se a maior parcela estava ai na pilha 1, ela continuará ai na pilha 2.

Os elementos que estavam abaixo de A na pilha 1 continuaram em suas mesmas posições na pilha 2. Observe que suas funções de custo também continuaram iguais afinal tudo o que importa é o custo de quem está acima dela, não importando a maneira de como elas estão arranjadas. Se a maior parcela estava ai na pilha 1, ela continuará ai na pilha 2.

Falta agora somente observar A e B, eles são os únicos que tem suas funções de custo afetadas quando olhamos a pilha 1 e a pilha 2. Vamos supor que o maior termo do função de custo da pilha vai será determinado por estes elementos.

Duas Pilhas em destaque

O custo da de A e B na pilha 1 é o maior destes termos:

  • KB*(PB+E)
  • KA*(PA+PB+E)

Onde E é o peso da pilha que está acima de B. O custo da pilha 2 é o maior destes termos:

  • KA*(PA+E)
  • KB*(PB+PA+E)

O maior de todos esses termos é KA*(PA+PB+E). Então o custo da pilha 2 será sempre menor ou igual o da pilha 1.

Ficou provado que ao trocar dois elementos fora de ordem os deixando em ordem conseguimos uma nova pilha que sempre terá um custo menor ou igual ao da pilha anterior.

Podemos fazer repetir essa operação várias vezes, deixando nossa pilha melhor. Essa operação não vai mais poder ser feita quando a pilha já estiver ordenada. Esse pilha ordenada é a pilha ótima. Como o algoritmo encontra esta mesma pilha, a pilha ordenada, então ele encontra a solução ótima.

Prova 2:

Seja S = <Ci1, Ci2, … , Ci(j-1), Cij, Ci(j+1), … , Cin> uma solução ótima diferente da encontrada pelo algoritmo.

Logo existe

Kij <= |Ki(j+1)

Ou seja, existem dois caras que estão fora da ordem (ou seja, S não está ordenado por K).

Seja S’ = <Ci1, Ci2, … , Ci(j-1), Ci(j+1), Cij, Ci(j+2), … , Cin>. Observe que S’ é construindo através de S, trocando dois elementos de lugar. Ou seja, pegando os dois elementos quaisquer que estavam fora de ordem e os rearrumando.

Pela otimalidade de S temos que:

C(S) <= C(S’)

Aplicando a definição de custo de uma solução:

Max{Ei1, Ei2, … , Ein} <= Max {Ei1, Ei2, … Ein}

Em particular temos

Max {Ei1, Ei2, … , Eij, Ei(j+1), … , Ein} <= Max {Ei1, Ei2, … , E’i(j+1), E’ij, … , Ein }

Note que os custos de quem está a direita de onde foi feita a troca para se construir S’, não mudou. Se o máximo estiver lá, então C(S) = C(S’). Senão, o máximo está em outro lugar.

Note que os custos de quem está a esquerda de onde foi feita a troca também não mudou. Se o máximo estiver lá, então C(S) = C(S’). Senão, o máximo está em outro lugar.

Então vamos olhar para os custos de quem mudou.

Max {Eij, Ei(j+1)} <= Max {E’i(j+1), E’ij }

Onde:

Eij = Kij * Somatorio {t=j até n} Pit

Ei(j+1) = Ki(j+1) * Somatorio {t=(j+1) até n} Pit

E’i(j+1) = Ki(j+1) * ( Pi(j+1)+ Pij + Somatorio {t=(j+2) até n} Pit )

E’ij = Kij * ( Pij + Somatorio {t=(j+2) até n} Pit )

Então:

Max { Kij * Somatorio {t=j até n} Pit , Ki(j+1) * Somatorio {t=(j+1) até n} Pit} <= Max {Ki(j+1) * ( Pi(j+1)+ Pij + Somatorio {t=(j+2) até n} Pit ) , Kij * ( Pij + Somatorio {t=(j+2) até n} Pit )}

Disso chegamos na contradição Kij > |Ki(j+1).

4 Comentários »

RSS feed for comments on this post. TrackBack URI

  1. A prova 2 está mal escria. Recomendo que se leia somente a prova 1.

  2. Bem vindo ao ano novo e boas festas

  3. Qual sera o impacto da crise financeira no sector publico? duvidas:+258847491854 / +258827111241


Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

Crie um website ou blog gratuito no WordPress.com.
Entries e comentários feeds.

%d blogueiros gostam disto: