É possível descobrir se existe uma sequência no tempo polinomial no seguinte problema?

27

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. {(A1,B1),(A2,B2),,(An,Bn)}

( A i , B i ) = ( A j , B j ) A i = A jB i = B(Ai,Bi)<(Aj,Bj)Ai<Aj(Ai=AjBi<Bj) (Ai,Bi)=(Aj,Bj)Ai=AjBi=Bj

A operação seguinte pode ser aplicado a um par: Swap(pair). Troca os elementos do par, para que se torne( 50 , 10 )(10,50)(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

(6, 5)
(1,2)
(3,4)
(7,8)

Se eu trocar o primeiro par, ele se tornará: (5,6) e depois de classificar o conjunto (colocando o par classificado em sua nova posição), teremos:

( 3 , 4 ) (5,6) ( 7 , 8 )(1,2)
(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).(3,4)(7,8)

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 )(0,0)
(1,4)
(3,2)
(5,5)

Oscar Mederos
fonte
1
A lista é classificada depois que você renomeia o arquivo e antes de escolher o próximo arquivo a ser renomeado? Você pode reescrever a condição de classificação como: iff ( A < A ) ou ( A = A e B < B ) ou ( A = A E B = B e C < C (A,B,C)<(A,B,C)A<AA=AB<BA=AB=BC<C)?
precisa saber é o seguinte
3
Problemas de atribuição não são bem-vindos no cstheory.stackexchange.com em geral.
Tsuyoshi Ito 31/01
3
Hmm, não tenho certeza. Normalmente, a lógica aqui é que não é uma boa prática responder a perguntas típicas da lição de casa, porque isso arruinará o propósito da lição de casa para alguém no futuro. Mas, neste caso, o problema não parece um problema típico .
Tsuyoshi Ito 31/01
2
talvez se você der uma motivação diferente de "era uma lição de casa", as pessoas pudessem se interessar e ela não será fechada. O que poderia ser uma possível aplicação disso?
Marcos Villagra
2
sobre como reformular o problema, você pode esquecer os arquivos e vê-lo dessa maneira. Você tem um conjunto de pares de números inteiros positivos , e as regras são as mesmas que você colocou. Inicialmente é classificado na primeira coluna, e você começa a renomear os pontos. A={(x1,y1),,(xn,yn)}
Marcos Villagra

Respostas:

16

... 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 jN2(aj,bj)bjajajbjbjajbj(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.bkbjbjbkN

  • Para cada considere b j (na posição da matriz a j ) como o elemento inicial s t a r t .(aj,bj)bjajstart

    • 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),akajakendakbk

      • gerar uma sequência de movimentos a partir de utilizando os seguintes critérios até chegar elemento de e n d (e uma solução foi encontrado), ou uma condição de paragemstartend

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. ConjuntobjLRLRRL

  • = número de arestas da esquerda para a direita (não conte a aresta final)edgesLR
  • = número de arestas da direita para a esquerda (não conte a aresta final)edgesRL
  • = e d g e s L R - e d g e s R LflowedgesLRedgesRL

Casos:

A) se , uma das duas partições ficará inacessível, pare|flow|>1

Agora suponha que , ou seja, e n d Rend>bjendR

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 dflow=1Lend

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 , paradaflow=1end

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 dflow=0Rend

Se ( e n d L ), B, C, D estão invertidos.end<bjendL

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 ) )endRend(start,end)

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:

for start = 1 to N
  for end = 1 to N
    for move = 1 to N
      make a move (fix a peg and update flows)
      check if another move can be done using flow     

Nenhuma escolha é feita durante o cálculo; portanto, a complexidade do algoritmo é O(N3)

CÓDIGO

Esta é uma implementação Java funcional do algoritmo:

