[All Languages]Alternatieve Programmeer Webstrijd

[Verwijderd]

Ik heb net de hele [All Language] Programmeer Webstrijd thread gelezen (Ja, duurde ff) en al heb ik bewondering voor hoe enthousiast sommige tweakers waren over het factoriseren van een getal van enkele honderden bits, toch kreeg ik het gevoel dat veel mensen die deel namen aan de discussie niet echt een gevoel hadden voor de complexiteit van zo'n probleem en een iets te hoge pet op hebben van de kracht van hun computertje.

Om een iets beter idee te krijgen van hoe complex bepaalde op het oog simpele problemem kunnen zijn bied ik het volgende probleem aan:

Bereken de korts mogelijke route door een een verzameling van 50 punten die random op een X-Y grid zijn geplaatst. Hierbij mag elk punt maar 1 keer worden bezocht. Verder moet het een gesloten route zijn, dwz het eindpunt van de route moet hetzelfde zijn als het begin punt. De afstand tussen twee punten is (heel voor de handliggend) de lengte van het lijnstuk dat de twee punten verbind (makkelijk te berekenen met Phytagoras).

Om er iets meer een wedstrijd van te maken is het misschien leuk als 1 persoon zo'n verzameling punten post en dat dan iedereen de korste route door die punten gaat berekenen. Er zijn dan in pricipe twee wedstrijden: 1 het eerste de optimale route vinden. 2 de beste route tot dan toe vinden. Uiteraard kan dit probleem benaderd worden met een gedistribueerde oplossing.

[rjsomeone]

49! mogelijk heden volgens mij...
Verder heb ik nu ff geen zin om er over na te denken, maar ook dit is wel een leuk idee.

(Is het vorige definitief van de baan oid)

[PrinsEdje80]

Dit het zogenaamde 'vertegenwoordigers-'/'handelaarsroute'-probleem.... Degene die de oplossing hiervoor vindt, kan zich melden bij de eerste de beste universiteit en krijgt een professor-stoel aangeboden

Ik heb wel eens gehoord dat de korste route te maken is door elke keer naar het dichtsbijzijnde punt te gaan... (kan geen referentie opgeven).

[Verwijderd]

Dit het zogenaamde 'vertegenwoordigers-'/'handelaarsroute'-probleem.... Degene die de oplossing hiervoor vindt, kan zich melden bij de eerste de beste universiteit en krijgt een professor-stoel aangeboden

Bijna, het is het Traveling Salesman Problem oftewel het Handelsreizigers Probleem. Als je hier een algemene polynomiale oplossing voor bedenkt ben je inderdaad een bikkel. Maar de probleem instantie die hierboven staat is denk ik best te doen, al vermoed ik wel dat het vinden van een optimale oplossing iets gedistribueerds zal vereisen.

Ik heb wel eens gehoord dat de korste route te maken is door elke keer naar het dichtsbijzijnde punt te gaan... (kan geen referentie opgeven).

Wat je voorstelt is een zogenaamde heuristiek en daar zijn er velen van. Degene die jij voorstelt is echter niet zo'n hele goeie.

[update]
Misschien is 50 toch wel een beetje hooggegrepen, even zien wat anderen er over te zeggen hebben, maar misschien kunnen we het beter proberen met 30 of 40, zeker als we van plan zijn om de echt korste route te gaan vinden.
[/update]

[tomato]

Hoe weet je dat je een (er kunnen er meer zijn) optimale route gevonden hebt?

[Verwijderd]

Tja, dat weet je idd alleen als je
1 Alle mogelijke routes hebt uitgeprobeerd.

of

2 Een upper- en lowerbound voor de oplossing hebt gedefineerd en deze twee op een of andere manier aan elkaar gelijk hebt kunnen krijgen.

Kortom: Het vinden van de optimale oplossing is meer iets voor de distributed mensen. Maar het vinden van een goede (de beste tot dan toe) oplossing kun je ook in je eentje met een slimme heuristiek. Dus, lol voor iedereen.

[Verwijderd]

Hmmm Het lijkt mij dat je dit met recursive calls moet gaan doen, en ik weet nu al dat je computer dit niet leuk gaat vinden.

Maar inderdaad is het een interessant verhaal. Je zult een functie moeten schrijven die iedere keer gaat kijken naar welk volgende punt hij kan, en met een bepaald getal bijhouden in welke volgorde hij de punten gaat doen.

Dat betekent dus met faculteiten gaan werken, er zijn 50! (faculteit ja) mogelijkheden om alle punten te gaan bezoeken. Dat is best wel veel

En dan nog moet je een soort van counter gebruiken om bij te houden in welke volgorde je de punten gaat volgen.
En wel zo dat je met een getal van 1 t/m 50! nooit een route dubbel doorloopt.

Dat betekent dus inderdaad het getal in de counter ontleden, en omzetten naar een binair getal, of wat anders, daar heb ik nog niet over nagedacht.

Dan komt dus het moeilijkste, en eigenlijk het probleem wat je beschrijft in de 1e post: schrijf daar maar eens een functie voor...

Je kunt natuurlijk heel simpel 50 loops nesten, maar ik vind dat geen nette oplossing. Ik denk dat het prima met 1 functie kan met een recursive call erin.

Vreet alleen geheugen...

[Janoz]

Op donderdag 08 november 2001 16:19 schreef Xalista het volgende:
...Als je hier een algemene polynomiale oplossing voor bedenkt ben je inderdaad een bikkel.....

Niet alleen een bikkel, maar heb je on the fly ook ff het P=NP probleem opgelost...

Waarschijnlijk is dit probleem pas fatsoenlijk op te lossen met quantum computers (die in theorie ideaal zijn voor nondeterministische problemen)...

Ik heb in Japan nog wel een keer een lecture bijgewoond over dit onderwerp. Daar had een knakker een redelijk goed werkend algoritme bedacht.

Waarom moeten we trouwens gebruik maken van Pythagoras? Manhattendistance werkt wat sneller, en het maakt uiteindelijk voor het algoritme niet zo veel uit..(wel voor de antwoorden)

[Verwijderd]

Op donderdag 08 november 2001 16:32 schreef tomato het volgende:
Hoe weet je dat je een (er kunnen er meer zijn) optimale route gevonden hebt?

Iedere keer de totale lengte berekenen, en vergelijken met een waarde in een stack. Als de lengte korter is moet je die in de stack douwen. En de route in een of andere variabele.

[edit]
Waarom ga ik in op jouw grapje

[tomato]

Cheatah: Iedere keer de totale lengte berekenen, en vergelijken met een waarde in een stack. Als de lengte korter is moet je die in de stack douwen. En de route in een of andere variabele.

[edit]
Waarom ga ik in op jouw grapje

Het was geen grapje maar een serieuze vraag. Een opdracht was als eerste de optimale route te vinden. Ik vraag mij dan af hoe de wedstrijdjurie gaat controleren of mijn route optimaal is.
Dat zie ik ze nog niet zomaar doen, je zult namelijk eerst de lengte van alle andere mogelijke routes moeten weten (nouja, kort door de bocht, er zijn truckjes om routes uit te sluiten).

En met die meerdere routes bedoelde ik dat er best meerdere optimale routes kunnen zijn (die dus exact even lang zijn).

[Janoz]

Op donderdag 08 november 2001 16:47 schreef Cheatah het volgende:
Hmmm Het lijkt mij dat je dit met recursive calls moet gaan doen, en ik weet nu al dat je computer dit niet leuk gaat vinden.

Maar inderdaad is het een interessant verhaal. Je zult een functie moeten schrijven die iedere keer gaat kijken naar welk volgende punt hij kan, en met een bepaald getal bijhouden in welke volgorde hij de punten gaat doen.

Dat betekent dus met faculteiten gaan werken, er zijn 50! (faculteit ja) mogelijkheden om alle punten te gaan bezoeken. Dat is best wel veel

En dan nog moet je een soort van counter gebruiken om bij te houden in welke volgorde je de punten gaat volgen.
En wel zo dat je met een getal van 1 t/m 50! nooit een route dubbel doorloopt.

Dat betekent dus inderdaad het getal in de counter ontleden, en omzetten naar een binair getal, of wat anders, daar heb ik nog niet over nagedacht.

Dan komt dus het moeilijkste, en eigenlijk het probleem wat je beschrijft in de 1e post: schrijf daar maar eens een functie voor...

Je kunt natuurlijk heel simpel 50 loops nesten, maar ik vind dat geen nette oplossing. Ik denk dat het prima met 1 functie kan met een recursive call erin.

Vreet alleen geheugen...

