Die Häufigkeit $K_i$s für das symmetrische Traveling-Salesman-Problem

Grundlegende Informationen

• Papier-ID: 2504.19608
• Titel: Die Häufigkeit $K_i$s für das symmetrische Traveling-Salesman-Problem
• Autor: Yong Wang (North China Electric Power University)
• Klassifizierung: cs.DM math.CO math.OC
• Veröffentlichungsdatum: 15. Oktober 2025 (arXiv v3)
• Papierlink: https://arxiv.org/abs/2504.19608v3

Zusammenfassung

Dieses Papier untersucht die Häufigkeit $K_i$s ($i\in[4,n]$) im symmetrischen Traveling-Salesman-Problem (TSP), um Kanten im optimalen Hamiltonschen Kreis (OHC) zu identifizieren. Die Häufigkeit $K_i$ wird durch die optimalen $i$-Vertex-Pfade mit $\binom{i}{2}$ gegebenen Endpunkten in $K_i$ berechnet. In der Häufigkeit $K_i$ ist die Häufigkeit einer Kante die Anzahl der optimalen $i$-Vertex-Pfade, die diese Kante enthalten. Die Forschung zeigt: OHC-Kanten haben in der entsprechenden Häufigkeit $K_i$ eine Häufigkeit größer als $\frac{1}{2}\binom{i}{2}$, während gewöhnliche Kanten kleiner als dieser Wert sind; die erwartete Häufigkeit von OHC-Kanten ist größer als $\frac{i^2-4i+7}{2}$, gewöhnliche Kanten kleiner als 2; wenn $i \geq [0.3660n + 5.5849]$, ist die durchschnittliche Häufigkeit gewöhnlicher Kanten kleiner als $\frac{1}{2}\binom{i}{2}$. Basierend auf diesen Erkenntnissen wird ein Algorithmus mit dynamischer Programmierung mit Zeitkomplexität $O(n^62^{0.3660n})$ vorgeschlagen.

Forschungshintergrund und Motivation

Problematischer Hintergrund

Das Traveling-Salesman-Problem (TSP) ist ein klassisches NP-vollständiges Problem in der kombinatorischen Optimierung. Gegeben ist ein vollständiger Graph $K_n$ mit $n$ Vertices, das Ziel ist es, den kürzesten Hamiltonschen Kreis zu finden, der alle Vertices genau einmal besucht. Für das symmetrische TSP sind die Abstände der Kanten $(u,v)$ und $(v,u)$ gleich.

Einschränkungen bestehender Methoden

1. Hohe Zeitkomplexität exakter Algorithmen: Der Algorithmus der dynamischen Programmierung von Bellman und Held-Karp benötigt $O(n^22^n)$ Zeit
2. Heuristische Methoden ohne theoretische Garantien: Obwohl heuristische Algorithmen wie LKH in der Praxis gut funktionieren, fehlt die theoretische Grundlage
3. Schwierig zu identifizierende Kantenstrukturmerkmale: OHC-Kanten haben keine signifikanten Merkmale in Bezug auf Abstände und sind schwer von gewöhnlichen Kanten zu unterscheiden

Forschungsmotivation

Bestehende Forschungen zeigen, dass OHC-Kanten basierend auf der Häufigkeit $K_4$s effektiv identifiziert werden können, aber es fehlt eine systematische Untersuchung des allgemeineren Falls der Häufigkeit $K_i$s ($i > 4$). Dieses Papier zielt darauf ab:

1. Theoretische Grenzen für OHC-Kanten und gewöhnliche Kanten in der Häufigkeit $K_i$s zu etablieren
2. Die Veränderungsmuster der Kantenhäufigkeit und Wahrscheinlichkeit mit $i$ zu analysieren
3. Basierend auf Häufigkeitsmerkmalen einen effizienten OHC-Identifikationsalgorithmus zu entwerfen

Kernbeiträge

