Можно ли найти, существует ли последовательность за полиномиальное время в следующей задаче?

Некоторое время я думал о следующей проблеме, и я не нашел ее полиномиального решения. Только грубая четверка. Я тоже пытался свести к этому проблему NP-Complete, но безуспешно.

Вот проблема :

У вас есть отсортированный набор пар целых положительных чисел. $\{(A_1, B_1), (A_2, B_2), \ldots, (A_n, B_n)\}$

$(A_i, B_i) < (A_j, B_j) \Leftrightarrow A_i < A_j \lor (A_i = A_j \land B_i < B_j)$ $(A_i, B_i) = (A_j, B_j) \Leftrightarrow A_i = A_j \land B_i = B_j$

Следующая операция может быть применена к паре: Swap(pair). Меняет местами элементы пары, поэтому станет $(10, 50)$ $(50, 10)$

При замене пары в наборе набор автоматически снова сортируется (пара поменялась местами, и она будет перемещена на свое место в наборе).

Проблема состоит в том, чтобы увидеть, существует ли последовательность, которая, начиная с некоторой пары, заменяет весь набор со следующим условием:

После обмена пары следующая пара должна быть либо преемницей, либо предшествующей парой в наборе.

Было бы здорово найти решение этой проблемы за полиномиальное время или свести к нему задачу NP-Complete.

Примечание:
это уже проблема решения. Я не хочу знать, какая последовательность: только если последовательность существует.

Пример того, как набор сортируется после обмена пары

$\textbf{(6, 5)}$
$(1,2)$
$(3,4)$
$(7,8)$

Если я поменяю местами первую пару, то получится: , и после сортировки набора (размещения отсортированной пары в новой позиции) мы получим: $(5,6)$

$(1,2)$
$(3,4)$
$\textbf{(5,6)}$
$(7,8)$

Затем я должен поменять местами пару (предшественник) или (наследник) и повторять процесс, пока все пары не поменяются местами (если это возможно). $(3,4)$ $(7,8)$

Важно:
вы не можете поменять местами уже обмененную пару.
Если существует последовательность операций подкачки, то все пары должны быть переименованы в один и только один раз.

Пример, где невозможно обменять все пары

$(0, 0)$
$(1, 4)$
$(3, 2)$
$(5, 5)$

ds.algorithms np-hardness sorting Оскар Медерос
источник

Сортируется ли список после переименования файла и до выбора следующего файла для переименования? Вы можете переписать условие сортировки следующим образом:

