Проблема алгоритма выбора подграфа (динамическое программирование или NP)

У нас есть проблема с алгоритмом, не могли бы вы написать свои идеи по этому поводу, спасибо!

Имеется N узлов с K разными цветами. Некоторые из узлов имеют прямое соединение друг с другом, а некоторые нет. Мы хотим выбрать M узлов из этих N узлов, но эти M узлов должны быть соединены. Кроме того, наша выбранная группа из M узлов должна иметь минимальное количество соседей разных цветов. Лучших комбинаций может быть несколько, найти любую из них и есть цель.

Например, мы выбрали M узлов и в сумме эти M узлов имеют следующих соседей: 5 красных, 3 синих, 1 зеленый. В этом случае мы подсчитываем уникальные цвета, поэтому количество соседей различных цветов в этом случае равно 3. Мы хотим минимизировать это число, выбрав наилучшую возможную комбинацию M узлов.

Пример визуализации графика:

график

В этом примере предположим, что M = 4, тогда наилучшей комбинацией узлов будет {9, 10, 11, 12}, поскольку в этой группе есть только один сосед, желтый. Если мы выберем {0, 1, 3, 5}, соседями этой комбинации будут {2, 4, 6}, которые состоят из 2 красных соседей и 1 зеленого соседа; что дает 2 балла, так как мы ищем разное количество цветных соседей.

Является ли этот вопрос алгоритма NP-полным? Как нам поступить? Если это не NP-полный алгоритм, какой лучший алгоритм мы можем использовать для решения этой проблемы? Можем ли мы комбинировать графовые алгоритмы, такие как алгоритмы Прима, Крускала, Флойда Уоршелла или алгоритмы обхода?


