Você já teve um requisito de negócios que acabou por ser um problema NP-completo?

Question

NP-completude parece-me como uma daquelas coisas que é na maior parte apenas teórica, e não é algo que você executar em um ambiente de trabalho normal.

Então, eu sou do tipo curioso, se alguém está já se deparou com um problema em seu trabalho que acabou por ser NP-completo, e que o projeto precisava ser mudado para acomodar para ele?

Answer 1

Como os outros declarou, a mochila (para embalagem de carga) e vendedores ambulantes problema são provavelmente os mais comuns "mundo real" problemas NP-completos.

I tendem a ter problemas no trabalho que não pode ser provado ser NP completo ou incompleto porque não está muito bem definido.

Answer 2

Qualquer tipo de ferramenta de mapeamento, onde você precisa encontrar pontos de viagem ideais entre mais de dois locais podem sem quaisquer alterações tornar-se um problema NP-completo

Answer 3

O problema de otimizar picking onda de um depósito é equivalente ao problema do caixeiro viajante .

Isto é, você tem N-ordens esperando para ser escolhido, e você quer encontrar as melhores n ordens para minimizar a distância percorrida e locais diferentes picareta visitados por um selecionador.

Recentemente, deparei com este problema. Nós punted e usou uma aproximação que irá funcionar bem para o caso médio, mas às vezes pode fornecer resultados sub-óptima.

Answer 4

Além disso, o problema da mochila (que é NP-hard) aparece com bastante frequência. É uma armadilha sedutora para tentar coisas otimizar.

Answer 5

É importante notar que existem técnicas de aproximação heurísticas para obtenção do "suficientemente bom" respostas para problemas NP-completos, como o recozimento simulado e recozimento comprimido. Se você pode reduzir o seu problema NP-completa para o problema do caixeiro viajante, você pode usar essas abordagens. (Qualquer problema NP-completo pode ser reduzido a qualquer outro problema NP-completo, mas na verdade fazendo isso às vezes é uma dor na bunda.)

-recozimento simulado De qualquer forma, não são e comprimido-recozimento implementações lá fora; um tal é Djinni , que é escrito em C ++ e tem ligações Python.

Answer 6

Eu concordei em software de gravação para o pai de um amigo quando eu era um estudante universitário de primeiro ano. Foi por recursos de agendamento. Eu não percebi isso na época, mas acabou por ser um problema NP completo.

Felizmente apenas encontrar uma solução aceitável - não precisa encontrar a solução ideal. Foi divertido escrever heurística - na verdade um conjunto deles - que poderia ser mudado enquanto o programa estava correndo e tentando resolver o problema.

Eu tinha uma solução feita de verão, mas, em seguida, trabalhou em novas versões a cada ano sucessivo. Meus grandes planos para vender caiu plana. Eu era um desenvolvedor melhor do comerciante.

Foi muito divertido e me ensinou desde cedo muito sobre o mundo real de desenvolvimento - (usuários finais, coleta de requisitos, testes, etc - um monte de coisas que você não ficar no CS graduação)

Para resolver a sua pergunta - que era para um professor que teve a estudantes de agendamento para instrução especial. Ele era um Fonoaudióloga - mas poderia ser aplicado a qualquer campo semelhante. Ele havia existente professor, sala de aula e atividades estudantis para contornar e teve que atender um número específico de vezes por semana com os alunos. É o problema da mochila ou qualquer número de outros problemas de programação semelhantes / equivalente.

Mais uma vez, descobriu-se que apenas começando uma solução estava bem - nós não têm para maximizar ou minimizar qualquer coisa - nós apenas tivemos que acomodar todos os alunos.

Eu só posso recordar não ser capaz de resolver os casos de teste que eu usei para executar cenários - todos os problemas que ele prestados ao longo dos anos temos resolvido.

Eu nunca fui capaz de comercializá-lo - principalmente porque eu não tinha idéia do que eu estava fazendo e eu não tinha certeza de como alcançar meu mercado / compradores.

Answer 7

O problema caixeiro-viajante é um exemplo perfeito. O mesmo tipo de problemas logísticos se aplicam a companhias aéreas, correios, e todos os tipos de indústrias.

Answer 8

Outro exemplo é que as empresas com centros de distribuição regionais, especialmente aqueles que entregar diretamente para o cliente (por exemplo, Netflix), precisa se preocupar com a família de NP-completos problemas conhecidos como local instalação .

Na verdade, a idéia de que os problemas NP-completos são relevantes no mundo real é evidenciado pelo fato de que algoritmos de aproximação para eles tão freqüentemente aparecem em revistas de pesquisa operacional.

Answer 9

Eu estava trabalhando em um programa de mapeamento de alguns anos atrás, como um nativo do Google Maps. Coloquei pequenos marcadores no mapa para locais, mas um monte de marcadores foram agrupados de perto em determinados locais. Meu chefe disse: "deixe-me fazer isso para que eu pode simplesmente arrastar os marcadores afastado um pouco" (e ele teria uma linha ou speech-bubble-ponteiro coisinha que vai do marcador para a localização real).

Eu pensei que era bobagem para fazer o usuário fazer isso, especialmente desde que ele gastaria 5 minutos tornando-o perfeito, e, em seguida, mudar o nível de zoom, e então tudo seria errado.

Eu decidi tentar escrever uma função para encontrar uma maneira de colocar para fora as etiquetas de tal forma que a distância ecrã total de cada rótulo para a sua localização foi minimizado. Eu acredito que eu me convenci no momento em que este foi NP-completos, mas que o número de pontos pode ser pequeno o suficiente para que ele ainda ser viável, pelo menos em muitos casos. (Lembro-me de pensar que passamos tempo demais na classe em provas NP-completo, e não o suficiente sobre soluções alternativas: se o seu chefe quer que algo seja feito, você não pode simplesmente dizer "NP duro, não vai fazer" - você ainda tem que vir acima com algo .)

Em seguida, o Google Maps veio e apenas splatted todos os rótulos em cima uns dos outros, que suga totalmente (e eu amaldiçoá-lo todos os dias), mas eu não posso competir com suas outras características, então eu desisti. : - (