Алгоритм: идентифицировать парные конфликты в наборе объектов, учитывая только "конфликт в этом списке" oracle

У меня есть (неупорядоченный) набор объектов. У меня также есть оракул, который принимает упорядоченный список объектов и возвращает true, если в этом списке был хотя бы один упорядоченный конфликт, в противном случае - false. Упорядоченный конфликт представляет собой упорядоченную пару объектов (A, B), так что оракул возвращает true для любого входного списка [..., A,..., B,...]. (A, B), являющийся упорядоченным конфликтом, не обязательно означает, что (B, A) является упорядоченным конфликтом.

Я хочу идентифицировать все неупорядоченные конфликты в наборе: то есть найти все пары {x, y} такие, что либо (x, y), либо (y, x) является упорядоченным конфликтом, как определено выше. Оракул медленный (от десятков до сотен миллисекунд за вызов), поэтому важно минимизировать количество вызовов оракула; очевидный наивный алгоритм (подавать каждую возможную упорядоченную пару элементов набора в вызовы oracle; O (n²)) неприемлем. Есть сотни элементов набора, и ожидается, что их будет менее десяти конфликтов.

Это до тех пор, пока я получил: если oracle возвращает true для двухэлементного списка, то, очевидно, элементы в списке представляют собой конфликт. Если oracle возвращает false для любого списка, то в этом списке нет упорядоченных конфликтов; если oracle возвращает false для обоих списков L и для разворота списка L, то в L. нет неупорядоченных конфликтов. Таким образом, алгоритм разделения и покоя, который не совсем отличается от приведенного ниже, должен работать:

Put all the set elements in a list L (choose any convenient order).
Invoke the oracle on L.
  If the oracle returns false, invoke the oracle on rev(L).
    If the oracle again returns false, there are no unordered conflicts within L.

# At this point the oracle has returned true for either L or rev(L).
If L is a two-element list, the elements of L constitute an unordered conflict.

Otherwise, somehow divide the set in half and recurse on each

Я застрял на части "разделяй набор пополам и рекурсив". Есть два осложнения. Во-первых, недостаточно взять верхнюю половину, а затем нижнюю половину упорядоченного списка, потому что конфликт может быть устранен разделом (рассмотрим [... A1, A2,... An... ] [... B1, B2,... Bn...]). Перечисление всех подмножеств размера n/2 должно работать, но я не знаю, как это сделать эффективно. Во-вторых, наивная рекурсия может повторить большую работу из-за неявного состояния в стеке вызовов - предположим, что мы определили, что A конфликтует с B, тогда любое обращение оракула со списком, содержащим как A, так и B, теряется, но мы все еще необходимо исключить другие конфликты {A, x} и {B, x}. Я могу сохранить memo-матрицу таким образом, что M [a] [b] истинна тогда и только тогда, когда (A, B) уже проверена, но я не знаю, как сделать эту игру приятной с рекурсией.

Дополнительные осложнения из-за контекста: если какой-либо объект появляется более одного раза в списке, второй и последующие экземпляры игнорируются. Кроме того, некоторые объекты имеют зависимости: if (P, Q) - зависимость, то любой вход oracle, в котором Q появляется перед первым появлением P (если есть), будет ложно сообщать о конфликте. Все зависимости уже определены до запуска этого алгоритма. Если P конфликтует с A, невозможно узнать, будет ли Q также противоречить A, но это приемлемое ограничение.

(Контекст: это для идентификации пар системных заголовков C, которые не могут быть включены в один и тот же исходный файл. "Оракул" - это компилятор.)

Ответ 1

Несколько предложений:

Поиск одного конфликта

Предположим, что вы знаете, что существует конфликт в n элементах, вы можете использовать операции O (log n) для поиска местоположения одного конфликта путем первого деления пополам в конечной точке и затем деления пополам в начальной точке.

Например, это может выглядеть так:

