Как сделать запрос из Направленного ациклического графа с эксклюзивными подмножествами - PullRequest
6 голосов
/ 23 сентября 2011

Вопрос в абстрактных терминах:

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

Вопрос в конкретных терминах:

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

Есть имя для этой проблемы или группы проблем?Стандартный алгоритм, который я могу исследовать, чтобы найти решение?


Возможные области решения:

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

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

1 Ответ

1 голос
/ 23 сентября 2011

Я думаю, что набор вершин, вытекающих из заданного выбора, выглядит сбивающим с толку, потому что на самом деле существует основная проблема оптимизации или удовлетворения: для сборки A вы можете удовлетворить ее зависимости через B1, B2 или B3, и каждый из нихВ этом случае выбор имеет свои собственные последствия.

Если мы рассматриваем это как проблему логического удовлетворения, то мы могли бы рассмотреть проблему, когда сборки бывают только двух версий, например, А1 или А2.Тогда такой пункт, как (a или b или не c), будет преобразован в сборку верхнего уровня, для которой требуется A1 или B1 или C2 - возможно, косвенно через X1, X2 и X3 - и сочетание предложений будет преобразовано в верхний верхнийсборка уровня, для которой требовались все сборки верхнего уровня.Поэтому я думаю, что если бы вы могли эффективно решить общую проблему, вы могли бы эффективно решить 3-SAT, а затем P = NP.

Любопытно, что если у вас нет ограничения, что вам разрешается только одна сборкакаждый тип (А1 или А2 или А3, но более одного за один раз), а затем задача очень легко переводится в предложения Хорна (Кнут, том 4, раздел 7.1.1, стр. 57), для которых проблема выполнимости может быть эффективно решена.Для этого вы работаете с обратными натуральными переменными, так что X1 означает, что A1 не включен.Затем, если вы рассматриваете версию предложения Horn как способ ослабления вашей проблемы, игнорируя ограничение, что может поддерживаться не более одной версии каждой сборки, вы получаете механизм, который сообщает вам, что какая-то версия сборки A1 не может быть в решении, потому что X1 = не А1 верно в ядре решения Хорна и, следовательно, верно в каждом удовлетворительном назначении.

...