Как я могу написать программу для генерации дерева решений сортировки?

Question

В классе нам дали простое дерево решений для сортировки 3 элементов (a, b, c).

_{(источник: brpreiss.com )}

Глядя на это, это имеет смысл для меня. Я был в состоянии следовать за этим.

Однако теперь мне нужно составить дерево решений для 4 элементов (a, b, c, d), а количество листов просто увеличилось до 24.

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

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

Answer 1

Возможно, вы захотите взглянуть на S orting Networks . Я думаю, что должна быть возможность преобразовать оптимальную сеть сортировки для заданного количества входных данных в дерево решений.

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

Наконец, вы можете сделать это в обратном порядке - например, используя подход типа сортировки слиянием: выложите все 24 возможных порядка сортировки внизу дерева. Выберите сравнение и разделите листья на два набора в зависимости от результата. Повторяйте рекурсивно для каждой ветви, пока у вас не будет только одного листа на ветку.

Answer 2

Простой способ, в данном случае , состоит в расширении существующего дерева. Дерево глубины 3 может сортировать до 2^3=8 различных результатов, что достаточно для сортировки 3 элементов, начиная с 3! = 6 и 6 <= 8. Чтобы отсортировать 4 элемента, вам нужна глубина не менее 5: 4! <= 2^5. Мы можем структурировать два новых, самых низких уровня, чтобы решить, куда вставить d, учитывая, что a, b и c уже отсортированы по существующей сети.

Предполагая, что x, y и z отсортированы, так что x<y<z вы можете использовать эту сеть для добавления нового элемента d в правильное положение:

// note: read from right to left
d<x<y<z -[yes]- (d<x)? -[yes]-- (d<y) -
x<d<y<z -[no]-/               /
x<y<d<z -[yes]- (d<z)? -[no]-/
x<y<z<d -[no]-/

Таким образом, вы можете взять существующее дерево, повторить его 4 раза и заменить каждый текущий лист указанным поддеревом, в каждом случае заменив x, y и z на порядок * 1024. *, b и c в текущем листе.

Обратите внимание, что, хотя это работает для вашего конкретного случая и дает минимальное дерево, добавление поддеревьев для вставки "следующего элемента" не даст деревьев сортировки минимальной высоты для других случаев. Например, для сортировки a,b,c,d,e минимальная высота будет равна 7, как 5! = 120 и 7^2 = 128. Однако поддерево для размещения e в уже отсортированном списке из 4 элементов само по себе должно иметь как минимум глубину 3 (так как существует 5 возможных позиций вставки) - так что мы можем легко построить глубину 5+3 = 8 дерево, но потребуется другой подход для построения корректного дерева глубины 7.

Для общего обсуждения ссылка на сортировку сетей в ответ Ника очень актуальна: вы можете построить дерево сортировки из сети, читая сеть слева направо, создавая узел для каждого соединения и в этот момент, рассматривая два варианта сети как дочерние: один, где был произведен обмен (скажем, a<b является ложным, так что теперь a и b меняются местами), и другой, где это не так необходимо (потому что a<b). Глубина дерева решений сортировки равна глубине его сети сортировки, и согласно этой странице, хотя является алгоритмом для генерации логарифмических деревьев / сетей глубины (AKS), он ни в коем случае не прост.

Answer 3

Тип алгоритма был описан Чарльзом Форджи: см. Алгоритм Рета . (Извините, статья в WP, конечно, не быстрый ответ, но, возможно, это хорошее начало)