Déterminer le programme enregistré par optimisation de combinaison
Problème d'affectation des tâches
Envisagez d'allouer plusieurs travaux à plusieurs ressources. Certaines paires de travaux ne peuvent pas être affectées à la même ressource. Maximisez la somme des valeurs de l'œuvre choisie.
Voici un exemple concret.
- Vous souhaitez enregistrer certains programmes diffusés. --Il existe des appareils enregistrables. ――Il n'est pas possible d'enregistrer des programmes dont les heures de diffusion se chevauchent sur le même appareil. (Enregistrement simultané interdit) --Maximisez la valeur totale des programmes enregistrés.
Façon de penser
Considérez les 5 programmes suivants. Supposons que vous ayez trois appareils d'enregistrement.
| Nom | Heure de début | Heure de fin | valeur |
|---|---|---|---|
| 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 |
Prenons un graphe avec un programme en tant que nœud et un enregistrement simultané interdit en tant que bord.
Considérez un nouveau graphique qui duplique ce graphique pour chaque périphérique, et créez des arêtes entre les mêmes programmes.
En résolvant le problème d'ensemble stable maximum sur ce graphique, il est possible d'obtenir une solution qui "satisfait l'interdiction d'enregistrement simultané et enregistre le même programme uniquement sur un appareil", donc quel programme doit être enregistré sur quel appareil Je sais si c'est bon.
Essayez de résoudre avec Python
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']
Vous pouvez voir que vous pouvez enregistrer A et E sur l'appareil 1, C sur l'appareil 2, et B et D sur l'appareil 3.
c'est tout
Recommended Posts