Provavelmente, todos se depararam com o fato de que teriam que enfrentar uma tarefa difícil, cuja solução não poderia ser encontrada, não apenas de imediato - mas mesmo após longas e teimosas horas de trabalho ou dias. Hoje vamos falar sobre uma das classes de tais problemas - NP-completo.
Em geral, é realista cumprir essas tarefas na vida cotidiana? Na verdade, eles surgem em um grande número de casos: combinatória, gráficos e redes, execução de fórmulas lógicas, trabalho com mapas, cargas ótimas, mapas, problemas de otimização discreta, encontrar as sequências mais longas, encontrar somas iguais e muitos problemas definidos! E esta não é uma lista completa.
Abaixo do corte está um guia informal - como entender que você pode ter um problema NP na sua frente e o que fazer se for exatamente o que acabou de ser. Hoje estamos atacando essa questão do lado prático.
Certifique-se de que ela realmente está na sua frente
Como você sabe quando se depara com um problema NP-completo? Primeiro, a heurística de detecção mais simples é uma busca por problemas NP-completos já conhecidos para determinar algo semelhante, existem muitas dessas listas, por exemplo .
Em segundo lugar, considere as seguintes propriedades de tarefas:
- Precisamos escolher uma solução em que n elementos do espaço exp (n)
- Se você já tem uma solução de comprimento n a partir deste espaço, ela pode ser facilmente (polinomialmente) verificada
- A escolha de um dos elementos de decisão (pode) afeta a escolha de todos os outros (não necessariamente de todos).
- No pior caso, as opções sempre podem ser enumeradas, considerando todo o espaço exponencial por uma simples enumeração.
- Os parâmetros n - o comprimento da solução ou o próprio espaço não têm um valor fixo, ou seja, não estamos falando do tabuleiro sempre fixo 8 por 8, mas da forma geral do problema N por N.
Leia mais sobre as propriedades dos problemas NP-completos aqui e aqui .
Um exemplo de trabalho nesta lista
Vamos dar um exemplo simples de um problema que foi recentemente aprovado como NP-completo!
Com base nos materiais do artigo. Você precisa colocar N rainhas em um tabuleiro de tamanho N por N, desde que K <= N já estejam colocados no tabuleiro (foto do artigo científico original)
Primeiro, observe que um problema muito semelhante com quadrados latinos parcialmente restritos NP está completo.
E então examinamos a lista:
- Você precisa encontrar N rainhas a partir do espaço exp (N) (= N ^ 2 * (N ^ 2-1) * ....).
- A solução de N rainhas é trivial de verificar - para cada rainha, você precisa verificar as diagonais, verticais e linhas horizontais.
- Definir um torna a escolha de vários outros inválida - ou seja, existem dependências entre os elementos da solução (você não pode organizar rainhas independentemente).
- Aqui você pode resolver o problema por força bruta para uma placa escolhida arbitrariamente em exp (N) - colocamos a primeira na primeira posição na posição (i, j), a segunda em qualquer outra não ocupada e assim por diante. O retrocesso certamente encontrará uma solução.
- O problema não tem parâmetros fixos - isto é, é formulado de uma forma geral e, à medida que N cresce, também aumenta a complexidade.
Observe que um dos itens da lista falha se sempre soubermos que o tabuleiro está limpo e a tarefa se torna trivial.
Além disso, é uma abordagem prática condicional - uma heurística para detectar problemas NP-completos (com todos os prós e contras).
Mistura
Fonte
Por que, tendo em mãos problemas semelhantes, não é fácil entender formalmente que temos um problema NP? Nós realmente precisamos apontar um problema NP para o nosso, então saberemos com certeza que nosso problema é NP-difícil! E se pudéssemos simular, como na lista acima, então ele está completo - ou seja, pelo menos NP e não mais que NP, de fato “o mais difícil entre os problemas NP” (como o resto do NP-completo).
Ok, nós precisamos disso? Não realmente, se você for direto, depois de todas as verificações, de que está enfrentando um problema NP, então não precisa provar nada, a menos que esteja escrevendo um artigo científico.
E você precisa (falaremos sobre isso a seguir):
- simular sua tarefa usando sistemas que resolvem tais tarefas;
- encontre uma solução que funcione rápido o suficiente no seu caso;
- encontre uma solução aproximada que nos satisfaça.
Não desista!
O mais importante é avaliar parâmetros-dimensões e cenários realistas!
xkcd.com/287
Por exemplo, você sabe que, apesar do fato de os valores dos parâmetros não serem fixos, o N <100 condicional não é implementado em todos os cenários práticos, o que significa que a enumeração condicional pode ser uma solução real para você.
Você precisa determinar por si mesmo: quais valores reais de parâmetros são possíveis e realmente entram no sistema, qual é a distribuição geral e as características dos dados, o que é real e o que não é? Precisamos da solução ideal? Vamos examinar esses pontos.
Distribuição de dados de entrada
Ou apesar do fato de que, no caso geral, os dados de entrada podem ser qualquer um, mas novamente para o exemplo das rainhas - geralmente uma rainha é fixa ou mesmo nenhuma. Isso significa que 90% das vezes você pode usar uma solução muito simples e apenas chamar uma complexa em casos extremos.
Um exemplo quando em média todas as combinações usuais são simples: o problema de complementar as rainhas - sabemos que as heurísticas DFS + condicionais podem, na maioria dos casos, encontrar soluções muito rapidamente, e apenas em situações muito fora do padrão pode ser extremamente difícil.
Aqui está um exemplo de como a solução para um problema de tiling NP-completo muito especializado foi avaliada em relação a um método geral para modelar uma classe inteira de tais problemas usando técnicas de programação lógica:
(do artigo Fatoração de dados relacionais (Paramonov, Sergey; van Leeuwen, Matthijs; De Raedt, Luc: fatoração de dados relacionais, aprendizado de máquina, volume 106))
Em primeiro lugar, a velocidade da solução LTM-k especial e o método geral são significativamente diferentes. Assim, uma solução baseada em heurística apenas para este tipo de problema pode resolver completamente este problema.
Em segundo lugar, ao sacrificar a qualidade da solução, o método de aproximação geral deu uma velocidade muito semelhante.
Heurística e aproximação
A última e mais poderosa ferramenta é usar sistemas de modelagem de problemas NP-completos, como a programação de conjuntos de respostas .
Mais sobre linguagens de programação lógicas.
Por exemplo, a solução para o problema de colocação da rainha será assim:
% domain
row(1..n).
column(1..n).
% alldifferent: guess a solution
1 { queen(X,Y) : column(Y) } 1 :- row(X).
1 { queen(X,Y) : row(X) } 1 :- column(Y).
% remove conflicting answers: check this solution
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 == Y2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 + X1 == Y2 + X2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 - X1 == Y2 - X2.
Após realizar uma experiência simples para encontrar soluções para um número diferente de rainhas N, obtemos o seguinte: ao longo do eixo X - rainhas, ao longo de Y - tempo por segundo para encontrar uma solução:
Vemos que, apesar do fato de que o crescimento do tempo claramente não é polinomial (o que é lógico), fazemos um bom trabalho com um número adequado de rainhas e tamanhos de tabuleiro.
Então, se soubermos quais tamanhos de placa são reais para nós, podemos entender como essa solução exata é aceitável para nós em um sistema real.
conclusões
Vamos revisar as ideias do artigo na forma de uma lista de verificação
- Determine se você realmente tem um problema NP.
- Entenda o que são valores de parâmetros realistas e distribuição de dados.
- Tente escrever (a ordem depende do desenvolvedor e / ou tarefa):
- Uma solução heurística precisa (com base em nossa análise) - será rápida o suficiente?
- — ?
- NP- — ? , CPU ? .
- : , .
- — , — . !
:
