[All Languages]Alternatieve Programmeer Webstrijd

[_JGC_]

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.

[Verwijderd]

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 ), 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

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.

[drZymo]

ok ik heb niet de hele topic gelezen maar ik ga er ff aan klooien. Ik post later op de dag wel de resultaten.

[drZymo]

Tja ff teveel werk te doen nog
i'll be back

[Verwijderd]

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 ), 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.

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.

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.:

Over the past 15 years, the record for the largest nontrivial TSP instance solved to optimality has increased from 318 cities [Crowder & Padberg, 1980] to 2392 cities [Padberg & Rinaldi, 1987] to 7397 cities [Applegate et al., 1995]. Admittedly, this last result took 3-4 years of CPU time on a network of machines of the caliber of a SPARCstation 2. (SPARC is a trademark of SPARC International, Inc. and is licensed exclusively to Sun Microsystems, Inc.). However, the branch-and-cut technology developed for these recordsetting performances has also had a major impact on the low end of the scale. Problems with 100 or fewer cities are now routinely soved within a few minutes on a workstation (although there are isolated instances in this range that take much longer) and instances in the 1000-city range typically take only a few hours (or days); see Padberg & Rinaldi [1991], Grötschel & Holland [1991], and Applegate et al. [1995].

Er is dus nog wat ruimte voor verbetering in jullie code

[ScuL]

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 )

[Verwijderd]

Op vrijdag 16 november 2001 18:44 schreef Xalista het volgende:
Er is dus nog wat ruimte voor verbetering in jullie code

Hehehe, geef mij een workstation met (echte) vector processing en ik draai je die 50 steden ook binnen een paar minuten uit.

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).

[Dash2in1]

Op vrijdag 16 november 2001 08:50 schreef Debbus het volgende:
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...

Uh, had ik ook hoor, maar er zat een foutje in me programma, waardoor de laatste waarde 2 keer werd geteld en bovendien had ik het verkeerd getypt.. bedoelde 041230, maar dat is natuurlijk hetzelfde als 032140. Achteraf behoorlijk stompzinnig van me.

[Verwijderd]

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.

Vector processors? Die zitten volgens mij alleen in Cray supercomputers, niet in workstations...

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).

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]

Op zaterdag 17 november 2001 11:44 schreef Xalista het volgende:
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.

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

BTW. Wat is het verschil tussen branch-and-bound en branch-and-cut?

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).

[MIster X]

Zeg, ik heb hier de afgelopen dagen ook een beetje naar lopen kijken. Erg interessant...
Hoe ver zijn jullie op dit moment?

[Dash2in1]

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

[afbeelding]

Hmm, noem me lui, maar welke punten heb je dan concreet .. is nogal onduidelijk op te maken?

[Verwijderd]

Op dinsdag 20 november 2001 16:26 schreef Dash2in1 het volgende:

[..]

Hmm, noem me lui, maar welke punten heb je dan concreet .. is nogal onduidelijk op te maken?

code:

13, 11 - 46
06, 05 - 0
04, 06 - 38
01, 09 - 25
05, 23 - 26
05, 26 - 11
02, 32 - 4
01, 34 - 40
02, 46 - 19
11, 39 - 43
15, 30 - 41
13, 29 - 7
12, 24 - 12
18, 27 - 23
22, 34 - 8
24, 37 - 30
19, 39 - 27
18, 41 - 9
18, 45 - 13
23, 44 - 21
23, 49 - 10
30, 50 - 28
43, 48 - 29
34, 40 - 39
39, 37 - 37
45, 36 - 22
44, 33 - 15
48, 31 - 34
49, 30 - 1
42, 23 - 2
37, 26 - 18
30, 32 - 24
31, 26 - 32
27, 24 - 35
29, 19 - 44
35, 22 - 49
36, 20 - 5
35, 19 - 6
36, 15 - 42
46, 12 - 33
50, 08 - 16
40, 10 - 31
36, 07 - 48
35, 08 - 20
31, 10 - 17
33, 06 - 3
36, 03 - 36
30, 00 - 47
25, 03 - 45
21, 03 - 14

[htca]

Ik kwam van de week mijn code tegen die ik hiervoor had geschreven. Zijn er mensen die hier nog steeds aan werken?