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. image

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. image

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