Nou, vergeet het maar... Op dit moment met de huidige computertechnieken (technieken dus, niet snelheid) kun je niks met dit soort oplossingen..

Bij kleine aantallen is het nog wel te doen.. Stel dat je de ideale oplossing voor 10 punten in 1 minuut vind, dan duurt het vervolgens
11 minuten voor 11
132 minuten voor 12
1716 minuten voor 13
24024 minuten voor 14
360360 minuten voor 15
en dan heb ik het nog niet eens over het geheugengebruik..

maw .. ALs je in die hoek een oplossing vindt, dan hoefen er maar een paar punten bij te komen en je algoritme is zinloos.

De oplossing moet meer gezocht worden in de hoek van bijvoorbeeld de genetische algoritmen..

[Janoz]

Op donderdag 08 november 2001 16:55 schreef tomato het volgende:

[..]

Het was geen grapje maar een serieuze vraag. Een opdracht was als eerste de optimale route te vinden. Ik vraag mij dan af hoe de wedstrijdjurie gaat controleren of mijn route optimaal is.
Dat zie ik ze nog niet zomaar doen, je zult namelijk eerst de lengte van alle andere mogelijke routes moeten weten (nouja, kort door de bocht, er zijn truckjes om routes uit te sluiten).

En met die meerdere routes bedoelde ik dat er best meerdere optimale routes kunnen zijn (die dus exact even lang zijn).

De jury heeft het makkelijk juist... Het voordeel van het traveling salesman probleem is dat een gevonden antwoord makkelijk te controleren is. OK, je kunt niet controleren of het echt de kortste is, maar wel wie de kortste geldige route heeft ingeleverd.

[edit]hmm.. mijn stelling gaat alleen op als de opdracht geintrepeteerd wordt als "Wie de allerkortste route uitrekend heeft gewonnen"

[edit2]ff mijn 1e edit op de juiste plek gezet

[Verwijderd]

Op donderdag 08 november 2001 16:55 schreef tomato het volgende:

Het was geen grapje maar een serieuze vraag. Een opdracht was als eerste de optimale route te vinden. Ik vraag mij dan af hoe de wedstrijdjurie gaat controleren of mijn route optimaal is.
Dat zie ik ze nog niet zomaar doen, je zult namelijk eerst de lengte van alle andere mogelijke routes moeten weten (nouja, kort door de bocht, er zijn truckjes om routes uit te sluiten).

En met die meerdere routes bedoelde ik dat er best meerdere optimale routes kunnen zijn (die dus exact even lang zijn).

Als je je programma wiskundig kunt onderbouwen met een strak bewijs, dan is het niet nodig om het te gaan controleren.

Ik ga er in ieder geval over denken, ik zit op dit moment te denken aan een 50 dimensionale matrix
Maar ik denk dat ik het eerst maar met 10 punten ga doen ofzo, ik verwacht niet dat ik dan getallen nodig heb van groter dan 10¹⁰.

Het zit er dik ik dat voor 50 punten een gigantische hoeveelheid processor power en geheugen nodig is.
Misschien zelfs een distributed.net probleem

[tomato]

Janoz: De jury heeft het makkelijk juist... Het voordeel van het traveling salesman probleem is dat een gevonden antwoord makkelijk te controleren is. OK, je kunt niet controleren of het echt de kortste is, maar wel wie de kortste geldige route heeft ingeleverd.

Even lezen
Ik had het dus over de kortste route (waar oorspronkelijk in het vraagstuk naar gevraagd werd).

[tomato]

Op donderdag 08 november 2001 17:01 schreef Cheatah het volgende:
Als je je programma wiskundig kunt onderbouwen met een strak bewijs, dan is het niet nodig om het te gaan controleren.

Dan ben ik erg benieuwd naar jouw wiskundig bewijs

[Verwijderd]

Op donderdag 08 november 2001 17:07 schreef tomato het volgende:

Dan ben ik erg benieuwd naar jouw wiskundig bewijs

Dat is ook het hele probleem: het programmeren is denk ik eenvoudiger dan het bewijs leveren.

[Verwijderd]

Niet alleen een bikkel, maar heb je on the fly ook ff het P=NP probleem opgelost...

Idd, en dat noem ik nou een bikkel

edit:

Dit geldt overigens alleen als het bepalen of een bepaalde route een kortst mogelijke route is, een NP-Compleet probleem is. Ik weet zo niet uit mijn hoofd of dat zo is. Jij wel?

[Tsjipmanz]

Op donderdag 08 november 2001 16:48 schreef Janoz het volgende:

[..]

Waarom moeten we trouwens gebruik maken van Pythagoras? Manhattendistance werkt wat sneller, en het maakt uiteindelijk voor het algoritme niet zo veel uit..(wel voor de antwoorden)

Leuk en aardig, Janoz, maar ik denk dat je als datastructuur voor dit probleem toch eerder een gewogen graaf gaat gebruiken (tenminste als je dit als een soort TSP ziet).

De preprocessing om de 50 punten en de afstanden in een bruikbare graaf te zetten zal een fractie zijn van de probleemoplossingstijd, of je nu Pythagoras gebruikt of Manhattan.

Of zie ik t nou weer eens verkeerd

[Verwijderd]

Waarom moeten we trouwens gebruik maken van Pythagoras? Manhattendistance werkt wat sneller, en het maakt uiteindelijk voor het algoritme niet zo veel uit..(wel voor de antwoorden)

Dit was alleen om aan te geven wat ik onder de afstand tussen twee punten versta. Bij een daadwerkelijk implementatie neem ik aan dat we een matrix met de afstanden gaan gebruiken. Deze matrix hoeven we dus maar 1 keer te berekenen, met whatever methode.

[Verwijderd]

Op donderdag 08 november 2001 17:23 schreef Xalista het volgende:

Dit was alleen om aan te geven wat ik onder de afstand tussen twee punten versta. Bij een daadwerkelijk implementatie neem ik aan dat we een matrix met de afstanden gaan gebruiken. Deze matrix hoeven we dus maar 1 keer te berekenen, met whatever methode.

Inderdaad een goede oplossing om de berekening zo snel mogelijk te houden. Er is slechts één matrix van 49 bij 49 hiervoor nodig. Een peuleschil vergeleken met het overig benodigde geheugen.

[Janoz]

Tsjipmanz
Reken eens uit hoeveel afstanden dat zijn

edit:
Oeps, denkfoutje.. Valt wel mee

.. Het lijkt me niet zo'n best idee om dit om te zetten naar een compleet verbonden graaf (alhoewel er wel een efficient triangulatie algoritme overheen gegooid kan worden, hierna edges gaan elimineren, en je komt waarschijnlijk el een heel eind..... * Janoz heeft al een ID Kom maar op met die punten!!!)


Xalista
Met een kleine aanpassing is het idd een NPC probleem (dan moet je als eis niet de kleinste, maar kleiner dan een vooraf ingestelde waarde nemen)

Tomato
Had ik al verbeterd toch

[Tsjipmanz]

Op donderdag 08 november 2001 17:30 schreef Janoz het volgende:
Tsjipmanz
Reken eens uit hoeveel afstanden dat zijn .. Het lijkt me niet zo'n best idee om dit om te zetten naar een compleet verbonden graaf (alhoewel er wel een efficient triangulatie algoritme overheen gegooid kan worden, hierna edges gaan elimineren, en je komt waarschijnlijk el een heel eind..... * Janoz heeft al een ID Kom maar op met die punten!!!)

Dat zijn vanuit punt:

1 : 49 afstanden (naar 2-50)
2 : 48 afstanden (naar 3-50)
[...]
49 : 1 afstand (naar 50)

In totaal dus 1+2+3+...+49 = 50*50/2= 1250 afstanden!

Foei Gijs

edit:
Toen ik begon te typen had je je denkfoutje nog niet neergezet lekker puh

[Verwijderd]

Ok, om ff te recapituleren.

Het vinden van de korste route is misschien toch niet zo'n leuke wedstrijd omdat het controleren of het de korste is net zo moeilijk is als het vinden ervan.

Je weet alleen zeker dat een oplossing de korste is als je alle mogelijkheden hebt uitgeprobeerd, of een met een wiskundig bewijs een upper- en een lowerbound hebt gedefineerd die aan elkaar gelijk zijn.

Vinden van de beste oplossing tot dan toe is wel een leuk (en makkelijk controleerbaar) probleem. Iedereen kan eraan mee doen: Die-hards met een distributed Bruteforce oplossing en slimmerikken met een handige heuristiek.

In pricipe komt hier niet al teveel super ingewikkeld programmeer werk bij kijken (voornamelijk array manipulatie) en dat maakt het probleem voor veel mensen toegankelijk.

