Распечатывает минимальный набор пакетов, необходимых для установки пакета

Question

Мне нужно создать структуру данных, представляющую зависимости между пакетами.

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

Например, предположим, что у меня есть следующий situtation:

1. упаковке1:
2. package2: упаковке1
3. упаковке3: упаковке1, package2
4. package4: упаковке1 | упаковка3
5. упаковка5: упаковка1, упаковка2 | упаковке3

Эта ситуация означает, что:

1. пакет 1 не имеет зависимостей.
2. упаковка 2 зависит от упаковки 1 (нам необходимо установить пакет 1).
3. упаковка 3 зависит от упаковки 1 и 2 (мы должны установить оба)
4. упаковка 4 зависит от пакета 1 или 3 (мы можем установить 1 или 3, но нам нужно выбрать лучший выбор, что означает выбор которые делают пакет 4 зависит от менее пакетов)
5. пакет 5 зависит от упаковки 1, и это зависит также либо на упаковке 2 или 3 (опять же, нам нужно выбрать лучший выбор)

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

Как их выбрать?

Почему, например, упаковка 4 должна зависеть от упаковки 1 вместо 3?

Мы могли бы проверить, какие пакеты пакетов 1 и 3 зависят от них, но как насчет того, если у нас есть 10000 вариантов, но нам нужен только 1 лучший выбор? Для этого понадобились бы тысячи петель и вещи, слишком сложные. Может быть, что-то простое, но я не знаю, что.

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

Answer 1

Мы можем моделировать его как проблему псевдобулевого оптимизации.

Предположим, есть k упаковки. Определить k булевых переменных x_i, где x_i истинно тогда и только тогда, когда окончательный выбор - установить package_i. Таким образом, целью является минимизация суммирования x_i, где 1 < = i < = k. Если для каждого пакета требуется различная «стоимость» для установки (например, размер пакета), вы можете свести к минимуму взвешенную сумму x_i.

Чтобы моделировать ограничение «package5: package1, package2 | package3», мы могли обнаружить, что «package5 установлен» подразумевает «package1 установлен». Если псевдо-логический оптимизатор поддерживает ограничения представлены в Conjunctive normal form, то она может быть записана в виде

(!x_5 + x_1) 

, если только линейные неравенства разрешены, то это

(1 - x_5) + x_1 >= 1 

Другая половина, «установлена ​​упаковке5 "подразумевает„упаковке2 и/или установлен упаковке3“, можно записать в виде

(!x_5 + x_2 + x_3) 

или

(1 - x_5) + x_2 + x_3 >= 1 

Наконец, вы должны заявить требуемый пакет.

x_k 

или

x_k = 1 

Теперь, когда мы смоделировали эту проблему как псевдо-булевой задачи оптимизации, вы могли бы назвать любой решатель доступны и решить. Вы можете обратиться к Pseudo Boolean Competition за новейшими решателями.

Answer 2

Вы можете создать направленный граф с двумя типами узлов:

• package узлы, чьи дети объединяются с помощью элемента И логики
• OR узлы, чьи дети объединяются с использованием логики ИЛИ

Все дуги, начиная с узла, представляют его зависимости.

Для примера это создало бы следующий график:

Если вы должны оценить минимальный набор зависимостей для пакета, вы можете посетить график с использованием алгоритма глубины первого поиска:

• при посещении package узла вы просуммировать количество зависимостей своих детей
• , когда вы посещаете OR узел вы считаете минимальное количество зависимостей своих детей

Пример кода

Ниже приведен пример того, как реализовать это в Python (я использовал Python, как его синтаксис почти как псевдо-кода; Вы должны быть в состоянии получить его суть):

#!/usr/bin/env python3 

class Package: 
    # Constructor 
    def __init__(self, name, dependencies): 
     self.name = name 
     self.dependencies = set(dependencies) 
    # Needed to print the package 
    def __str__(self): 
     return self.name 
    # This method returns the optimal set of dependencies for this package 
    def getOptimalDependencies(self): 
     optimalDependencies = set() 
     for dependency in self.dependencies: 
      optimalDependencies = optimalDependencies.union(dependency.getOptimalDependencies()) 
     optimalDependencies.add(self) 
     return optimalDependencies 

class Or: 
    # Constructor 
    def __init__(self, dependencies): 
     self.dependencies = set(dependencies) 
    # This method returns the optimal set of dependencies 
    # of the packages combined with this 'OR' 
    def getOptimalDependencies(self): 
     optimalDependencies = set() 
     for dependency in self.dependencies: 
      alternativeDependencies = dependency.getOptimalDependencies() 
      if len(optimalDependencies) == 0 or len(alternativeDependencies) < len(optimalDependencies): 
       optimalDependencies = alternativeDependencies 
     return optimalDependencies 

Вы можете создать пакеты вашего, например, как:

package1 = Package("package1", []) 
package2 = Package("package2", [package1]) 
package3 = Package("package3", [package1, package2]) 
package4 = Package("package4", [Or([package1, package3])]) 
package5 = Package("package5", [package1, Or([package2, package3])]) 

Чтобы получить список оптимальных dependecies для package5 вы можете затем позвоните по телефону package5.getOptimalDependencies().

Если мы выводим его:

print(','.join(map(str, package5.getOptimalDependencies()))) 

мы получаем:

package2,package1,package5 

Если у вас есть зависимости циклов вы должны ввести некоторый контроль за этим.