distributie-algoritme?

[Verwijderd]

[weet niet zeker of dit hier thuishoort.. maar ook niet waar het anders thuis zou horen ;)]

stel, ik heb een aantal punten, creatief genaamd 1 t/m 6, die op een bepaalde positie staan in een 2d veld. dit zijn de lichtgroene punten op het plaatje. elk van deze punten moet op een van de donkere punten terechtkomen. (hierbij mogen er geen 2 groene punten op 1 donker punt terechtkomen)



nu mogen ze niet zomaar allemaal een willekeurig punt zoeken, de opdracht is om de verdeling te vinden waarbij de afstand die het punt dat de langste afstand moet 'afleggen' kleiner is dan bij welke andere verdeling dan ook

het correcte resultaat wordt dan:



dit klinkt een beetje vaag wellicht, dus bij wijze van uitleg: stel dat punt 1 niet naar het linksonderste, maar naar het middenonderste punt was gegaan. hierdoor zou bijv punt 3 daar niet meer terecht kunnen, die zou dan juist naar de linksonderste 'base' moeten. de afstand die 3 hierdoor moet afleggen wordt groter dan de afstand die 1 (samen met 2 de langste reiziger) moet afleggen in het 'correcte' plaatje, dus is deze oplossing niet goed.

als er meerdere oplossingen zijn die voldoen aan de hoofdvoorwaarde, dan moet degene worden gekozen die de kleinste cumulatieve afstand heeft (alle puntreisjes opgeteld). immers, anders zouden 4 en 5 in mijn voorbeeld ook elkaars targets kunnen kiezen, ondanks dat dat onnodig langere reisjes voor ze oplevert.


nu het daadwerkelijke probleem: hoe programmeer ik dit? (qua algoritme/pseudocode/principe) na flink wat peinzen kom ik er niet uit
enige manier die deze oplossing geeft die ik kan verzinnen is brute-force alle mogelijkheden uitproberen..

..en dat is natuurlijk niet de bedoeling


*edit: voor de overdadigheid: ik zoek een oplossing die bij welk een begindistributie (qua posities) van groene puntjes dan ook werkt, niet een die alleen voor dit voorbeeld werkt

[ Voor 14% gewijzigd door Verwijderd op 02-11-2010 17:51 ]

[itarix]

Hoe meet je de afstand die de punten af moeten leggen?

[Matis]

je hebt (aantal punten)! mogelijkheden. Misschien kun je het bruteforcen

[.oisyn]

Moet de topologie hetzelfde blijven? Of mag bijvoorbeeld de 6 uit je voorbeeld ook onder de rest terecht komen als de rest al op de beste plek staat.

[TGEN]

Klinkt als TSP. Gebruik een genetisch/simulated annealing algoritme .

[Verwijderd]

itarix schreef op dinsdag 02 november 2010 @ 17:23:
Hoe meet je de afstand die de punten af moeten leggen?

gewoon hemelsbreed van oorsprong naar donkere punt

Matis schreef op dinsdag 02 november 2010 @ 17:38:
je hebt (aantal punten)! mogelijkheden. Misschien kun je het bruteforcen

uiteindelijk moet dit voor 11 punten gaan werken.. dus dat wordt lastig

.oisyn schreef op dinsdag 02 november 2010 @ 17:39:
Moet de topologie hetzelfde blijven? Of mag bijvoorbeeld de 6 uit je voorbeeld ook onder de rest terecht komen als de rest al op de beste plek staat.

