O que é um algoritmo para minimizar o desvio padrão de M somas somadas a partir de n sumands?[com tentativa]

Question

Eu tenho mixas (somas) e n summands. Cada suposta vai entrar em uma lixeira. A fim de minimizar o desvio padrão, eu tenho um algoritmo ganancioso que parece realizar isso. Não tenho certeza do nome, mas gostaria de saber mais. Todas as caixas M devem ter uma soma maior que zero no final do algoritmo.

Parece simples:

Classifique o suficiente do mais alto para o menor.

para cada summand no summands: Encontre a primeira caixa disponível com soma mínima e coloque-a na bin

Eu não provou nada sobre isso, mas eu inventei alguns conjuntos de dados de teste e parece funcionar.

editar --- Aqui está a minha tentativa de uma análise:

O algoritmo procura minimizar o desvio padrão de M somas somadas a partir de n sumands.

A média é sempre a soma do sum sumands dividido por m, que é dado.

Para minimizar o desvio padrão, o algoritmo faz a escolha gananciosa para minimizar o desvio padrão ou variância (seja). Eu quero provar que a escolha gananciosa é sempre a escolha ideal.

Suponha que haja um bin M1, não a bin mínima, que é uma melhor escolha do que a soma mínima da soma. Adicionando a este bin minimizará o desvio padrão em torno de você.

Em outras palavras, colocando o próximo valor n para este m irá diminuir maximamente a variação, o que significa que diminuímos maximamente a soma de (m_i - u) ^ 2. Nota: m1 '= m1 + x, m'= m + x, onde x é o próximo summand.

Então: restant_sum_var + (m1 '- u) ^ 2 + (m - u) ^ 2

Simplifique e fator:

(m1 '- u) ^ 2 + (m - u) ^ 2 <(m' - u) ^ 2 + (m1 - u ^ 2)

M1 '^ 2 - 2um1' + 2U ^ 2 + M ^ 2 - 2um

m1 '^ 2 - 2um1' + m ^ 2 - 2um

Ignorando termos lineares cuja diferença será constante (linearidade).

m1 '^ 2 + m ^ 2

Se tivermos adicionado sumvo e x para m1 isso se expande para:

(M1 + x) ^ 2 + m ^ 2 <(M + X) ^ 2 + M1 ^ 2

m1 ^ 2 + 2m1x + x ^ 2 + m ^ 2

2m1x <2mx

m1

Answer 1

Não, seu algoritmo nem sempre produz a solução ideal.Quando $ m= 2 $ , isto é (pelo menos tão duro quanto) o Problema de partição , que é NP-Hard.Wikipedia discute o algoritmo ganancioso e lista um contraexemplo que mostra que o seu algoritmo não funciona.

Answer 2

Eu descobri que o algoritmo é o algoritmo LPT.Está coberto aqui junto com outros algoritmos para uma tarefa de exemplo: Agendamento em máquinas paralelas com trabalhos fixos.O problema é NP HARD e NP completo.Os algoritmos de tempo polinômio são aproximações.

https://depositonce.tu-berlin.de/bitstream/11303/11089/3/GRIGORIU_LILIANA_2019.pdf