Установление хронологии списка на основе дерева ориентированных графов

Question

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

Допустим, у вас есть следующее дерево чисел a b c d e f g h:

    a
   / \
   b  c
 / |  |
g  d  f
|  |
h  e

Каждый шаг вниз по дереву означает, что следующее число больше предыдущего. Так что c или c Допустим, у нас есть упорядоченный список чисел, например [a, b, c, d, e]. Как нам написать алгоритм, который проверяет, является ли порядок чисел в списке (при условии, что L [i] I. E, оба [a, c, b, d, e] и [a, b, d, c, e] верны, но [c, a, b, d, e] нет (так как мы знаем, что c> а, кроме прочего, относительно того, как устроены другие числа).

Ради алгоритма, давайте предположим, что наш доступ к дереву является функцией provbly_greater (X, Y), который возвращает true, если дерево знает, что число больше другого числа. И.Е. provbly_greater (a, d) = True, но proviable_greater (d, f) = False. Естественно, если число доказуемо не больше, оно также возвращает false.

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

Заранее спасибо.

Answer 1

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

1. Сначала выполните обход Эйлера по дереву, запомнив начальный и конечный индексы для каждого узла. Если вы используете одно и то же дерево для проверки большого количества списков, вам нужно сделать это только один раз. Смотри https://www.geeksforgeeks.org/euler-tour-tree/

2. Создать изначально пустое двоичное дерево поиска индексов

3. Итерация по списку. Для каждого узла проверьте, содержит ли дерево какие-либо индексы между его начальными и конечными индексами тура Эйлера. Если это так, то список не в порядке. Если это не так, вставьте его начальный индекс в дерево. Это предотвратит появление какого-либо предположительно меньшего узла позже в списке.

Вот и все - O (N log N) в целом и для каждого списка.

A TreeSet в Java или std::set в C ++ можно использовать для бинарного дерева поиска.

Answer 2

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

Сначала настройте структуру данных, которая позволяет быстро оценивать provably_greater(X, Y) на основе дерева.Эта структура может быть набором или хэш-таблицей, которая займет много памяти, но обеспечит быстрый доступ.Для каждого листа дерева проложите путь до корня.В каждом узле посмотрите на все узлы-потомки и добавьте упорядоченную пару к набору, который показывает отношение меньше чем для этих двух узлов.В вашем примере дерева, если вы начинаете с узла h, вы переходите к узлу g и добавляете (g,h) к набору, затем переходите к узлу b и добавляете пары (b,h) и (b,g) взатем перейдите к узлу a и добавьте пары (a,h), (a,g) и (a,b) к набору.Сделайте то же самое для листовых узлов e и f.Пара (a,b) будет добавлена ​​дважды к набору из-за конечных узлов h и e, но структура набора может с этим легко справиться.

Функция provably_greater(X, Y) теперь быстрая ипросто: результат True, если пара (Y,X) находится в наборе, и False в противном случае.

Теперь вы смотрите на все пары чисел в вашем списке - для списка [a,b,c,d,e] выбудет смотреть на пары (a,b), (a,c), (b,c) и т. д. Если provably_greater(X, Y) верно для любой из этих пар, список не в порядке.В противном случае список упорядочен.

Это должно быть очень легко реализовать на языке, подобном Python.Дайте мне знать, если вам нужен код Python 3.