Get best of the week

O livro “Algoritmo Perfeito. Algoritmos gananciosos e programação dinâmica »

imagemOlá, habrozhiteli! No novo livro, Tim Rafgarden fala sobre algoritmos gananciosos (o problema de planejamento, árvores abrangentes mínimas, clustering, códigos Huffman) e programação dinâmica (o problema da mochila, alinhamento de sequências, caminhos mais curtos, árvores de pesquisa ideais). Este post apresenta um trecho "Desenvolvendo um algoritmo ganancioso". Os algoritmos

gananciosos parecem bem adequados à tarefa de agendar trabalhos, minimizando a soma ponderada dos tempos de conclusão. A saída tem uma estrutura iterativa, onde o trabalho é processado um de cada vez. Por que não usar um algoritmo ganancioso que decide iterativamente qual trabalho será o próximo?

O primeiro passo do nosso plano é resolver dois casos especiais do problema geral. Nossas soluções para esses casos mostrarão como um algoritmo ganancioso pode parecer no caso geral. Em seguida, reduzimos o domínio a um algoritmo candidato e provamos que é esse candidato que resolve o problema corretamente. O processo pelo qual chegamos a esse algoritmo é mais importante para lembrar do que o próprio algoritmo; esse processo é repetitivo e você pode usá-lo em seus próprios aplicativos.

13.3.1 Dois casos especiais


Vamos supor que, para a tarefa de minimizar a soma ponderada das datas de conclusão, de fato, exista um algoritmo guloso correto. Como seria se assumíssemos que todos os trabalhos têm o mesmo comprimento (mas possivelmente pesos diferentes) ou, inversamente, o mesmo peso (mas possivelmente comprimentos diferentes)?
13.2

(1) , ?
(2) , ?
) ;
) ;
) ;
) ;
( . 13.3.3.)

13.3.2.


Em geral, o trabalho pode ter pesos e comprimentos diferentes. Sempre que nossas duas regras práticas - para preferir um trabalho mais curto e com pesos mais altos - têm a sorte de dois empregos coincidirem, sabemos qual deles planejar primeiro (mais curto com pesos mais altos). Mas e se essas duas regras derem conselhos conflitantes? O que devemos fazer com um trabalho curto com baixo peso e um trabalho longo com alto peso?

Qual será o algoritmo ganancioso mais simples que funcionará como deveria? Cada trabalho possui dois parâmetros, e o algoritmo deve considerar os dois. A melhor opção seria desenvolver uma fórmula que compila o comprimento e o peso de cada trabalho em uma única marca (contribuição), para garantir o planejamento do trabalho da nota mais alta à mais baixa para minimizar a quantidade de datas de conclusão ponderadas. Se essa fórmula existe, a partir de nossos dois casos particulares, segue-se que ela deve ter duas propriedades: (i) deixando o comprimento fixo, deve aumentar pelo peso da obra; (ii) deixando o peso fixo, deve diminuir a duração do trabalho (lembre-se de que quanto maior a marca, melhor). Passe um minuto discutindo várias fórmulas que possuem essas duas propriedades.

imagem

Talvez a função mais simples, que aumenta de peso e diminua de comprimento, seja a diferença entre elas:
proposta nº 1. para a marca da imagem

obra.A marca indicada pode ser negativa, mas isso não coloca obstáculos à construção consistente de obras da marca mais alta à mais baixa . No entanto, existem muitas outras opções. Por exemplo, a proporção de dois parâmetros é outro candidato: a

proposta nº 2. para marcar o trabalho.Estas imagem

duas funções para calcular a marca levam a dois algoritmos gananciosos diferentes.
DIFERENÇA DE GREEDY GREEDYDIFF

Planeje o trabalho em ordem decrescente imagem
(interrompendo arbitrariamente a coincidência de valores).
GREEDYRATIO

imagem
( ).

Portanto, nosso primeiro estudo de caso ilustra o primeiro tópico do paradigma ganancioso (seção 13.1.2): geralmente não é difícil propor vários algoritmos gananciosos concorrentes para uma tarefa. Mas qual dos dois algoritmos, se houver, está correto? Uma maneira rápida de excluir um deles é encontrar uma instância na qual dois algoritmos exibam agendamentos diferentes com valores diferentes da função objetivo. Para qualquer algoritmo cujos resultados são piores neste exemplo, podemos concluir que nem sempre é o ideal. Em dois casos especiais com trabalhos do mesmo peso ou do mesmo comprimento, ambos os algoritmos agem corretamente. O exemplo mais simples possível da exclusão de uma delas pode ser uma instância de uma tarefa na qual duas obras têm pesos e comprimentos diferentes,como resultado, ambos os algoritmos planejam trabalhar em ordens opostas. Ou seja, estamos procurando duas obras, cuja ordem é diferente da ordem em relação à sua diferença. Exemplo:

