---

I forbindelse med arrangering af en rotur har jeg grublet lidt over om der
er en smart måde at sætte bådholdene på.

Det mest simple scenarie:
x personer skal fordeles på y både over z dage.
Udfordringen består i at minimere antallet af tilfælde hvor 2 personer ror
sammen mere end 1 gang.
Det er selvfølgelig ikke muligt for alle kombinationer af x,y,z men for
mange er det.

Bådene har plads til enten 3 eller 5 personer, så x vil altid være n*5+m*3

Ekstra kompleksiteter
Kun en del af personerne er styrmænd, der skal være mindst 1 styrmand i hver
båd.
Ikke nødvendigvis alle x personer er med på hele turen. Dels kan der være
dage (oftest i starten) hvor der er færre personer, dels kan der være
udskiftninger undervejs.

Lige nu er jeg ret blank mht metodik for at løse opgaven. Startede med at
tro at det var rimeligt trivielt, men kan ikke finde nogen pæn måde at gøre
det på (man kan jo altid lave alle kombinationer og finde den der giver
færrest kollisioner).

Nogen der har en ide om hvad retning man skal kigge i?

--
Martin Højriis Kristensen - http://usenet.makr.dk/

---

Scripsit "Martin Højriis Kristensen" <usenet@makr.dk>

> I forbindelse med arrangering af en rotur har jeg grublet lidt over om der
> er en smart måde at sætte bådholdene på.

Hm, det ser umiddelbart temmelig NP-hårdt ud...

> Lige nu er jeg ret blank mht metodik for at løse opgaven.
> Nogen der har en ide om hvad retning man skal kigge i?

Du er på udkig efter en heuristik til at finde en "god" løsning, idet
den "bedst mulige" løsning nok er beregningsmæssigt unåeligt.

Jeg er kun halvstuderet amatør indenfor kombinatorisk optimering, men
det lyder som et problem man kunne angribe med simuleret udglødning
(eng: simulated annealing). Prøv og se om google giver dig nogen
referencer der inspirerer dig.

--
Henning Makholm "`Update' isn't a bad word; in the right setting it is
useful. In the wrong setting, though, it is destructive..."

---

Henning Makholm <henning@makholm.net> wrote in message news:<87k6u6ko92.fsf@kreon.lan.henning.makholm.net>...
> Du er på udkig efter en heuristik til at finde en "god" løsning, idet
> den "bedst mulige" løsning nok er beregningsmæssigt unåeligt.

Eller med andre ord finde en "nabodefinition" der giver et søgerum,
hvor de lokale minima, der er tætte på det globale minimum, har en god
stor omegn hvor det "går ned af bakke".

> Jeg er kun halvstuderet amatør indenfor kombinatorisk optimering, men
> det lyder som et problem man kunne angribe med simuleret udglødning
> (eng: simulated annealing).

Jahhh, og så har simuleret udglødning jo den ganske udemærkede
egenskab, at det kan bevises, at man når det globale minima, når bare
temperartursænkning sker i infitisimalt små skridt.
Men man undgår jo stadigvæk ikke at skulle finde på en god
"nabodefintion".
Jeg har kendskab til flere bøger der beskæftiger sig med valg af gode
heuristiker, med de er godt nok lidt tekniske og så på engelsk.

J.O.

---

Scripsit jenspolsen@hotmail.com (Jens Olsen)
> Henning Makholm <henning@makholm.net> wrote

> > Du er på udkig efter en heuristik til at finde en "god" løsning, idet
> > den "bedst mulige" løsning nok er beregningsmæssigt unåeligt.

> Eller med andre ord finde en "nabodefinition" der giver et søgerum,
> hvor de lokale minima, der er tætte på det globale minimum, har en god
> stor omegn hvor det "går ned af bakke".

Umiddelbart ville jeg starte med at sige at man finder en nabo ved at
vælge to både der sejler på samme tidspunkt og bytte N af passagererne
i den ene ud med N af passagererne i den anden.

Men jeg har ikke nok kendskab til emnet til at vide hvordan man ville
vurdere om det er en god definition.

> Jahhh, og så har simuleret udglødning jo den ganske udemærkede
> egenskab, at det kan bevises, at man når det globale minima, når bare
> temperartursænkning sker i infitisimalt små skridt.

Det har man jo ikke tid til. Så kan man lige så godt opremse alle
løsninger og finde den med den bedste score.

--
Henning Makholm "Norske nisser nyser ikke."

---

Henning Makholm <henning@makholm.net> wrote in message news:<877jpz7d02.fsf@kreon.lan.henning.makholm.net>...

> > Jahhh, og så har simuleret udglødning jo den ganske udemærkede
> > egenskab, at det kan bevises, at man når det globale minima, når bare
> > temperartursænkning sker i infitisimalt små skridt.
>
> Det har man jo ikke tid til. Så kan man lige så godt opremse alle
> løsninger og finde den med den bedste score.

Ja det har du ret i. Praktisk anvendelse har denne egenskab ved
simuleret udglødning ikke. Men det er da en interessant egenskab.

J.O.

---

On Mon, 4 Oct 2004 23:48:49 +0200
"Martin Højriis Kristensen" <usenet@makr.dk> wrote:

> I forbindelse med arrangering af en rotur har jeg grublet lidt over om > der er en smart måde at sætte bådholdene på.
>
> Det mest simple scenarie:
> x personer skal fordeles på y både over z dage.
> Udfordringen består i at minimere antallet af tilfælde hvor 2 personer > ror sammen mere end 1 gang. Det er selvfølgelig ikke muligt for alle > kombinationer af x,y,z men for mange er det.
>
> Bådene har plads til enten 3 eller 5 personer, så x vil altid være
> n*5+m*3

Jeg havde engang et kusus i diskret matematik. Det ligger lidt fjernt
nu, men så vidt jeg kan se er dit spørgsmål noget med blokdesign. Jeg
kan ikke huske om der er en formel der løser dit problem, men hvis du
starter på denne side og surfer lidt rundt, så er der måske et svar :)
http://mathworld.wolfram.com/BlockDesign.html

Så vidt jeg kan se har emnet været oppe at vende i gruoppen før, men jeg ved ikke om der er så meget information i den gamle thread
http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&frame=right&th=5773d23106a26590&seekm=3df5c9f6%240%2488174%24bc7fd3c%40news.sonofon.dk#link4

---

"Martin Højriis Kristensen" <usenet@makr.dk> wrote in message
news:4161c53a$0$176$edfadb0f@dtext01.news.tele.dk...
>I forbindelse med arrangering af en rotur har jeg grublet lidt over om der
>er en smart måde at sætte bådholdene på.

Tak for svarene

--
Martin Højriis Kristensen - http://usenet.makr.dk/