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

У меня проблема с алгоритмом зависимостей, зависимость аналогична зависимости от maven, за исключением строгой версии.

Например:

component A, version 1 depends on: component B, version 1~3; and component C, version 2~3
component D, version 1 depends on: component B, version 2~4; and component C, version 1~2

Теперь я хочу получить зависимости, когда хочу установить компонент A, версию 1 и компонент D, версию 1. Потому что все они зависят от компонента B, C, поэтому мне нужен правильный алгоритм для получения правильной версии B и С

Кроме того, мне может понадобиться обновить компоненты A и D. Например, теперь у меня есть ниже новых версий:

component A, version 2 depends on: component B, version 3~5; and component C, version 4~5
component A, version 3 depends on: component B, version 6~7; and component C, version 4~5
component D, version 2 depends on: component B, version 3~4; and component C, version 3~4

Теперь мне нужен алгоритм для получения правильной версии A и D, которую я могу обновить до и всех их зависимостей. Одна из проблем заключается в том, что компонент A, версия 3 и компонент D, версия 2 имеет конфликт зависимостей компонента B

Существует ли существующий алгоритм для решения такой проблемы? Или аналогичная (более простая) проблема. Есть ли у вас предложения?

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

Спасибо заранее!

Ответ 1

Эта проблема NP-hard через следующее сокращение от 3SAT. Учитывая формулу 3CNF, для каждой переменной есть компонент с двумя версиями, и для каждого предложения есть компонент с тремя версиями. Мы хотели бы установить одну версию "супер" компонента, которая зависит от всех компонентов предложения, но не придирчивы к версиям. Для каждого предложения компонент 1 предложения зависит от первой переменной, которая должна появиться в предложении, с требуемой версией 1, если литерал положителен и 0, если он отрицательный. Параметр предложения 2 зависит от второй переменной и т.д. Мы можем установить суперкомпонент тогда и только тогда, когда формула выполнима.

В свете этого сокращения имеет смысл сформулировать вашу проблему как ограничение ограничений. Каждый компонент является переменной, возможными значениями которой являются версии этого компонента, плюс "не установлен", если не установлен этот компонент. Для каждого компонента A с версией, зависящей от версии компонента B, существует ограничение, включающее переменную для A и B, ограничивающую выбор версий определенным подмножеством произведения их доменов. Для A и B в первом примере это {(1, 1), (1, 2), (1, 3)}, так как версия 1 зависит от B-версий 1 ~ 3. Если версия 2 из А была также доступна, это ограничение было бы {(1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (2, 5) }. Если нам не нужно было устанавливать A или B, тогда {(none, none), (none, 1), (none, 2), (none, 3), (none, 4), (none, 5), (1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (2, 5)}.

Поскольку ваши экземпляры невелики, вы, вероятно, хотите получить полный поиск отскакивания, возможно, с распространением ограничений. Общий алгоритм распространения ограничений AC-3, который обеспечивает согласованность дуги, а именно, удаление из рассмотрения всех версий, которые явно не сработают, на основе того, что было устранено. Например, учитывая ограничение {(1, 1), (1, 2), (1, 3)}, мы можем исключить B = none, так как никто никогда не появляется. Теперь, когда выбор для B ограничен, мы можем сделать выводы о зависимости B от C и т.д. Когда больше не осталось упрощения, мы должны угадать; одна стратегия состоит в том, чтобы выбрать компонент с наименьшим количеством версий и рекурсивно попробовать все из них (обратное отслеживание).

Ответ 1

Ответ 2