Алгоритм зависимости - найдите минимальный набор пакетов для установки

Я работаю над алгоритмом, целью которого является найти минимальный набор пакетов для установки пакета "X".

Я объясню лучше с примера:

X depends on A and (E or C)
A depends on E and (H or Y)
E depends on B and (Z or Y)
C depends on (A or K)
H depends on nothing
Y depends on nothing
Z depends on nothing
K depends on nothing

Решение заключается в установке: A E B Y.

Вот образ, чтобы описать пример:

Есть ли алгоритм для решения проблемы без использования подхода грубой силы?

Я уже много читал об алгоритмах, таких как DFS, BFS, Dijkstra и т.д. Проблема в том, что эти алгоритмы не могут обрабатывать условие "ИЛИ".

UPDATE

Я не хочу использовать внешние библиотеки.

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

UPDATE

Одним из возможных решений могло бы быть вычисление всех возможных путей каждой вершины и для каждой вершины на возможном пути, делая то же самое. Таким образом, возможный путь для X будет (A E), (A C). Теперь для каждого элемента этих двух возможных путей мы можем сделать то же самое: A = (E H), (E Y)/E = (B Z), (B Y) и так далее... В конце мы можем объединить возможные пути каждой вершины в SET и выбрать ту, которая имеет минимальную длину.

Как вы думаете?

Ответ 1

К сожалению, нет надежды найти алгоритм, который намного лучше грубой силы, учитывая, что проблема на самом деле NP-hard (но даже не NP-complete).

Доказательство NP-твердости этой проблемы состоит в том, что минимальная проблема вершина покрывает (хорошо известная как NP-hard, а не NP-полная) легко приводима к нему:

С учетом графика. Позвольте создать пакет P _v для каждой вершины v графа. Также создайте пакет X, который "и" запрашивает (P _u или P _v) для каждого ребра (u, v) графа. Найдите минимальный набор пакетов, которые нужно установить для удовлетворения X. Тогда v находится в минимальном вершинном покрытии графа iff соответствующего пакета P _v находится в установочном наборе.

Ответ 2

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

В вашем случае способ решения проблемы состоит в том, чтобы сформулировать ее как смешанную целочисленную линейную программу, где для каждого пакета i существует двоичная переменная x_i. Вы можете преобразовать требования A requires (B or C or D) and (E or F) and (G) к ограничениям формы x_A <= x_B + x_C + x_D ; x_A <= x_E + x_F ; x_A <= x_G, и вы можете потребовать, чтобы пакет P был включен в окончательное решение с помощью x_P = 1. Решение такой модели точно относительно просто; например, вы можете использовать пакет пульпы в python:

import pulp

deps = {"X": [("A"), ("E", "C")],
        "A": [("E"), ("H", "Y")],
        "E": [("B"), ("Z", "Y")],
        "C": [("A", "K")],
        "H": [],
        "B": [],
        "Y": [],
        "Z": [],
        "K": []}
required = ["X"]

# Variables
x = pulp.LpVariable.dicts("x", deps.keys(), lowBound=0, upBound=1, cat=pulp.LpInteger)

mod = pulp.LpProblem("Package Optimization", pulp.LpMinimize)

# Objective
mod += sum([x[k] for k in deps])

# Dependencies
for k in deps:
    for dep in deps[k]:
        mod += x[k] <= sum([x[d] for d in dep])

# Include required variables
for r in required:
    mod += x[r] == 1

# Solve
mod.solve()
for k in deps:
    print "Package", k, "used:", x[k].value()

Это выводит минимальный набор пакетов:

Package A used: 1.0
Package C used: 0.0
Package B used: 1.0
Package E used: 1.0
Package H used: 0.0
Package Y used: 1.0
Package X used: 1.0
Package K used: 0.0
Package Z used: 0.0

Для очень больших экземпляров проблем это может занять слишком много времени. Вы можете либо принять потенциально субоптимальное решение с использованием тайм-аута (см. здесь), либо вы можете перейти от стандартных решателей с открытым исходным кодом к коммерческому решатель, такой как gurobi или cplex, который, вероятно, будет намного быстрее.

Ответ 3

"У меня проблема с" или "(изображение не загружается для меня). Вот мои рассуждения. Скажем, мы берем стандартного кратчайшего маршрута algo, такого как Dijkstras, а затем используем эквивалентный вес, чтобы найти лучший путь. Принимая ваш пример Выберите лучший вариант Xr из списка ниже

Xr= X+Ar+Er
Xr= X+Ar+Cr

где Ar = наилучший вариант из дерева A = H (и последующего дочернего) или = Y (и последующих дочерних элементов)

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

Однако нам нужно сначала определить, какой лучший выбор означает, предположить, что наименьшее количество зависимостей, т.е. кратчайший путь, является критерием. По логике выше мы назначаем вес 1 для X. Затем вперед

X=1
X=A and E or C hence X=A1+E1 and X=A1+C1
A= H or Y, assuming H and Y are  leaf node hence A get final weight as 1
hence , X=1+E1 and X=1+C1

