problema NP-completo possível?
https://stackoverflow.com/questions/956699
-
12-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu apenas gostaria de alguém para verificar se o seguinte problema é NP-completo ou se há realmente uma solução melhor / mais fácil para ele do que simples verificação combinação de força bruta.
Nós temos uma espécie de recurso problema de alocação em nosso software, e eu vou explicar com um exemplo.
Vamos dizer que precisamos de 4 pessoas para estar no trabalho durante o dia-shift. Este número, eo fato de que é um "dia-shift" registada na nossa base de dados.
No entanto, nós não exigem qualquer um para preencher essas manchas, há alguns requisitos que precisa ser preenchido de forma a caber a conta.
Daqueles 4, digamos 2 deles tem que ser uma enfermeira, e um deles tem de ser médicos.
Um dos médicos também tem de trabalhar como parte de uma equipe particular.
Então nós temos esse conjunto de informações:
Dia-shift: 4
1 médico
1 médico, necessidade de trabalho em equipe A
1 enfermeiro
O acima não é o problema. O problema vem quando começar a escolher as pessoas para trabalhar no dia-shift e tentando descobrir se as pessoas que você escolheu até agora pode realmente preencher os critérios.
Por exemplo, digamos que nós escolhemos James, John, Ursula e Mary ao trabalho, onde James e Ursula são médicos, John e Mary são enfermeiros.
Ursula também trabalha em equipa A.
Agora, dependendo da ordem tentamos encaixar o projeto de lei, que pode acabar deduzindo que temos as pessoas certas, ou não, a menos que começar a tentar combinações diferentes.
Por exemplo, se descer a lista e escolher Ursula primeira, que poderia coincidir com ela com os critérios "1 médico". Então nós começamos a James, e percebe-se que uma vez que ele não funciona na equipa A, os outros critérios sobre "1 médico, necessidade de trabalho em equipe A", não pode ser preenchido com ele. Desde as outras duas pessoas são enfermeiros, eles não se encaixam que os critérios de qualquer um.
Então, nós recuar e tentar James primeiro, e ele também pode caber o primeiro critério, e depois Ursula pode caber os critérios que precisam dessa equipe.
Assim, os olhares Problema para nós como nós precisamos tentar combinações diferentes até que tenhamos tanto tentei todos eles, caso em que temos alguns critérios que ainda não estão preenchidos, mesmo que o número total de cabeças de trabalho é o mesmo como o número total de cabeças necessário, ou nós encontramos uma combinação que funciona.
É esta a única solução, alguém pode pensar em um melhor?
Editar :. Alguns esclarecimentos
Comentário para esta questão menciona que com este poucas pessoas, devemos ir com força bruta, e eu concordo, que é provavelmente o que poderíamos fazer, e podemos até fazer isso, na mesma pista que algumas otimizações de ordenação olhar o tamanho dos dados e escolhe diferentes algoritmos de ordenação com sobrecarga menos inicial, se o tamanho dos dados é pequeno.
O problema, porém, é que isso é parte de um sistema de planejamento de lista, em que você pode ter um número bastante algumas das pessoas envolvidas, tanto como "Precisamos de pessoas X no turno do dia", bem como "Temos este piscina de pessoas Y que vai fazer isso", bem como o potencial para um grande 'temos esta lista de critérios de Z para os X pessoas que terão de alguma forma corresponder-se com essas pessoas Y', e, em seguida, você adicionar ao fato de que teremos um número de dias para fazer o mesmo cálculo para, em tempo real, como o líder ajusta a lista, e, em seguida, a necessidade de uma solução rápida veio acima.
Basicamente, o líder verá uma informação soma ao vivo na tela que diz quantas pessoas ainda estão desaparecidas, tanto no dia-shift como um todo, bem como quantas pessoas está ajustando os diversos critérios, e quantas pessoas que realmente definida, além de os que temos. Esta exposição terá que atualizar semi-live enquanto o líder ajusta a lista com "E se James leva o dia-shift em vez de Ursula e Ursula leva a noite-shift".
Mas enormes graças às pessoas que responderam a esta Até agora, os sons problema da satisfação de restrições como a maneiraprecisamos ir, mas vamos definitivamente olhar difícil em todos os links e nomes algoritmo aqui.
Este é por isso que eu amo StackOverflow:)
Solução
O que você tem aí é um restrição satisfação problema ; sua relação com a NP é interessante, porque eles são tipicamente NP mas muitas vezes não NP-completo, ou seja, eles são tratáveis ??com soluções de tempo polinomial.
Como ebo observado nos comentários, seus sons situação como ele pode ser formulado como um exato problema de cobertura , que você pode aplicar de Knuth Algoritmo X para. Se você tomar este rumo, por favor deixe-nos saber como ele funciona para você.
Outras dicas
Ele faz olhar como você tem um restrição problema de satisfação .
No seu caso eu particularmente olhar para técnicas de propagação de restrições primeiros - você pode ser capaz de reduzir o problema a um tamanho administrável dessa forma.
O que acontece se ninguém se encaixa nos critérios?
Como para mim, eu provavelmente tentando encontrar redução bipartite graph correspondência problema . Também para provar que problema é NP geralmente é muito mais complicado do que ficar você não consegue encontrar solução polinomial.
Não estou certo o seu problema é NP, ele não cheira assim, mas o que eu faria se eu fosse você seria a de ordenar os requisitos para as posições tais que você tentar preencher o mais específico primeira vez que menos pessoas estará disponível preencher essas vagas, assim que você é menos provável que tenha de recuar muito. Não há nenhuma razão porque você não deve combinar isso com o algoritmo de X, um algoritmo de pura Knuth-ness.
Vou deixar a teoria para os outros, desde a minha savvy matemática não é tão grande, mas você pode encontrar uma ferramenta como o Cassowary / Cassowary.net ou NSolver útil para representar o seu problema de forma declarativa como um problema de satisfação de restrições e, em seguida, resolver o restrições.
Em tais ferramentas, o método simplex combinada com a propagação de restrição é frequentemente empregue para deterministamente reduzir o espaço de solução e, em seguida, encontrar uma solução óptima dada uma função de custo. Para espaços de solução grandes (que não parecem se aplicar no tamanho do problema que você especificar), algoritmos genéticos, ocasionalmente, são empregados.
Se bem me lembro, NSolver também inclui no código de exemplo uma simplificação de um problema real-rostering enfermeira que o Dr. Chun trabalhados em Hong Kong. E há um artigo sobre o trabalho que ele fez.
Parece-me que você tem um par de problemas separáveis ??que seria muito mais fácil de resolver:
- selecione um médico da equipa A - selecionar outro médico de qualquer equipe - seleccionar duas enfermeiras
Então você tem três problemas independentes.
Um esclarecimento, porém, você tem que ter dois médicos (um da equipe especificado) e duas enfermeiras, ou um médico da equipe especificado, dois enfermeiros e um outro que pode ser tanto médico ou enfermeiro?
Algumas perguntas:
- É o objetivo de satisfazer as restrições exatamente , ou única aproximadamente (mas, tanto quanto possível)?
- Uma pessoa pode ser um membro de várias equipes?
- Quais são todas as restrições possíveis? (Por exemplo, poderíamos precisa de um médico, que é membro de várias equipes?)
Se você quiser satisfazer as restrições exatamente , então gostaria de pedir as restrições cada vez menos por rigor, isto é, os que são mais difíceis de alcançar (por exemplo, médico e equipa A no seu exemplo acima ) deve ser verificado início !
Se você quiser satisfazer as restrições aproximadamente , então é uma história diferente ... você teria que especificar algum tipo de / importância-função de ponderação que determina o que nós em vez teria, quando não pode corresponder exatamente, e tem várias possibilidades para escolher.
Se você tem várias ou muitas restrições, dê uma olhada Drools Planner (fonte aberta, java).
Força bruta , ramo e vinculada e técnicas semelhantes demorar muito. algoritmos determinísticos tais como preencha os maiores deslocamentos primeira são muito abaixo do ideal. Meta-heurísticas são uma boa maneira de lidar com isso.
Tome um olhar específico para o exemplo rostering enfermeira do mundo real do Drools Planner. É fácil adicionar muitas restrições, como "jovens enfermeiros não querem trabalhar sábado à noite" ou "alguns enfermeiros não querem trabalho para muitos dias seguidos".
