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

«У меня нет проблемы с» или «(изображение не загружается для меня). Вот мои рассуждения. Скажем, мы берем стандартный алгоритм кратчайшего маршрута, такой как Дейкстра, а затем используем равный вес, чтобы найти лучший путь. лучший Xr снизу 2 варианта

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

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

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

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

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

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

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

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

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

Определения:
Узел u - Текущий узел.
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
}

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

Многие ответы здесь сосредоточены на том, что это теоретически сложная проблема из-за ее 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. Точное решение такой модели относительно несложно; например, вы можете использовать пакет pulp в 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, которые, вероятно, будут намного быстрее.

Чтобы добавить к ответу Мизандриста: ваша проблема NP-complete NP-hard (см. Ответ dened).

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

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

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

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

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

Основная процедура переводит входные данные в граф и начинает обход в начальном узле.

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 ищет все узлы, которые являются необходимыми преемниками узла (которые связаны с n через И-отношение через 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 ищет кратчайшее решение среди всех возможных решений для необязательных соседей (ИЛИ). Этот алгоритм является полным перебором (будут проверены все возможные варианты выбора для соседей.

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

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

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

Мой код находится здесь.

Сценарий:

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

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

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

target = X, result=[]

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

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

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

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

Единственный узел E должен быть истинным. Итак, (E | C) всегда верно. Удалите его из мишени.

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

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

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

Добавьте к результату единственный узел B. Замените узел 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]

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

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

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

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

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

   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

2. Установите X как цель.
3. Вставьте B, H, K, Y, Z как факты.
4. Запустите прямую цепочку и остановитесь при первом появлении X (цель). В данном случае это должен быть кратчайший путь к достижению цели (просто не забудьте отслеживать использованные факты).

Дайте мне знать, если что-то неясно.

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

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

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

Genetic Step следующие:

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

б. мутация: мутация небольшого процента из них (например: 0,5%).

c. Оценка: оценка (также называемая фитнесом) всем индивидуумам.

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

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

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

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

Вот что вам предстоит решить:

1. Найдите генетический код для своего человека

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

В вашем случае это может быть группа букв, представляющая узел, который соблюдает ограничение ИЛИ и НЕ.

Например :

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

2. Найдите способ оценить человека

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

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

Например :

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

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

[A E B Y] как лучшая оценка, чем [A E Z B Y]

3. Выбор

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

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

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

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

Например :

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

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

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

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

5. Мутация

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

Например :

• Удалить узел

• Сделайте некоторую корректировку, чтобы соответствовать или, и ограничению.

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