Test 1,2,3,4,5,6,7,8,9,10 -> Conflict
Test 1,2,3,4,5 -> Good
Test 1,2,3,4,5,6,7 -> Conflict
Test 1,2,3,4,5,6 -> Good (Now deduce Endpoint is 7, the last end with a conflict)
Test 3,4,5,6 -> Conflict
Test 5,6 -> Good
Test 4,5,6 -> Conflict (Now deduce Startpoint is 4.)

Теперь вы знаете, что 4,5,6,7 являются жесткими (т.е. не могут быть уменьшены без устранения конфликта), поэтому мы можем заключить, что 4 и 7 должны конфликтовать.

Поиск дополнительных конфликтов

Как только вы обнаружите проблему, вы можете удалить один из элементов-нарушителей и проверить оставшийся набор. Если это все еще конфликтует, вы можете использовать метод bisection для идентификации другого конфликта.

Повторяйте, пока не будет найдено больше конфликтов.

Поиск оставшихся конфликтов

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

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

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

Ответ 2

Вам нужно найти ответы на n * (n-1) вопросы, каждый вопрос будет, если у упорядоченной пары есть конфликт. Всякий раз, когда вы отправляете последовательность длины k, и оракул говорит "хорошо", у вас будут ответы на k (k-1) такие вопросы.

Создайте и инициализируйте эти n * (n-1) вопросы как матрицу смежности со значениями по умолчанию -1 (установите собственные ребра как 0). Настройте последовательность случайным образом и примените свой рекурсивный алгоритм. Всякий раз, когда вы обнаружите, что в последовательности нет знака конфликта, соответствующий ответ в матрице (0). Пометить как конфликт (1), если последовательность ровно двух имеет конфликт.

Теперь, после большой итерации, у вас есть эта матрица с -1s, 0s и 1s. Предположим, что -1s являются ребрами и находят самый длинный путь. Повторите свой алгоритм. Продолжайте делать это, пока количество неизвестных не будет очень маленьким. В этот момент вы отправляете пары оракулу.

Ответ 3

Поскольку вы говорите, что у вас сотни заголовков и менее 10 конфликтов, я собираюсь дать оптимальное решение наихудшего варианта в предположении, что у вас есть n элементов и элементы O (lg n), участвующие в конфликтах. В худшем случае, если у вас есть элементы Theta (lg n), участвующие в конфликтах, все эти элементы конфликтуют друг с другом, и нет никакого способа определить это, используя меньше, чем Omega ((lg n) ^ 2) вызовы oracle, Таким образом, O ((lg n) ^ 2) вызовы оракула были бы оптимальными, предполагая элементы Theta (lg n), участвующие в конфликтах.

Во всяком случае, вот алгоритм. Сначала вы говорите, как сказал другой ответ, и итеративно идентифицируйте конфликт в O (lg n) вызовах оракула и удалите один элемент в конфликте из своего набора, пока не останетесь с набором, у которого нет конфликтов. Это занимает не более O ((lg n) ^ 2) вызовов оракула. Затем для каждого элемента Z, который вы удалили, вы положили Z в начале набора без конфликтов и выполнили двоичный поиск, чтобы найти более поздний элемент X, который создает конфликт, или определить, что ни один не существует. (И если такой X найден, удалите X и повторите). Таким образом, вы обнаруживаете все конфликты, начинающиеся с Z, и каждый такой конфликт встречается в O (lg n) вызовах oracle. Аналогичным образом вы помещаете Z в конец списка без конфликтов и выполняете двоичный поиск, чтобы найти все предыдущие элементы X, которые создают конфликт. Тогда остается только найти все конфликты между элементами, которые вы первоначально удалили на первом этапе алгоритма. Но из них существует только O (lg n) по предположению, поэтому это принимает O ((lg n) ^ 2) вызовы оракула. Таким образом, общее число вызовов оракула равно O ((lg n) ^ 2).