1. Etablierung der Häufigkeitsuntergrenzentheorie: Es wird bewiesen, dass OHC-Kanten in der Häufigkeit $K_i$ eine Häufigkeit größer als $\frac{1}{2}\binom{i}{2}$ haben, während gewöhnliche Kanten kleiner als dieser Wert sind
2. Analyse der Häufigkeitsveränderungsmuster: Es werden die Muster offengelegt, dass die Häufigkeit von OHC-Kanten mit zunehmendem $i$ zunimmt oder stabil bleibt, während die Häufigkeit gewöhnlicher Kanten monoton abnimmt
3. Bestimmung des kritischen Punktes: Es wird bewiesen, dass wenn $i \geq [0.3660n + 5.5849]$, OHC-Kanten und gewöhnliche Kanten vollständig unterschieden werden können
4. Vorschlag eines effizienten Algorithmus: Ein Algorithmus mit Zeitkomplexität $O(n^62^{0.3660n})$ basierend auf Häufigkeitsmerkmalen
5. Bereitstellung von Wahrscheinlichkeitsabnahmebedingungen: Bereitstellung des Wahrscheinlichkeitsabnahmekriteriums $p_{i+1}(g) < [1-\frac{2}{i(i-1)}]p_i(g)$ zur Identifikation gewöhnlicher Kanten

Methodische Erläuterung

Aufgabendefinition

Eingabe: Vollständiger Graph $K_n$ mit $n$ Vertices und Abstandsfunktion $d(u,v)$Ausgabe: Optimaler Hamiltonscher Kreis OHC Einschränkung: Symmetrisches TSP, d.h. $d(u,v) = d(v,u)$

Kernkonzepte

Optimaler $i$-Vertex-Pfad (OP^i)

Gegeben $i$ Vertices in $K_i$ und feste Endpunkte, ist der optimale $i$-Vertex-Pfad der kürzeste Pfad, der alle $i$ Vertices genau einmal besucht. Jedes $K_i$ enthält $\binom{i}{2}$ verschiedene OP^i mit unterschiedlichen Endpunktpaaren.

Häufigkeit $K_i$

Die Häufigkeit $K_i$ hat dieselben Vertices und Kanten wie das entsprechende $K_i$, aber die Kantengewichte werden durch die Häufigkeit ersetzt, mit der die Kante in den $\binom{i}{2}$ OP^i vorkommt.

Theoretischer Rahmen

Theorem 3.3 (Häufigkeitsuntergrenze für OHC-Kanten)

Für $K_i$ ($i \geq 4$) mit $\binom{i}{2}$ OP^i ist die Häufigkeit von OHC-Kanten in der entsprechenden Häufigkeit $K_i$ größer als $\frac{1}{2}\binom{i}{2}$.

Beweisidee:

• Für $i=4$ wird durch Aufzählung aller möglichen Häufigkeiten $K_4$ verifiziert
• Für $i>4$ wird Induktion verwendet, um die Monotonie der OHC-Kantenhäufigkeit bei der Erweiterung von $K_i$ zu $K_{i+1}$ zu beweisen

Theorem 3.4 (Häufigkeitsobergrenze für gewöhnliche Kanten)

Gewöhnliche Kanten haben in der Häufigkeit $K_i$ eine Häufigkeit kleiner als $\frac{1}{2}\binom{i}{2}$, und die erwartete Häufigkeit im besten Durchschnittsfall ist kleiner als $\frac{i+2}{2}$.

Theorem 4.1 (Häufigkeitsgrenzen für OHC-Kanten in $K_n$)

Für OHC-Kanten in $K_n$ ist ihre Häufigkeit in jeder beliebigen Häufigkeit $K_i$, die diese Kante enthält, im schlimmsten Durchschnittsfall größer als $\frac{1}{2}\binom{i}{2}$.

Algorithmisches Design

Häufigkeitsbasierter Identifikationsalgorithmus

