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

Question

У меня проблема с алгоритмом зависимостей, зависимость похожа на зависимость от 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 

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

более того, я, возможно, потребуется обновить компонент а и 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

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

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

Заранее благодарен!

Answer 1

Это вариант satisfiability problem. osgi тоже имеет дело с этим. Таким образом, вы можете посмотреть в спецификации osgi и/или реализациях и посмотреть, как они ее решают.

Answer 2

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

В свете этой редукции имеет смысл сформулировать вашу проблему как constraint satisfaction. Каждый компонент является переменной, возможными значениями которой являются версии этого компонента, плюс «не установлен», если не установлен этот компонент. Для каждого компонента 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 и т. Д. Когда больше нет упрощения, мы должны угадать; одна стратегия состоит в том, чтобы выбрать компонент с наименьшим количеством версий и рекурсивно попробовать все из них (откат).