Поиск всех пар элементов из двух возрастающих списков в определенном порядке - PullRequest
Новая
       62

Поиск всех пар элементов из двух возрастающих списков в определенном порядке

0 голосов
/ 16 июня 2020

Я работаю над точным алгоритмом NP-полной задачи декомпозиции дерева. Для контекста, узлы декомпозиции дерева - это подмножества вершин графа.

Есть два списка A и B, которые содержат деревья. Мне нужно перебрать каждую неупорядоченную пару элементов, где один элемент находится в A, а один элемент - в B. Во время итерации в любой список могут быть добавлены новые элементы.

В настоящее время я достигаю этого с помощью следующего псевдокода: 

for (int i = 0; i < A.Count; i++) {
    Tree a = A[i];
    B.add(a);
    for (int j = 0; j < B.Count; j++) {
        Tree b = B[j];

        // do stuff
        // new trees might be appended to A and B here, but the code handles that just fine
    }
}

Теперь я хочу реализовать эвристию c, которая выполняет итерацию по парам сначала большие деревья. (Большое значение означает мощность объединения узлов в дереве или, что эквивалентно, количество вершин, которые они покрывают.) Моя первая мысль заключалась в том, чтобы разбросать элементы A и B в сегменты, которые индексируются размер дерева и сначала перебираем большие a и b. В таком случае итерация будет выглядеть примерно так: 

for (int i = 0; i < A.Count; i++) {
    Tree a = largest element in A that hasn't been iterated over
    B.add(a);
    for (int j = 0; j < B.Count; j++) {
        Tree b = largest element in B that hasn't been iterated over by this 'a'

        // do stuff
        // new trees might be appended to A and B here, but the code handles that just fine
    }
}

Однако сначала выполняется только большая a, но не большая b, в том смысле, что порядок итерации равен 

  A  | B  Large   Medium   Small                                
 Large     -------------------> 
 Medium    -------------------> 
 Small     ------------------->

Я бы хотел, однако, что-то вроде этого: 

  A  | B  Large   Medium   Small                                
 Large     / / / / / / / / / /
 Medium     / / / / / / / / /
 Small     / / / / / / / / / /

Что делает старый подход еще хуже, так это то, что новые деревья, построенные во время итераций, всегда больше, чем a и b они сделаны из. Таким образом, если такое большее дерево помещается в A, текущее a должно пройти go через остальную часть списка B, прежде чем новое дерево можно будет перебрать.

Самый эффективный способ, который я знаю, - это связать набор ha sh с каждым деревом в A дерева в B, с которым он уже был связан, и go оттуда, но тогда память станет огромной проблема.

Я знаю, что это требует многого, но есть ли эффективный способ изменить порядок итераций на более близкий к тому, что я хочу?

...