1. Berechnung der Häufigkeit $K_i$: Für ausgewählte $i$-Werte werden die Häufigkeiten aller $K_i$ berechnet
2. Kantenklassifizierung: Kanten werden basierend auf dem Häufigkeitsschwellenwert $\frac{1}{2}\binom{i}{2}$ klassifiziert
3. Wahrscheinlichkeitsabnahmeerkennung: Verwendung der Bedingung $p_{i+1}(g) < [1-\frac{2}{i(i-1)}]p_i(g)$ zur Identifikation gewöhnlicher Kanten

Zeitkomplexitätsanalyse

• Die Berechnung einzelner OP^i für $K_i$ benötigt $O(i^42^i)$ Zeit
• Für $i = [0.3660n + 5.5849]$ beträgt die Gesamtzeitkomplexität $O(n^62^{0.3660n})$

Experimentelle Einrichtung

Datensätze

1. Kleinmaßstäbliche TSP-Instanzen: Konstruierte Instanzen mit $n \in [4,14]$ und Subgraphen von Oliver30
2. Echte TSP-Instanzen: 48 Instanzen aus TSPLIB, einschließlich:
   • Euklidisches TSP: att48, eil51, pr76 usw.
   • ATT TSP: att532 usw.
   • GEO TSP: mehrere geografische Distanzinstanzen
   • Matrix TSP: si535, si1032 usw.

Bewertungsmetriken

• Häufigkeitsgenauigkeit: Häufigkeitsverteilung von OHC-Kanten und gewöhnlichen Kanten
• Trennungseffekt: Anteil der Kanten, die mit dem Häufigkeitsschwellenwert korrekt klassifiziert werden
• Algorithmuseffizienz: Berechnungszeit und Raumkomplexität

Implementierungsdetails

• Verwendung dynamischer Programmierung zur Berechnung von OP^i
• Für großmaßstäbliche Instanzen wird eine zufällige Stichprobe von 1000 $K_i$ zur Berechnung der durchschnittlichen Häufigkeit verwendet
• C++-Implementierung auf einem Laptop mit 2,3-GHz-CPU und 4-GB-RAM

Experimentelle Ergebnisse

Verifizierung der Häufigkeitsgrenzen

Ergebnisse für kleinmaßstäbliche Instanzen

Für Instanzen mit $n \in [4,14]$:

• OHC-Kantenhäufigkeit: Die Mindesthäufigkeit ist immer größer als $\frac{7}{18}\binom{i}{2}$, in den meisten Fällen größer als $\frac{1}{2}\binom{i}{2}$
• Gewöhnliche Kantenhäufigkeit: Die maximale Häufigkeit ist kleiner als $\frac{1}{2}\binom{i}{2}$, die durchschnittliche Häufigkeit liegt nahe bei 2
• Häufigkeitsverhältnis: Das durchschnittliche Häufigkeitsverhältnis von OHC-Kanten zu gewöhnlichen Kanten wächst von 4 ($n=4$) auf 37,3 ($n=14$)

Ergebnisse für echte TSP-Instanzen

Für TSPLIB-Instanzen:

• Die kleinste OHC-Kantenhäufigkeit ist in den meisten Fällen größer als $f_{lb} = \frac{1}{2}\binom{i}{2}$
• Die zweitkleinste OHC-Kantenhäufigkeit ist fast immer größer als $f_{lb}$
• Die durchschnittliche OHC-Kantenhäufigkeit $f_{avg} > f_{oavg} = \frac{i^2-4i+7}{2}$

Kantenklassifizierungseffekt

Klassifizierung basierend auf Häufigkeitsschwellenwert

Verwendung der 1., 5., 10., 15., 20. kleinsten OHC-Kantenhäufigkeit als Schwellenwert:

• 1. kleinste Häufigkeit: Behält 20%-30% der gewöhnlichen Kanten (kleine Instanzen), der Anteil ist bei großen Instanzen niedriger
• 5. kleinste Häufigkeit: Der Anteil der behaltenen gewöhnlichen Kanten sinkt auf unter 15% (kleine Instanzen), unter 10% (mittlere Instanzen)
• Mit zunehmendem Schwellenwert sinkt die Anzahl der behaltenen gewöhnlichen Kanten schnell

