@RobinJacobsson: Du kan generera upp kombinationer av arbetare och stationer utan att slumpa något alls. Har lite ont om tid så jag hoppas att det blir förståeligt, men här är en enkel metod för att undersöka alla möjligheter. Ponera att du har tre arbetare och tre stationer, och att alla inte kan arbeta överallt, ungefär så här:
data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAARMAAACbCAYAAABBPX...
Om varje kant i grafen viktas med arbetarens preferens (och den kan du slumpa, variera beroende på tidigare placering eller liknande) så kan du representera det i en matris på det här sättet:
| S1 S2 S3
---+---------
A1 | 1 1 0
A2 | 2 1 1
A3 | 8 0 2
För att generera en kombination så kan du börja med att ta den första stationen S1, och se att den går att kombinera med tre arbetare: A1, A2 och A3, samt deras preferenser:
[(A1,S1,1)] ; Lista med (arbetare, station, preferens)
[(A2,S1,2)] ; Ignorerar i exemplet
[(A3,S1,8)] ; Ignorerar i exemplet
Nu har du två stationer kvar i din lista, så för varje kombination du redan har hittat lägger du till de nya. För den första listan blir det då:
[(A1,S1,1),(A1,S2,1)] ; A1 redan vald.
[(A1,S1,1),(A2,S2,1)] ; Ok
[(A1,S1,1),(A3,S2,0)] ; A3 får inte.
Nu har du tre nya listor från den första, men bara en är giltig att fortsätta med. En station återstår:
[(A1,S1,1),(A2,S2,1),(A1,S3,0)] ; A1 redan vald.
[(A1,S1,1),(A2,S2,1),(A2,S3,1)] ; A2 redan vald.
[(A1,S1,1),(A2,S2,1),(A3,S3,2)] ; Ok
Nu har du en möjlig kombination: Alla stationer är tillsatta med arbetare, och om du summerar preferenserna så får du ett värde på 4, det kan du ta som den totala belåtenheten. Genererar du resten av kombinationerna på samma sätt så kommer du hitta fler möjliga alternativ, och kan välja den med högst belåtenhet.