algorithm graph-theory floyd-warshall minimum-spanning-tree np-complete
person dornekci    schedule 20.05.2021    source источник
comment
Поскольку у вас нет кода, я бы сказал, что этот вопрос лучше подходит для SE по математике, SE по исследованию операций или SE по теоретической информатике. Вы можете попытать счастья там!   -  person N. Wouda    schedule 20.05.2021
comment
Если мы можем установить K = N и M = N/log N, то это NP-сложно путем редукции из задачи расширения малого множества. Это, очевидно, с фиксированными параметрами, управляемыми в M, и я думаю, что это может быть с фиксированными параметрами, управляемыми в K (со временем выполнения, как O (2 ^ K poly (N)). В зависимости от того, в каком режиме мы находимся, я бы порекомендуйте либо динамическое программирование, либо SMT-решатель.   -  person David Eisenstat    schedule 20.05.2021

Ответы (2)


arrow_upward
0
arrow_downward

Если это проблема NP, для ее решения можно использовать ASP. Учитывая instance.lp

color(0,yellow).
color(3,yellow).
color(8,yellow).
color(10,yellow).
color(2,green).
color(5,green).
color(12,green).
color(7,blue).
color(1,red).
color(4,red).
color(6,red).
color(9,red).
color(11,red).

edge(0,5).
edge(0,1).
edge(0,2).
edge(0,6).
edge(5,3).
edge(5,4).
edge(6,4).
edge(3,4).
edge(2,7).
edge(7,8).
edge(8,9).
edge(5,3).
edge(9,10).
edge(9,11).
edge(9,12).
edge(11,12).

edge(B,A) :- edge(A,B).

и encoding.lp

node(X) :- color(X,_).

%select exactly one start node
1 {start(X) : node(X)} 1.

% start node is in sub graph
sub(X) :- start(X).
% for any node in the sub graph you can add any connected node
{sub(Y) : edge(X,Y)} :- sub(X).

% it is wrong if we do not have exactly m nodes in the sub graph
:- not m = #sum {1,X: sub(X)}.

#minimize {1,C : sub(X), edge(X,Y), not sub(Y), color(Y,C)}.

#show sub/1.

Вызов clingo encoding.lp instance.lp --const m=4 дает вам оптимальное решение:

sub(3) sub(5) sub(4) sub(6)

Звонок clingo encoding.lp instance.lp --const m=4 --opt-mode=optN --project дает вам все оптимальные решения. Инструменты можно найти по адресу https://potassco.org/.

person Max Ostrowski    schedule 21.05.2021

arrow_upward
0
arrow_downward

Подграф { 4 3 5 6 } также является хорошим ответом, имеющим одного красного соседа.

Я обнаружил, что этот подграф запускает небольшую программу под названием subs.

C:\Users\James\code\subs>subs
l 0 1 1
l 0 6 1
l 0 5 1
l 0 2 1
l 2 7 1
l 3 5 1
l 3 4 1
l 4 6 1
l 4 5 1
l 7 8 1
l 8 9 1
l 9 10 1
l 9 11 1
l 9 12 1
l 11 12 1
n 0 yellow
n 1 red
n 2 green
n 3 yellow
n 4 red
n 5 green
n 6 red
n 7 blue
n 8 yellow
n 9 red
n 10 yellow
n 11 red
n 12 green
<-cPathFinder::read
n1 n0 n6 n5  colors 3
n1 n0 n6 n2  colors 3
n1 n0 n6 n4  colors 2
n1 n0 n5 n2  colors 3
n1 n0 n5 n3  colors 2
n1 n0 n5 n4  colors 3
n1 n0 n2 n7  colors 3
n0 n6 n5 n2  colors 3
n0 n6 n5 n3  colors 2
n0 n6 n5 n4  colors 3
n0 n6 n2 n7  colors 3
n0 n6 n2 n4  colors 4
n0 n6 n3 n4  colors 2
n0 n5 n2 n7  colors 2
n0 n5 n2 n3  colors 2
n0 n5 n2 n4  colors 3
n0 n5 n3 n4  colors 2
n0 n2 n7 n8  colors 2
n6 n5 n3 n4  colors 1
n2 n7 n8 n9  colors 3
n7 n8 n9 n10  colors 2
n7 n8 n9 n11  colors 2
n7 n8 n9 n12  colors 3
n8 n9 n10 n11  colors 2
n8 n9 n10 n12  colors 2
n8 n9 n11 n12  colors 2
n9 n10 n11 n12  colors 1
n0 n6 n5 n2  colors 3
n0 n6 n5 n3  colors 2
n0 n6 n5 n4  colors 3
n0 n6 n2 n7  colors 3
n0 n6 n2 n4  colors 4
n0 n6 n3 n4  colors 2
n0 n5 n2 n7  colors 2
n0 n5 n2 n3  colors 2
n0 n5 n2 n4  colors 3
n0 n5 n3 n4  colors 2
n0 n2 n7 n8  colors 2
n6 n5 n3 n4  colors 1
n2 n7 n8 n9  colors 3
n7 n8 n9 n10  colors 2
n7 n8 n9 n11  colors 2
n7 n8 n9 n12  colors 3
n8 n9 n10 n11  colors 2
n8 n9 n10 n12  colors 2
n8 n9 n11 n12  colors 2
n9 n10 n11 n12  colors 1
n6 n5 n3 n4  colors 1
n2 n7 n8 n9  colors 3
n7 n8 n9 n10  colors 2
n7 n8 n9 n11  colors 2
n7 n8 n9 n12  colors 3
n8 n9 n10 n11  colors 2
n8 n9 n10 n12  colors 2
n8 n9 n11 n12  colors 2
n9 n10 n11 n12  colors 1
n2 n7 n8 n9  colors 3
n7 n8 n9 n10  colors 2
n7 n8 n9 n11  colors 2
n7 n8 n9 n12  colors 3
n8 n9 n10 n11  colors 2
n8 n9 n10 n12  colors 2
n8 n9 n11 n12  colors 2
n9 n10 n11 n12  colors 1
n2 n7 n8 n9  colors 3
n7 n8 n9 n10  colors 2
n7 n8 n9 n11  colors 2
n7 n8 n9 n12  colors 3
n8 n9 n10 n11  colors 2
n8 n9 n10 n12  colors 2
n8 n9 n11 n12  colors 2
n9 n10 n11 n12  colors 1
n7 n8 n9 n10  colors 2
n7 n8 n9 n11  colors 2
n7 n8 n9 n12  colors 3
n8 n9 n10 n11  colors 2
n8 n9 n10 n12  colors 2
n8 n9 n11 n12  colors 2
n9 n10 n11 n12  colors 1
n8 n9 n10 n11  colors 2
n8 n9 n10 n12  colors 2
n8 n9 n11 n12  colors 2
n9 n10 n11 n12  colors 1
n8 n9 n10 n11  colors 2
n8 n9 n10 n12  colors 2
n8 n9 n11 n12  colors 2
n9 n10 n11 n12  colors 1
n8 n9 n10 n11  colors 2
n8 n9 n10 n12  colors 2
n8 n9 n11 n12  colors 2
n9 n10 n11 n12  colors 1
n9 n10 n11 n12  colors 1

subgraph n6, n5, n3, n4,   has 1 differently colored neighbours

Ничего умного в сабах нет. Он генерирует подграфы и ищет в них связный подграф, который имеет наименьшее количество соседей уникального цвета. Есть много вложенных циклов, так что это не будет хорошо, когда есть тысячи узлов.

Код находится по адресу https://gist.github.com/JamesBremner/5a3965cc725c54dcaabd4beb44f9104f.

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

person ravenspoint    schedule 20.05.2021