Neem nu de versie van het handelsreizigersprobleem waarin de afstanden tussen steden de rechte lijnen hiertussen zijn, en dus de situatie in 2d op schaal getekend kan worden. Er wordt geen rekening gehouden met bergen en omwegen.
Stel nu dat de volgende handelswijze altijd de kortste route geeft:
*********
- verbindt de 3 punten waarmee je de driehoek krijgt met de grootst mogelijke omtrek.
- verbindt de punten binnen de driehoek met de driehoek. Neem steeds het punt dat het dichtst bij een lijn licht, en verbindt het met de lijn die het dichtste bij ligt
- verbindt de punten buiten de driehoek. Neem steeds het punt dat het verste weg ligt bij een lijn, en verbindt het met de lijn die het dichtste bij ligt.
- als je alle punten gehad hebt: schrap de langste afstand
na het schrappen moet voor allebei de laatste 3 punten van de lijn een driehoek worden getekend, waarvan vervolgens de langste zijde moet worden geschrapt.
De dichtstbijzijnde punt bij een lijn wordt bepaald door de loodrechte afstand. De dichtstbijzijnde lijn van een punt wordt bepaald door: de loodrechte afstand / de lengte van de lijn waartoe de loodrechte afstand genomen wordt. De kleinste uitkomst van deze som is de lijn waarmee het punt moet worden verbonden.
****************
Dat zou betekenen dat voor elk extra punt de handelswijze maar 1 keer extra hoeft te worden uitgevoerd. Wat zou dit voor gevolgen hebben voor de oplosbaarheid van het P vs. NP probleem?
Laatste berichten
-
22:54
Herleiden afmetingen vanaf een foto 12
-
18:53
Ik wil studeren via afstandsonderwijs, kennen jullie Tech?
-
18:09
Rotatie van het heelal 32
-
17:19
Ervaringen met "herontdekkingen" 12
-
18 apr
hall effect in vloeistof gebruiken als stromingssensor 6
-
18 apr
Gezocht: de/een naam voor een getallenrij met een cauchyrij als partieelsommenrij
-
18 apr
Casus uit de praktijk: positief test THC 18
-
17 apr
speciale rel. theorie 4
-
17 apr
Vreemde stank in huis 11
-
17 apr
3 vragen over mijn rooskleurige r.berekening H2netGekoppeldeHBrflowbatterij.
-
17 apr
Interpretatie reactie-energie 3
-
17 apr
Logistic equation (Pierre Verhulst,Belgian Mathematician) 5
-
16 apr
vB 9
-
15 apr
Kunnen quantum Zonnecellen 190% quantum efficiënt zijn 1
-
15 apr
Python: sockets sluiten 4
-
14 apr
Een eenvoudige logische redenering waarom tijd niet kan bestaan 'daarbuiten' 6
-
14 apr
Hoe kun je op quantumwijze getallen vinden in een rij die kleiner zijn dan getal k 3
-
13 apr
Documentenverdwijnen uit onedrive 1
-
12 apr
Behoud van impulsmoment en energie 5
-
12 apr
INLOG STORING / TIPS 4
Nieuwsberichten
-
04 mar
Een nieuw soort magnetisme: altermagnetisme
-
31 okt
AI kan via stem diabetes vaststellen 11
-
21 okt
Einstein krijgt wéér gelijk 45
-
07 feb
witter dan wit 20
-
19 jun
irrigatie en de aardas
Handelsreizigersprobleem
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
-
- Berichten: 7.068
Re: Handelsreizigersprobleem
Dat kunnen we best stellen, maar het is volgens mij niet waar.Stel nu dat de volgende handelswijze altijd de kortste route geeft:
Het handelsreizigerprobleem is, volgens mij, NP-volledig. Als dit algoritme zou werken dan heb je bewezen dat NP=P. Het probleem is echter de 'als'. Je zal dus moeten bewijzen dat het algoritme altijd de korste route geeft. De kans dat dit gaat lukken lijkt mij zeer laag.Dat zou betekenen dat voor elk extra punt de handelswijze maar 1 keer extra hoeft te worden uitgevoerd. Wat zou dit voor gevolgen hebben voor de oplosbaarheid van het P vs. NP probleem?
-
- Pluimdrager
- Berichten: 3.505
Re: Handelsreizigersprobleem
Volgens Wikipedia: "Van het probleem is aangetoond dat het NP-moeilijk is en de formulering in beslisbaarheidsvorm ("Gegeven de afstanden en een totale afstand x, beslis of er een oplossing mogelijk die korter is dan x") is NP-volledig."
"Mathematics is a gigantic intellectual construction, very difficult, if not impossible, to view in its entirety." Armand Borel
-
- Berichten: 2.906
Re: Handelsreizigersprobleem
Esthetisch schreef: ↑zo 21 jul 2013, 02:01
Stel nu dat de volgende handelswijze altijd de kortste route geeft:
....
Ik vind je uitleg erg onduidelijk, dus ik zou niet kunnen zeggen of dit inderdaad de kortste route oplevert.
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }
-
- Berichten: 113
Re: Handelsreizigersprobleem
Het zou mij eveneens verbazen, maar voor de gevallen waarop ik het geprobeerd heb klopt het steeds, voor zolang in het uiteindelijke pad geen wegen meer heeft die bij de begindriehoek zaten. Als dit wel het geval is moet je een andere begindriehoek nemen.
Maar waarom denk jij dat het niet waar is?
Welk deel begrijp je niet?Math-E-Mad-X schreef: ↑di 23 jul 2013, 14:04
Ik vind je uitleg erg onduidelijk, dus ik zou niet kunnen zeggen of dit inderdaad de kortste route oplevert.
UPDATE: het klopt inderdaad niet.
Destruction has an end. Creation doesn't.
-
- Berichten: 113
Re: Handelsreizigersprobleem
UPDATE 2: Hij klopt toch wel, althans voor de versie waarvan ik dacht dat die niet klopte.
Destruction has an end. Creation doesn't.
-
- Berichten: 10.179
Re: Handelsreizigersprobleem
Toon dan eens dat hij klopt?
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
-
- Berichten: 2.906
Re: Handelsreizigersprobleem
Ik neem aan dat je hier bedoelt: 'schrap de langste lijn'Esthetisch schreef: ↑zo 21 jul 2013, 02:01
- als je alle punten gehad hebt: schrap de langste afstand
Maar hoe weet je dan nog zeker dat je inderdaad alle punten met elkaar verbonden hebt? Doordat je één van de lijnen schrapt zou het toch kunnen dat je één van de punten losgekoppeld hebt van de rest?
En van deze zin begrijp ik al helemaal niets. Je hebt het over "de laatste 3 punten van de lijn". Welke lijn bedoel je hier, en wat zijn in godsnaam de laatste 3 punten van een lijn? En vervolgens zeg je dat voor alle drie de punten een driehoek moet worden getekend. Bedoel je dat je dus 3 driehoeken tekent? Of bedoel je dat je 1 driehoek tekent die precies door die 3 punten heen gaat? In het eerste geval: waar teken je die 3 driehoeken dan?
na het schrappen moet voor allebei de laatste 3 punten van de lijn een driehoek worden getekend, waarvan vervolgens de langste zijde moet worden geschrapt.
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }
-
- Berichten: 10.561
Re: Handelsreizigersprobleem
Ik weet niet of het algoritme goed begrepen heb, maar denk niet dat deze altijd de kortste route zal geven. Stel dat je 5 punten hebt (A, B, C, D en E), en dat de grootste driehoek (ABC) die je kunt vormen een is met 2 lange zijden AC en BC en 1 (zeer) korte AB. De andere 2 punten D en E liggen in de nabijheid van deze korte zijde, een een stuk buiten de driehoek, een een stukje erbinnen (zie bijgevoegde figuur).
Het algoritme volgend wordt dan de korte zijde "opgeofferd" voor de vorming van verbindingen AD en DB, en daarna wordt DB "opgeofferd" voor de vorming van DE en EB. De route wordt dan A-D-E-B-C (links) waarbij 1 van de lange zijdes dus gehandhaafd blijft.
Is deze route daadwerkelijk korter dan het alternatief B-D-A-E-C (rechts) ?
- TSP.gif (6.05 KiB) 1246 keer bekeken
Is deze route daadwerkelijk korter dan het alternatief B-D-A-E-C (rechts) ?
Cetero censeo Senseo non esse bibendum
-
- Berichten: 113
Re: Handelsreizigersprobleem
Ik begrijp het punt. Echter voer je het vrijwel helemaal, maar net niet perfect uit. Waarschijnlijk is namelijk "de lijn AB / (loodrechte afstand E-AB)" groter dan "de lijn AC / (loodrechte afstand E-AC)", dus zul je de tweede optie ervan moeten kiezen.Marko schreef: ↑wo 24 jul 2013, 12:07
Is deze route daadwerkelijk korter dan het alternatief B-D-A-E-C (rechts) ?
Maar het algoritme klopt inderdaad niet. Ik heb er zelf ook een aantal gevonden waarvoor het niet klopt.
Helaas pindakaas.
Telkens loop ik tegen hetzelfde probleem aan, namelijk dat je ergens moet beginnen met definiëren. Ik dacht dit op te lossen met de grootste driehoek, omdat die lijnen vrijwel zeker niet in de eindroute komen, maar naar nu blijkt is dat dus toch niet voldoende. Het kan nog steeds voor komen dat de lijn na 1 of 2 keer breken nog steeds over een pad loopt dat niet bij de eindronde zit, maar dus ook niet meer bewerkt wordt.
Overigens is voor de niet kloppende voorbeelden met de op-1-of-2-na-grootste begindriehoek de route alsnog te vinden, maar dat is natuurlijk te vaag en onbevredigend, dus ik denk dat ik me hier nu op zal moeten concentreren.
Destruction has an end. Creation doesn't.
-
- Berichten: 113
Re: Handelsreizigersprobleem
@Marko: je moet trouwens ook eerst de punten binnen de driehoek verbinden, en daarna pas die erbuiten.
Destruction has an end. Creation doesn't.
-
- Berichten: 113
Re: Handelsreizigersprobleem
Je begint met een driehoek, dus een rondlopend ononderbroken pad. Je eindigt met een pad dat langs alle punten gaat, en waarmee je weer op het beginpunt uitkomt. Echter is het niet nodig om helemaal rond te lopen, dus kan je de rondlopende lijn op 1 plek onderbreken, dit doe je daar waar je het meeste afstand kan verliezen.Math-E-Mad-X schreef: ↑wo 24 jul 2013, 11:30
Ik neem aan dat je hier bedoelt: 'schrap de langste lijn'
Maar hoe weet je dan nog zeker dat je inderdaad alle punten met elkaar verbonden hebt? Doordat je één van de lijnen schrapt zou het toch kunnen dat je één van de punten losgekoppeld hebt van de rest?
Nadat het pad dus onderbroken is, heb je 2 eindpunten van het pad. Namelijk de voor en achter kant. Je controleert daar of de drie laatste punten van het pad wel de kortste zijde van hun driehoek gebruiken, zo niet, dan is er een kortere verbinding mogelijk tussen die 3 punten. Die vrijheid ontstaat dankzij het onderbreken van de lijn.Math-E-Mad-X schreef: ↑wo 24 jul 2013, 11:30
En van deze zin begrijp ik al helemaal niets. Je hebt het over "de laatste 3 punten van de lijn". Welke lijn bedoel je hier, en wat zijn in godsnaam de laatste 3 punten van een lijn? En vervolgens zeg je dat voor alle drie de punten een driehoek moet worden getekend. Bedoel je dat je dus 3 driehoeken tekent? Of bedoel je dat je 1 driehoek tekent die precies door die 3 punten heen gaat? In het eerste geval: waar teken je die 3 driehoeken dan?
Destruction has an end. Creation doesn't.
-
- Berichten: 10.561
Re: Handelsreizigersprobleem
Nee, ik heb bewust punt E zo gezet dat hij dichter bij BD ligt dan bij AC.Ik begrijp het punt. Echter voer je het vrijwel helemaal, maar net niet perfect uit. Waarschijnlijk is namelijk "de lijn AB / (loodrechte afstand E-AB)" groter dan "de lijn AC / (loodrechte afstand E-AC)",
Klopt, dat was niet goed; maar dat maakt voor het resultaat uiteindelijk niet uit.@Marko: je moet trouwens ook eerst de punten binnen de driehoek verbinden, en daarna pas die erbuiten.
Je algoritme is op zich slim bedacht; zoals je aangeeft: door te beginnen met de langste lijnstukken en die te vervangen, zul je je kans vergroten om op een korte route uit te komen. Ik meen dat je niet de eerste bent om met een dergelijk algortime te komen, en heb in een ver verleden iets dergelijks voorbij zien komen, maar ik zou niet weten welke naam daarbij hoort.
Cetero censeo Senseo non esse bibendum
-
- Berichten: 113
Re: Handelsreizigersprobleem
Als het aantal bewerkingen om tot de kortste route te komen gelijk is aan de som van n, geldt dan P = NP?
Destruction has an end. Creation doesn't.
-
- Berichten: 113
Re: Handelsreizigersprobleem
En bij n in het kwardraat?Esthetisch schreef: ↑za 10 aug 2013, 18:42
Als het aantal bewerkingen om tot de kortste route te komen gelijk is aan de som van n, geldt dan P = NP?
En maakt het nog uit of je de symmetrische of asymmetrische neemt?
Dan ga ik nog eens een keertje ff lekker puzzelen.
Destruction has an end. Creation doesn't.