Effekt der Wahrscheinlichkeitsabnahmebedingung

Verwendung der Bedingung $p_i(g) - p_{i+1}(g) > \frac{2p_i(g)}{i(i-1)}$:

• Bei $i=4 \to 5$ werden etwa 90% der gewöhnlichen Kanten identifiziert
• Bei $i=5 \to 6$ werden alle gewöhnlichen Kanten identifiziert ($n \leq 10$)
• Effizienter als die Häufigkeitsschwellenwertmethode mit geringerem Rechenaufwand

Häufigkeitsveränderungsmuster

Häufigkeitsveränderung von OHC-Kanten

• Monotonie: Die Wahrscheinlichkeit $p_i(e)$ nimmt mit zunehmendem $i$ zu oder bleibt stabil
• Spitzenwert: Die Häufigkeit erreicht ihren Höchstwert bei $P_0 = \frac{n}{2}+2$ (gerade $n$) oder $P_0 = \frac{n+1}{2}+1$ (ungerade $n$)
• Fehlergrenze: Bei Wahrscheinlichkeitsabnahme gilt $p_{i+1}(e) \geq [1-\frac{2}{i(i-1)}]p_i(e)$

Häufigkeitsveränderung gewöhnlicher Kanten

• Monotone Abnahme: Die Wahrscheinlichkeit $p_i(g)$ nimmt mit zunehmendem $i$ monoton ab
• Schneller Rückgang: Das Abnahmevolumen ist normalerweise größer als $\frac{2p_i(g)}{i(i-1)}$
• Kritischer Punkt: Wenn $i \geq [0.3660n + 5.5849]$, ist die durchschnittliche Häufigkeit kleiner als $\frac{1}{2}\binom{i}{2}$

Verwandte Arbeiten

TSP-Exaktalgorithmen

• Dynamische Programmierung: Bellman (1962) und Held-Karp (1962) $O(n^22^n)$ Algorithmus
• Branch-and-Bound: Algorithmen von Carpaneto et al. für großmaßstäbliche asymmetrische TSP
• Schnittebenenverfahren: Applegate et al. lösten Instanzen mit 85.900 Städten

TSP-Heuristiken

• Lin-Kernighan-Algorithmus: Klassischer lokaler Suchalgorithmus
• LKH-Algorithmus: Verbesserte Version basierend auf $\alpha$-Maß
• Pseudo-Backbone-Edge-Methode: Von Jäger et al. vorgeschlagene Methode für hochwertige Touren

Häufigkeitsmethoden

• Häufigkeit $K_4$: Erstmals von Wang und Remmel (2016) vorgeschlagene Methode basierend auf Häufigkeitsvierecken
• Binomialverteilungsmodell: Etablierung eines Wahrscheinlichkeitsmodells für Kantenhäufigkeit
• Notwendige und hinreichende Bedingungen: Wang (2019) gab notwendige und hinreichende Bedingungen basierend auf Häufigkeit $K_4$ an

Schlussfolgerung und Diskussion

Hauptschlussfolgerungen

1. Theoretische Grenzen: Etablierung strenger Grenzen für OHC-Kanten und gewöhnliche Kanten in der Häufigkeit $K_i$
2. Veränderungsmuster: Offenlegung unterschiedlicher Veränderungsmuster der Kantenhäufigkeit mit $i$
3. Algorithmuseffizienz: Vorschlag eines Identifikationsalgorithmus mit verbesserter Zeitkomplexität gegenüber traditionellen Methoden
4. Praktikabilität: Verifizierung der Methodeneffektivität auf verschiedenen Arten von TSP-Instanzen

Einschränkungen

