Geekfood! Yay!

[Onkel]

Bare for hjernetrimmens skyld tenkte jeg jeg kunne dele dette. Et utfordrende problem her, som antagelig har en "åh, herregud så lurt!"-aktig løsning et eller annet sted...

 

Skal prøve å skrive (eller kanskje lure noen til å gjøre det for meg...) et program som plasserer 30 personer på hvert sitt sted, av nærmere 100 mulige steder. Noen av stedene er mer populære enn andre og vil få flere søkere enn det er plass til (som regel en eller to personer på hvert sted), så ikke alle kan få førstevalget sitt. Derfor får alle sette opp et 1., 2. og 3.-valg. Vi har til nå gjort dette manuelt, men ikke funnet noen rettferdig måte å fordele på.

 

Og problemet er at antall mulige kombinasjoner av prioritertingsutfall er gitt ved (antall prioriteringsvalg) ^ (antall personer). I dette tilfellet blir det 3^30 = 2.0e14 mulige kombinasjoner, og en gjennomkjøring vil antagelig ta flere år sånn som programmet er satt opp i dag (6,5 år hvis vi tenker oss at programmet spiser en million kombinasjoner i sekundet).

 

Målet her er å gjøre noe med strukturen eller finne noen snarveier sånn at det kan presses ned i max en dag. Og før du blir skremt: tiden det tar er en VELDIG eksponensiell funksjon, så små grep kan faktisk presse det veldig ned! For eksempel kan det å dele personene i to grupper på femten, der gruppe to tildeles plassene som er igjen etter gruppe en, senke tida fra 6,5 år til 30 sekunder... Men det er jo ikke så rettferdig dah!

 

Skjematisk sett ser programmet slik ut:

 

Det programmet skal gjøre, er å finne den kombinasjonen hvor flest mulig har fått høyest mulig prioriterte valg. Tanken er at det at en person plasseres ved sin førsteprioritet gis 3 poeng, andreprioritet 2 poeng, tredjeprioritet 1 poeng og det å ikke få noen plass fra lista gis 0 poeng. Sånn kan programmet gå igjennom ulike kombinasjoner av plasseringer utfra ett gitt sett av ønsker, og finne den kombinasjonen som får høyest poengsum, og antas å være mest rettferdig.

 

Kort fortalt skjer det ved at programmet går igjennom alle mulige kombinasjoner av prioriteringer. Et eksempel: hvis to personer har to prioriteringer (0 og 1) blir det fire mulige kombinasjoner: kombinasjon nr 0 = "00", 1="01", 2="10" og 3="11" (innholdet i kombinasjonen skan altså genereres utfra nummeret på kombinasjonen, sånn kan alle kombinasjonene dekkes ved å bare la en for-next-løkke telle fra null til anntall mulige kombinasjoner). Da vil kombinasjonen "01", som tilsvarer at andre person får andrevalget sitt, få en litt høyere poengsum (5p) enn "11", som tilsvarer at første person også gjør det (4p). Men før poengsummen beregnes, sjekker programmet om det er en kombinasjon som fordeler for mange personer til samme plass. Til slutt husker programmet det kombinasjonsnummeret som gav høyest poengsum, gjør hvert av prioriteringstallene om til konkrete plasser, og skriver det ut.

 

Og her ligger det nok et potensiale for forbedring: sånn som det er tenkt til nå, kaster programmet bort masse tid med å prosessere en haug med kombinasjoner som ikke er mulige fordi de plasserer for mange personer på hvert sted. Ideer til hvordan dette kunne blitt isolert?

 

Andre ideer: deler man gruppa i to, har det som sagt masse å si. Man kan for eksempel la programmet gå igjennom 1000 tilfeldig valgte slike splittpunkter, og huske den høyeste poengsummen. Da ville det tatt ca en dag.

