Dan ben ik erg benieuwd naar jouw wiskundig bewijs
Verwijderd
Dat is ook het hele probleem: het programmeren is denk ik eenvoudiger dan het bewijs leveren.Op donderdag 08 november 2001 17:07 schreef tomato het volgende:
Dan ben ik erg benieuwd naar jouw wiskundig bewijs
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?
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?
/u/13620/crop611bc7af5725b_cropped.png?f=community)
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
There's no such thing as a mistake, just happy accidents - Bob Ross
Relaxte muziek: altijd okee!
- Soulseek rulez -
:strip_exif()/u/13818/episodebutler_60x60.gif?f=community)
Tsjipmanz
Reken eens uit hoeveel afstanden dat zijn (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
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 Oeps, denkfoutje.. Valt wel mee
(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
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Dat zijn vanuit punt:Op donderdag 08 november 2001 17:30 schreef Janoz het volgende:
Tsjipmanz
Reken eens uit hoeveel afstanden dat zijn
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
Toen ik begon te typen had je je denkfoutje nog niet neergezet
lekker puh There's no such thing as a mistake, just happy accidents - Bob Ross
Relaxte muziek: altijd okee!
- Soulseek rulez -
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 !
There's no such thing as a mistake, just happy accidents - Bob Ross
Relaxte muziek: altijd okee!
- Soulseek rulez -
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Verwijderd
Bedenk een algoritme, deze hoeft niet daadwerkelijk uitgevoerd te worden, als je maar kunt zien dat het werkt.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 !
Voor een daadwerkelijke berekening is een 10tal punten wel genoeg. Als het daarvoor geldt, dan geldt het ook voor 50 punten.
[edit]
*knip*
Verwijderd
Xalista: oops 
Plak jij je punten effe terug ?
[edit]
Ik doe brute-force, en zal ook de eerste 20 punten gebruiken.
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:
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:
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.
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| 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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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.
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.
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.
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.
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.
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
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Dat idee, en het bewijs, zou ik wel eens willen zien.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
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
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
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 )
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
)
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
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
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.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
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
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
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.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
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
Ik ga er even aan schrijven
Dat betekent inderdaad dat ik van de brute-force methode afstap, en wat strategischer ga werken
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...
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...
There's no such thing as a mistake, just happy accidents - Bob Ross
Relaxte muziek: altijd okee!
- Soulseek rulez -
Verwijderd
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.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
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.
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
/u/13464/Delphi.png?f=community)
Ik heb de vorige 10 minuten ook even wat uitgeprobeerd, wel wat simpel:
Is het iets of ben ik weer es dom bezig?
Is het iets of ben ik weer es dom bezig?
"The shell stopped unexpectedly and Explorer.exe was restarted."
Het is iig niet de kortste route, dat kun je direct al zienjelmervos: Is het iets of ben ik weer es dom bezig?
Verwijderd
Hoe zie jij datOp 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:Op vrijdag 09 november 2001 21:25 schreef tomato het volgende:
[..]
Het is iig niet de kortste route, dat kun je direct al zien
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.
"The shell stopped unexpectedly and Explorer.exe was restarted."
Heel simpel, ik zie stukjes in zijn route (bijvoorbeeld linksonder) waar je het 'draadje' langs kunt leggen op een kortere manierdev: Hoe zie jij dat
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.
/u/2305/crop653618cca8542_cropped.png?f=community)
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... 
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...
Cool zo'n uitleg, volgen er meer?
Is namelijk intressant om te lezen.
Is namelijk intressant om te lezen.
"The shell stopped unexpectedly and Explorer.exe was restarted."
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
Nu zie ik het ook, was niet helemaal wakkerOp 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.
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.
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.
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.
Brute force is 30414093201713400000000000000000000000000000000000000000000000000 mogelijkheden testen!
"The shell stopped unexpectedly and Explorer.exe was restarted."
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
Wat knap dat jij weet hoeveel mogelijkheden ik test zonder mijn algoritme te kennnenOp zaterdag 10 november 2001 15:37 schreef jelmervos het volgende:
Brute force is 30414093201713400000000000000000000000000000000000000000000000000 mogelijkheden testen!
(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.)
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.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
(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
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!
Deze methode is natuurlijk niet het optimaalst maar wel lekker snel
Ga vannacht nog wat verder klooien.
CoDeR Uit!
Verwijderd
Alle respect hoor, maar dat lijkt dus nergens opOp 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]
Twee snijdende lijnen moet niet kunnen, dat is altijd een omweg namelijk.
(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)
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)
Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'
Verwijderd
Ik post ook nog maar een resultaatje De kortst mogelijke route over de eerste 19 punten:
Is er nog belangstelling voor m'n code?
De kortst mogelijke route over de eerste 19 punten:code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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...Op zondag 11 november 2001 00:34 schreef mietje het volgende:
Ik post ook nog maar een resultaatje
code:
Is er nog belangstelling voor m'n code?
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 gekomenOp zaterdag 10 november 2001 15:14 schreef mietje het volgende:
Ik zit nog steeds brute force te klooien
) 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:
1
2
3
4
5
6
7
8
9
10
11
12
| 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
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.
/me bloost
Die versie die ik boven link is nu 460 regels, puur console.
Ik ben welliswaar geen bruteforcer meer, maar ik kan je wel vertellen dat je algoritme niet exact is. (Wat je zelf ook al verwachte)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 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
Dit is ook niet de best mogelijke routeOp 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
Ik heb nog een bugje uit m'n brute-forcer gehaald en hem eens op 20 punten losgelaten:code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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!Op maandag 12 november 2001 16:38 schreef mietje het volgende:
[..]
Dit is ook niet de best mogelijke route
code:
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.
:strip_icc():strip_exif()/u/7491/24.jpg?f=community)
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?
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:
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
Ik kan helaas geen sjieke schermpjes posten, maar wel optimale resultaten
21 punten:
(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.)
21 punten:
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 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.)
:strip_icc():strip_exif()/u/2277/companioncube.jpg?f=community)
Goh.. Waarom is de fileserver nou toch zo traag¿ en het downloaden schiet ook al voor geen meter op
tyrips, tywreps, tiewreps, tiereps, tie raps, ripties, taiwraps, kabelbindbandjes » Tie Wraps
\o/
Wat was ook alweer een goeie java decompiler?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.
[..]
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.
Inderdaad smerig snel die oplossing.
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 laagOp dinsdag 13 november 2001 19:51 schreef dev het volgende:
[..]
Ziet er goed uit. Ik ben benieuwd of iemand nog lager komt
lijkt me wel wat voor recursief backtracken, je computer heeft zomaar een oplossing gevonden (mits je genoeg RAM hebt ), en rekent gewoon alle oplossingen door tot je hem stilzet. Heeft ie een betere? dan slaat ie die op en gaat ie verder. Niet zo moeilijk lijkt het op zich, maar onderschat het niet
Op school hebben we eens een roosterprogramma gemaakt wat dit deed met docenten, lokalen, beschikbaarheid van beiden, vakken en leerlingen. Kwam altijd wel een redelijk rooster uit, maar de eerste versies vraten óf een heleboel geheugen, óf een heleboel I/O door de SQL database die eraan hing.
), en rekent gewoon alle oplossingen door tot je hem stilzet. Heeft ie een betere? dan slaat ie die op en gaat ie verder. Niet zo moeilijk lijkt het op zich, maar onderschat het niet Op school hebben we eens een roosterprogramma gemaakt wat dit deed met docenten, lokalen, beschikbaarheid van beiden, vakken en leerlingen. Kwam altijd wel een redelijk rooster uit, maar de eerste versies vraten óf een heleboel geheugen, óf een heleboel I/O door de SQL database die eraan hing.
Verwijderd
Als je een paar pagina's terug kijkt zie je dat ik een link naar de (C++) code voor een recursieve backtracker gepost heb. Helaas is de complexiteit van dit probleem facultatief, dus je zult in principe 50! mogelijkheden moeten testen. Hoewel je de te testen mogelijkheden met een constante factor kunt beperken door branch and bound en branch and cut methodes (zitten beide in mijn code) blijft de complexiteit facultatief, en blijft het een NP probleem.Op vrijdag 16 november 2001 13:15 schreef _JGC_ het volgende:
lijkt me wel wat voor recursief backtracken, je computer heeft zomaar een oplossing gevonden (mits je genoeg RAM hebt
/u/11182/peertop.png?f=community)
"There are three stages in scientific discovery: first, people deny that it is true; then they deny that it is important; finally they credit the wrong person."
Een standaard branch-and-bound (backtracken met een bound) heeft helemaal niet zoveel geheugen nodig, omdat de recursie diepte nooit hoger is dan het aantal punten waar je een route door zoekt. Natuurlijk wordt dat geheugengebruik veel hoger als je allerlei zaken over reeds bekeken routes gaat bijhouden om je algoritme sneller te maken, maar dat heeft dus niet zoveel te maken met de recursie op zich.Op vrijdag 16 november 2001 13:15 schreef _JGC_ het volgende:
lijkt me wel wat voor recursief backtracken, je computer heeft zomaar een oplossing gevonden (mits je genoeg RAM hebt
Op school hebben we eens een roosterprogramma gemaakt wat dit deed met docenten, lokalen, beschikbaarheid van beiden, vakken en leerlingen. Kwam altijd wel een redelijk rooster uit, maar de eerste versies vraten óf een heleboel geheugen, óf een heleboel I/O door de SQL database die eraan hing.
Ik heb het een beetje druk gehad, en heb dit probleem een beetje op een laag pitje gezet. Ik was van plan om voor dit probleem een Lin-Kernighan algoritme te implementeren, maar dat was me iets te veel moeite om het goed te krijgen. Het resultaat met lengte 305,xx voor 50 steden lijkt me vrij optimaal, maar misschien implementeer ik voor de fun nog een keer een 2-opt of 3-opt algoritme om te kijken wat die vinden. In de praktijk zou een 2 of 3-opt algoritme in een aantal runs wel het optimale resultaat moeten kunnen vinden voor 50 steden.
Voor alle brute-forcers die voor exacte resultaten gaan, ik vond dit in "Local search in Combinatorial Optimization" van Aarts, Lenstra et al.:
Er is dus nog wat ruimte voor verbetering in jullie code
/u/2205/nzflag_60x60.png?f=community)
fok! als je zo kan programmeren vind ik je echt sick!
ik programmeer al een jaar of 8 maar dit niveau kan ik dus echt niet bijbenen.. respect
(ben wel benieuwd naar een tekening van de snelste route )
ik programmeer al een jaar of 8 maar dit niveau kan ik dus echt niet bijbenen.. respect
(ben wel benieuwd naar een tekening van de snelste route
)
ProMods ETS2 uitbreiding - Mijn tijdszone is UTC+13
Verwijderd
Hehehe, geef mij een workstation met (echte) vector processing en ik draai je die 50 steden ook binnen een paar minuten uit.Op vrijdag 16 november 2001 18:44 schreef Xalista het volgende:
Er is dus nog wat ruimte voor verbetering in jullie code
Ik heb trouwens wel interesse in je brute force code, ik zou met name graag willen zien hoe jij je bounding implementeert (volgens mij bound ik op eoa. manier nog steeds te laat).
Vector processors? Die zitten volgens mij alleen in Cray supercomputers, niet in workstations...Op vrijdag 16 november 2001 21:10 schreef mietje het volgende:
[..]
Hehehe, geef mij een workstation met (echte) vector processing en ik draai je die 50 steden ook binnen een paar minuten uit.
Mijn code? Joh, die is echt zo basic al wat... Het is niet voor niks dat die van jouw véél sneller is. Maar, voor de record, ik bound als de lengte van het stuk route waar ik op dat moment naar kijk + de lengte van de terugreis langer is dan de beste route tot dan toe. Verder niks.
BTW. Wat is het verschil tussen branch-and-bound en branch-and-cut?
Verwijderd
Mja, het gaat mij dus om "+ de lengte van de terugreis". Als ik dat java-appletje bekijk voel ik gewoon aan m'n water dat er eerder te bounden moet zijn
Cut algoritmes werken niet door een bepaalde grens (de bound) te naderen en te backtracken als die grens overschreden wordt, maar nemen andere criteria die niet stap voor stap een grens naderen om de recursieboom te beperken (bv. mijn criterium dat er geen paden mogen kruisen).
:strip_icc():strip_exif()/u/40087/crop58e29e169f35a_cropped.jpeg?f=community)
:strip_icc():strip_exif()/u/39359/OCR2.jpg?f=community)
![[afbeelding]](http://members.home.nl/kreunen/got.JPG){kind=link}