Now for E and C
E1=B1+Z1 and B1+Y1 . C1=A1 and C=K1.
Assuming B1,Z1,Y1,A1and K1 are leaf node 

E1=1+1 and 1+1 . C1=1 and C1=1
ie E=2 and C=1

Hence
X=1+2 and X=1+1 hence please choose X=>C as the best route

Надеюсь, это очистит его. Также нам нужно позаботиться о циклических зависимостях X = > Y = > Z = > X, здесь мы можем назначить такие узлы равными нулю на уровне родительского или листового уровня node и заботиться о dependecy. "

Ответ 4

Чтобы добавить к Misandrist ответ: ваша проблема ~~NP-complete~~ NP-hard (см. расширенный ответ).

Изменить: прямое копирование экземпляра Установить обложку (U, S) в экземпляр "проблема с пакетом": сделать каждую точку z наземного множества U и требование И для X. Сделайте каждый набор из S, который покрывает точку z, а требование OR для z. Тогда решение проблемы с пакетом дает минимальное заданное покрытие.

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

Ответ 5

Я действительно считаю, что диаграммы являются подходящей структурой для этой проблемы. Обратите внимание, что A и (E или C) < == > (A и E) или (A и C). Таким образом, мы можем представить X = A и (E или C) со следующим набором направленных ребер:

A <- K1
E <- K1
A <- K2
C <- K2
K1 <- X
K2 <- X

По сути, мы просто разлагаем логику оператора и используем узлы "dummy" для представления AND.

Предположим, что мы разложим все логические выражения таким образом (фиктивные узлы Ki для ANDS и направленные ребра в противном случае). Затем мы можем представить ввод как DAG и рекурсивно пересечь DAG. Я думаю, что следующий рекурсивный алгоритм может решить проблему:

Определения:
Node u - Текущий Node.
S - посещенный набор узлов.
children (x) - возвращает соседних соседей x.

Алгоритм:

shortestPath u S = 
if (u has no children) {
    add u to S
    return 1
} else if (u is a dummy node) {
  (a,b) = children(u)
  if (a and b are in S) {
    return 0
  } else if (b is in S) { 
    x = shortestPath a S
    add a to S
    return x
  } else if (a in S) {
    y = shortestPath b S
    add b to S
    return y
  } else {
    x = shortestPath a S
    add a to S
    if (b in S) return x
    else {
        y = shortestPath b S
        add b to S
        return x + y
    }
  }
} else {
  min = Int.Max
  min_node = m
  for (x in children(u)){
    if (x is not in S) {
      S_1 = S
      k = shortestPath x S_1
      if (k < min) min = k, min_node = x
    } else {
      min = 1
      min_node = x
    }
  }
  return 1 + min
}

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

Ответ 6

Мой код здесь.

Сценарий:

Представьте ограничения.

X : A&(E|C)
A : E&(Y|N)
E : B&(Z|Y)
C : A|K

Подготовьте две переменные target и result. Добавьте цель node X.

target = X, result=[]

Добавьте единственный результат node X в результат. Замените node X своим зависимым от цели.

target = A&(E|C), result=[X]

Добавьте одиночный node A в результат. Замените node A с его зависимым от цели.

target = E&(Y|N)&(E|C), result=[X, A]

Одиночный node E должен быть правдой. Итак, (E | C) всегда истинно. Удалите его из цели.

target = E&(Y|N), result=[X, A]

Добавьте одиночный node E в результат. Замените node E его зависимым от цели.

target = B&(Z|Y)&(Y|N), result=[X, A, E]

Добавьте сингл node B. Замените node B его зависимым от цели.

target = (Z|Y)&(Y|N), result=[X, A, E, B]

Больше нет узлов. Затем разверните целевое выражение.

target = Z&Y|Z&N|Y&Y|Y&N, result=[X, A, E, B]

Замените Y & Y на Y.

target = Z&Y|Z&N|Y|Y&N, result=[X, A, E, B]

Выберите термин с наименьшим числом узлов. Добавьте все узлы в этот термин к цели.

target = , result=[X, A, E, B, Y]

Ответ 7

Я предлагаю вам сначала преобразовать граф в AND-OR Tree. После выполнения вы можете выполнить поиск в дереве для лучшего (где вы можете выбрать, что означает "лучший": кратчайший, самый низкий уровень памяти для пакетов в узлах и т.д.).

Предположим, что условие для установки X было бы чем-то вроде install(X) = install(A) and (install(E) or install(C)), заключается в группировке узлов OR (в данном случае: E и C) в один node, скажем EC, и преобразуем условие в install(X) = install(A) and install(EC).

В альтернативном варианте, основываясь на идее AND-OR Tree, вы можете создать собственный график AND-OR, используя идею группировки. Таким образом, вы можете использовать адаптацию алгоритма обход графа, который может быть более полезен в определенных сценариях.

Еще одним решением может быть использование Forward Chaining. Вам нужно будет выполнить следующие действия:

Преобразование (просто переписывание здесь условий):

A и (E или C) = > X

E и (H или Y) = > A

B и (Z или Y) = > E

(A and E) or (A and C) => X
(E and H) or (E and Y) => A
(B and Z) or (B and Y) => E