Eventuelt kan man tenke seg at det oppstår grupperinger, at f.eks 15 personer synes 10 av stedene høres flotte ut, 10 personer sloss om 7 helt andre steder og 5 personer om 3 steder, med veldig lite overlapp mellom gruppene. Hvis det finnes noen måter å analysere gruppevalgene på, kunne kanskje programmet gjøre tre separate analyser. Dette eksempelet ville tatt 14 sek.

 

SÅ! HIV DERE OVER NOTATBØKER OG KALKULATORER! RING JOLA SIGMOND!

 

Beste funksjonelle forslag premieres med en Bugg, samt vissheten av å være en ****** i kreativ problemløsning!

 

 

 

Får man stadig kjøpt Bugg?

[daysleper]

http://scm.nostdal.net/cgi-bin/viewcvs.cgi/tests/?root=tests (ta en titt på findseats.cpp)

 

Slang sammen noe i farta her. Mulig jeg har misforstått ting og tang, for jeg leste bare kjappt igjennom innlegget ditt.

 

Programmet er forøvrig skrevet i C++.

 

Når programmet kjøres får jeg denne utskriften:

 

Lars is finding a place to sit.

Lars sits down at seat number 1, which for him/her is a priority 1 seat.

 

Kari is finding a place to sit.

Kari sits down at seat number 2, which for him/her is a priority 2 seat.

 

Per is finding a place to sit.

Per sits down at seat number 3, which for him/her is a priority 3 seat.

 

Lise is finding a place to sit.

 

 

Placements

----------

Seat number: 1 -- Lars

Seat number: 2 -- Kari

Seat number: 3 -- Per

 

Remaining

---------

Lise did not get any of the seats that he/she wished for.

 

 

Kan prøve å forklare åssen jeg har tenkt.

Jeg har her kun tatt hensyn til at hvert "sted" er et sete med kun plass til én person, men det er ikke noe i veien for å endre på dette.

 

Når alle personene og deres prioriteringer av seter i problemet er lagt til, kalles Seats::sit() -metoden.

Den finner det setet som har høyest mulig prioritet hos hver person og sjekker om det er tilgjengelig. Hvis det er tilgjengelig "setter" personen seg og koden hopper videre til neste person. Hvis det ikke er tilgjengelig sjekker metoden om setet på 2. prioritet er ledig - osv.

 

Seats::showPlacements() viser hvor alle har satt seg.

 

De som ikke har fått noen av sine ønskede sitteplasser har ennå ikke satt seg. Hva skal vi gjøre med disse? Be dem sette seg på et tilfeldig, ledig sete etter de andre har satt seg?

Du sjekker om noen ikke har fått noen av sine ønsker med Seats::showRemaining() metoden.

 

 

..som sagt er det mulig jeg har misforstått alt, og det kan hende det er noen "bug(g)s" her. Har ikke testet koden så alt for mye ennå.

[daysleper]

Legger ut noen eksekverbare filer av programmet:

 

Windows: http://nostdal.net/lars/forumstuff/findseats.exe

Linux: http://nostdal.net/lars/forumstuff/findseats

[MailMan13]

hm... mine tanker om det som er foreslått

 

Daysleepers forslag er så vidt jeg kan se en greedy algoritme som itererer gjennom alle personene og plasserer dem på den beste ledige plassen, dersom ingen av de tre valgene er ledig forkastes personen som uplassérbar og man fortsetter med neste, man tar altså ikke hensyn til at plasseringen av to personer med samme valg på en prioritet, men ulike valg på lavere prioritet kan påvirke hvor mange av de resterende vi får plassert. Nå er jeg helt ny på c++ og syns syntaksen for en del ting er helt grusom, så jeg beklager hvis jeg har lest programmet feil.

 

Algoritmen blir naturligvis svært rask, siden den ikke tar hensyn til hvordan valg påvirker hverandre holder det å sjekke hver person en gang, men er vi uheldig med input kan vi få langt fra optimal output, og helt optimal output vil også være sjelden for andre enn helt små datamengder.

 