Nogmaals, om er echt een wedstrijd van te maken moet iemand ff zeg 50 random punten posten. Met die punten kun je allerlei wedstrijden maken: b.v. de korste route door de eerste 20, 30, 40 of 50(voor de echte die hards) punten.

[Tsjipmanz]

Op donderdag 08 november 2001 17:34 schreef Xalista het volgende:

Nogmaals, om er echt een wedstrijd van te maken moet iemand ff zeg 50 random punten posten. Met die punten kun je allerlei wedstrijden maken: b.v. de korste route door de eerste 20, 30, 40 of 50(voor de echte die hards) punten.

Hoeveel punten het ook zijn, het gaat om het algoritme... ipv die-hards kan je misschien beter praten over mensen die een supercomputer in hun achtertuin hebben staan !

[Janoz]

Count me in (mits de tijd het toe laat) Mischien is er (als er veel mensen mee doen) ook wel een opsplitsing te maken in verschillende categorieën.. Brute force en trucjes.. Op die manier kunnen de brute forcers op 1 set gaan werken, terwijl de 'slimmerikken' op verschillende type datasets hun skills los kunnen laten..

[Verwijderd]

Op donderdag 08 november 2001 17:40 schreef Tsjipmanz het volgende:

[..]

Hoeveel punten het ook zijn, het gaat om het algoritme... ipv die-hards kan je misschien beter praten over mensen die een supercomputer in hun achtertuin hebben staan !

Bedenk een algoritme, deze hoeft niet daadwerkelijk uitgevoerd te worden, als je maar kunt zien dat het werkt.

Voor een daadwerkelijke berekening is een 10tal punten wel genoeg. Als het daarvoor geldt, dan geldt het ook voor 50 punten.

[edit]
*knip*

[Verwijderd]

Ok, hier zijn 50 punten in de range [0..50,0..50], maar die range doet er eigenlijk niet toe. Het gaat om de afstanden tussen de punten.

code:

06 05
49 30
42 23
33 06
02 32
36 20
35 19
13 29
22 34
18 41
23 49
05 26
12 24
18 45
21 03
44 33
50 08
31 10
37 26
02 46
35 08
23 44
45 36
18 27
30 32
01 09
05 23
19 39
30 50
43 48
24 37
40 10
31 26
46 12
48 31
27 24
36 03
39 37
04 06
34 40
01 34
15 30
36 15
11 39
29 19
25 03
13 11
30 00
36 07
35 22

Ik stel voor dat we deze punten nummeren van 0 t/m 49, in de volgorde zoals ze er nu staan. Je kunt dan een oplossing geven door de nummers 0 t/m 49 in een bepaalde volgorde te posten.

Zelf ga ik proberen met een brute force algoritme de kortste route door de eerste 20 punten te vinden. Daarna voeg ik me bij de groep 'slimmerikken' en ga proberen een zo kort mogelijke route te vinden door de eerste 30 punten. Daarna eventueel door 40 en 50 punten. Iedereen veel plezier en ik zie wel met welke oplossingen jullie komen.

[Verwijderd]

edit:

laat maar

[Verwijderd]

Xalista: oops

Plak jij je punten effe terug ?

[edit]

Ik doe brute-force, en zal ook de eerste 20 punten gebruiken.

[Verwijderd]

Voorlopig heb ik in Java dit ervan gebakken:

code:

