[PYTHON] Bestimmen Sie das aufgezeichnete Programm durch Kombinationsoptimierung
Problem bei der Auftragsvergabe
Ziehen Sie in Betracht, mehrere Jobs mehreren Ressourcen zuzuweisen. Bestimmte Arbeitspaare können nicht derselben Ressource zugewiesen werden. Maximieren Sie die Summe der Werte der ausgewählten Arbeit.
Hier ist ein konkretes Beispiel.
- Es gibt einige Broadcast-Programme, die Sie aufnehmen möchten.
- Es gibt einige beschreibbare Geräte. ―― Es ist nicht möglich, Programme mit überlappenden Sendezeiten auf demselben Gerät aufzuzeichnen. (Gleichzeitige Aufnahme verboten)
- Maximieren Sie den Gesamtwert der aufgezeichneten Programme.
Denkweise
Betrachten Sie die folgenden 5 Programme. Angenommen, Sie haben drei Aufnahmegeräte.
| Name | Startzeit | Endzeit | Wert |
|---|---|---|---|
| A | 9:00 | 9:30 | 1 |
| B | 9:30 | 10:00 | 1 |
| C | 9:00 | 10:00 | 1 |
| D | 9:00 | 9:30 | 1 |
| E | 9:30 | 10:00 | 1 |
Betrachten Sie ein Diagramm mit einem Programm als Knoten und einer gleichzeitigen Aufzeichnung, die als Kante verboten ist.
Stellen Sie sich ein neues Diagramm vor, das dieses Diagramm für jedes Gerät dupliziert, und erstellen Sie Kanten zwischen denselben Programmen.
Durch Lösen des Problems der maximalen stabilen Einstellung in diesem Diagramm ist es möglich, eine Lösung zu erhalten, die "das Verbot der gleichzeitigen Aufzeichnung erfüllt und dasselbe Programm nur auf einem Gerät aufzeichnet", sodass welches Programm auf welchem Gerät aufgezeichnet werden sollte Ich weiß, ob es gut ist.
Versuche mit Python zu lösen
python3
import networkx as nx
from itertools import combinations
from more_itertools import grouper
from ortoolpy import maximum_stable_set, Autodict
g = nx.Graph()
dc = Autodict()
for i in 'ABCDE':
for j in'123':
g.add_node(dc[i+j], weight=1)
for i, j in grouper(2, 'ACADBCBECDCE'):
for k in '123':
g.add_edge(dc[i+k], dc[j+k])
for i in 'ABCDE':
for j, k in combinations('123', 2):
g.add_edge(dc[i+j], dc[i+k])
print([dc.keys[i] for i in maximum_stable_set(g)[1]])
>>>
['A1', 'B3', 'C2', 'D3', 'E1']
Sie können sehen, dass Sie A und E auf Gerät 1, C auf Gerät 2 und B und D auf Gerät 3 aufzeichnen können.
das ist alles
Recommended Posts