dat mag best, alleen lijkt me dat je dan niet voldoet aan de voorwaarde:
- 6 legt in zo'n distributie de langste afstand af (an sich is dat prima), maar
- er zijn andere distributies te verzinnen (zoals plaatje #2) waarin het punt dat de langste afstand aflegt een kortere afstand aflegt dan de 6 van jouw voorbeeld

(hoop dat het zo duidelijk is)

*edit: misschien snapte ik je verkeerd oisyn: mocht de topografie veranderen, maar je voldoet wel aan die voorwaarde, dan is dat ook prima ja

TGEN schreef op dinsdag 02 november 2010 @ 17:41:
Klinkt als TSP. Gebruik een genetisch/simulated annealing algoritme .

heb je iets meer info, misschien een link naar wat basic uitleg? ik heb hier 0 kaas van gegeten en google gooit moeilijke woorden naar me

*edit2: zit nog wel een andere voorwaarde te bedenken: als er meerdere oplossingen zijn die voldoen aan de hoofdvoorwaarde, dan moet degene worden gekozen die de kleinste cumulatieve afstand heeft (alle puntreisjes opgeteld). immers, anders zouden 4 en 5 in mijn voorbeeld ook elkaars targets kunnen kiezen, ondanks dat dat onnodig langere reisjes voor ze oplevert. topic aangepast*

[ Voor 27% gewijzigd door Verwijderd op 02-11-2010 17:53 ]

[.oisyn]

Verwijderd schreef op dinsdag 02 november 2010 @ 17:44:
dat mag best, alleen lijkt me dat je dan niet voldoet aan de voorwaarde:
- 6 legt in zo'n distributie de langste afstand af (an sich is dat prima), maar
- er zijn andere distributies te verzinnen (zoals plaatje #2) waarin het punt dat de langste afstand aflegt een kortere afstand aflegt dan de 6 van jouw voorbeeld

Oh wacht ik interpreteerde de voorwaarde verkeerd. Het gaat alleen om de langst afgelegde afstand, niet om de totale afgelegde afstand van alle punten.

[Soultaker]

Volgens de TS is de langst afgelegde afstand het hoofdcriterium, maar het minimaliseren van de som van de afstanden wel een secundair criterium. Ik denk dat dit relatief efficiënt exact kan. Even denken...

[Verwijderd]

idd, voor de duidelijkheid: die secundaire voorwaarde heb ik later toegevoegd, realiseerde het me eerst niet dat die wel zo nuttig is

[Soultaker]

Ik hoop dat ik niet net je huiswerk voor je gedaan heb, maar hier volgt een efficiënte oplossing (ook voor veel punten). Stel dat we het minimaliseren van de maximumafstand even negeren, dan kunnen we het probleem voor de tweede constraint als volgt oplossen.

Definieer een flow network met punten s (source), t (sink) en 1 t/m 2n (voor de punten). Voeg edges (s,x), (x,n+y), (n+y,t) voor 1<=x,y<=n toe. Alle edges hebben capaciteit 1 en kosten 0, behalve edges (x,n+y), die hebben een per-unit cost gelijk aan de afstand tussen de punten x en y. Los nu het minimum cost maximum flow probleem op (bijvoorbeeld met het Ford-Fulkerson algoritme waarbij Dijkstra's algoritme of iets dergelijks gebruikt wordt om steeds het kortste augmenting path met unit flow te vinden.)

edit:
(Wat ik hierboven beschrijf is een oplossingmethode voor het vinden van een minimum weight maximum matching in een gewogen bipartiete graaf. Een meer gebruikelijke methode is het Hongaarse algoritme; als je iets vanaf het begin moet opbouwen kun je die beter gebruiken. De enige reden dat ik die niet meteen noemde is dat ik er niet aan gedacht had )

De resulterende flow correspondeert met een toekenning van de n bronpunten aan de n doelpunten waarbij de totale verplaatsing minimaal is. Dit was het secundaire criterium. Nu nog het eerste criterium.

Stel dat je weet wát de maximumafstand is die mogelijk is, dan kun je simpelweg de edges in het flow network die corresponderen met grotere afstanden weglaten (of hun capaciteit op nul zetten, naar gelang wat makkelijker is). Hoewel je die maximumafstand helaas niet weet, kun je hem wel met behulp van binary search achterhalen, en dus relatief snel een willekeurig nauwkeurige benadering vinden. Een andere manier om de maximumafstand te vinden, is simpelweg de verschillende kosten van de edges (x,y) te proberen. Je haalt dan steeds de duurste edge uit het netwerk, totdat je het minimum cost flow probleem niet meer met de gewenste flow van n units op kunt lossen.

De eerste methode zal efficiënter zijn bij heel veel punten en beperkte nauwkeurigheid. De tweede leidt tot maximaal n² applicaties van het maximum flow algoritme, wat zelf al O(n³) tijd kost, dus dan zit je op O(n⁵) in totaal. (edit: Het Hongaarse algoritme kan ook in O(n³) geïmplementeerd worden en dan is de complexiteit hetzelfde.) Dat is praktisch tot een punt of honderd. In ieder geval is het polynomiaal, wat een stuk beter is dan alle combinaties uitproberen.

[ Voor 10% gewijzigd door Soultaker op 02-11-2010 18:42 ]

[.oisyn]

Mijn eerste idee (bij lange na niet vollledig uitgewerkt, dus wellicht mis ik wat): mik alle bron-doel punten in een priority queue op basis van afstand, en haal die vervolgens een voor een eruit waarbij je het bron aan het doel bindt. Is een doel al bezet, dan backtrack je door je vorige opties om de boel op een betere manier te verdelen (indien mogelijk, wellicht heb je al de beste oplossing). Je bent klaar zodra alle punten verdeeld zijn, en dat is dan ook meteen de beste oplossing.

(hierin zit je tweede conditie nog niet verwerkt, maar die is triviaal)

[ Voor 5% gewijzigd door .oisyn op 02-11-2010 18:29 ]

[Verwijderd]

@soultaker: bedankt voor je uitgebreide post op basis daarvan ben ik alleen wel weer uren of dagen bezig om te begrijpen waar het over gaat maar dat is prima, heb ik weer wat dingen om op los te googlen
overigens, dit is geen huiswerk, vrees niet

@oisyn: ook een idee, ik zal zelf ook even nadenken of dit potentie heeft. vooral de manier van implementatie van het backtracken zal ook wel weer een probleem op zich worden, maar wie weet.. tnx

/me duikt er morgen verder in

[Soultaker]

Ok, als je je nog verveelt: het lijkt een instantie van het linear bottleneck assignment problem te zijn, maar helaas is daar weinig over te vinden buiten een aantal academische papers over het onderwerp.

Verder is 11 faculteit minder dan 40 miljoen, dus dat is nog wel binnen de grenzen van het bruteforcebare, als je bereid bent een seconde ofzo op het resultaat te wachten. Het wordt natuurlijk wel heel snel meer. Misschien is het sowieso handig om de bruteforcemethode implementeren om de resultaten van een efficiëntere oplossing mee te verifiëren.

[ Voor 12% gewijzigd door Soultaker op 02-11-2010 18:54 ]

[Verwijderd]

het moet realtime in een spel, mag eigenlijk niet meer dan een milliseconde of 10 duren

ter controle is het bruteforcen idd wel een goed plan

*trouwens soultaker: na wat snel inleeswerk: heeft het hongaarse algoritme ook niet tot gevolg dat ik wel aan mn secundaire, maar niet aan mn primaire voorwaarde voldoe?

[ Voor 36% gewijzigd door Verwijderd op 02-11-2010 19:21 ]

[Soultaker]

Vandaar de tweede helft van mijn post: als je een bovengrens kent, dan kun je paren punten die te ver van elkaar liggen weglaten (bij de matrixmethode met het Hongaarse algoritme betekent dat de kosten op oneindig zetten). Als je de bovengrens gaat gokken, kijk je na het oplossen of je totale kosten onder oneindig liggen; zoniet, dan is die bovengrens te laag.

Verder wil ik het laatste deel nog even herzien: de mogelijkheden voor de grootste afstand zijn precies de afstanden tussen de n² paren van punten. Als je die eerst sorteert, en op de gesorteerde lijst binary searcht, heb je maar 2x²log n iteraties nodig, en kom je in totaal op O(n³log n) uit. Dat moet te doen zijn met 11 punten in en 10 ms.

[Verwijderd]

je bent geweldig
dacht dat het 2e deel van je post alleen opging voor flow netwerkjes, niet zo snugger van me

nog een ding,
"de mogelijkheden voor de grootste afstand zijn precies de afstanden tussen de n² paren van punten."
die snap ik nog niet helemaal..
*edit, oh je bedoeld: als je alle exacte max afstanden weet hoef je niet gewoon te gokken, maar kun je daar specifiek op zoeken, waardoor het sneller is, zeker?

[ Voor 63% gewijzigd door Verwijderd op 02-11-2010 20:04 ]

[Soultaker]

Het langste pad in een oplossing is de lengte van een pad tussen één van je beginpunten en één van je eindpunten. Er zijn dus n² mogelijkheden voor het langste pad, en daarmee maximaal n² bovengrenzen om uit te proberen.

[maxjuh]

knip

[ Voor 98% gewijzigd door maxjuh op 03-11-2010 13:38 ]

[Soultaker]

Dat geeft wel een aardige benadering (geen gek idee als de tijd beperkt is) maar werkt niet volgens de specificaties van de TS. Bijvoorbeeld als je beginpunten op (2,0) en (1,0) liggen, en je eindpunten op (3,0) en (4,0), dan verbind je (2,0)-(3,0) en (1,0)-(4,0), wat een maximale afstand van 4 geeft in plaats van 2.

Waarschijnlijk kun je wel wat hacken om dat ook weer te fixen, maar ik betwijfel of je een 100% correcte oplossing kunt krijgen op een greedy manier. (Misschien kan het wel... het probleem op het euclidische vlak is minder algemeen dan een assignment problem denk ik.)

[_js_]

Soultaker schreef op dinsdag 02 november 2010 @ 19:54:
Vandaar de tweede helft van mijn post: als je een bovengrens kent, dan kun je paren punten die te ver van elkaar liggen weglaten (bij de matrixmethode met het Hongaarse algoritme betekent dat de kosten op oneindig zetten). Als je de bovengrens gaat gokken, kijk je na het oplossen of je totale kosten onder oneindig liggen; zoniet, dan is die bovengrens te laag.

Verder wil ik het laatste deel nog even herzien: de mogelijkheden voor de grootste afstand zijn precies de afstanden tussen de n² paren van punten. Als je die eerst sorteert, en op de gesorteerde lijst binary searcht, heb je maar 2x²log n iteraties nodig, en kom je in totaal op O(n³log n) uit. Dat moet te doen zijn met 11 punten in en 10 ms.

Het kan zijn dat ik jouw verhaal verkeerd lees en/of ik je niet snap. Als dat zo is dan mijn post maar ignoren.

Is het niet handiger om eerst het laagste langste pad uit te zoeken en dan pas je Hongaarse methode toe te passen? Volgens mij kom je dan uit op O(n²log n) + O(n³). Dat langste pad uit zoeken kan zoals je eerder zei door telkens de langste(n) weg te gooien en kijken of er nog een pad is, n²log n krijg je door n*n verbindingen te sorteren op afstand, en de langste(n) weg te gooien tot dat een bron of een doel nog maar 1 verbinding heeft.

[Soultaker]

_js_ schreef op woensdag 03 november 2010 @ 03:24:
Is het niet handiger om eerst het laagste langste pad uit te zoeken en dan pas je Hongaarse methode toe te passen?

Als dat kan, zou dat ideaal zijn, maar hoe doe je dat? Ik ga er vanuit dat je met een gegeven maximum het assignment problem probeert op te lossen (ofwel met minimum cost maximum flow, ofwel met de Hongaarse methode, dat maakt verder weinig uit) en als dat niet lukt, dan is je maximum dus te laag.

Dat langste pad uit zoeken kan zoals je eerder zei door telkens de langste(n) weg te gooien en kijken of er nog een pad is.

Hoe wil je dát (in constante tijd ) doen?

Eventueel zou je voor het bepalen van het minimale langste pad een gewone (ongewogen) bipartiete matching kunnen uitvoeren. Dat zal in de praktijk iets sneller zijn, maar daar win je qua complexiteit niets mee.

[_js_]

Edit: niet.

Ik zie nu mijn denkfout

[ Voor 78% gewijzigd door _js_ op 03-11-2010 05:51 ]

[maxjuh]

knip

[ Voor 99% gewijzigd door maxjuh op 03-11-2010 13:36 ]

[Verwijderd]

In principe zou de 'kortste afstand eerst' methode ook werken , maar dit levert meestal ee 1,5 keer de 'optimale' route

(Wikipedia : The Christofides algorithm follows a similar outline but combines the minimum spanning tree with a solution of another problem, minimum-weight perfect matching. This gives a TSP tour which is at most 1.5 times the optimal)

Indien je dit voor een game wil gebruiken zou je een A* algoritme kunnen gebruiken.

[pedorus]

maxjuh schreef op woensdag 03 november 2010 @ 11:16:
Hoe kom je op een maximale afstand van 2? Als je de begintpunten laat verbinden met de andere aanwezige mogelijkheid kom je toch ook op 4? (2,0)-(4,0) en (1,0)-(3,0). Of zie ik iets over het hoofd.

max(2,2)=2

Soultaker schreef op woensdag 03 november 2010 @ 01:51:
het probleem op het euclidische vlak is minder algemeen dan een assignment problem denk ik.

Dat weet ik wel zeker aangezien het een wel altijd in het ander is om te schrijven, maar dit omgekeerd niet geld. Toch is het nog vrij lastig om een algoritme te bedenken dat altijd werkt. Ik heb het vermoeden dat er een soort sweep line algorithm mogelijk is, of dat dat in ieder geval een zeer goede heuristiek is.

Ik vraag me trouwens af of het 2e criterium wel logisch is. Is het niet logischer om als tweede criterium het minimaliseren van de 2e grootste afstand te nemen, enzovoorts? Dan krijg je een lexicographic bottleneck assignment problem.

[Knutselsmurf]

Ik zit me af te vragen of de tweede voorwaarde (minimaliseren van de totale afstand) er ook niet voor zorgt dat dan automatisch aan de eerste voorwaarde wordt voldaan.
Stel, ik heb een suboptimale oplossing, waarin ik twee paren onderling ga uitwisselen. Dan kan het toch nooit zo zijn, dat door die ene verwisseling de totale afstand kleiner wordt, maar de maximale afstand groter?

[Verwijderd]

hm misschien niet bij het wisselen van 2, maar wel van meer (snelle schatting hoor)

het kan bijv zijn dat elk punt *op 1 na* al bijna bij een 'destination punt' staat. echter, als ze die kiezen blijft er 1 punt over die juist het hele veld over moet.

met mijn voorwaarde is er misschien juist een oplossing waarbij elk punt een 'eindje' moet 'lopen' (terminologie ftw ) maar waardoor er geen enkel punt is dat het hele veld over moet. de totaalafstand van alle punten opgeteld zou dan wel groot worden, ik vermoed groter dan de totaalafstand in de andere situatie. toch is dat dan preferabel


* heb een leuk artikel gevonden over het 'hongaarse algoritme': Assignment Problem and Hungarian Algorithm

ik snap alleen sommige stukjes niet, omdat ik geen 'wiskundesyntax' kan lezen (de HAVO gaat zover niet ). nog maar eens goed uitzoeken.. it's a start.
heb na flink googlen wel geconcludeerd dat er voor dit algoritme veel wegen naar rome zijn, omdat er binnen het oplossen ook nog andere algoritmes nodig zijn, bijv voor het verfijnen van de mogelijke routes. en dan zijn er ook nog oplossingen met verschillende complexiteit..

wat me trouwens opvalt; die wiki die soultaker over het hongaarse algoritme geeft doet alsof het heel simpel is, terwijl alle voorbeelden met code die ik vind enorme lappen code opleveren. blijkbaar is de theorie makkelijker dan de (goede) uitvoering

[Onbekend]

Ik heb ook wel die problemen gehad die softwarematig opgelost moesten worden.
Maar bij ons zat punt 6 soms een stuk verder weg, of die was er zelfs niet.

Maar wat is bij jou beter?
A. 5 punten met een zeer korte afstand en 1 punt er ver vanaf. (Dus zoveel mogelijk punten met een kleine afwijking.)
B. 6 punten die er verder vanaf liggen waarvan de totale afstand minder is dan bij A. (Zo min mogelijk afwijking voor alle punten.)


Dit is niet uit te rekenen, maar steeds in de praktijk passen, meten en corrigeren zodat de afwijking steeds kleiner wordt.
Wij hadden toen software gebruikt die ook in de ruimtevaartindustrie wordt gebruikt.

[Verwijderd]

B is voor mij dus beter. hoop dat dat gaat lukken op de beschreven manier (dus afstand verkorten tot je geen oplossing meer krijgt)

[writser]

Verwijderd schreef op dinsdag 02 november 2010 @ 18:57:
het moet realtime in een spel, mag eigenlijk niet meer dan een milliseconde of 10 duren

Klinkt cool. Kun je wat meer vertellen over waarom je het nodig hebt? Misschien zoek je wel een oplossing voor het verkeerde probleem. Iets met multitouch ofzo? Dat je vingers moet tracken? En is het noodzakelijk dat je _precies_ de meest efficiente oplossing vindt? Of is iets 'in de buurt' ook goed. Ben benieuwd!

[pedorus]

Ik heb even wat getest met 12 willekeurige punten en een hungarian algorithm waarbij steeds de combinaties het vorige maximum op oneindig wordt gezet (min/meer methode Soultaker). Hierbij de code:

C#:

    static class Program
    {
        public static double Distance(PointF from, PointF to)
        {
            return Math.Sqrt(((double)from.X - (double)to.X) *
                ((double)from.X - (double)to.X) +
                ((double)from.Y - (double)to.Y) *
                ((double)from.Y - (double)to.Y));
        }
        static Random rand = new Random();
        static PointF randomPoint()
        {
            return new PointF((float)rand.NextDouble(), (float)rand.NextDouble());
        }
        static void test()
        {
            var s = Stopwatch.StartNew();
            int howmany = 12;
            var iterator = Enumerable.Range(1, howmany);
            var sources = iterator.Select(a => randomPoint()).ToArray();
            var targets = iterator.Select(a => randomPoint()).ToArray();
            double[,] distances = new double[howmany, howmany];
            for (int i = 0; i <= distances.GetUpperBound(0); i++)
                for (int j = 0; j <= distances.GetUpperBound(1); j++)
                    distances[i, j] = Distance(sources[i], targets[j]);
            var solution = ((double[,])distances.Clone()).FindAssignments();
            var bestSolution = solution;
            var bestMax = double.MaxValue;
            var its = 0;
            while (true)
            {
                var max = double.MinValue;
                for (int i = 0; i < solution.Length; i++)
                    max = Math.Max(distances[i, solution[i]], max);
                if (max > bestMax)
                    break;
                its++;
                bestSolution = (int[])solution.Clone();
                bestMax = max;
                for (int i = 0; i <= distances.GetUpperBound(0); i++)
                    for (int j = 0; j <= distances.GetUpperBound(1); j++)
                        if (distances[i, j] >= max) distances[i, j] = double.MaxValue;
                solution = ((double[,])distances.Clone()).FindAssignments();
            }
            Console.WriteLine(its + "-" + s.ElapsedMilliseconds);
        }
        static void Main(string[] args)
        {
            for (int i = 0; i < 100; i++)
                test();
        }
    }

Dit gebruikt deze code met int[,] overal aangepast in double[,] en int.MaxValue aangepast in double.MaxValue. Draaitijd van de test is niet goed meetbaar in milliseconden (<=1ms), dus het lijkt erop dat dit prima werkt. Gezien het geringe aantal benodigde iteraties (13 is het hoogste dat ik heb gezien) is een binary search niet echt nuttig.

[Verwijderd]

hey bedankt voor de moeite ga er zo naar kijken. wel opvallend hoe kort je code is, ik zit intussen al aan de lappen code.. is je oplossing wel optimaal? (misschien komt het ook door die ingebouwde c# functies die c++ naar mijn weten dan weer niet heeft)

@writser:

leuke gok maar het is voor mijn voetbalspel (had het maar niet genoemd, omdat de meeste technisch ingestelde mensen daar een hekel aan hebben )

het gaat om de dynamische rolverdeling. stel, je hebt 3 backs, en 1tje rukt met de bal op naar het vijandelijke doel. je hebt nu nog maar 2 verdedigers achterin, en een extra 'aanvaller' voorin. als de bal daar wordt gekaapt heb je achterin dus een probleem.

idee is nu dat op basis van de situatie die dan bestaat (de groene stipjes in mijn voorbeeld zijn je mannetjes) een nieuwe opstelling wordt gemaakt op basis van je 'basisopstelling'. maw: je opstelling heeft achterin 3 backs, dus wordt de persoon die daar het best 'in past' tijdelijk een nieuwe back. dat zou bijv. een middenvelder kunnen zijn.

samengevat: het moet er voor zorgen dat de huidige situatie, waar je ventjes ook staan, in jouw basisopstelling 'geperst' kan worden zodat iedereen de meest logische (contextuele) rol krijgt toebedeeld

ander voorbeeld: je spits is om een of andere curieuze reden je laatste man, en er stormt een tegenstander met bal op hem af. hij moet dan wel weten dat hij in die context een back is, en dus stevig de tackle moet inzetten oid.

ik wil dit overigens gaan gebruiken in combinatie met mijn huidige manier van verdedigen, waarbij poppetjes vrij dynamisch rondrennen op basis van 'forcefields'. daardoor kan het ook voorkomen dat een middenvelder soms extra hard moet verdedigen (= op een plaats staat die logischerwijs door een back wordt ingenomen) en dergelijke zaken. hier een korte demonstratie (zie description voor wat uitgebreidere uitleg van de implementatie) http://www.youtube.com/watch?v=WwBOTJ14bVw&fmt=22

[Soultaker]

Knutselsmurf schreef op woensdag 03 november 2010 @ 17:07:
Ik zit me af te vragen of de tweede voorwaarde (minimaliseren van de totale afstand) er ook niet voor zorgt dat dan automatisch aan de eerste voorwaarde wordt voldaan.

Dat vroeg ik me ook af, maar er zijn simpele tegenvoorbeelden, bijvoorbeeld als je van a=(1,1), b=(2,1) naar b=(2,1), c=(2,2) wil gaan. Als je de totale afstand minimaliseert laat je b op b, en verplaats je a naar c (totale en maximale afstand wortel 2), maar als je de maximale afstand minimaliseert gaat a naar b en b naar c (totale afstand 2, maar maximale afstand 1).

Stel, ik heb een suboptimale oplossing, waarin ik twee paren onderling ga uitwisselen. Dan kan het toch nooit zo zijn, dat door die ene verwisseling de totale afstand kleiner wordt, maar de maximale afstand groter?

Dat niet, maar zoals ik eerder ook aangaf leidt het greedy uitwisselen van paren niet tot een correcte oplossing (maxjuh heeft zijn code al weggehaald, zie ik ) Waarschijnlijk zit daar de denkfout.

Verwijderd schreef op woensdag 03 november 2010 @ 17:24:
wat me trouwens opvalt; die wiki die soultaker over het hongaarse algoritme geeft doet alsof het heel simpel is, terwijl alle voorbeelden met code die ik vind enorme lappen code opleveren. blijkbaar is de theorie makkelijker dan de (goede) uitvoering

Mja, dat komt waarschijnlijk omdat het algoritme ontworpen is om op papier uitgevoerd te worden (in de jaren 50 had je nog nauwlijks computers) net als bijvoorbeeld de simplexmethode. Alles is dus opgedeeld in stappen die je op papier snel kunt uitvoeren, zoals een rij doorstrepen, het minimum of maximum maar in een rij vinden et cetera.... dingen die je op papier redelijk snel doet maar als je ze exact wil programmeren je eindeloos for-lusjes nodig hebt.

De implementatie die pedorus gebruikte is volgens mij vrij typisch wat betreft de grootte van de implementatie. De max flow oplossing is waarschijnlijk wel wat korter.

pedorus schreef op woensdag 03 november 2010 @ 20:49:
Gezien het geringe aantal benodigde iteraties (13 is het hoogste dat ik heb gezien) is een binary search niet echt nuttig.

Klopt, een binary search zou hier 7 à 8 iteraties gebruiken (voor 12 punten), maar waarschijnlijk is het gemiddelde aantal iteraties in de praktijk laag genoeg. Kwestie van uitproberen lijkt me.

[ Voor 71% gewijzigd door Soultaker op 04-11-2010 02:38 ]

[Verwijderd]

die snap ik niet.. als er n² mogelijkheden zijn, hoeveel kans is er dan dat je (zonder binaire search) al zo snel de goeie maximum lengte weet te kiezen?

wil ik toch even weten voor ik aan een binary search begin te coden

[ Voor 18% gewijzigd door Verwijderd op 04-11-2010 16:32 ]

[Soultaker]

Omdat je wél al de totale afstand minimaliseert, en zoals Knutselsmurf al aangaf, zit er wel enige correlatie tussen oplossingen met lage maximum- en lage totaalafstanden. Dat geldt zeker als je met uniform-random gedistribueerde punten begint, zoals in pedorus' test.

Daardoor kun je elke iteratie een aantal stappen overslaan, en alle onmogelijke stappen aan de onderkant sla je sowieso over (dat zijn er sowieso minstens n, bij verschillende lengtes tenminste).

[pedorus]

Even getest met

C#:

            var posMax = distances.OfType<double>().OrderBy(a => a).ToArray();

en

C#:

                Console.WriteLine(Array.BinarySearch(posMax, max));

Het blijkt dat het Hongaarse algoritme bepaalde mogelijke maxima simpelweg niet kiest. Je ziet dus dingen als:

111
108
75
74
61

Waarbij #61 dan het beste maximum oplevert.
Gemiddeld zijn er trouwens zo'n 4.4 iteraties nodig bij 11 punten (incl. de iteratie die geen oplossing meer oplevert).

Als n flink oploopt dan wordt binary search wel nuttig overigens. Er zijn bij 50 punten gemiddeld 13.4 iteraties nodig, terwijl binary search er 11-12 nodig heeft en minder variantie kent.

[Soultaker]

Ik wil zelfs beweren dat de variantie met binary search altijd <1 is.
edit: ≤¼ zelfs.

[ Voor 19% gewijzigd door Soultaker op 04-11-2010 17:13 ]

[pedorus]

Je kunt bij binary search natuurlijk van hetzelfde fenomeen gebruikmaken, door een tabelletje met ranks bij te houden en max te updaten na iedere geslaagde iteratie. De variantie loopt dan wel iets op.

[Verwijderd]

nou jongens, het lijkt allemaal te zijn geslaagd

aangezien de tijd idd erg mee lijkt te vallen (paar millisec, onmeetbaar eigenlijk) ben ik maar even te lui geweest voor die binaire search

als een verdediger naar voren trekt wisselt hij nu braaf rollen met een middenvelder wanneer het logisch lijkt lastig te debuggen of het echt perfect klopt, maar zo op het oog ziet het er allemaal geloofwaardig genoeg uit na een tijdje kijken.
/me zeer tevree

ik wil iedereen erg bedanken voor alle hulp en ideeen, en soultaker in het bijzonder!

/me biedt hem zijn ziel dan maar aan als dank