public class Route
{
    public static void main(String[] args)
    {
        int match = 0;
        int[] sequence = new int[4];

        for (int a = 1; a <= 4; a++)
        {
            sequence[0] = a;
            match = 0;
            for (int x = 0; x < 0; x++)
            {
                if (sequence[x] == a) match++;
            }
            if (match == 0)
            {
                for (int b = 1; b <= 4; b++)
                {
                    sequence[1] = b;
                    match = 0;
                    for (int x = 0; x < 1; x++)
                    {
                        if (sequence[x] == b) match++;
                    }
                    if (match == 0)
                    {
                        for (int c = 1; c <= 4; c++)
                        {
                            sequence[2] = c;
                            match = 0;
                            for (int x = 0; x < 2; x++)
                            {
                                if (sequence[x] == c) match++;
                            }
                            if (match == 0)
                            {
                                for (int d = 1; d <= 4; d++)
                                {
                                    sequence[3] = d;
                                    match = 0;
                                    for (int x = 0; x < 3; x++)
                                    {
                                        if (sequence[x] == d) match++;
                                    }
                                    if (match == 0)
                                    {
                                        System.out.println(">" + sequence[0] + sequence[1] + sequence[2] + sequence[3]);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

Dit levert alle mogelijke combinaties van de volgorde van de cijfers 1 2 3 en 4.

Maar zoals ik al eerder zei is het bij grotere getallen ranzige code. Dit is heel goed door te zetten tot 50 cijfers, uiteindelijk krijg je iedere keer een array met alle 50 getallen erin, iedere keer in een andere volgorde.

Nu moet dit worden teruggebracht naar één functie met behulp van een recursive call.
Iets in de geest van het volgende:

code:

static void loop(int n)
{
    for (int a = 1; a <= 4; a++)
    {
        sequence[n] = a;
        match = 0;
        for (int x = 0; x < n; x++)
        {
            if (sequence[x] == a) match++;
        }
        if (match == 0)
        {
            if (n < 4)
            {
                loop(n+1);
            }
            else
            {
                System.out.println(">" + sequence[0] + sequence[1] + sequence[2] + sequence[3]);
            }
        }
    }
}

Het is me nog niet gelukt het aan het werk te krijgen.
De 'lelijke' versie werkt in ieder geval, in plaats van de System.out.println(); moet dan een berekening van de totale lengte van het af te leggen traject komen, en een vergelijking met de tot dan toe kortste afstand.

[Verwijderd]

Wow, dat is wel heel erg bruteforce.

Ik heb het iets subtieler aangepakt, een branch and bound methode.

Ik heb al wat resultaten, maar ik betwijfel of dit voor 20 punten te doen is.
Dit zijn (volgens mij) de korste afstanden van de routes door de eerste X punten. Ik moet m'n algoritme nog even aanpassen zodat ie ook de routes uitspugt waar de afstand voor geldt, maar dat komt nog.

<removed due to bug>

Zo, nu begint het echt tijd te kosten. Voor 20 punten zal het wel meerdere uren kosten. Eerst maar eens wat routes meeleveren.

[Verwijderd]

Op donderdag 08 november 2001 21:00 schreef Xalista het volgende:
Wow, dat is wel heel erg bruteforce.

Ik heb het iets subtieler aangepakt, een branch and bound methode.

Ik heb al wat resultaten, maar ik betwijfel of dit voor 20 punten te doen is.
Dit zijn (volgens mij) de korste afstanden van de routes door de eerste X punten. Ik moet m'n algoritme nog even aanpassen zodat ie ook de routes uitspugt waar de afstand voor geldt, maar dat komt nog.

In welke taal heb je dit geschreven?

En die branch en bound methode, weet je daarmee 100% zeker dat er niet meerderekortere mogelijkheden zijn?

[Verwijderd]

Op donderdag 08 november 2001 21:06 schreef Cheatah het volgende:

[..]

In welke taal heb je dit geschreven?

En die branch en bound methode, weet je daarmee 100% zeker dat er niet meerderekortere mogelijkheden zijn?

In Delphi. Die branch and bound methode geeft me de korste afstand. Het kan natuurlijk zijn dat er een aantal routes zijn met die afstand, maar er zal nooit een route zijn met een kortere afstand. O, btw ik heb een bug gevonden in m'n progje, dus negeer die resultaten van net maar ff.

[Verwijderd]

Ok, nu zijn de bugs eruit. Hier zijn mijn resultaten:

5 punten
Afstand: 130,490613243764
Duur: 00:00:00
Route: 0 3 2 1 4

10 punten
Afstand: 145,246759296736
Duur: 00:00:00
Route: 0 3 6 5 2 1 8 9 7 4

13 punten:
Afstand: 163,502651322452
Duur: 00:00:03
Route: 0 12 11 4 7 8 9 10 1 2 5 6 3

14 punten:
Afstand: 164,471794343377
Duur: 00:00:13
Route: 0 12 11 4 7 8 9 13 10 1 2 5 6 3

15 punten
Afstand: 164,955344732085
Duur: 00:00:32
Route: 0 14 3 6 5 2 1 10 13 9 8 7 4 11 12

17 punten
Afstand: 187,549937805454
Duur: 00:29:55
Route: 0 14 3 16 6 5 2 1 15 10 13 9 8 7 4 11 12

Het lijkt me dat 20 punten exact dus wel een beetje lang gaat duren. Ik schat ruim een week. Begin ik dus verder maar niet aan. Voor de fun ga ik morgen wel zitten stampen op 18 punten.

[Janoz]

Ik heb gister nog ff over het probleem nagedacht, en heb de complexiteit al kunnen terugbrengen van een 'faculteit'-complexiteit naar een exponentiele complexiteit.. En heb ook nog een bewijs bedacht dat je dan nog steeds de minimale route overhoud

[Verwijderd]

Leuke opdracht, count me in.

Ik zou er iedereen nog wel weer even op wijzen dat (zoals Cheetah al eerder gemeld heeft) de route weer moet eindigen op het eindpunt...

[Verwijderd]

Op vrijdag 09 november 2001 08:22 schreef Janoz het volgende:
Ik heb gister nog ff over het probleem nagedacht, en heb de complexiteit al kunnen terugbrengen van een 'faculteit'-complexiteit naar een exponentiele complexiteit.. En heb ook nog een bewijs bedacht dat je dan nog steeds de minimale route overhoud

Dat idee, en het bewijs, zou ik wel eens willen zien.

[Janoz]

Op vrijdag 09 november 2001 09:46 schreef Xalista het volgende:

[..]

Dat idee, en het bewijs, zou ik wel eens willen zien.

Ik heb het nog niet helemaal uitgewerkt, maar het maakt gebruik van het feit dat eindpunt=beginpunt, en dat alle punten in hetzelfde vlak liggen. Voor een route waarvoor geldt eindpunt =/= beginpunt gaat het niet op (Dus nee, ik heb niet het TSP opgelost )

Maar ja, een exponentiele complexiteit is ook nog erg zwaar

[Janoz]

Sorry, brak Got

Zit ik thuis een antwoord te posten krijg ik de hele tijd timeouts, kijk ik op de pagina staan ze er niet bij, probeer ik het nog een keer, zelfde effect..

Kijk nu weer eens, staat mijn reactie d'r tig keer in ... hmm .. lekker is dat (En nee, ik doe het niet om aan techposts te komen )

[Verwijderd]

Op vrijdag 09 november 2001 10:04 schreef Janoz het volgende:
Maakt gebruik van het feit beginpunt==eindpunt en dat alle punten in 1 vlak liggen... Het bewijs gaat niet op voor het TSP omdat dat niet een cycle is..

Huh? Volgens mij is het TSP wel een cykel (dwz. een gesloten wandeling door een graaf waarbij alle punten behalve het begin- en het eindpunt verschillend zijn), en zelfs een Hamilton-cykel (een cykel door alle punten van de graaf).

[Verwijderd]

Is er trouwens een vast beginpunt?

edit:

Lijkt me een beetje stom als een handelaar eerst de kortste route berekent en dan nog eerst naar het startpunt moet reizen voor ie begint

[Janoz]

Op vrijdag 09 november 2001 11:24 schreef fladder het volgende:
Is er trouwens een vast beginpunt?

edit:

Lijkt me een beetje stom als een handelaar eerst de kortste route berekent en dan nog eerst naar het startpunt moet reizen voor ie begint

Het is nu een cycle.. Dus het maakt niet uit bij welk punt je begint.

[Verwijderd]

Op vrijdag 09 november 2001 11:02 schreef mietje het volgende:

[..]

Huh? Volgens mij is het TSP wel een cykel (dwz. een gesloten wandeling door een graaf waarbij alle punten behalve het begin- en het eindpunt verschillend zijn), en zelfs een Hamilton-cykel (een cykel door alle punten van de graaf).

Idd.

BTW,
Voor de eerste 18 punten is de kortste nu ook bekend.

18 punten.
Afstand: 191,85930182215
Duur: 02:27:03
Route: 0 12 11 4 7 8 9 13 10 15 1 2 5 6 16 3 17 14

Ik schat dat 19 punten dus een uurtje of 15 gaat kosten. Ik zal em morgen vroeg eens laten beginnen, dan is ie tegen middernacht wel klaar

[Verwijderd]

Zijn er behalve Cheetah en ik eigenlijk nog mensen bezig met een oplossing?

Met een kick ass heuristiek kun je een goede route maken door 30-50 punten, en aangezien brute force op zoveel punten haast ondoenlijk is begint de wedstrijd dan pas echt goed.

[Verwijderd]

Op vrijdag 09 november 2001 12:36 schreef Xalista het volgende:
Zijn er behalve Cheetah en ik eigenlijk nog mensen bezig met een oplossing?

Ik zit op 20 punten te stampen, maar ik zit achter een p200 Als ik op m'n werk ben laat ik een servertje een weekend op 22 punten of zo stampen.

Met een kick ass heuristiek kun je een goede route maken door 30-50 punten, en aangezien brute force op zoveel punten haast ondoenlijk is begint de wedstrijd dan pas echt goed.

Ik gebruik ook een branch en bound en ik cap de bound door eerst een heuristiek toe te passen (weg van de kortste paden). Verder controlleer ik nog of ik geen symmerische oplossingen zit te berekenen (bv. wandeling 1 2 3 1 tov. 1 3 2 1).

[Verwijderd]

Op vrijdag 09 november 2001 12:47 schreef mietje het volgende:

[..]

Ik gebruik ook een branch en bound en ik cap de bound door eerst een heuristiek toe te passen (weg van de kortste paden). Verder controlleer ik nog of ik geen symmerische oplossingen zit te berekenen (bv. wandeling 1 2 3 1 tov. 1 3 2 1).

Dat eerste doe ik dus ook. Dat tweede is wel slim, ff kijken of ik dat er bij mij ook op een simpele manier in kan bouwen.

[Verwijderd]

Xalista: ik heb nog een ideetje wat jouw berekeningen gi-gan-tisch gaat verkorten

Ik ga er even aan schrijven

Dat betekent inderdaad dat ik van de brute-force methode afstap, en wat strategischer ga werken

[Verwijderd]

Da's goed, zolang je maar blijft vermelden of je gegarandeerd de kortst oplossing berekend of een goede benadering.

ff BTW, branch and bound is ook brute force hoor en het doet niks met de complexiteit van je programma. Door branch and bound wordt je programma hooguit een constante sneller, maar als die constante toevallig 10 is, is het voor een beperkt aantal punten toch nog interesant.

edit:

Oh, en het lijkt me voor zich spreken dat je methode geen gebruik mag maken van iemand anders' resultaten...
M.a.w. Je progje moet het ook doen op een andere verzameling punten.

[Tsjipmanz]

Ik ben benieuwd wanneer (en natuurlijk OF) Janoz' idee wordt uitgewerkt.

Had op zich ook wel even mee willen doen maar dan moet ik er weer tijd in steken en daar heb ik even geen zin in.
Ben benieuwd of er ook mensen zijn die genetische algoritmen gaan proberen...

[Verwijderd]

Op vrijdag 09 november 2001 13:58 schreef Xalista het volgende:
ff BTW, branch and bound is ook brute force hoor en het doet niks met de complexiteit van je programma. Door branch and bound wordt je programma hooguit een constante sneller, maar als die constante toevallig 10 is, is het voor een beperkt aantal punten toch nog interesant.

Als je nu eens een rij van bounds neemt zodat je voor elke stap in je algoritme een andere bound hebt. De grootste bound bereken je via relatief simpele heuritische algoritme. Dan heb je de bounds[n]. (n = aantal punten)
de bounds[n-1] = bounds[n] - de korste afstand tussen 2 punten. bounds[n-2] = bound[n]-de kortst mogelijke route tussen 3 punten enz.
voor bounds[n-x] kun je ook nemen bound[n]- x keer de korste afstand tussen twee punten dat is sneller te berekenen maar minder precies.
Als op deze manier de bounds gebruikt in plaats van eentje wordt de complexiteit wel degelijk minder

[Verwijderd]

Op vrijdag 09 november 2001 14:27 schreef borganism het volgende:

[..]

Als je nu eens een rij van bounds neemt zodat je voor elke stap in je algoritme een andere bound hebt. De grootste bound bereken je via relatief simpele heuritische algoritme. Dan heb je de bounds[n]. (n = aantal punten)
de bounds[n-1] = bounds[n] - de korste afstand tussen 2 punten. bounds[n-2] = bound[n]-de kortst mogelijke route tussen 3 punten enz.
voor bounds[n-x] kun je ook nemen bound[n]- x keer de korste afstand tussen twee punten dat is sneller te berekenen maar minder precies.
Als op deze manier de bounds gebruikt in plaats van eentje wordt de complexiteit wel degelijk minder

Teneerste, als je gelijk zou hebben, heb je zojuist bewezen dat P=NP. Dan zou ik als ik jou was gelijk wat je hierboven hebt uitgelegd uitprinten en bij een universiteit indienen. Je bent dan per direct gepromoveerd, en vervolgens kun je overal aan de slag als professor in de combinatorische optimalisatie.

Ten tweede, laat dat teneerste maar zitten, want je hebt geen gelijk. Je gaat ervan uit dat door het toevoegen van een punt aan een route de lengte groter moet worden, maar dat is niet zo. Als dat punt toevallig op de beste route zonder dat punt ligt blijft de lengte van je route gelijk. Kortom jij denkt dat je een bounds[n] array kunt maken dat "increasing" is, maar dat is niet zo. Helaas, maar goed geprobeerd, ik vond het een leuk idee.

[Verwijderd]

Ik heb een oplossing met lengte 311,90. Deze heb ik gekregen door de punten in groepen te verdelen [door te kijken welke punten dicht bij elkaar liggen]; aan elk van deze groepen met punten een beginpunt en een eindpunt te geven; hierna tussen begin- en eindpunt het optimale pad berekent; en tenslotte hiervan 1 pad door de alle punten gemaakt.

Ik ga nu nog effe kijken of ik door punten in het gevonden pad te switchen een betere oplossing kan krijgen...

[Verwijderd]

Op vrijdag 09 november 2001 16:11 schreef DiFool het volgende:
Ik heb een oplossing met lengte 311,90. Deze heb ik gekregen door de punten in groepen te verdelen [door te kijken welke punten dicht bij elkaar liggen]; aan elk van deze groepen met punten een beginpunt en een eindpunt te geven; hierna tussen begin- en eindpunt het optimale pad berekent; en tenslotte hiervan 1 pad door de alle punten gemaakt.

Ik ga nu nog effe kijken of ik door punten in het gevonden pad te switchen een betere oplossing kan krijgen...

Door hoeveel punten gaat je route?

[Verwijderd]

Op vrijdag 09 november 2001 16:25 schreef Xalista het volgende:

[..]

Door hoeveel punten gaat je route?

Allemaal

[Verwijderd]

Update: 310,11 -> 305,28

[Verwijderd]

Ik ben nu begonnen aan DE heuristiek voor het benaderen van TSP's, maar dat is nog best wat werk. Hopelijk heeft niemand dezelfde methode af voor mij

[jelmervos]

Ik heb de vorige 10 minuten ook even wat uitgeprobeerd, wel wat simpel:


Is het iets of ben ik weer es dom bezig?

[tomato]

jelmervos: Is het iets of ben ik weer es dom bezig?

Het is iig niet de kortste route, dat kun je direct al zien

[Verwijderd]

Op vrijdag 09 november 2001 21:25 schreef tomato het volgende:

[..]

Het is iig niet de kortste route, dat kun je direct al zien

Hoe zie jij dat

[Verwijderd]

Brute Force??????

[jelmervos]

Op vrijdag 09 november 2001 21:25 schreef tomato het volgende:

[..]

Het is iig niet de kortste route, dat kun je direct al zien

Kan wel, wat ik doe is dit:
Ik pak het eerste punt en zoek het punt wat het dichst bij ligt, daar gaat een lijn heen, dan de volgende, enz.

Lekker simpel dus, en daarom denk ik ook dat het niet echt klopt, dus dat er betere zijn.

[Verwijderd]

jelmervos: Misschien ben ik scheel maar waar zijn de punten (5, 23) en (5, 26) in jouw tekening; en waar is positie (0, 0), links-boven?

[tomato]

DiFool: Misschien ben ik scheel maar waar zijn de punten (5, 23) en (5, 26) in jouw tekening; en waar is positie (0, 0), links-boven?

Hij genereert eerst zelf steeds een reeks punten en gebruikt dus niet de hier gegeven reeks.

[tomato]

dev: Hoe zie jij dat

Heel simpel, ik zie stukjes in zijn route (bijvoorbeeld linksonder) waar je het 'draadje' langs kunt leggen op een kortere manier
Als een deel van de route te optimaliseren is, is de totale route dus ook niet optimaal. Maar als je zulke stukjes niet meer 1 2 3 ziet in het plaatje wil dat nog niet zeggen dat het wel de optimale route is.

[The - DDD]

Dit is een probleem wat erom vraagt om in een boom gezet te worden.

Eerst verbind je alle punten met alle punten. Voilla, je basis boom. (spagetti zooitje)

Vervolgens ga je daar alsmaar padden uit weg srepen op een slimme manier en zodoende hou je uiteindelijk met een ACCEPTABELE REKENTIJD een redelijk geoptimaliseerde route over. Afhankelijk van je algoritme kun je ervoor zorgen dat je een beter resultaat hebt tegenover de rekentijd.

Hoe het werkt?

Een mogelijke oplossing zou zijn om alsmaar van ieder punt 1 route weg te strepen. Welke? De langste natuurlijk. Net zolang totdat alle punten nog maar 1 in en 1 uit route heeft. (op je begin en eindpunt na dan, tenzij dit hetzelfde punt is)

Uiteraard hoe beter je dit algoritme implementeert hoe beter. Een eerste verbetering zou al zijn om te beginnen bij de punten die de meeste verbindingen hebben. Of alle gekruisde routes eerst filteren, Kruisingen geven namelijk aan dat er iets niet oged is gegaan.

Wat je eigenlijk wil bereiken is een depth first tree met indien mogelijk slechts 1 draad van begin tot eind over de korste paden die mogelijk zijn.

Conceptueel en op papier heel makkelijk te bedenken en uit te voeren, maar doe het nu maar is in code. *uche* Moet wel te doen zijn, is ook geen probleem. Enige nadeel is dat het behoorlijk rekenintensief is. En dat de allerbeste oplossing gewoon teveel rekentijd vergt om in de praktijk toepasbaar te zijn. Je wil namelijk wel hebben dat de volgende ochtend er een route klaarligt voor AL je vertegenwoordigers en niet een paar perfecte voor een deel van je buitendienst. Daarnaast zijn er ook nog de volgende problemen in de praktijk: is afstand in kilometers wel de beste maatstaaf. Ok nemen we reistijd. Ligt die vast met de verkeersellende van tegenwoordig.... Hmmm, lastig.

Het zou bijvoorbeeld kunnen dat het effectiever blijkt te zijn in de praktijk om eerst dicht bij huis te beginnen, vervolgens (na de ochtend-spits) de punten op grote afstand te doen om vervolgens (voor de avond-spits) dicht bij huis nog wat afspraken af te lopen.

Oh ja, in m'n derde jaars stage ben ik hier mee bezig geweest. Alhoewel het toen zo was dat er al een bestaande route was die vervolgens aangepast moest worden met 1 voor 1 binnenkomende afspraken. En de geplande tijden voor de afspraken mochten niet gewijzigd worden. M.a.w.: Hoofdbrekens misselijkmakend moeilijk om op te lossen. Maar het was wel erg leuk om te zien dat het uiteindelijk wel werkte tijdens mijn eindpresentatie (dankzij de op voorhand nauwkeurig bepaalde en geteste afspraken set). Weet de stage mentor van school veel. Het bedrijf was op de hoogte van deze problematiek en was onder de indruk van de inzichten die ik ze heb kunnen verschaffen.

Ik zie dat ik al weer een veeeeel te lang verhaal getyped heb. Tijd om een slaapje te doen lijkt me...

[jelmervos]

Cool zo'n uitleg, volgen er meer?
Is namelijk intressant om te lezen.

[tomato]

The - DDD: Een mogelijke oplossing zou zijn om alsmaar van ieder punt 1 route weg te strepen. Welke? De langste natuurlijk. Net zolang totdat alle punten nog maar 1 in en 1 uit route heeft. (op je begin en eindpunt na dan, tenzij dit hetzelfde punt is)

Denk je er wel aan dat je een gesloten route moet hebben? Dus 8 korte routes die los liggen daar heb je niets aan

En begin- en eindpunt zijn dezelfde, dat was gegeven.

[Verwijderd]

Ik heb jullie discussie gelezen. Ik vraag me af of jullie toevallig een algoritme weten waarmee je binnen redelijke tijd zowel een graaf als een kortste route kan maken. Hierbij maak je dus eerder de graaf uit de kortste route dan de korste route uit de kortste graaf. De graaf hoeft slechts te worden gegeven door een afstandenmatrix met gehele getallen; het hoeft dus geen representatie hebben als een vlak met alle punten erop. In werkelijkheid is het trouwens toch ook zo dat de korste weg niet hemelsbreed is. Met dit algoritme kan je dus wél een graaf opgeven als jury waar jij een optimale route voor weet. En ik vind hem ook wel een leuke vervanging voor priemfactorisatie in public/private key encryptie. Dat is namelijk het onderwerp van mijn profielwerkstuk. Ik zoek namelijk snelle generatoren voor input van (voorlopige) NP-problemen bij gegeven output, die echter niet makkelijk te hacken is omdat de generator niet willekeurig genoeg is. Heeft iemand van jullie een idee (een ander NP-probleem is ook welkom)? Alvast bedankt!

[Verwijderd]

Op zaterdag 10 november 2001 00:09 schreef tomato het volgende:

[..]

Heel simpel, ik zie stukjes in zijn route (bijvoorbeeld linksonder) waar je het 'draadje' langs kunt leggen op een kortere manier
Als een deel van de route te optimaliseren is, is de totale route dus ook niet optimaal. Maar als je zulke stukjes niet meer 1 2 3 ziet in het plaatje wil dat nog niet zeggen dat het wel de optimale route is.

Nu zie ik het ook, was niet helemaal wakker

[Verwijderd]

Zelf heb ik als stage opdracht een heuristische zoekmethode moeten implementeren voor een Dial-a-Ride Probleem met meerdere voertuigen, multiple capacities en time windows. Dit probleem is nog veel complexer dan het TSP.

Omdat een aantal mensen het leuk vinden om te lezen zal ik hier een van de methoden bespreken (in het kort) die ik heb gebruikt.

De methode heet Simulated Annealing. Simulated annealing gaat uit van een willekeurige route door de punten. Vervolgens wordt er héél vaak (en daar ligt de kracht van deze methode) een hele kleine verandering in de route aangebracht. Zo'n verandering kan van alles zijn, b.v. het verplaatsen van een willekeurig punt binnen de route. Als die kleine verandering tot een kortere route leidt accepteer je hem altijd. Als de verandering tot een slechtere route leidt accepteer je hem met een bepaalde kans. Als je een verandering niet accepteerd moet je hem ongedaan maken. De kans is in het begin heel groot en wordt naarmate het proces (het simuleren) vorderd steeds kleiner. Dit zou je kunnen vergelijken met het bevriezen van een vloeistof of het condenseren van een gas, vandaar de naam Simulated Annealing. De reden om soms ook verslechterende veranderingen te accepteren is om uit lokale minima te kunnen komen. Een lokaal minimum is een route waarbij elke kleine verandering leidt tot een slechtere route terwijl het best kan zijn dat je met een iets grotere verandering een nog véél betere route kunt vinden. Als je dan nooit een slechtere route accepteerd kom je nooit uit dit lokale minimum, en vind je nooit de beste route.

Zo, als iemand dit implementeerd en hij kiest een paar leuke kleine veranderingen kan ie wel eens recordhouder worden bij problemen met heel veel punten (> 1000 bv)

Gesnapt?

[Verwijderd]

Op zaterdag 10 november 2001 00:49 schreef The - DDD het volgende:
Dit is een probleem wat erom vraagt om in een boom gezet te worden.

[..]

Volgens mij probeer je hier uit te leggen dat je een minimaal opspannende boom door je punten moet maken en daaruit een route destileren. Dit is een bekende methode en het voordeel ervan is dat je gegarandeerd een route krijgt die maximaal 2 keer zo lang is als de optimale route.

Er zijn echter methodes die welliswaar niet zo'n worstcase garantie hebben, maar wel een (veel) betere avarage case behaviour. Er zijn methodes die "on avarage" routes produceren die maar 1,04 keer zo lang zijn als de optimale route.

[Verwijderd]

Mijn oplossing/idee:

Brute-force trek ik (maar vooral mijn peeceetje) niet.
Dus ik ga het op een andere manier oplossen.
De oplossing die ik gekozen heb is gebaseerd op wat kleine
testjes en de paden die op het beeldscherm zag verschijnen.

Stap 1)
Ik zag allemaal 'ronde' vormen voor de kortste route
verschijnen. Op zich logisch, omdat het een gesloten route
is. M.a.w. mijn eerste stap is om de punten te sorteren in
graden.
Bereken hiervoor het middelpunt van alle punten en
bereken voor elk punt de graden t.o.v. dit middelpunt en
sorteer deze...

Stap 2)
Je zal een route zien die soms van binnen naar buiten en
weer naar binnen gaat. Dit is natuurlijk niet snel.
M.a.w. probeer elke punt een andere plaats in de lijst te
geven en kijk of de route korter wordt...

En toen was er geen Stap 3
Tis niet de kortste route, maar zoals de tekening hieronder
toont, heb ik een vrij korte route berekent in 1,27 seconde.

[Verwijderd]

Ik zit nog steeds brute force te klooien Ik heb overigens wel een algoritme dat een stuk sneller is nu. (10 minuten voor 17 punten op een p200). Leuke is dat er nu geen heuristiek meer in het algoritme zit; ik sorteer alle punten op onderlinge afstand, en loop tijdens de recursie de punten van kleinste tot grootste afstand door (hierbij kun je nog steeds op symmetrie testen). Verder bound ik nog wat eerder door bij de actuele route de kleinste afstand tot het startpunt (0) op te tellen.

[jelmervos]

Brute force is 30414093201713400000000000000000000000000000000000000000000000000 mogelijkheden testen!

[The - DDD]

Op zaterdag 10 november 2001 12:30 schreef Xalista het volgende:

[..]

Volgens mij probeer je hier uit te leggen dat je een minimaal opspannende boom door je punten moet maken en daaruit een route destileren. Dit is een bekende methode en het voordeel ervan is dat je gegarandeerd een route krijgt die maximaal 2 keer zo lang is als de optimale route.

Er zijn echter methodes die welliswaar niet zo'n worstcase garantie hebben, maar wel een (veel) betere avarage case behaviour. Er zijn methodes die "on avarage" routes produceren die maar 1,04 keer zo lang zijn als de optimale route.

Ik heb het ook niet zelf getest

Ik denk zowiezo dat de beste methode een vorm van heuristiek zal zijn. Bijvoorbeeld eerst dicht bij elkaar liggende punten bewerken en een goede route voor maken. En dan de zo verkregen "eilandjes" weer zo optimaal mogelijk proberen te verbinden.

Of een aantal willekeurige locaties kiezen met als voorwaarde dat ze neit te dicht bij elkaar liggen en van daaruit gaan zoeken. Opties opties opties.

[Verwijderd]

Op zaterdag 10 november 2001 15:37 schreef jelmervos het volgende:
Brute force is 30414093201713400000000000000000000000000000000000000000000000000 mogelijkheden testen!

Wat knap dat jij weet hoeveel mogelijkheden ik test zonder mijn algoritme te kennnen (Je hoeft met een branch en bound niet alle mogelijkheden te testen.) Ik snap natuurlijk dat brute force niet haalbaar is met 50 punten, het gaat me erom dat brute force algoritme zo "slim" mogelijk te maken terwijl ik toch nog gegarandeerd de optimale oplossing vindt. Als je met met heuristieken werkt kun geen enkele garantie geven dat je oplossing ook optimaal is.

(Indicatie: 50 minuten voor 18 punten; ter vergelijking met de tijden die Xalista post, die waarschijnlijk een zwaardere pc heeft dan een 200Mhz pentium.)

[Verwijderd]

Op zaterdag 10 november 2001 16:51 schreef mietje het volgende:

[..]

Wat knap dat jij weet hoeveel mogelijkheden ik test zonder mijn algoritme te kennnen (Je hoeft met een branch en bound niet alle mogelijkheden te testen.) Ik snap natuurlijk dat brute force niet haalbaar is met 50 punten, het gaat me erom dat brute force algoritme zo "slim" mogelijk te maken terwijl ik toch nog gegarandeerd de optimale oplossing vindt. Als je met met heuristieken werkt kun geen enkele garantie geven dat je oplossing ook optimaal is. Post ook eens wat resultaten (lengtes en routes)

(Indicatie: 50 minuten voor 18 punten; ter vergelijking met de tijden die Xalista post, die waarschijnlijk een zwaardere pc heeft dan een 200Mhz pentium.)

Da's zeker verrekte rap! Ik heb dan ook echt alleen maar een standaard brach and bound geïmplementeerd. Ik neem aan dat jij wel dezelfde resultaten krijgt als ik voor de aantalen die ik heb berekend. Ik zou best wat meer van je algoritme willen zien. Eventueel code. Je bent zeker in C bezig.

[Verwijderd]

Op zaterdag 10 november 2001 18:08 schreef Xalista het volgende:
Da's zeker verrekte rap! Ik heb dan ook echt alleen maar een standaard brach and bound geïmplementeerd. Ik neem aan dat jij wel dezelfde resultaten krijgt als ik voor de aantalen die ik heb berekend. Ik zou best wat meer van je algoritme willen zien. Eventueel code. Je bent zeker in C bezig.

Ik krijg natuurlijk de zelfde resultaten De code is nu 344 regels C++, ik weet niet of dat niet teveel van het goede is; als het geen probleem is post ik hem wel. (Ik zit er nog aan te optimizen, ik haal nu 39 minuten voor 18 punten.)

[Verwijderd]

Ben ook eens aan het proberen geslagen, gebruik makend van de 'naaste buur' methode heb ik een route gevonden van 343.814007209701 lang.
Deze methode is natuurlijk niet het optimaalst maar wel lekker snel
Ga vannacht nog wat verder klooien.

CoDeR Uit!

[Verwijderd]

Op zaterdag 10 november 2001 21:57 schreef CoDeR het volgende:
Ben ook eens aan het proberen geslagen, gebruik makend van de 'naaste buur' methode heb ik een route gevonden van 343.814007209701 lang.
Deze methode is natuurlijk niet het optimaalst maar wel lekker snel
Ga vannacht nog wat verder klooien.

CoDeR Uit!

[afbeelding]

Alle respect hoor, maar dat lijkt dus nergens op

Twee snijdende lijnen moet niet kunnen, dat is altijd een omweg namelijk.

[Janoz]

(Ik moet ook maar ff van me laten horen)

Ik ben al ff bezig geweest met mijn programma, maar ik moet nog allerlei graven datastructuren en algoritmes implementeren. Mijn werkwijze komt ongeveer overeen met wat DDD eerder ook al gepost heeft.

Om het van een facultatieve complexiteit terug te brengen naar een exponentiele gebruik ik een Delaunay triangulatie. Ik heb een bewijs bedacht (nog niet helemaal uitgewerkt) dat de ideale oplossing een subset van de edges is die wordt gegenereerd door die Delaunay triangulatie. Bij dat bewijs maak ik gebruik van het feit dat bij kruisende edges altijd een betere oplossing te vinden is. Daarnaast is mbv Euler te bewijzen dat (bij 50 punten) door de triangulatie van de 50! mogelijke edges slechts 98 over blijven.

Omdat een exponentieel algoritme natuurlijk nog steeds niet optimaal is ben ik nog aan het nadenken over de manier om hieruit een kleine route te krijgen.

(hoofdrekenfouten en denkfouten voorbehouden, ik ben namelijk niet helemaal zeker van de 98... Feit blijft dat de complexiteit naar beneden schiet )

[edit] Nog ff gerekend, het moeten er geen 98, maar 148 zijn.. het blijft iig recht evenredig met het aantal vertices, waardoor mijn beweringen nog wel kloppen)

[Verwijderd]

Ik post ook nog maar een resultaatje De kortst mogelijke route over de eerste 19 punten:

code:

 0             0
14  15.1327459504216
17  27.3393015661553
 3  31.8114375211548
16  48.9286802897785
 6  67.5297555275168
 5  68.9439690898899
18  75.0267316201881
 2  80.8576835150334
 1  90.7571784516451
15  96.5881303464904
10  122.988887911379
13  129.392012148811
 9  133.392012148811
 8   141.45426989711
 7  151.749900038097
 4  163.151654289088
11  169.859858221588
12  177.139968110868
 0  197.064826956039

Tijd:   0/04:25:44.270

Is er nog belangstelling voor m'n code?

[Verwijderd]

Op zondag 11 november 2001 00:34 schreef mietje het volgende:
Ik post ook nog maar een resultaatje De kortst mogelijke route over de eerste 19 punten:

code:

 0             0
14  15.1327459504216
17  27.3393015661553
 3  31.8114375211548
16  48.9286802897785
 6  67.5297555275168
 5  68.9439690898899
18  75.0267316201881
 2  80.8576835150334
 1  90.7571784516451
15  96.5881303464904
10  122.988887911379
13  129.392012148811
 9  133.392012148811
 8   141.45426989711
 7  151.749900038097
 4  163.151654289088
11  169.859858221588
12  177.139968110868
 0  197.064826956039

Tijd:   0/04:25:44.270

Is er nog belangstelling voor m'n code?

Ik heb wel belangstelling, kun je een link posten, 344 regels is wel een beetje teveel van het goede...

[Verwijderd]

Op zaterdag 10 november 2001 15:14 schreef mietje het volgende:
Ik zit nog steeds brute force te klooien Ik heb overigens wel een algoritme dat een stuk sneller is nu. (10 minuten voor 17 punten op een p200). Leuke is dat er nu geen heuristiek meer in het algoritme zit; ik sorteer alle punten op onderlinge afstand, en loop tijdens de recursie de punten van kleinste tot grootste afstand door (hierbij kun je nog steeds op symmetrie testen). Verder bound ik nog wat eerder door bij de actuele route de kleinste afstand tot het startpunt (0) op te tellen.

Dat ik daar niet op ben gekomen zeg, dat laatste van die afstand naar het startpunt bedoel ik. Briliant (vandaar dat ik het raar vind dat ik er zelf niet op ben gekomen ) Door dit ff toe te voegen (letterlijk het toevoegen van een halve regel code) ging bij mij de tijd om de beste route door 17 punten te vinden omlaag van 00:29:55 naar 00:01:23 !!!!
FF ter vergelijking, ik werk op een een Celeron 633@790 Mhz.

Mijn zooitje staat in 158 regels Delphi, incl. GUI (Die welliswaar echt geen ruk voorsteld)

[Verwijderd]

Kan een van de brute forcers deze lijst controleren? t/m 19 heb ik ze kunnen controleren met de resultaten van Xalista en Mietje, Mocht het kloppen dan heb ik 'n heeeeel snel algoritme (ik reken er niet op want hij heeft hier z'n nukken al maar hopen mag toch?! )

code:

14:0 12 11 4 7 8 9 13 10 1 2 5 6 3  Distance: 164.471794462532780
15:0 14 3 6 5 2 1 10 13 9 8 7 4 11 12  Distance: 164.955345117594760
16:0 14 3 6 5 2 1 15 10 13 9 8 7 4 11 12  Distance: 164.984570201119000
17:0 14 3 16 6 5 2 1 15 10 13 9 8 7 4 11 12  Distance: 187.549941769515040
18:0 14 17 3 16 6 5 2 1 15 10 13 9 8 7 4 11 12  Distance: 191.859316463395370
19:0 14 17 3 16 6 5 18 2 1 15 10 13 9 8 7 4 11 12  Distance: 197.064826956039500
20:0 14 17 3 16 6 5 18 2 1 15 10 13 9 8 7 19 4 11 12  Distance: 219.911529436364700
21:0 14 17 3 20 16 6 5 18 2 1 15 10 13 9 8 7 19 4 11 12  Distance: 220.622713792487190
22:0 14 17 3 20 16 6 5 18 2 1 15 21 10 13 9 8 7 19 4 11 12  Distance: 222.928495409858410
23:0 14 17 3 20 16 6 5 18 2 1 15 22 21 10 13 9 8 7 19 4 11 12  Distance: 225.793633709206660
24:0 14 17 3 20 16 6 5 18 2 1 15 22 21 10 13 9 8 23 7 19 4 11 12  Distance: 228.945426123652740
25:0 14 17 3 20 16 6 5 18 2 1 15 22 24 21 10 13 9 8 23 7 19 4 11 12  Distance: 234.952644987923320

[Verwijderd]

Op zondag 11 november 2001 15:03 schreef Xalista het volgende:
Ik heb wel belangstelling, kun je een link posten, 344 regels is wel een beetje teveel van het goede...

Ok, je kunt hem vinden op http://www.xs4all.nl/~guyvago/got/handel.c (Waarschuwing: bijna 500 regels slecht ontworpen C++ zonder commentaar)

Dit is trouwens een nog geavanceerdere versie (18 punten in 8 minuten op mijn p200). Deze keer ga ik er ook nog van uit dat ik tijdens het brute forcen geen kruisende wandelingen mag veroorzaken. Dit kost wel nogal wat geheugen in mijn implementatie, maar dat ligt vooral er aan hoe de STL std::bit_vector geimplementeerd is, daar sla ik bits in op die aangeven of alle (n * (n-1) / 2) * ((n-2) * (n-3) / 2) mogelijke variaties van lijnen tussen punten elkaar kruisen.

Ik zit nog te klooien met het algoritme dat het kruisen van twee lijnstukken bepaalt, ik weet niet zeker of dat correct is en heb geen zin vectorclasses te gaan schrijven.

Op zondag 11 november 2001 15:14 schreef Xalista het volgende:
Dat ik daar niet op ben gekomen zeg, dat laatste van die afstand naar het startpunt bedoel ik. Briliant

/me bloost

Mijn zooitje staat in 158 regels Delphi, incl. GUI (Die welliswaar echt geen ruk voorsteld)

Die versie die ik boven link is nu 460 regels, puur console.

[Verwijderd]

Op zondag 11 november 2001 16:28 schreef Yarvieh het volgende:
Kan een van de brute forcers deze lijst controleren? t/m 19 heb ik ze kunnen controleren met de resultaten van Xalista en Mietje, Mocht het kloppen dan heb ik 'n heeeeel snel algoritme (ik reken er niet op want hij heeft hier z'n nukken al maar hopen mag toch?! )

code:

[..]

Ik ben welliswaar geen bruteforcer meer, maar ik kan je wel vertellen dat je algoritme niet exact is. (Wat je zelf ook al verwachte)
Ik heb met m'n eigen benaderings algoritme namelijk een route door 20 punten gevonden die korter is dan die van jouw.
Route door 20 punten.
Afstand: 212,859702849706
Duur: 00:00:00 (Tja, benaderen gaat wel ietsjes sneller dan exact )
Route: 10 13 9 8 6 5 18 15 1 2 16 3 17 14 0 12 7 11 4 19

Het algoritme waar ik nu mee bezig ben is in de praktijk één van de beste benaderings algoritmes voor het TSP. Maar ik weet uit m'n hoofd niet precies hoe het werkt, dus werkt mijn implementatie ervan ook niet helemaal goed. Hij vindt nu wel goeie oplossingen, maar ook nog veel te vaak een hele slechte oplossing. Als ik hem goed krijg zal ik jullie vertellen welk algoritme het betreft en zal ik er iets over vertellen. Interesting Stuff

[Verwijderd]

Op maandag 12 november 2001 12:29 schreef Xalista het volgende:
Route door 20 punten.
Afstand: 212,859702849706
Duur: 00:00:00 (Tja, benaderen gaat wel ietsjes sneller dan exact )
Route: 10 13 9 8 6 5 18 15 1 2 16 3 17 14 0 12 7 11 4 19

Dit is ook niet de best mogelijke route Ik heb nog een bugje uit m'n brute-forcer gehaald en hem eens op 20 punten losgelaten:

code:

 0             0
14  15.1327459504216
17  27.3393015661553
 3  31.8114375211548
16  48.9286802897785
 6  67.5297555275168
 5  68.9439690898899
 2  75.6521730223893
 1  85.5516679590009
15  91.3826198538462
18  101.282114790458
 8  118.282114790458
 9  126.344372538756
13  130.344372538756
10  136.747496776189
19  157.960700211786
 4  171.960700211786
11  178.668904144285
 7  187.212907889603
12  192.311927403195
 0  212.236786248367

Tijd:   0/00:32:39.960

[Verwijderd]

Op maandag 12 november 2001 16:38 schreef mietje het volgende:

[..]

Dit is ook niet de best mogelijke route Ik heb nog een bugje uit m'n brute-forcer gehaald en hem eens op 20 punten losgelaten:

code:

 0             0
14  15.1327459504216
17  27.3393015661553
 3  31.8114375211548
16  48.9286802897785
 6  67.5297555275168
 5  68.9439690898899
 2  75.6521730223893
 1  85.5516679590009
15  91.3826198538462
18  101.282114790458
 8  118.282114790458
 9  126.344372538756
13  130.344372538756
10  136.747496776189
19  157.960700211786
 4  171.960700211786
11  178.668904144285
 7  187.212907889603
12  192.311927403195
 0  212.236786248367

Tijd:   0/00:32:39.960

Chapeau!
Maar ik zie op internet implementaties die echt schandalig snel zijn. Moet je hier eens kijken. Die java applet heeft een knop die in een flits de optimale route door 25 punten uitrekent.

Ik ben de hele dag een beetje bezig geweest om mijn benaderings algoritme aan de gang te krijgen, maar dat is dus echt voor geen meter gelukt . Toch maar eerst ff opzoeken hoe dat algoritme nou echt werkt. Dat wordt dus morgen.

[Twilight Burn]

Ik ben ook maar eens begonnen, met een benader-algoritme, en kom op de volgende antwoorden uit:

10: 164,263073914482
15: 170,045298403029
16: 170,281936670863
17: 224,52893545121
18: 215,73855651718
19: 203,384677221841
20: 225,899021602838
25: 276,576176803398
30: 309,156097175675
50: 317,940488421684

Zoals je kunt zien is het niet perfect (kijk maar eens naar de uitkomst van 19, en vergelijk deze met die van 17 en 18)
maar geeft hij soms toch best goede benaderingen

Zouden anderen die ook met een benaderings-methode bezig zijn hun resultaten kunnen posten?

edit:

Mijn route voor 50:
0 14 45 47 36 3 17 20 48 31 16 33 42 6 5 49 44 35 32 18 2 1 34 15 22 37 24 39 29 28 10 21 13 9 27 30 8 43 19 40 4 11 26 7 41 23 12 46 25 38
en een screenie:

[Verwijderd]

Plaatje, lengte 305,28, alleen begin is anders:

[Verwijderd]

Ik kan helaas geen sjieke schermpjes posten, maar wel optimale resultaten

21 punten:

code:

 0             0
14  15.1327459504216
17  27.3393015661553
 3  31.8114375211548
20   34.639864645901
16   49.639864645901
 6  68.2409398836393
 5  69.6551534460124
 2  76.3633573785118
 1  86.2628523151234
15  92.0938042099687
18   101.99329914658
 8   118.99329914658
 9  127.055556894879
13  131.055556894879
10  137.458681132312
19  158.671884567908
 4  172.671884567908
11  179.380088500408
 7  187.924092245725
12  193.023111759318
 0  212.947970604489

Tijd:   0/00:24:57.112

(Ik ben overgestapt naar de server op het werk, en het zit er naar uit dat ik tot 25 punten wel in redelijke tijd berekenen kan.)

[StarLite]

Op dinsdag 13 november 2001 09:49 schreef mietje het volgende:
Tijd: 0/00:24:57.112[/code]
(Ik ben overgestapt naar de server op het werk, en het zit er naar uit dat ik tot 25 punten wel in redelijke tijd berekenen kan.)

Goh.. Waarom is de fileserver nou toch zo traag¿ en het downloaden schiet ook al voor geen meter op

[Verwijderd]

Op dinsdag 13 november 2001 00:23 schreef DiFool het volgende:
Plaatje, lengte 305,28, alleen begin is anders:

[afbeelding]

Ziet er goed uit. Ik ben benieuwd of iemand nog lager komt

[The - DDD]

Op maandag 12 november 2001 17:18 schreef Xalista het volgende:

[..]
Maar ik zie op internet implementaties die echt schandalig snel zijn. Moet je hier eens kijken. Die java applet heeft een knop die in een flits de optimale route door 25 punten uitrekent.
[..]

Wat was ook alweer een goeie java decompiler?

[goalgetter]

Die rekent niet de optimale route uit, maar zoals eronder staat een redelijke route die gebaseerd is op het nearest neighbour principe. Excuus, niet vergenoeg naar beneneden gescrolled Inderdaad smerig snel die oplossing.

[Twilight Burn]

Op dinsdag 13 november 2001 19:51 schreef dev het volgende:

[..]

Ziet er goed uit. Ik ben benieuwd of iemand nog lager komt

Ik heb mijn "algoritme" (tis niet echt een algoritme, maar een zooitje van verschillende loops die met een bepaalde volgorde worden uitgevoerd) wat geoptimaliseerd en kom nu op dezelfde route uit, en ook na handmatig proberen te optimaliseren kom ik niet op een kortere route uit, de kans dat iemand hier lager mee komt schat ik heel laag

[Dash2in1]

Op donderdag 08 november 2001 22:26 schreef Xalista het volgende:
Ok, nu zijn de bugs eruit. Hier zijn mijn resultaten:

5 punten
Afstand: 130,490613243764
Duur: 00:00:00
Route: 0 3 2 1 4

(...)

Is een kortere route niet 0 4 3 2 1 0?

[Twilight Burn]

Op donderdag 15 november 2001 16:28 schreef Dash2in1 het volgende:

[..]

Is een kortere route niet 0 4 3 2 1 0?

Nope, die is 146,63

[Verwijderd]

Kleine tip voor Dash2in1 (en anderen natuurlijk), probeer even een lusje aan je programma te maken die je kortste route op het beeldscherm zet. Wellicht had je dan meteen gezien dat je een langere route had...