Jonas Jalling <jonas@jalling.dk> writes:
> Uffe Kousgaard wrote:
>> "Jonas Jalling" <jonas@jalling.dk> wrote in message
>> news:494b65db$0$90262$14726298@news.sunsite.dk...
>>> Jeg har siddet og kæmpet lidt på opgaven om elgen på denne side:
>>>
http://ing.dk/artikel/93340
>>
>> Det er samme opgave, som jeg kender med cigaretter og nogle flere
>> andre elementer. Meget gammel.
>>
>> Den kan løses med papir og blyant, hvis man trinvis konstaterer at
>> nogle kombinationer af naboskab / dyr / hobby m.m. ikke er mulige og
>> til sidst er kun én mulighed tilbage. Trinvis. Ikke alt sammen i ét
>> hug.
>>
>> Hilsen
>> Uffe
>>
>>
> Ja, det er sådan jeg har gjort indtil nu. Men er det _metoden_?
Der er i princippet to metoder til at lave et program
1) Det letteste er at lave et program med en masse for-løkker inde i
hinanden. Start med at konstatere at skovridderen kan bo i hus 1,2,3,4
eller 5. Nu kan du undersøge disse huse et ad gangen. For hvert valg
af skovridder kan du finde fire mulige placeringer af den
fuldmægtige. Nu undersøger du dem en ad gangen. For hver placing af
den fuldmægtige kan du finde 3 placeringer af skovarbejderen
osv. Sådan kan du få et program til at undersøge alle muligheder og
returnere den løsning der er lovlig.
2) Hvis det skal være rigtigt fint kan du bruge lineær
programmering. Du kan regne på et array hver hvert element x(i,j,k)
har værdier mellem 0 og 1.
Her angiver i,j,k følgende
i angiver om vi snakker job, fritidsinteresse eller madret
j angiver en værdi (skovridder, skovarbejder, yoga eller spaghetti)
k angiver et husnummer 1..6
Her er et par eksempler på hvad værdierne af x kan betyde:
x(1,1,1)=1 hvis skovridderen bor i hus 1
x(1,1,1)=0 hvis skovridderen ikke bor i hus 1
x(1,1,2)=1 hvis skovridderen bor i hus 2
x(1,1,2)=0 hvis skovridderen ikke bor i hus 2
.... osv
x(1,2,1)=1 hvis skovarbejderen bor i hus 1
x(1,2,1)=0 hvis skovarbejderen ikke bor i hus 1
x(1,2,2)=1 hvis skovarbejderen bor i hus 2
x(1,2,2)=0 hvis skovarbejderenriddre ikke bor i hus 2
.... osv
x(2,1,1)=1 hvis personen i hus 1 spiser spaghetti
x(2,1,1)=0 hvis personen i hus 1 ikke spiser spaghetti
x(2,2,1)=1 hvis personen i hus 1 spiser kødret
x(2,2,1)=0 hvis personen i hus 1 ikke spiser kødret
.... osv
Nu kan man begynder at opskrive uligheder. Her et et par eksempler
Alle sandsynligheder skal være mellem 0 og 1.
0 <= x(i,j,k) <= 1
(I virkeligheden håber vi på en løsning hvor x(i,j,k) altid er et
heltal, men det er lettere at skrive det generelt op.)
Her er et par flere eksempler på uligheder:
Jeg går ud fra at der højst er en skovridder i de 6 huse
x(1,1,1)+x(1,1,2)+x(1,1,3)+x(1,1,4)+x(1,1,5)+x(1,1,6)<=1
Jeg går ud fra at der højst er en person i de 6 huse der spiser spaghetti.
x(2,1,1)+x(2,1,2)+x(2,1,3)+x(2,1,4)+x(2,1,5)+x(2,1,6)<=1
Jeg går ud fra at personen i hus 1 højst har et job
x(1,1,1)+x(1,2,1)+x(1,3,1)+x(1,4,1)+x(1,5,1)+x(1,6,1)<=1
Givet alle disse uligheder kan vi førsøge maksimere en funktion. Den
oplagte funktion at maksimere er summen af alle værdierne i x.
Maximer følgende funktion
f(x) = x(1,1,1)+x(1,1,2)+.... + x(6,6,6).
Hvis vi er heldige kan vi finde en læsning hvor f(x)=6*6*6;
Der findes en masse pakker til at optimere lineære funktioner under
lineære bibetingelser, man kan eksempelvis finde nogen biblioteker
her:
http://www.coin-or.org/
Man kan også finde information på wikipedia:
http://en.wikipedia.org/wiki/Assignment_problem
Niels