Optimalisering

Et typisk problem i informatikk g?r ut p? at man skal optimalisere l?sningen av et problem (finne beste l?sning), og at man har en del parametere man kan tweake for ? pr?ve ? finne en bedre l?sning.

Vi skal her se p? en versjon av et slikt problem, der vi bare har to parametere vi skal tweake, og der vi ganske enkelt kan sjekke hvor bra en "tweaking" er. Det eneste som gj?r dette vanskelig er at det er kostbart ? sjekke hvor bra et sett med parametere er, slik at vi har et begrenset antall med sjekk.

Problemet er slik:

• Vi st?r i et landskap som er et rutenett med en viss st?rrelse
• Landskapet har p? hvert punkt en h?yde og vi antar at det finnes en rekke h?yder og at disse er noenlunde "smoothe" (alts? ikke bare random st?y)
• ? sjekke h?yden p? et punkt er kostbart (se for deg at det kan tilsvare ? kj?re en full simulering av l?sningen p? et problem), og vi kan derfor ikke sjekke h?yden over alt. Anta at vi har N sjekk vi har lov til ? gj?re.
• M?let er i l?pet av N sjekk ? finne en posisjon p? brettet som gir s? h?y score som mulig.
• Landskapet kan f. eks se noe slikt ut i 3 dimensjoner:

Mulige strategier

• Man kan pr?ve alle mulige posisjoner: Dette g?r ikke fordi vi bare har N sjekk
• Man kan velge N tilfeldige lokasjoner og returnere den med h?yest score: Det er stor sjanse for at ingen av disse gir den beste scoren
• Man kan velge noen lokasjoner og pr?ve ? bevege seg oppover: G? i den retningen som ser ut til ? gi bedre score

Oppgave

Last ned denne filen. Du trenger ? ha installert numpy og matplotlib (for ? plotte landskapet).

Filen inneholder en klasse landskap som gj?r at du kan lage et landskap:

from landskap import Landskap
landskap = Landskap(30, 30)  # 30x30 ruter stor
landskap.lag_landskap()  # lag landskapet
landskap.plott_3d()  # plott i 3d (krever matplotlib)

score = landskap.hent_score(4, 3)  # henter scoren p? en rute, man har maks 1000 slike kall

Skriv kode som gitt et landskap returnerer den posisjonen man tror gir h?yest score. Du kan f. eks lage en funksjon eller klasse som tar et landskap.

En mulig approach er ? lage en klasse Person. Vi ser for oss at en Person er et individ som befinner seg i landskapet og som pr?ver ? finne h?yeste punkt. Om man setter ulike personer ut i landskapet p? forskjellige random plasser, kan man la disse s?ke lokalt og s? kan man til slutt sjekke hvilken person som fant den h?yeste peaken.