© h.hofstede (h.hofstede@hogeland.nl)

Optimale Matchings.
       
Vorige les ontdekten we een manier om een perfecte matching te vinden om n werkers n taken te laten verrichten. Maar vaak zijn er meerdere perfecte matchings mogelijk, en dan rijst natuurlijk meteen de vraag:  "Wat is de optimale perfecte matching?"
Neem aan dat elke verbindingslijn van de bipartiete graaf een gewichtsfactor heeft  (denk aan de efficiëntie van de werker bij de betreffende taak). Dan wil je natuurlijk graag precies de matching vinden waarvoor het totale gewicht maximaal is.
Die matching noemen we de optimale matching. Het probleem om zo'n optimale matching te vinden heet ook wel het "optimale toekenningsprobleem".

Je zou natuurlijk gewoon alle mogelijk perfecte matchings kunnen bekijken en dan degene met de grootste gewicht kiezen. Maar dat kan nog wel eens erg veel werk zijn  (bij n knooppunten in de orde van n!  berekeningen).

We gaan een algoritme bekijken om sneller zo'n optimale matching te vinden.  Ik hoop dat je een beetje nieuwsgierig bent geworden.....

Oké, we hebben dus vanaf nu te maken met een bipartiete graaf met knooppunten X1, X2, ..., Xn  en  Y1, Y2, ..., Yn
Verder heeft elke verbindingslijn XiYj  gewicht  wij . Zó eentje dus  (de gewichten zijn rood):
       

       
Je ziet bijvoorbeeld dat  w85 = 8  en  w67 = 5

Eerst gaan nu we alle knooppunten een nieuw nummer N geven, en dat doen we zó dat   N(Xi) + N(Yj)  ≥ wij .
Ofwel:  de nummers van de eindpunten van een verbindingslijn zijn samen altijd minstens gelijk aan het gewicht van die verbindingslijn.
Knooppunten mogen daarbij best dezelfde nummers hebben, dat doet er niet toe.

Dat lukt altijd.
(Je kunt bijvoorbeeld  heel flauw elke Yi nummer 0 geven en elke Xi het nummer van de grootste (qua gewicht) verbindingslijn die er aan zit).

De verzameling van verbindingslijnen V waarvoor het gelijkteken geldt (dus  N(Xi) + N(Yj)  = wij)  noemen we  VN. En de subgraaf  die bestaat uit al die lijnen en bijbehorende knopen van VN  noemen we de gelijkheids-subgraaf  GN  die hoort bij deze nummering N.
Zó dus bijvoorbeeld:
       

       
Stelling 1. 

Als GN  een perfecte matching bevat, dan is dat direct ook een optimale matching.
       
Deze stelling is de basis van het volgende algoritme om een optimale matching te vinden. Het komt van Kuhn en Munkres, en gaat als volgt:
   
1. Maak een willekeurige nummering N.
2. Bekijk de daarbij horende gelijkheids-subgraaf GN  en probeer volgens de methode van de vorige les daarvan een perfecte matching te vinden.
3. Als dat lukt ben je klaar.
Als dat niet lukt dan is het kennelijk vastgelopen op een verzameling V van punten uit X die een kleinere verzameling W als buren in Y  had  (zie de vorige les).
4. Pas N als volgt aan:
• Je hebt nu dus een aantal knooppunten V en een aantal knooppunten W waarop "het vastliep".
• Bereken nu het verschil  N(Xi) + N(Yj) - wij,  en doe dat voor alle punten uit V met alle punten NIET uit W.
• Neem het kleinste verschil dat je vindt, noem dat d,  en maak nu de volgende nieuwe nummering N*:
     
   

   
  Kortom:  de nummering van alle X-knopen in V maak je d kleiner en die van alle Y-knopen in W maak je  d groter.
(De nummering van knopen niet in V of W laat je ongewijzigd).

5.

 Begin met deze nieuwe nummering weer bij stap 2.
       