1. Rechenkomplexität: Obwohl der Exponent verbessert wurde, bleibt es für übergroße Instanzen schwierig
2. Spezialfälle: Bei Instanzen mit vielen gleichgewichtigen Kanten kann die Methodeneffektivität sinken
3. Stichprobenfehler: Die Verwendung von Zufallsstichproben bei großmaßstäblichen Instanzen kann Fehler einführen
4. Speicheranforderungen: Speicherung großer Mengen von $K_i$ und OP^i erforderlich, höhere Raumkomplexität

Zukünftige Richtungen

1. Algorithmusoptimierung: Weitere Reduzierung der Zeitkomplexität, besonders der Konstanten
2. Parallelisierung: Nutzung der Unabhängigkeit der Häufigkeitsberechnung für parallele Optimierung
3. Approximationsmethoden: Entwicklung von Approximationsalgorithmen basierend auf Häufigkeitsmerkmalen
4. Erweiterte Anwendungen: Erweiterung der Methode auf asymmetrisches TSP und andere kombinatorische Optimierungsprobleme

Tiefgreifende Bewertung

Stärken

1. Theoretische Strenge: Vollständige mathematische Beweise und theoretische Analyse
2. Umfassende Experimente: Abdeckung von kleinmaßstäblichen bis großmaßstäblichen und verschiedenen Arten von TSP-Instanzen
3. Methodische Innovation: Erste systematische Untersuchung der Eigenschaften und Anwendungen von Häufigkeit $K_i$s
4. Praktischer Wert: Bereitstellung implementierbarer Algorithmen und klarer Zeitkomplexitätsgrenzen

Mängel

1. Ausführliche Schreibweise: Papier ist zu lang, einige Inhalte könnten gestrafft werden
2. Komplexe Symbole: Viele mathematische Symbole, Lesbarkeit könnte verbessert werden
3. Experimentelle Skalierung: Aufgrund von Rechenbeschränkungen ist die maximale Instanzgröße relativ klein
4. Unzureichende Vergleiche: Mangel an direktem Leistungsvergleich mit anderen Exaktalgorithmen

Einfluss

1. Theoretischer Beitrag: Neue Perspektive für die Forschung der Struktureigenschaften von TSP
2. Algorithmischer Wert: Bereitstellung eines effektiven Exaktalgorithmus für bestimmte Größenbereiche
3. Methodische Inspiration: Häufigkeitsanalysemethode könnte auf andere kombinatorische Optimierungsprobleme anwendbar sein
4. Implementierungsschwierigkeit: Methode ist relativ komplex, praktische Anwendung erfordert gewisse technische Fähigkeiten

Anwendungsszenarien

1. Mittlere TSP-Größe: Besonders geeignet für exakte Lösungsanforderungen mit $n \leq 100$
2. Theoretische Forschung: Bereitstellung von Werkzeugen für die Strukturanalyse von TSP
3. Vorverarbeitungsschritt: Kann als Kantenfiltervorbereitung für großmaßstäbliche TSP dienen
4. Lehre und Forschung: Bereitstellung von Fallstudien für die Lehre kombinatorischer Optimierung

Literaturverzeichnis

Dieses Papier zitiert 25 wichtige Referenzen, einschließlich:

• Bellman (1962), Held & Karp (1962): Grundlegende Arbeiten zum TSP-Algorithmus der dynamischen Programmierung
• Lin & Kernighan (1973): Klassischer LK-Heuristikalgorithmus
• Helsgaun (2000, 2009): LKH-Algorithmusserie
• Wang & Remmel (2016): Originalarbeit zur Häufigkeit $K_4$-Methode
• Applegate et al. (2009): Rekorde zur Lösung großmaßstäblicher TSP

Gesamtbewertung: Dies ist ein Papier mit tiefgreifender Theorie und umfassenden Experimenten in der kombinatorischen Optimierung, das wichtige Beiträge zur Forschung der Kantenstrukturmerkale von TSP leistet. Obwohl es noch Verbesserungsspielraum in Bezug auf Algorithmuseffizienz und Schreibkompaktheit gibt, sind sein theoretischer Wert und seine methodische Innovation anerkennenswert.