Normaal is het startpunt van een algoritme tav een TSP (traveling salesman problem) een matrix met (directe) afstanden. In deze matrix geldt de zogenaamde driehoeksongelijkheid: als we zeggen dat
\(d(x,y)\)
de afstand van stad x tot stad y is, dan geldt dat \(d(x,y) \leq d(x,z) + d(z,y) \)
voor alle steden x, y en z. Hierdoor weet je altijd dat de afstanden in de matrix altijd de kortste afstanden zijn, waardoor je geen Dijkstra hoeft te gebruiken in je matrix. Ik zou zeggen dat je dit als redelijk startpunt kan gebruiken voor een algoritme: zo'n matrix creeren is namelijk redelijk triviaal (door middel van Dijkstra).In jouw verhaal lijk je te suggereren alsof er geen (exacte) oplosmethoden voor een TSP zijn, behalve alle combinaties uitproberen. Dit is pertinent niet waar: bijvoorbeeld met behulp van branch&bound kan je redelijk makkelijk met de hand een TSP van 5 steden oplossen. Alleen voor hele grote matrices gaat dit mis, want dan doe je er heel lang over, maar wel veel minder lang dan de brute-force oplossing.
Maar goed, nu jouw algoritme. Ik begrijp hem nog niet helemaal (ook door gebrek aan wiskundige notatie), maar als ik het goed begrijp maak je eerst een optimale oplossing die alle steden verbindt (maar uit verschillende routes) bestaat, om vervolgens deze routes op de beste manier aan elkaar te verbinden. Dit is dezelfde methode als de branch&cut methode, wat geldt als een van de beste manieren om een TSP op te lossen. Hij is alleen nog steeds niet zo efficient dat het in polynomiale tijd oplosbaar is.
Als ik je complexiteitsberekeningen zie, heb ik geen vertrouwen in de correctheid daarvan. Ik weet daar zelf te weinig van af om het zelf uit te rekenen, maar ik zie wel dat je veel vergeet: operaties als sorteren en het minimum uitrekenen heb je helemaal niet meegenomen terwijl deze juist veel rekentijd in beslag nemen. Als je bijvoorbeeld het minimum van een (ongesorteerde) verzameling getallen laat uitrekenen door een computer, moet je namelijk alle getallen af en elk getal vergelijken enz. De beste manier om de complexiteit te berekenen is het algoritme programmeren en dan een computer het laten berekenen. Nu slaat het eigenlijk weinig op wat je zegt.
Bovendien wil ik eigenlijk ook meegeven dat dit soort grote stellingen in de wiskunde niet op dit niveau worden opgelost. Je kunt dit ook vergelijken met de Laatste Stelling van Fermat (er zijn geen geheeltallige x, y en z waarvoor geldt dat
\(x^n + y^n = z^n\)
voor \(n \geq 3 \)
). Er hebben mensen jaren verspild aan het proberen van getallen om te bewijzen dat de stelling niet klopte. Uiteindelijk is het pas na honderden jaren bewezen door middel van heel geavanceerde wiskunde bewezen dat de stelling juist was. Ook met het handelsreizigersprobleem zijn er al heel lang heel veel mensen bezig. No offense, maar het is erg naief om te denken dat zo'n groot probleem als P=NP kan worden opgelost door een simpel algoritmetje. Natuurlijk, het is mogelijk dat je aan iets denkt waar nog niemand aan heeft gedacht, maar dat is zeer onwaarschijnlijk, zeker voor iemand die niet zo wiskundig vaardig is.