Onkels forslag går ut på et kombinatorisk søk gjennom alle muligheter, denne vil da ha 4 muligheter på person (tre prioriteter og en "ikke innvilget" som kan plasseres vilkårlig til slutt), som gir kjøretid på O(4^n), dette er forferdlig tregt, og når n (antall personer vokser), ryker kjøretiden til himmels veldig tidlig, selv med veldig gode avskjæringer.

 

Jeg har laget et eksempel på en slik algoritme, PlasserKomb.java, som arbeider slik og avskjærer alle ulovlige kombinasjoner så tidlig som mulig, på en tilfeldig generert datamengde var det umulig å få den til å kjøre på skapelig tid på noe mer enn 15-16 personer, og kjøretiden vil bli på mange dager fra 19-20 og oppover.

 

Hadde man derimot kunnet luke ut alle førstevalgene som ikke kommer i konflikt med hverandre før man kjører løsningen (det er enkelt å legge til her), vil man kunne redusere kjøretiden ganske betraktlig og sannsynligvis få den veldig rask for 'gunstige' input, på den andre siden blir det inputens karrakter som avgjør om det tar 15 sekunder eller 15 dager å løse problemet.

 

Mitt forslag er dynamisk programmering, vi har ikke tid til å generere alle mulige, så vi itererer gjennom alle personene og velger den beste der og da, men i stedet for å gi opp slik som daysleepers algoritme gjør, når vi ikke får plassert noen prøver vi å omplassere noen med høyere prioritet til et lavere prioritert valg for å gjøre plass på en av personens høyrere valg, på den måten sikrer vi at høye prioriterte valg ikke kommer i veien for andre høye prioriterte valg hvis vi kan ofre prioritet for en person for å få plassert en annen som ellers ikke ville blitt plassert på en høy prioritet.

 

PlasserDyn.java bruker en slik strategi.

 

Denne vil for de fleste inputs kjøre på O(n), men teoretisk 'worst case' er O(n^3), så tregt vil den aldri gå å praksis og selv om det gjorde det ville det gå veldig mye raskere enn O(4^n) som det kombinatoriske søket gir. Jeg har kjørt den på 100000 personer og det eneste som tok nevneverdig tid var å skrive ut resultatet.

 

Algoritmen tar ikke hensyn til at om man ikke får plassert noen, om man da bytter noen med samme prioritet på et valg, men ulike valg på lavere prioritet som har blitt ulikt plassert kan byttes om for å gi plass. Jeg har ikke klart å bevise hverken at dette kan skje eller om det er umulig, om noen som er glad i mattematikk/algoritmer kan se på det hadde det vert fint (er blitt litt frustrert over dette). Det vil i tilfellet si at enkelte 3 prioritets valg kan bli unødvendig utelatt, jeg har ikke klart å fremprovosere dette på datamengder som det er mulig å kontrollere med det kombinatoriske søket (som gir en garantert optimal løsning).

 

Tilslutt, en tilfeldig input algoritme, InputGen.java, som genererer tilfeldig input, den tar ikke hensyn til dupliserte valg, men det er heller ikke avgjørende for noen av algoritmene som er foreslått.

 

Programmene mine tar input fra stdin og skriver output til stdout, input på formen:

<antplasser>
<kapaistet, plass1>
<kapaistet, plass2>
...
<antpersoner>
<person 1, valg1, 2 3
...

Kjør inputgeneratoren så skjønner du visa.

[Onkel]

Wow. Hadde faktisk ikke regnet med at noen skulle gidde å svare, lagt mindre faktisk sette seg sånn inn i problemet som dere har. Utroligfenomenalt!

 

Skal sette meg inn i det dere foreslo, har bare ikke hatt tid til å gjøre det enda (og hva gjør jeg med .java-programmer? Kan de kjøres i feks en nettleser?).

 

 

 

