Estou pensando no seguinte problema há um tempo e não encontrei uma solução polinomial para ele. Apenas fonte bruta. Eu também tenho tentado reduzir um problema NP-Complete sem sucesso.
Aqui está o problema :
Você tem um conjunto classificado de pares inteiros positivos.
( A i , B i ) = ( A j , B j ) ⇔ A i = A j ∧ B i = B
A operação seguinte pode ser aplicado a um par: Swap(pair)
. Troca os elementos do par, para que se torne( 50 , 10 )
Quando um par no conjunto é trocado, o conjunto é automaticamente classificado novamente (o par trocado está fora do lugar e será movido para seu lugar no conjunto).
O problema consiste em verificar se existe uma sequência que, iniciando em algum par, troque o conjunto inteiro, com a seguinte condição:
Depois que um par é trocado, o próximo par a ser trocado deve ser o par sucessor ou predecessor no conjunto.
Seria ótimo encontrar uma solução de tempo polinomial para esse problema ou uma redução de um problema NP-Complete nele.
Nota:
já é um problema de decisão. Não quero saber qual é a sequência: apenas se houver uma sequência.
Exemplo de como o conjunto é classificado após a troca de um par
Se eu trocar o primeiro par, ele se tornará: e depois de classificar o conjunto (colocando o par classificado em sua nova posição), teremos:
( 3 , 4 ) (5,6) ( 7 , 8 )
Então eu tenho que trocar o par (predecessor) ou ( 7 , 8 ) (sucessor) e repetir o processo até que todos os pares sejam trocados (se possível).
Importante:
Você não pode trocar um par já trocado.
Se houver uma sequência de operações 'swap', todos os pares deverão ser renomeados para uma e apenas uma vez.
Exemplo onde não é possível trocar todos os pares
( 1 , 4 ) ( 3 , 2 ) ( 5 , 5 )
fonte
Respostas:
... Pesquisei alguns padrões para reduzir o problema de um NPC, mas não encontrei uma maneira de representar um "fluxo" com um "garfo" ...
Então (depois de algum trabalho) este é um algoritmo polinomial ...
ALGORITMO
A lista inicial pode ser vista como uma matriz de " furos " consecutivos . Para cada par inicial ( a j , b j ) , coloque o " elemento " b j no número do furo a j . Cada par pode ser visto como uma aresta direcionada da posição a j para a posição b j . Um movimento consiste em escolher um elemento b j na posição a j e movê-lo para sua posição de destino b jN∗2 (aj,bj) bj aj aj bj bj aj bj (o orifício de destino se torna um peg imóvel ). Excluímos a aresta e prosseguimos para escolher o próximo movimento que começará a partir de um dos dois elementos alcançáveis mais próximos partir da posição b j (somente orifícios entre b j e b k são permitidos). Precisamos encontrar uma sequência de N movimentos consecutivos.bk bj bj bk N
Para cada considere b j (na posição da matriz a j ) como o elemento inicial s t a r t .(aj,bj) bj aj start
Para cada considerar um k como o elemento final e n d (a borda a partir da posição de um K na posição b k vai ser a borda final).(ak,bk),ak≠aj ak end ak bk
Ao fazer um movimento, você fixa um pino na posição e o array é dividido em duas partições L (esquerda) e R (direita) e a única maneira de ir de L para R (ou de R para L ) é usando um borda que salta através do pino. Conjuntobj L R L R R L
Casos:
A) se , uma das duas partições ficará inacessível, pare|flow|>1
Agora suponha que , ou seja, e n d ∈ Rend>bj end∈R
B) se , então há uma vantagem extra da esquerda para a direita, você deve ir para a esquerda (escolha o elemento mais próximo de L ), caso contrário, você nunca vai chegar e n dfl o w = 1 eu e n d
C) se , então há uma vantagem extra da direita para a esquerda e qualquer nó que você escolher você nunca vai chegar e n d , paradafl o w = - 1 e n d
D) se você deve ir para a direita (escolha o elemento mais próximo dos R ), caso contrário você vai neve alcance e n dfl o w = 0 R e n d
Se ( e n d ∈ L ), B, C, D estão invertidos.e n d< bj e n d∈ L
NOTA: ao mover para a esquerda ou para a direita, você deve considerar como um peg. Por exemplo, se você deve ir para a direita, mas o elemento mais próximo em R é e n d então o movimento é impossível (e você deve proceder com outro par ( s t a r t , e n d ) )e n d R e n d ( S t a r t , e n d)
Aplique a mesma ressonância a cada movimento.
COMPLEXIDADE
Os fluxos sobre cada furo podem ser pré-calculados em O (N) e reutilizados a cada varredura.
Os loops são:
Nenhuma escolha é feita durante o cálculo; portanto, a complexidade do algoritmo éO ( N3)
CÓDIGO
Esta é uma implementação Java funcional do algoritmo:
fonte
Esta não é uma solução, mas uma reformulação que evita a menção explícita das operações de troca e classificação. Comece classificando toda a lista combinada de nomes de arquivos e suas versões trocadas e identifique cada nome de arquivo com seu índice nessa lista. Em seguida, dois arquivos são vizinhos se todos os nomes de arquivos antigos entre eles já foram destruídos e se nenhum dos novos nomes de arquivos entre eles já foi criado. O problema reformulado é o seguinte:
Dado um conjunto de arestas dirigidas disjuntos ( um , b ) com um , b ∈ { 1 , 2 , ... , 2 n } , existe uma ordenação ( um 1 , b 1 ) , ( um 2 , b 2 ) , . . . , ( a n , b n ) dessas arestas, de modo quen ( a , b ) a , b ∈ { 1 , 2 , … , 2 n } ( a1, b1) , ( Um2, b2) , . . . , ( umn, bn)
fonte