Algorytm do rozwiązywania zależności zależnych od zakresu wersji

Question

Mam problem z algorytmem zależności, zależność jest podobna do zależności maven, z wyjątkiem ścisłego zakresu wersji.

Na przykład:

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 

Teraz chcę uzyskać zależnościami gdy chcę zainstalować składnik A, wersja 1 i składnik D, wersja 1. Ponieważ są to wszystko zależy od składnika B, C, więc potrzebuję poprawnego algorytmu dostać poprawną wersję B i C

Co więcej, może muszę uaktualnić składnik a i D. na przykład, teraz mam poniżej nowych wersjach:

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 

Teraz potrzebuję algorytmu, aby uzyskać poprawną wersję A i D, do której mogę uaktualnić i wszystkie ich zależności. Jednym z problemów jest komponent A, wersja 3 i komponent D, wersja 2 ma konflikt zależności komponentu B

Czy istnieje algorytm rozwiązania tego problemu? Lub podobny (łatwiejszy) problem. Czy masz jakieś propozycje?

Ponieważ nie powinno być dużo danych, nie należy brać pod uwagę wydajności.

Z góry dziękuję!

Answer 1

To jest wariant satisfiability problem. osgi też musi sobie z tym poradzić. Możesz więc zajrzeć do specyfikacji i/lub implementacji osgi i zobaczyć, jak je rozwiązują.

Answer 2

Ten problem jest NP-trudny poprzez następujące zmniejszenie z 3SAT. Biorąc pod uwagę formułę 3CNF, dla każdej zmiennej występuje komponent z dwiema wersjami, a dla każdej klauzuli występuje komponent w trzech wersjach. Chcielibyśmy zainstalować jedną wersję "super" komponentu, który zależy od wszystkich składników klauzuli, ale nie jest wybredny w stosunku do wersji. W przypadku każdej klauzuli komponent klauzuli 1 zależy od pierwszej zmiennej, która pojawia się w klauzuli, z wersją 1 wymaganą, jeśli literał jest dodatni, a 0, jeśli jest ujemna. Składnik klauzuli 2 zależy od drugiej zmiennej itd. Możemy zainstalować super składnik wtedy i tylko wtedy, gdy formuła jest satysfakcjonująca.

W świetle tego zmniejszenia, warto sformułować problem jako constraint satisfaction. Każdy komponent jest zmienną, której możliwe wartości są wersjami tego komponentu plus "niezainstalowany", jeśli nie ma opcji, że zainstalowany jest dany komponent. Dla każdego komponentu A z wersją, która zależy od wersji składnika B, istnieje ograniczenie obejmujące zmienną dla A i B, ograniczającą wybór wersji do konkretnego podzbioru produktu ich domen. Dla A i B w pierwszym przykładzie jest to {(1, 1), (1, 2), (1, 3)}, ponieważ A wersja 1 zależy od wersji B 1 ~ 3. Jeżeli wersja 2 punktu A również byłaby dostępna, to ograniczenie to wynosiłoby {(1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (2, 5) }. Jeśli nie musimy instalować A lub B, wtedy {(none, none), (none, 1), (none, 2), (none, 3), (none, 4), (none, 5), (1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (2, 5)}.

Ponieważ Twoje instancje są małe, prawdopodobnie potrzebujesz kompletnego przeszukiwania wstecznego, prawdopodobnie z propagacją ograniczeń. Powszechnym algorytmem propagacji ograniczeń jest AC-3, który wymusza spójność łuku, a mianowicie usunięcie z rozważenia wszystkich wersji, które wyraźnie nie będą działać, w oparciu o to, co zostało wyeliminowane. Na przykład, biorąc pod uwagę ograniczenie {(1, 1), (1, 2), (1, 3)}, możemy wyeliminować B = none, ponieważ żaden nie pojawia się. Teraz, gdy wybory dla B są ograniczone, możemy wyciągnąć wnioski na temat zależności B od B, itd. Gdy nie ma już potrzeby dalszego uproszczenia, musimy zgadywać; jedną z nich jest wybranie komponentu z najmniejszą liczbą wersji i rekurencyjne wypróbowanie ich wszystkich (backtracking).