Skal bare slenge ut tanker om en annen ide:

 

Starte med tabell med til å begynne med en enkelt rekke av prioriteringstall. Aller første rekka innvilger alle førstevalget (F.eks. "11111").

Så en algoritme som går igjennom og identifiserer de stedene som er blitt overbelastet ut fra rekka som undersøkes, identifiserer de personene som har valgt stedet, og lagrer flere nye versjoner av rekka etter den aktuelle i tabellen over rekker. De nye versjonene av rekka utgjør alle kombinasjoner av personer som må gå ned på en lavere prioritet (F.eks "21121", "22111" og "12121"). Så slettes den undersøkte rekka fra tabellen, og neste rekke (som nettopp ble generert) undersøkes på samme måte.

 

Hvis algoritmen derimot finner at en rekke faktisk går opp, kan den f.eks. lagres i en fil sammen med poengsummen sin.

 

Men så blir problemet:

Dette tilsvarer jo å gå langs alle forgreiningene av "treet" som utgjør hvem som settes ned en prioritet. Hver av greinene kan/vil jo ha nye forgreininger osv osv. Og når alle rekkene skal holdes i minnet, er det vel en viss fare for overflow.

 

Er det noen mulighet for å finne ut av hvor mange rekker tabellen maksimalt vil inneholde? Noen triks for å begrense dybden, f.eks å følge en grein helt til "tuppen" (for å holde på metaforen) der den går opp, før man starter med neste grein, og slik sørge for å bli fortest mulig ferdig med de ballene man har i lufta?

[daysleper]

Algoritmen min sikkrer at så mange som mulig får høyest mulig tilgjengelige prioriterte valg.

 

Tror ikke man på noen måte kan være uheldig med input som du sier: -Den skal gjøre det samme som i eksemplene under uansett:

 

 

Eks1:

10 personer med første prioritert på 10 forskjellige seter --> 10 får sitt første ønske.

0 resterende personer.

10 fikk første valg.

 

 

Eks2:

10 personer med første prioritet på 5 forskjellige seter --> 5 får sitt første valg.

5 resterende personer.

5 personer med andre prioritet på 5 forskjellige seter --> 5 får sitt andre valg.

0 resterende personer.

5 fikk første valg, 5 fikk andre valg.

 

 

Eks3:

10 personer med første prioritet på 5 forskjellige seter --> 5 får sitt første valg.

5 resterende personer.

5 personer med andre prioritet på 3 forskjellige seter --> 3 får sitt andre valg.

2 resterende personer.

2 personer med tredje prioritet på 1. sete --> 1 får sitt tredje valg.

1 resterende person.

1 person med fjerde prioritet på 1. sete --> 1 får sitt fjerde valg.

0 resterende personer.

5 fikk første valg, 3 fikk andre valg, 1 fikk tredje valg og 1 fikk fjerde valg.

 

 

Jeg ser ingen annen måte som kan være mer rettferdig enn dette .. Jeg er treg i hue noen ganger - så si fra.

 

Hva hvis vi tar en liten test? -- Vi tar begge algoritmene våre og gir dem samme datafil som input for så å se hva de gjør ut av det? Eller 3 datafiler kanskje? En liten, en mellomstor og en stor?

 

Kunne du generert noe data med den Java-snutten din og lagt en link her?

Så legger vi begge ut resultat av output fra algoritmene våre?

[daysleper]

Her er Eks. 3's input (nå i form av C++ -kode, men kunne godt vært en simpel .txt-fil som leses inn):

 

Seats::Person person1;

person1.name("Lars");

person1.addWish(1, 1); // priority, seat number

person1.addWish(2, 2);

person1.addWish(3, 3);

seats.addPerson(person1);

 

Seats::Person person2;

person2.name("Kari");

person2.addWish(1, 2); // priority, seat number

person2.addWish(2, 2);

person2.addWish(3, 1);