imagem

O primeiro trabalho tem uma proporção maior e maior, imagemmas uma diferença maior (–2 vs. –1). Assim, o algoritmo GreedyDiffplaneja o segundo trabalho primeiro, enquanto o algoritmo GreedyRatioplaneja o oposto.
EXERCÍCIO 13.3

Qual é a soma das datas de conclusão ponderada nos planejamentos deduzidos pelos algoritmos GreedyDiffe , respectivamente GreedyRatio?

a) 22 e 23
b) 23 e 22
c) 17 e 17
d) 17 e 11
(Para uma solução e explicação, consulte a seção 13.3.3.)

Avançamos excluindo o algoritmo GreedyDiffde uma análise mais aprofundada. No entanto, o resultado do exercício 13.3 não leva diretamente ao fato de que o algoritmo GreedyRatioserá sempre ideal. Até onde sabemos, há outros casos em que esse algoritmo produz um cronograma não ideal. Você sempre deve ser cético em relação a um algoritmo que não é acompanhado por uma prova de sua correção, mesmo que esse algoritmo faça a coisa certa em vários casos de teste e seja extremamente cético em relação a algoritmos gananciosos.

No nosso caso, o algoritmo GreedyRatio, de fato, é garantido para minimizar a quantidade de datas de conclusão ponderadas.

Teorema 13.1 (a correção do algoritmo GreedyRatio) . Para cada conjunto de pesos de trabalho positivosimageme comprimentos de trabalho positivos, o imagemalgoritmo GreedyRatioexibe uma programação com a menor soma possível de datas de conclusão ponderadas.

Essa afirmação lógica não é óbvia e você não deve confiar nele sem receber evidências. De acordo com o terceiro tema do paradigma ganancioso (seção 13.1.2), essa prova ocupa a próxima seção inteira.
, . .

. — , ( ). — , , , . «» ( ) , .

O tema restante do paradigma ganancioso é a simplicidade da análise em tempo de execução (seção 13.1.2). Aqui, é claro, é isso. O algoritmo GreedyRatio classifica apenas os trabalhos por relação, o que leva tempo O (n log n), em que n é o número de trabalhos na entrada (consulte a nota de rodapé 1 na p. 24).

13.3.3 Soluções para Exercícios 13.2–13.3


A solução para o exercício 13.2 A

resposta correta é: (a) . Primeiro, suponha que todos os n trabalhos tenham o mesmo tamanho, digamos 1. Então, cada agendamento tem exatamente o mesmo conjunto de prazos - {1, 2, 3, ..., n} - e a única pergunta é que tipo de trabalho recebe data de conclusão e qual é o prazo. Nossa semântica para pesos de trabalho certamente implica que o trabalho com maior peso deve receber tempos de conclusão mais curtos, e isso é verdade. Por exemplo, você não gostaria de planejar um trabalho com um peso de 10 terços (com um prazo final de 3) e trabalhar com um peso de 20 quintos (com um prazo de 5); seria melhor alterar as posições desses dois trabalhos, o que reduziria a soma dos prazos de conclusão ponderada em 20 (como você pode ver por si mesmo).

O segundo caso, no qual todas as obras têm o mesmo peso, é um pouco mais fino. Aqui você deseja dar preferência a trabalhos mais curtos. Por exemplo, considere dois trabalhos de peso unitário com comprimentos de 1 e 2. Se você planeja primeiro um trabalho mais curto, os prazos de conclusão serão 1 e 3 com um total de 4. Na ordem inversa, os prazos serão 2 e 3 com o pior resultado 5. Em geral, o planejado o trabalho primeiro contribui para o tempo de conclusão de todo o trabalho, uma vez que todo o trabalho deve aguardar a conclusão do primeiro. Tudo igual, planejar o trabalho mais curto primeiro minimiza esse impacto negativo. O segundo contribui de trabalho para todas as datas de conclusão, exceto o primeiro emprego, para que o trabalho segunda menor devem ser planejadas seguinte, e assim por diante.

Solução de exercício 13,3

A resposta correta é b). O algoritmo GreedyDiffplaneja primeiro um segundo trabalho. O prazo para concluir este trabalho é imagemque o prazo para concluir outro trabalho é imagemSoma dos prazos ponderados para o término

imagem

O algoritmo GreedyRatioplaneja o primeiro trabalho primeiro, resultando em prazos imagem
e a soma dos prazos ponderados iguais a

imagem

Como o algoritmo GreedyDifffalha ao calcular a programação ideal para este exemplo , ele nem sempre está correto.

»Mais informações sobre o livro podem ser encontradas no site da editora
» Conteúdo
» Trecho

Para Khabrozhiteley desconto de 25% no cupom - Algoritmos

Após o pagamento da versão impressa do livro, um livro eletrônico é enviado por e-mail.

More articles:


All Articles