Алгоритм разрешения зависимостей

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

В каждом пакете есть список версий, и каждая версия содержит следующую информацию:

  • Соответствующий идентификатор
  • Зависимости (список пакетов и для каждого пакета набор допустимых версий)
  • Конфликты (список пакетов и для каждого пакета - набор версий, которые вызывают проблемы вместе с этой версией).
  • Предоставляет (список пакетов и для каждого пакета - набор версий, которые этот пакет также содержит/содержит)

Для текущего состояния у меня есть список пакетов и их текущие версии.

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

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

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

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

Единственная идея, которую я имею до сих пор, заключается в создании структуры всех возможных состояний для всех возможных версий рассматриваемых пакетов, а затем удаления недопустимых состояний. Я действительно надеюсь, что это не единственное решение, так как оно чувствует себя "грубой силой". Пребывание в течение нескольких секунд для ~ 500 доступных пакетов с ~ 100 версиями каждый, и ~ 150 установленных пакетов были бы хорошей целью (хотя чем быстрее, тем лучше).

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

struct Version
    integer id
    list<Package, set<integer>> dependencies
    list<Package, set<integer>> conflicts
    list<Package, set<integer>> provides

struct Package
    string id
    list<Version> versions

struct State
    map<Package, Version> packages
    map<Package, boolean> isVersionLocked

State resolve(State initialState, list<Package> availablePackages, list<Package> newPackages)
{
    // do stuff here
}

(если вы должны иметь реальный код или знать о существующей реализации того, что делает это (на любом языке, предпочитаемом на С++), не стесняйтесь упоминать его в любом случае)

Ответы

Ответ 1

Это NP-hard

Некоторые плохие новости: эта проблема NP-hard, поэтому, если P = NP, нет алгоритма, который бы мог эффективно решить все его экземпляры. Я докажу это, показывая, как преобразовать в полиномиальное время любой данный случай NP-жесткой проблемы 3SAT в структуру графа зависимостей, подходящую для ввода в вашу проблему, и как превратить выход любого алгоритма разрешения зависимостей в эту проблему обратно в решение исходной задачи 3SAT снова в полиномиальное время. Логика в основном состоит в том, что если бы существовал какой-то алгоритм, который мог бы решить проблему разрешения зависимостей в полиномиальное время, то он также разрешил бы любой экземпляр 3SAT в полиномиальное время, - и поскольку компьютерные ученые потратили десятилетия на поиск такого алгоритма, не найдя его, это считается невозможным.

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

Сначала давайте сформулируем слегка расслабленную версию проблемы разрешения зависимостей, в которой мы предполагаем, что пакеты уже не установлены. Все, что нам нужно, - это алгоритм, который при заданном пакете возвращает набор версий пакетов для установки: (a) включает некоторую версию целевого пакета и (b) удовлетворяет все зависимости и свойства конфликта для каждого пакета в set или возвращает "IMPOSSIBLE", если набор версий пакетов не будет работать. Ясно, что если эта проблема NP-hard, то это более общая проблема, в которой мы также указываем набор уже установленных версий пакета, которые не подлежат изменению.

Построение экземпляра

Предположим, нам дан экземпляр 3SAT, содержащий n предложений и k переменных. Мы создадим 2 пакета для каждой переменной: один соответствует литералу x_k, а один соответствует литералу! X_k. Пакет x_k будет иметь конфликт с пакетом! X_k и наоборот, гарантируя, что пакет управления пакетами будет установлен не более одного из этих двух пакетов. Все эти "буквальные" пакеты будут иметь только одну версию и никаких зависимостей.

Для каждого предложения мы также создадим один "родительский" пакет и 7 версий "дочернего" пакета. Каждый родительский пакет будет зависеть от любой из 7 версий его дочернего пакета. Пакеты для детей соответствуют способам выбора по крайней мере одного элемента из набора из 3 элементов и каждый из них будет иметь 3 зависимости от соответствующих пакетов литералов. Например, в предложении (p,! Q, r) будут иметь версии дочерних пакетов, имеющие зависимости от буквенных пакетов (p, q,! R), (! P,! Q,! R), (! P, q, r), (p,! q,! r), (p, q, r), (! p,! q, r) и (p,! q, r): первые 3 версии удовлетворяют точно одному из литералы p,! q или r; следующие 3 версии удовлетворяют ровно 2; и последнее удовлетворяет всем 3.

Наконец, мы создаем пакет "root", в котором все пакеты предложений родительского пакета n являются его зависимостями. Это будет пакет, который мы запрашиваем у менеджера пакетов.

Если мы запустим диспетчер пакетов в этом наборе версий пакета 2k + 8n + 1, попросив его установить корневой пакет, он либо вернет "IMPOSSIBLE", либо список версий пакетов для установки. В первом случае проблема 3SAT неудовлетворительна. В последнем случае мы можем легко извлечь значения для переменных: если был установлен литеральный пакет для x_k, установите x_k в true; если установлен литеральный пакет! x_k, установите x_k в false. (Обратите внимание, что не будет никаких переменных, в которых не установлен ни один пакет буклета: каждая переменная появляется хотя бы в одном предложении, и каждое предложение создает 7 дочерних пакетов, по крайней мере один из которых должен быть установлен, и который заставит установить один из двух литералов для этой переменной.)

Даже некоторые ограничения жесткие

Эта конструкция не использует предварительно установленные пакеты или информацию "Предоставляет", поэтому проблема остается NP-жесткой, даже если это запрещено. Более интересно, учитывая наше предположение о том, что одновременно может быть установлена ​​не более одной версии любого пакета, проблема остается NP-жесткой, даже если мы не допускаем конфликтов: вместо создания литералов x_k и! X_k отдельных пакетов с предложениями о конфликтах в каждом направлении мы просто делаем их двумя разными версиями одного и того же пакета!