public class StrangeSort {
    static int PEG = 0xffffff, HOLE = 0x0;
    static int M = 0, N = 0, choices = 0, aux = 0, end;
    static int problem[][], moves[], edgeflow[], field[];    
    boolean is_hole(int x) { return x == HOLE; }
    boolean is_peg(int x) { return x == PEG; }
    boolean is_ele(int x) { return ! is_peg(x) && ! is_hole(x); };
    int []cp(int src[]) { // copy an array
        int res[] = new int[src.length];
        System.arraycopy(src, 0, res, 0, res.length);
        return res;
    }    
    /* find the first element on the left (dir=-1) right (dir=1) */
    int find(int pos, int dir, int nm) {
        pos += dir;
        while (pos >= 1 && pos <= M ) {
            int x = field[pos];
            if ( is_peg(x) || (pos == end && nm < N-1) ) return 0;
            if ( is_ele(x) ) return pos;
            pos += dir;
        }
        return 0;
    }
    void build_edges() {
        edgeflow = new int[M+1];
        for (int i = 1; i<=M; i++) {
            int start = i;
            int b = field[start];
            if (! is_ele(b)) continue;
            if (i == end) continue;
            int dir = (b > start)? 1 : -1;
            start += dir;
            while (start != b) { edgeflow[start] += dir; start += dir; }
        }
    }
    boolean rec_solve(int start, int nm) {
        boolean f;
        int j;
        int b = field[start];
        moves[nm++] = b;
        if (nm == N) return true;
        //System.out.println("Processing: " + start + "->" + field[start]);        
        field[start] = HOLE;
        field[b] = PEG;
        int dir = (b > start)? 1 : -1;
        int i = start + dir;
        while (i != b) { edgeflow[i] -= dir; i += dir; } // clear edge                
        int flow = edgeflow[b];
        if (Math.abs(flow) > 2) return false;
        if (end > b) {
            switch (flow) {
            case 1 :                    
                j = find(b,-1,nm);
                if (j <= 0) return false;
                return rec_solve(j,nm);
            case -1 :
                return false;
            case 0 :          
                j = find(b,1,nm);
                if (j <= 0) return false;
                return rec_solve(j,nm);
            }        
        } else {
            switch (flow) {
            case -1 :                    
                j = find(b,1,nm);
                if (j <= 0) return false;
                return rec_solve(j,nm);
            case 1 :
                return false;
            case 0 :          
                j = find(b,-1,nm);
                if (j <= 0) return false;
                return rec_solve(j,nm);
            }            
        }
        return false;
    }
    boolean solve(int demo[][]) {
        N = demo.length;
        for (int i = 0; i < N; i++)
            M = Math.max(M, Math.max(demo[i][0], demo[i][1]));
        moves = new int[N];
        edgeflow = new int[M+1];
        field = new int[M+1];
        problem = demo;        
        for (int i = 0; i < problem.length; i++) {
            int a = problem[i][0];
            int b = problem[i][1];
            if ( a < 1 || b < 1 || a > M || b > M || ! is_hole(field[a]) || ! is_hole(field[b])) {
                System.out.println("Bad input pair (" + a + "," + b + ")");
                return false;
            }
            field[a] = b;
        }
        for (int i = 1; i <= M; i++) {
            end = i;
            build_edges();
            if (!is_ele(field[i])) continue;
            for (int j = 1; j <= M; j++) {
                if (!is_ele(field[j])) continue;
                if (i==j) continue;
                int tmp_edgeflow[] = cp(edgeflow);
                int tmp_field[] = cp(field);
                choices = 0;
                //System.out.println("START: " + j + " " + " END: " + i);
                if (rec_solve(j, 0)) {
                    return true;
                }
                edgeflow = tmp_edgeflow;
                field = tmp_field;
            }
        }
        return false;
    }
    void init(int demo[][]) {

    }
    public static void main(String args[]) {
        /**** THE INPUT ********/        

        int demo[][] =  {{4,2},{5,7},{6,3},{10,12},{11,1},{13,8},{14,9}};

        /***********************/        
        String r = "";
        StrangeSort sorter = new StrangeSort();       
        if (sorter.solve(demo)) {
            for (int i = 0; i < N; i++) { // print it in clear text
                int b =  moves[i];
                for (int j = 0; j < demo.length; j++)
                    if (demo[j][1] == b)
                        r += ((i>0)? " -> " : "") + "(" + demo[j][0] + "," + demo[j][1] + ")";
            }             
            r = "SOLUTION: "+r;
        }
        else
            r = "NO SOLUTIONS";
        System.out.println(r);
    }    
}
Marzio De Biasi
fonte
Esta é uma abordagem interessante. Em geral, sempre que você usa uma aresta , deve haver um número igual (ou diferente de um) de arestas não utilizadas que cruzam b em cada direção; e se os números diferirem em um, você sabe qual borda deve seguir. Quando os números são iguais, você tem uma opção, a qual deve resolver testando as duas opções. Parece uma estratégia de pesquisa eficiente o suficiente, mas como você sabe que é polinomial no pior dos casos? Ou seja, como você sabe que encontrará apenas opções O ( log n ) onde o número de arestas de cruzamento não utilizadas em cada direção é igual? (a,b)bO(logn)
mjqxxxx
@mjqxxxx ... eu reescrevi toda a resposta para coincidir com o algoritmo de Java ...
Marzio De Biasi
@mjqxxxx ... ok, finalmente consegui-lo ... :-)
Marzio De Biasi
2
Isso parece correto e muito elegante para mim. Depois de usar uma aresta , você não pode mais "andar" através de b ; as únicas transições restantes em b são os "saltos" não utilizados (bordas direcionadas) que o atravessam, todos os quais você deve usar. Se a aresta final ( a n , b n ) for especificada, você precisará terminar no mesmo lado de b que a n(a,b)bb(an,bn)ban. Existe apenas uma direção possível para caminhar após cada borda, pois um número ímpar (par) de saltos o deixará no lado oposto (mesmo) para o qual você caminhou inicialmente. Portanto, o teste de cada escolha de arestas inicial e final pode ser feito em tempo polinomial.
Mjqxxxx
1
Este é um belo algoritmo. Nunca me ocorreu corrigir o último passo primeiro. Pontos secundários: (1) Como mjqxxxx escreveu, final deve ser a_k. Caso contrário, a condição "end> b_j" está incorreta. (2) A definição de “fluxo” deve ser negada ou os casos B e C devem ser trocados.
Tsuyoshi Ito
10

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,,2n}(a1,b1),(a2,b2),...,(an,bn)

  • se está entre b i e a i + 1 , então j i , eajbiai+1ji
  • se está entre b i e a i + 1 , então j i + 1 ?bjbiai+1ji+1
mjqxxxx
fonte
2
+1. Essa é uma maneira muito mais simples de declarar o problema equivalente. Apenas um esclarecimento: as arestas (a, b) são direcionadas (no sentido de que a aresta (a, b) e a aresta (b, a) têm significados diferentes).
Tsuyoshi Ito
@ Tsuyoshi: obrigado; Eu editei para dizer 'dirigido'.
Mjqxxxx #
Pelo que entendi, a frase " está entre a e c " significa a b c . Então acho que vale a pena mudar a notação anterior pela última. bacabc
Oleksandr Bondarenko
@Oleksandr: Aqui "b está entre a e c" significa "a <b <c ou c <b <a".
Tsuyoshi Ito