I mitt første år som systemutvikler diskuterte vi om det ville være mulig å skrive en algoritme for sidelayout i aviser, og da spesielt for å plassere annonser innimellom journalistisk innhold. Reklameplass ble solgt for en spesiell seksjon av publikasjonen, som "sportssidene", "nyhetsseksjonen" o.s.v.. Journalistisk innhold varierte fra dag til dag, så man ville ikke kjenne størrelsen før layout var ferdig. Bare tanken på antallet mulige kombinasjoner gjorde oss svimle, og vi mente det var en umulig oppgave. Vi gjorde aldri noe forsøk.
Få år seinere så jeg denne meldingen i en av mine faste nyhetsgrupper; en kar fikk spørsmål fra sin arbeidsgiver om han kunne skrive programvare for å kalkulere best utnyttelse av verkstedmaskiner. Det fantes et et antall maskiner (som alle kunne gjøre alle jobber), en liste av jobber, noen absolutte krav og faktorer for å beregne utnyttelsesgrad:
- Når en ny, annerledes jobb ble igangsatt ville det ta 20 minutter å sette opp maskinen.
- Alle jobber måtte være avsluttet ve avslutningen av et 8-timers skift
- Noen jobber ville foretrekkes å gjøre snarest mulig
- Resultat ville bedømmes etter utnyttelsesgrad justert for i hvilken grad hastejobber ble ferdig tidlig.
Et problem beslektet med det tidligere beskrevet for automatisk sidelayout, man forstår raskt at algoritmen ville måtte teste en enorm mengde mulige kombinasjoner (som effektivt ville sette grense for antall håndterbare enheter) eller gjøre komplekse kalkulasjoner for å begrense til bare de fornuftige. Det kunne minne noe om den klassiske Travelling Salesman's Problem (som man i dag kan si er ganske effektivt løst i en tjeneste som Google Maps, selv om denne noen ganger produserer tåpelige resultat som f.eks. å sende deg en ekstra runde rundt en rundkjøring).
Det slo meg: "Randomisering!"
Det store problemet med å teste en stor mengde kombinasjoner gjennom alle mulige permutasjoner - det kan rett og slett ta for lang tid og din beste kombinasjon kan være blandt en av de siste på lista. Randomisering hjelper deg til å unngå dette, fordi det å teste en av de siste permutasjonene faktisk snart ville skje.
randomisering er ikke et godt konsept for å bestemme den ideelle kombinasjonen, men du kan ende opp med en ganske god en på en brøkdel av tiden.
Det er selvfølgelig ett krav som må tilfredsstilles om man skal kalkulere maksimal utnyttelse: En måte å bedømme resultatene, så du kan velge det beste.
Om vi tar et enklere eksempel, en algoritme for å velge planker fra en trevarehandel med minst mulig kapp. Man spesifiserer en liste med ønskede lengder og legger inn lengdene man faktisk finner på trevarehandelen og får forslag om et godt valg og hvilke biter som skal kappes av hvilken planke.
Hvis du bare trenger noen få biter kan du faktisk teste alle mulige kombinasjoner. Men - med f.eks. 10 ulike lengder å kutte fra et utvalg av 6 ulike planker er du allerede oppe i ca. 2,3 milliarder kombinasjoner som skal testes:
Ønskede lengder (mm): 2450, 2300, 2200, 2000, 1350, 1100, 1000, 980, 750, 550
Lengder som fins i butikken (mm): 4230, 4119, 3860, 3720, 3650, 2470
Permutasjoner av planker / ønskede lengder kunne være:
Planker: 4230, 4119, 3860, 3720, 3650, 2470
Ønskede lengder:
- 2450, 2300, 2200, 2000, 1350, 1100, 1000, 980, 750, 550
- 2450, 2200, 2300, 2000, 1350, 1100, 1000, 980, 750, 550
- 2450, 2000, 2300, 2200, 1350, 1100, 1000, 980, 750, 550
- 2450, 1350, 2000, 2300, 2200, 1100, 1000, 980, 750, 550
...osv., alle 3,628,800 mulige kombinasjoner før neste permutasjon av planker og repetering av prosessen.
Problemet kunne være at denne spesielle rekkefølgen av permutasjoner ville føre til at det potensielt smarte valget - bruke planken på 2470mm for biten på 2450mm - ikke ville dukke opp før den siste ~1% av permutasjoner. Ved å teste randomiserte kombinasjoner ville denne kombinasjonen dukke opp i hvert ~30. forsøk, og dette problemet er unngått.
Ulempen med randomisert testing er, som nevnt, at du sannsynligvis ikke finner den ideelle kombinasjonen. Du har ingen måte å teste dem alle, med mindre du først lager en liste av alle permutasjoner og velger en av gangen i tilfeldig rekkefølge inntil alle er testet. Men det er en annen algoritme - denne dreier seg om å oppnå et greit resultat innenfor en akseptabel tidsramme.
En JavaScript-implementasjon av dette eksemplet vil bli publisert i løpet av kort tid.