тогда и только тогда, когда (

) или (

(A, B, C) < (A^{'}, B^{'}, C^{'})

$(A,B,C) < (A',B',C')$

A < A^{'}

$A < A'$

A = A^{'}

$A=A'$

B < B^{'}

$B<B'$

A = A^{'}

$A=A'$

B = B^{'}

$B=B'$

C < C^{'}

$C < C'$ )?

mjqxxxx

Проблемы с назначением не приветствуются на cstheory.stackexchange.com в целом.

Tsuyoshi Ito

Хм, я не уверен. Обычно логика заключается в том, что не стоит отвечать на типичные домашние задания, потому что это в будущем разрушит цель домашнего задания для кого-то. Но в этом случае проблема не выглядит типичной проблемой.

Tsuyoshi Ito

может быть, если вы дадите мотивацию, отличную от «это была домашняя работа», люди могут заинтересоваться, и она не будет закрыта. Что может быть возможным применением этого?

Маркос Вильягра

о переформулировании проблемы, вы можете забыть о файлах и посмотреть на это так. У вас есть набор пар натуральных чисел

, и правила те же, что и вы. Первоначально сортируется в первом столбце, затем вы начинаете переименовывать точки.

A = {(x_{1}, y_{1}), \dots, (x_{n}, y_{n})}

$A=\{(x_1,y_1),\dots,(x_n,y_n)\}$

Маркос Вильягра

Ответы:

... Я искал некоторые шаблоны, чтобы построить сокращение от проблемы NPC, но не нашел способа представить «поток» с помощью «вилки» ...

Итак (после некоторой работы) это полиномиальный алгоритм ...

АЛГОРИТМ

Стартовый список можно рассматривать как массив из последовательных « дырок ». Для каждой начальной пары поместите « элемент » в номер отверстия . Каждая пара может рассматриваться как направленный край от положения до положения . Шаг состоит в выборе элемента в положении и перемещение его в положение назначения $N*2$ $(a_j,b_j)$ $b_j$ $a_j$ $a_j$ $b_j$ $b_j$ $a_j$ $b_j$ (отверстие назначения становится неподвижным колышком ). Мы удаляем ребро и продолжаем выбирать следующий ход, который начнется с одного из двух ближайших достижимых элементов из позиции ( разрешены только отверстия между и ). Мы должны найти последовательность из последовательных ходов. $b_k$ $b_j$ $b_j$ $b_k$ $N$

Для каждого рассмотрим (в позиции массива ) как начальный элемент . $(a_j,b_j)$ $b_j$ $a_j$ $start$
- Для каждого рассмотрим в качестве конечного элемента (край от позиции в положение будет конечный край). $(a_k,b_k), a_k \neq a_j$ $a_k$ $end$ $a_k$ $b_k$
  - генерирует последовательность ходов от с использованием следующих критериев , пока не достигнут элементом (и решение было найдено), или условие остановки $start$ $end$

Когда вы делаете ход, вы фиксируете колышек в позиции и массив разбивается на два раздела (слева) и (справа), и единственный способ перейти от к (или от к ) - это использовать край, который прыгает через колышек. Поставил $b_j$ $L$ $R$ $L$ $R$ $R$ $L$

= количество ребер слева направо (не считайте конечное ребро) $edgesLR$
= количество ребер справа налево (не считайте конечное ребро) $edgesRL$
= $flow$ $edgesLR - edgesRL$

случаи:

А) если то один из двух разделов станет недоступным, остановите $| flow | > 1$

Теперь предположим, что , т.е. $end > b_j$ $end \in R$

B) если то слева слева направо есть дополнительное ребро, вы должны идти налево (выбрать ближайший элемент ), иначе вы никогда не достигнете $flow = 1$ $L$ $end$

C) если то есть дополнительное ребро справа налево, и какой бы узел вы ни выбрали, вы никогда не достигнете , остановитесь $flow = -1$ $end$

D) если вы должны идти направо (выберите ближайший элемент ), иначе вы никогда не достигнете $flow = 0$ $R$ $end$

Если ( ), B, C, D инвертируются. $end < b_j$ $end \in L$

ПРИМЕЧАНИЕ: при перемещении влево или вправо, вы должны рассматривать как колышек. Например, если вы должны идти прямо, но ближайший элемент на является , то ход невозможно (и вы должны действовать с другой парой ) $end$ $R$ $end$ $(start,end)$

Применяйте одно и то же звучание при каждом движении.

СЛОЖНОСТИ

Потоки через каждое отверстие могут быть предварительно рассчитаны в O (N) и использованы повторно при каждом сканировании.

Петли являются:

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

Во время вычислений выбор не сделан, поэтому сложность алгоритма равна $O(N^3)$

КОД

Это рабочая реализация алгоритма на Java:

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);
    }    
}

Марцио Де Биаси
источник

Это интересный подход. В общем, всякий раз, когда вы используете ребро

, должно быть одинаковое (или отличающееся на единицу) количество неиспользуемых ребер, пересекающих

в каждом направлении; и если числа отличаются на единицу, вы знаете, какое преимущество вы должны взять дальше. Когда числа равны, у вас есть выбор, который вы должны решить, протестировав оба варианта. Это кажется достаточно эффективной поисковой стратегией, но как вы узнаете, что в худшем случае это полином? То есть откуда вы знаете, что вы встретите только

вариантов, где количество неиспользуемых пересекающихся ребер в каждом направлении равно?

(a, b)

$(a,b)$

b

$b$

O (\log n)

$O(\log n)$

mjqxxxx

@mjqxxxx ... Я переписал весь ответ, чтобы соответствовать алгоритму Java ...

Марцио Де Биаси

@mjqxxxx ... хорошо, наконец-то я понял ... :-)

Марцио Де Биаси

Это выглядит правильно и очень элегантно для меня. Как только вы используете ребро

, вы больше не можете «ходить» через

; единственные оставшиеся переходы через

- это неиспользованные «скачки» (направленные ребра), пересекающие его, и все это вы должны использовать. Если задано последнее ребро

, то вам нужно свернуть на той же стороне

что

(a, b)

$(a,b)$

b

$b$

b

$b$

(a_{n}, b_{n})

$(a_n, b_n)$

b

$b$

a_{n}

$a_n$ , Тогда есть только одно возможное направление для ходьбы после каждого ребра, так как нечетное (четное) количество прыжков оставит вас на противоположной (той же) стороне, по которой вы изначально шли. Таким образом, тестирование каждого выбора начального и конечного ребер может быть выполнено за полиномиальное время.

mjqxxxx

Это прекрасный алгоритм. Мне никогда не приходило в голову исправить последний ход первым. Незначительные моменты: (1) Как писал mjqxxxx, end должен быть a_k. В противном случае условие «конец> b_j» неверно. (2) Либо определение «поток» должно быть отменено, либо случаи B и C должны быть заменены.

Tsuyoshi Ito

Это не решение, а переформулировка, которая позволяет избежать явного упоминания об операциях обмена и сортировки. Начните с сортировки всего объединенного списка имен файлов и их замененных версий и определите каждое имя файла с указателем в этом списке. Тогда два файла являются соседями, если все старые имена файлов между ними уже уничтожены, и если ни одно из новых имен файлов между ними еще не создано. Переформулированная проблема заключается в следующем:

$n$ $(a, b)$ $a, b \in \{1,2,…,2n\}$ $(a_1, b_1), (a_2, b_2),...,(a_n, b_n)$

$a_j$ $b_i$ $a_{i+1}$ $j \le i$
$b_j$ $b_i$ $a_{i+1}$ $j \ge i+1$

mjqxxxx
источник

+1. Это гораздо более простой способ сформулировать эквивалентную проблему. Только одно уточнение: ребра (a, b) направлены (в том смысле, что ребро (a, b) и ребро (b, a) имеют разные значения).

Tsuyoshi Ito

@ Tsuyoshi: спасибо; Я отредактировал, чтобы сказать 'направленный'.

mjqxxxx

b

$b$

a

$a$

c

$c$

a ⩽ b ⩽ c

$a\leqslant b\leqslant c$

@ Александр: Здесь «b между a и c» означает «либо <b <c, либо c <b <a».

Tsuyoshi Ito