Старый, неправильный ответ, но начните здесь
Во-первых, вы должны признать, что у вас есть двудольный граф .То есть вы можете закрасить узлы красным и синим так, чтобы никакие ребра не соединяли красный узел с красным узлом или синий узел с синим узлом.
Далее, признайте, что вы пытаетесь решить проблема вершинного покрытия .Из Википедии:
В математической дисциплине теории графов покрытие вершины (иногда покрытие узла) графа представляет собой набор вершин, так что каждое ребро графа инцидентно по крайней мере одной вершине.из набора.Проблема нахождения минимального покрытия вершин является классической задачей оптимизации в информатике и является типичным примером задачи NP-сложной оптимизации с алгоритмом аппроксимации.
Поскольку у вас есть специальный граф,Разумно думать, что, возможно, NP-хард не относится к вам.Эта мысль приводит нас к теореме Кенига , которая связывает проблему максимального соответствия с проблемой минимального покрытия вершин.Зная это, вы можете применить алгоритм Хопкрофта – Карпа , чтобы решить эту проблему за O (| E | √ | V |) времени, хотя вам, вероятно, потребуется джиггерэто немного, чтобы гарантировать, что вы сохраняете все B узлы.
Новый, правильный ответ
Оказывается, что это колебание - создание«проблема покрытия вершин ограниченного двудольного графа», которая спрашивает нас, существует ли покрытие вершин, которое использует менее a A-узлов и менее b B-узлов.Проблема в том, что NP-завершена, так что не стоит.Джиггеринг был сложнее, чем я думал!
Но использование меньшего, чем минимальное количество узлов, не является ограничением, которое мы хотим.Мы хотим убедиться, что используется минимальное количество A-узлов и максимальное количество B-узлов.
Теорема Кенига, приведенная выше, является частным случаем задачи о максимальном потоке.Размышление о проблеме с точки зрения потоков приводит нас довольно быстро к задачам с минимальными затратами .
В этих задачах нам дан график, ребра которого имеют указанные пропускную способность и удельные затраты на транспортировку,Цель состоит в том, чтобы найти минимальные затраты, необходимые для перемещения запаса заданного количества из произвольного набора узлов-источников в произвольный набор узлов-получателей.
Оказывается, ваша проблема может быть преобразована в минимумпроблема потока затрат.Для этого сгенерируем исходный узел, который подключается ко всем узлам A , и узел приемника, который подключается ко всем узлам B .
Теперь давайтемы делаем стоимость использования ребра Source-> A равной 1, а все остальные ребра стоим равным нулю.Далее, давайте сделаем емкость ребер Source-> A равной бесконечности, а емкость всех остальных ребер равной 1.
Это выглядит следующим образом:
Красные края имеют стоимость = 1, емкость = инф.Синие ребра имеют Cost = 0, Capacity = 1.
Теперь решение проблемы минимального потока становится эквивалентным использованию как можно меньшего количества красных ребер.Любое красное ребро, которое не используется, выделяет поток 0 соответствующему узлу A, и этот узел можно удалить из графика.И наоборот, каждый узел B может передавать только одну единицу потока в приемник, поэтому все узлы B должны быть сохранены для решения проблемы.
Поскольку мы преобразовали вашу проблему в эту стандартную форму,мы можем использовать существующие инструменты, чтобы получить решение;а именно, Инструменты исследования операций Google .
Это дает следующий ответ на приведенный выше график:
Красные края не используются, а черные используются.Обратите внимание, что если красный край выходит из источника, к которому подключается A-узел, он не генерирует черные края.Также обратите внимание, что каждый B-узел имеет по крайней мере один входящий черный край.Это удовлетворяет ограничения, которые вы поставили.
Теперь мы можем обнаружить A-узлы, которые нужно удалить, ища ребра Source-> A с нулевым использованием.
Исходный код
Исходный код, необходимый для генерации приведенных выше рисунков и связанных с ними решений, выглядит следующим образом:
#!/usr/bin/env python3
#Documentation: https://developers.google.com/optimization/flow/mincostflow
#Install dependency: pip3 install ortools
from __future__ import print_function
from ortools.graph import pywrapgraph
import matplotlib.pyplot as plt
import networkx as nx
import random
import sys
def GenerateGraph(Acount,Bcount):
assert Acount>5
assert Bcount>5
G = nx.DiGraph() #Directed graph
source_node = Acount+Bcount
sink_node = source_node+1
for a in range(Acount):
for i in range(random.randint(0.2*Bcount,0.3*Bcount)): #Connect to 10-20% of the Bnodes
b = Acount+random.randint(0,Bcount-1) #In the half-open range [0,Bcount). Offset from A's indices
G.add_edge(source_node, a, capacity=99999, unit_cost=1, usage=1)
G.add_edge(a, b, capacity=1, unit_cost=0, usage=1)
G.add_edge(b, sink_node, capacity=1, unit_cost=0, usage=1)
G.node[a]['type'] = 'A'
G.node[b]['type'] = 'B'
G.node[source_node]['type'] = 'source'
G.node[sink_node]['type'] = 'sink'
G.node[source_node]['supply'] = Bcount
G.node[sink_node]['supply'] = -Bcount
return G
def VisualizeGraph(graph, color_type):
gcopy = graph.copy()
for p, d in graph.nodes(data=True):
if d['type']=='source':
source = p
if d['type']=='sink':
sink = p
Acount = len([1 for p,d in graph.nodes(data=True) if d['type']=='A'])
Bcount = len([1 for p,d in graph.nodes(data=True) if d['type']=='B'])
if color_type=='usage':
edge_color = ['black' if d['usage']>0 else 'red' for u,v,d in graph.edges(data=True)]
elif color_type=='unit_cost':
edge_color = ['red' if d['unit_cost']>0 else 'blue' for u,v,d in graph.edges(data=True)]
Ai = 0
Bi = 0
pos = dict()
for p,d in graph.nodes(data=True):
if d['type']=='source':
pos[p] = (0, Acount/2)
elif d['type']=='sink':
pos[p] = (3, Bcount/2)
elif d['type']=='A':
pos[p] = (1, Ai)
Ai += 1
elif d['type']=='B':
pos[p] = (2, Bi)
Bi += 1
nx.draw(graph, pos=pos, edge_color=edge_color, arrows=False)
plt.show()
def GenerateMinCostFlowProblemFromGraph(graph):
start_nodes = []
end_nodes = []
capacities = []
unit_costs = []
min_cost_flow = pywrapgraph.SimpleMinCostFlow()
for node,neighbor,data in graph.edges(data=True):
min_cost_flow.AddArcWithCapacityAndUnitCost(node, neighbor, data['capacity'], data['unit_cost'])
supply = len([1 for p,d in graph.nodes(data=True) if d['type']=='B'])
for p, d in graph.nodes(data=True):
if (d['type']=='source' or d['type']=='sink') and 'supply' in d:
min_cost_flow.SetNodeSupply(p, d['supply'])
return min_cost_flow
def ColorGraphEdgesByUsage(graph, min_cost_flow):
for i in range(min_cost_flow.NumArcs()):
graph[min_cost_flow.Tail(i)][min_cost_flow.Head(i)]['usage'] = min_cost_flow.Flow(i)
def main():
"""MinCostFlow simple interface example."""
# Define four parallel arrays: start_nodes, end_nodes, capacities, and unit costs
# between each pair. For instance, the arc from node 0 to node 1 has a
# capacity of 15 and a unit cost of 4.
Acount = 20
Bcount = 20
graph = GenerateGraph(Acount, Bcount)
VisualizeGraph(graph, 'unit_cost')
min_cost_flow = GenerateMinCostFlowProblemFromGraph(graph)
# Find the minimum cost flow between node 0 and node 4.
if min_cost_flow.Solve() != min_cost_flow.OPTIMAL:
print('Unable to find a solution! It is likely that one does not exist for this input.')
sys.exit(-1)
print('Minimum cost:', min_cost_flow.OptimalCost())
ColorGraphEdgesByUsage(graph, min_cost_flow)
VisualizeGraph(graph, 'usage')
if __name__ == '__main__':
main()