seats.addPerson(person2);

 

Seats::Person person3;

person3.name("Per");

person3.addWish(1, 3); // priority, seat number

person3.addWish(2, 1);

person3.addWish(3, 2);

seats.addPerson(person3);

 

Seats::Person person4;

person4.name("Lise");

person4.addWish(1, 4); // priority, seat number

person4.addWish(2, 2);

person4.addWish(3, 3);

seats.addPerson(person4);

 

Seats::Person person5;

person5.name("Ola");

person5.addWish(1, 5); // priority, seat number

person5.addWish(2, 2);

person5.addWish(3, 3);

seats.addPerson(person5);

 

Seats::Person person6;

person6.name("Anja");

person6.addWish(1, 1); // priority, seat number

person6.addWish(2, 6);

person6.addWish(3, 3);

seats.addPerson(person6);

 

Seats::Person person7;

person7.name("Kjetil");

person7.addWish(1, 2); // priority, seat number

person7.addWish(2, 7);

person7.addWish(3, 1);

seats.addPerson(person7);

 

Seats::Person person8;

person8.name("Nils");

person8.addWish(1, 3); // priority, seat number

person8.addWish(2, 8);

person8.addWish(3, 2);

seats.addPerson(person8);

 

Seats::Person person9;

person9.name("Kine");

person9.addWish(1, 4); // priority, seat number

person9.addWish(2, 6);

person9.addWish(3, 9);

seats.addPerson(person9);

 

Seats::Person person10;

person10.name("Bjarne");

person10.addWish(1, 5); // priority, seat number

person10.addWish(2, 7);

person10.addWish(3, 9);

person10.addWish(4, 10);

seats.addPerson(person10);

 

 

Her er Eks 3's output:

Lars is finding a place to sit.

Lars sits down at seat number 1, which for him/her is a priority 1 seat.

 

Kari is finding a place to sit.

Kari sits down at seat number 2, which for him/her is a priority 1 seat.

 

Per is finding a place to sit.

Per sits down at seat number 3, which for him/her is a priority 1 seat.

 

Lise is finding a place to sit.

Lise sits down at seat number 4, which for him/her is a priority 1 seat.

 

Ola is finding a place to sit.

Ola sits down at seat number 5, which for him/her is a priority 1 seat.

 

Anja is finding a place to sit.

Anja sits down at seat number 6, which for him/her is a priority 2 seat.

 

Kjetil is finding a place to sit.

Kjetil sits down at seat number 7, which for him/her is a priority 2 seat.

 

Nils is finding a place to sit.

Nils sits down at seat number 8, which for him/her is a priority 2 seat.

 

Kine is finding a place to sit.

Kine sits down at seat number 9, which for him/her is a priority 3 seat.

 

Bjarne is finding a place to sit.

Bjarne sits down at seat number 10, which for him/her is a priority 4 seat.

 

 

Placements

----------

Seat number: 1 -- Lars

Seat number: 2 -- Kari

Seat number: 3 -- Per

Seat number: 4 -- Lise

Seat number: 5 -- Ola

Seat number: 6 -- Anja

Seat number: 7 -- Kjetil

Seat number: 8 -- Nils

Seat number: 9 -- Kine

Seat number: 10 -- Bjarne

 

Remaining

---------

 

 

Hvis jeg bytter om rekkefølgen jeg legger til personer får jeg seff. samme output.

[daysleper]

Skal sette meg inn i det dere foreslo, har bare ikke hatt tid til å gjøre det enda (og hva gjør jeg med .java-programmer? Kan de kjøres i feks en nettleser?).

 

Java

 