Uitgebreid voorbeeld.

Neem de volgende graaf, met 8 werkers en 8 taken:

       
Nogal een chaos, niet? En dan moeten alle gewichten ook nog bij al die lijnen worden gezet!!
Voor de overzichtelijkheid stap ik daarom maar over naar de matrixnotatie, waarbij ik als matrixelementen de gewichten noteer. Een gewicht nul betekent dat de knooppunten niet zijn verbonden. Zie de matrix rechts.
       

       
Nou, dan gaan we nu eerst maar willekeurig een nummering N aan de 16 knooppunten toevoegen. Die staat in het rood hieronder.
       

       
Je ziet dat ik er voor heb gezorgd dat de som van de nummeringen minstens gelijk zijn aan het gewicht van de verbindingslijn (ofwel: in de matrix rechts is het getal op de kruising nooit groter dan de som van beide rode getallen die erbij horen)
In de matrix rechts heb ik meteen maar aangegeven voor welke verbindingen de som van de gewichten van de uiteinden precies gelijk is aan het gewicht van de verbindingslijn. Ofwel:  daar in het blauw staan de elementen van onze gelijkheidsgraaf GN.
       
Die gelijkheidsgraaf GN bij deze nummering zie je hiernaast.
Dus gaan we daarvan proberen een perfecte matching te vinden.

Dat doen we op de manier van de vorige les  (weet je nog: begin met een willekeurige matching, en probeer dan een M-vergrotend pad te vinden...).

Dat gaat bij deze graaf niet lukken!
Hoe weet ik dat?
       
Oké, ik heb een beetje vals gespeeld (om tijd te winnen). Dit is precies het laatste voorbeeld uit de vorige les!
En daar kwamen we tot de conclusie dat er geen perfecte matching is te vinden omdat de gele verzameling V = {X1, X3, X6} de kleinere groene buurverzameling W = {Y2, Y3} heeft.  

Tijd om de nummering aan te passen dus!!!
Om d te berekenen bekijken we de punten  X1, X3, X6 (wél uit V) en   Y1, Y4, Y5, Y6, Y7, Y8  (níet uit W)
Bereken voor alle combinaties daarvan  N(Xi) + N(Yj) - wij, 
       
  Y1 Y4 Y5 Y6 Y7 Y8
X1 1 2 6 1 3 4
X3 3 6 5 7 7 8
X6 2 5 9 2 1 7
       
De kleinste daarvan is  d = 1
We gaan nu de gewichten van de knooppunten in V en W (dus van X1, X3, X6, Y2, Y3) aanpassen. Omdat we de X-en d kleiner maken en de Y's d groter blijft de som gelijk aan het gewicht van de verbindingslijn, dus de verbindingslijn blijft deel van GN. Dus we veranderen  X1 = 0, X3 =  4,  X6 = 3  en   Y2 = 4,  Y3 = 2
Dat geeft:
       

       
Je ziet dat daardoor aan de gelijkheidsgraaf de verbindingen x1y1 en  x1y6  en  x6y7  worden toegevoegd  (omdat we het kleinste verschil d hebben genomen weten we zeker dat we geen mogelijke verbindingen "overslaan")
Met die nieuwe gelijkheidsgraaf is er opeens wél een M-vergrotend pad te vinden
We pikken de situatie weer op waar we in de vorige les waren geëindigd, toen het vastliep, en dat zie je in de graaf rechts:
Het pad  x1 - y3 - x6 - y7  is M-vergrotend.
Dus die gaan we om-en-om van kleur veranderen.
       

       
En nu beginnen we weer opnieuw.  In neem aan dat je snel ziet dat de verbinding  x5y6  toevoegen een perfecte matching levert.

       
Daar is ie dan!  De optimale perfecte matching  (totaal gewicht trouwens  39, tel maar na).
       

© h.hofstede (h.hofstede@hogeland.nl)