Задайте X как цель.
Вставьте B, H, K, Y, Z в качестве фактов.
Перемещение вперед и остановка в первом вхождении X (цель). Это должен быть самый короткий путь для достижения цели в этом случае (просто не забудьте отслеживать факты, которые были использованы).

Сообщите мне, если что-то неясно.

Ответ 8

Это пример Проблема ограничения ограничений. Существуют решения Constraint Solvers для многих языков, даже некоторые, которые могут работать на общих 3SAT-двигателях и, таким образом, запускаться на GPGPU.

Ответ 9

Поскольку граф состоит из двух разных типов ребер (отношения AND и OR), мы можем разбить алгоритм на две части: искать все узлы, которые являются обязательными для последователей node, и искать все узлы, из которых мы имеем для выбора одного единственного node (OR).

Узлы содержат пакет, список узлов, которые должны быть преемниками этого node (AND), список списка узлов, которые могут быть преемниками этого node (OR), и флаг, который отмечает, на котором шаг в алгоритме посещения node.

define node: package p , list required , listlist optional , 
             int visited[default=MAX_VALUE]

Основная процедура преобразует входной сигнал в график и начинает обход в начале node.

define searchMinimumP:
    input: package start , string[] constraints
    output: list

    //generate a graph from the given constraint
    //and save the node holding start as starting point
    node r = getNode(generateGraph(constraints) , start)

    //list all required nodes
    return requiredNodes(r , 0)

requiredNodes ищет все узлы, которые являются преемниками node (которые связаны с n через AND-отношение через 1 или несколько ребер).

define requiredNodes:
    input: node n , int step
    output: list

    //generate a list of all nodes that MUST be part of the solution
    list rNodes
    list todo

    add(todo , n)

    while NOT isEmpty(todo)
        node next = remove(0 , todo)
        if NOT contains(rNodes , next) AND next.visited > step
            add(rNodes , next)
            next.visited = step

    addAll(rNodes , optionalMin(rNodes , step + 1))

    for node r in rNodes
        r.visited = step

    return rNodes

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

define optionalMin:
    input: list nodes , int step
    output: list

    //find all possible combinations for selectable packages
    listlist optSeq
    for node n in nodes
        if NOT n.visited < step
            for list opt in n.optional
                add(optSeq , opt)

    //iterate over all possible combinations of selectable packages
    //for the given list of nodes and find the shortest solution
    list shortest
    int curLen = MAX_VALUE

    //search through all possible solutions (combinations of nodes)
    for list seq in sequences(optSeq)
        list subseq

        for node n in distinct(seq)
            addAll(subseq , requiredNodes(n , step + 1))

        if length(subseq) < curLen
            //mark all nodes of the old solution as unvisited
            for node n in shortest
                n.visited = MAX_VALUE

            curLen = length(subseq)
            shortest = subseq
        else
            //mark all nodes in this possible solution as unvisited
            //since they aren't used in the final solution (not at this place)
            for node n in subseq
                n.visited = MAX_VALUE

     for node n in shorest
         n.visited = step

     return shortest

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

ПРИМЕЧАНИЕ. Пока этот алгоритм не намного лучше грубой силы. Я обновлю, как только найду лучший подход.

Ответ 10

Другим (интересным) способом решить эту проблему является использование генетического алгоритма.

Генетический алгоритм является мощным, но вам нужно использовать множество параметров и найти лучший.

Генетический шаг следующий:

a. Создание: несколько случайных лиц, первое поколение (например: 100)

б. мутация: мутация с низким процентом из них (например: 0,5%)

с. Оценить: скорость (также называйте фитнес) всем человеком.

д. Воспроизведение: выберите (используя ставки) пару из них и создайте дочерний элемент (например: 2 ребенка)

е. Выбор: выберите "Родительский и дочерний", чтобы создать новое поколение (например: сохранить 100 по отдельности)

ф. Loop: вернитесь к шагу "a" и повторите весь процесс за раз (например: 400 поколений)

г. Выберите. Выберите человека последнего поколения с максимальной скоростью. Индивидуальное решение будет вашим.

Вот что вы должны решить:

Найти генетический код для вашего индивидуального

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

В вашем случае это может быть группа букв, представляющая node, которые рассматривают ограничение OR и NOT.

Например:

[A E B Y], [A C K H], [A E Z B Y]...

Найдите способ оценить индивидуальный

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

В вашем случае это может быть довольно легко: индивидуальная скорость = число node - количество отдельных node

Например:

[A E B Y] = 8 - 4 = 4

[A E Z B Y] = 8 - 5 = 3

[A E B Y] как более высокая скорость, чем [A E Z B Y]

Выбор

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

Например, используя Выбор колеса рулетки с генетическим алгоритмом

Воспроизведение

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

Например:

Возьмите node из первого и замените его на node второго.

Сделайте некоторую настройку для соответствия "или" и "ограничение".

[A E BY], [AC K H] = > [AC E HBY], [AEC K BY]

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

Мутация

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

Например:

Удалить node
Сделайте некоторую настройку, чтобы она соответствовала ограничениям "или" и "".

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