Du må ha Java runtime og en Java kompiler installert. ( http://java.sun.com/j2se/downloads.html SDK-kolonnen altså! )

Du trenger ikke den pakken som inkluderer Netbeans.

 

 

For å kompilere

Få frem en kommandolinje og skriv:

javac InputGen.java

 

..og ut kommer en InputGen.class -fil.

 

 

For å kjøre

java InputGen

 

 

 

C++

 

Du trenger en C++ kompiler: http://prdownloads.sf.net/mingw/MinGW-3.1.0-1.exe?download

Denne er for Windows, hos Linux er det allerede installert en tilsvarende kompiler.

 

I hovedsak er det ganske likt det å kompilere Java-kode:

 

 

Kompilere

Få frem en kommandolinje og skriv:

g++ findseats.cpp -o findseats

 

..og ut kommer en findseats.exe -fil.

 

Kjøre

findseats

 

 

Flere detaljer

Windows: http://nostdal.net/forum/viewtopic.php?p=154#154

Linux: http://nostdal.net/forum/viewtopic.php?p=155#155

 

FAQ'en for C++ her på sourcecode.no er "føkka" (forum-bytte) - derfor jeg linker til en backup.

[MailMan13]

Algoritmen min sikkrer at så mange som mulig får høyest mulig tilgjengelige prioriterte valg.

 

Tror ikke man på noen måte kan være uheldig med input som du sier: -Den skal gjøre det samme som i eksemplene under uansett:

 

Hvis man sier at man har 4 plasser med alle kapasitet på 1, og 4 personer med henholdsvis 123 241 342 og 231 som ønsker, her vil en greedy algoritme plassere person 1-3 på plass 1-3, da blir alle valgene til person 4 opptatt, plasserer man derimot person 2 på plass 4 får man plass til person 4 på plass to, altså har de fått sin prioritet 1211 innvilget som er mer optimal enn 1110 som det blir med ditt forslag, skal man få til slike vurderinger må man la algoritmen dynamisk endre deler av resultatet som allerede er bestemt, det kan jeg ikke se at du har gjort.

 

Algoritmen din sikrer at man får høyeste tilgjengelige plass i den rekkefølgen input kommer i, og ikke et optimalt resultat basert på at flest mulig skal plasseres.

[daysleper]

Ja, dette:

 

Seats::Person person1;

person1.name("Lise");

person1.addWish(1, 1); // priority, seat number

person1.addWish(2, 2);

person1.addWish(3, 3);

seats.addPerson(person1);

 

Seats::Person person2;

person2.name("Ole");

person2.addWish(1, 2); // priority, seat number

person2.addWish(2, 4);

person2.addWish(3, 1);

seats.addPerson(person2);

 

Seats::Person person3;

person3.name("Per");

person3.addWish(1, 3); // priority, seat number

person3.addWish(2, 4);

person3.addWish(3, 2);

seats.addPerson(person3);

 

Seats::Person person4;

person4.name("Anja");

person4.addWish(1, 2); // priority, seat number

person4.addWish(2, 3);

person4.addWish(3, 1);

seats.addPerson(person4);

 

 

Gir denne output'en:

 

Lise is finding a place to sit.

Lise sits down at seat number 1, which for him/her is a priority 1 seat.

 

Ole is finding a place to sit.

Ole sits down at seat number 2, which for him/her is a priority 1 seat.

 

Per is finding a place to sit.

Per sits down at seat number 3, which for him/her is a priority 1 seat.

 

Anja is finding a place to sit.

 

 

Placements

----------

Seat number: 1 -- Lise

Seat number: 2 -- Ole

Seat number: 3 -- Per

 

Remaining

---------

Anja did not get any of the seats that he/she wished for.

 

 

Stakkars Anja blir m.a.o. stående igjen når Ole i stedet kunne satt seg på plass 4 (hans 2. valg) og Anja fått hans plass 2 (hennes 1. valg) altså?

 

Jeg sa jeg var treg i hue noen ganger.

 

Se om jeg kan legge til noe som bytter litt om her da ..

[inaktiv000]

Kanskje det er lettere å ta utgangspunkt i plassene, for så å finne hvilke personer som vil sitte på hver enkelt plass?

 

Plass 1: Person 1(1), Person 2(1) og Person 3(2)

Plass 2: Person 1(2), Person 2(3) og Person 3(1)

 

Slike grupperinger vil man vel få da, det er kanskje lettere å gjøre valg ut fra dette?

[Torbjørn]

dette hadde vært meget interessant å løse med genetisk programmering.

får se om jeg får tatt meg tida til å prøve

[MailMan13]

Skal bare slenge ut tanker om en annen ide:

 

Starte med tabell med til å begynne med en enkelt rekke av prioriteringstall. Aller første rekka innvilger alle førstevalget (F.eks. "11111").

Så en algoritme som går igjennom og identifiserer de stedene som er blitt overbelastet ut fra rekka som undersøkes, identifiserer de personene som har valgt stedet, og lagrer flere nye versjoner av rekka etter den aktuelle i tabellen over rekker. De nye versjonene av rekka utgjør alle kombinasjoner av personer som må gå ned på en lavere prioritet (F.eks "21121", "22111" og "12121"). Så slettes den undersøkte rekka fra tabellen, og neste rekke (som nettopp ble generert) undersøkes på samme måte.

Det er fortsatt en algoritme med eksponensiell kjøretid, før eller siden sprekker det, og du blir aldri ferdig, slike 'brute force' angrep kan virke fornuftige ved at de gir en oversiktlig algoritme med garanti som er enkel å bevise, men jeg tror vi må være litt smartere i dette tilfellet hvis det skal komme effektivt program ut av det, det går fort med mye minne og veldig mange iterasjoner/rekursive kall før man kommer noen vei.

 

En løsning jeg har tenkt litt på er å få rede på hvor mange første-prioriteter som kan innfris uten å skape konflikter, deretter plasserer vi disse og fjerner dem fra datamengden, så sjekker vi hvem av de som er igjen som har andre og tredje valg som skaper konflikter og innfrir førstevalget så langt som mulig for disse mens vi hele tiden fjerner dem fra datamengden når vi plasserer dem, deretter gjentar vi prosessen for andre valg og tilsluttt fyller inn tredjevalg så langt som mulig for de som er igjen. Det blir litt på samme måte som forslaget ditt her, men uten den samme 'alle muligheter' genereringen som har en tendens til å ødelegge moroa for oss.

 

Jeg har ikke skrevet noen kode for dette, men du skjønner kanskje gangen i det.

 

Jeg har hverken påvist eller motbevist den påståtte svakheten i det dynamiske eksempelet mitt heller enda, det viser seg å alltid gi optimalt svar tror jeg det skal mye til å finne noe raskere løsning, på den andre siden er det godt mulig den faller sammen med riktig uheldig input (jeg har en følelse av at man kan lure den opp i spesielle tilfeller slik at den går glipp av noen tildelinger med lav prioritet).

[daysleper]

Ser ut som om det er mange måter å gjøre det her på --

 

Jeg prøver meg med en algoritme der personer spør hverandre om de kan få plassen til en annen på grunnlag av hvor mye den personen som spør taper i "rettferdighet" hvis han/hun ikke får byttet, mot det han/hun som blir spurt taper i "rettferdighet" hvis han/hun velger å akseptere byttet.

 

De spør personene "under" hverandre igjen, rekursivt (hm, tror jeg) -- for så å rapportere tilbake til den som spurte på "toppen" om hvor mye han/hun og de under han/hun taper til sammen.

 

Rettferdighet måles i hvor mange prioriterte valg en person må gi slipp på for at andre skal få vilja si.

 

..mulig jeg misser noe her.. måtte bare få skrevet det ned og se om det ble klarere.

 

Kan hende dette blir noe som tar fryktlig lang tid, men jeg vil prøve meg på en algoritme som på en måte finner en "perfekt" løsning på en systematisk måte uten å måtte prøve alle kombinasjoner - hvis det er mulig.

 

Så var det å holde tungen bent i munnen ..

[zyp]

Må bare prøve meg jeg også...

Sitter å eksperimenterer litt nå...

[Onkel]

Jeg lagde hele greia nå i natt. I QBasic 7.1, fordi det er det eneste jeg er helt stø i! Hey, ikke le!

 

Det var mange variabler i lufta, en skikkelig tungarettimunnen-oppgave der ja.

 

Løsningen jeg brukte, så ut til å være veldig effektiv: å starte langs "stammen" i "treet" (som er at alle i utgangspunktet får førstepri). Så finne ut hvilke personer som konkurrerer om samme sted. Så lage alle kombinasjoner av hvem som må ned en prioritet, og lagre de kombinasjonene som nye "greiner" i treet. Så tilbake til utgangspunktet, undersøke og utvide neste grein på samme måte. Greina eller stammen som akkurat ble undersøkt slettes fra lista, fordi den enten bir utvidet til nye greiner, eller gir et treff (en kombinasjon hvor det er nok plasser på de tildelte stedene).

 

Dette viste seg å ikke være på langt nær så "brute force" som jeg hadde trodd. Ved å alltid undersøke greinene så langt vekk fra stammen som mulig ble lista over greiner å undersøke holdt på et minimum, fordi man ganske fort finner et treff. Dessuten la jeg inn en sperre som gjorde at en grein ikke lenger undersøkes hvis "rettferdighetsverdien" dens er blitt lavere enn et treff som allerede er funnet. Jeg taper ikke potensielle gode kombinasjoner på dette, siden enhver ny forgreining vil være et skritt ned i rettferdighet.

 

Resultat: Ei liste på ti personer og fire prioriteter hver (inkl. en som tilsvarer å ikke få noen av valgene sine) ble løst i løpet av I UNDERKANT AV HUNDRE LOOPS, og lista over greiner som gjenstod å undersøke overskred faktisk aldri ni! Resultatene ble lagret i ei liste over de ti mest rettferdige treffene. Til sammenligning ville det første forslaget jeg kom med krevd 1048576 loops, med et kombinasjons-array på samme størrelse!

 

Noen småting gjenstår enda, feks blir noen av treffene som lagres i ti-på-topp-lista samme grein av en eller annen grunn. Og når jeg testet med en lengre liste over personer fikk jeg en sånn "subscript-out-of-range"-feil. Sånt kan ta litt tid å rette når det er mange arrays som er hverandres indekser, sinnssykt uoversiktlig, så jeg tar den senere. Regner med det er finpussing, og jeg ble fornøyd nok med selve løsningsstrukturen (som jo egentlig var det interessante).

 

Flere forslag?

 

Noen som ville være interessert i den jeg lagde?

[MailMan13]

Resultat: Ei liste på ti personer og fire prioriteter hver (inkl. en som tilsvarer å ikke få noen av valgene sine) ble løst i løpet av I UNDERKANT AV HUNDRE LOOPS

For 10 stykker er det nok en bra løsning, og algoritmen har i utgangspunktet logaritmisk vekst, som er svært brukbart. Problemet er slik som jeg ser det at treèt ditt vokser eksponensielt med antall konflikter og du fort kan bruke opp all tilgjengelig minne hvis det er mange konflikter. Hvis du for eksempel har 4 konflikter får du teoretisk 4^4 = 256 muligheter, har du bare 2 til blir det 4096 muligheter. Hvis du kjører denne for 100 personer får man fort flere kolisjoner enn man kan telle på fingrene, og da sprekker det hvis ikke du har en veldig god avskjæring.

 

Men for all del, jeg kan ha forstått deg feil, prøv den med 100, 1000 og 10000 personer og se hva du får. Her har du tilfeldig genererte input hvis du trenger (halvparten så mange plasser, slik at du får rikelig med konflikter):

 

100, 1000, 10000