La frequenza $K_i$s per il problema del commesso viaggiatore simmetrico

Informazioni di base

• ID articolo: 2504.19608
• Titolo: La frequenza $K_i$s per il problema del commesso viaggiatore simmetrico
• Autore: Yong Wang (North China Electric Power University)
• Classificazione: cs.DM math.CO math.OC
• Data di pubblicazione: 15 ottobre 2025 (arXiv v3)
• Link articolo: https://arxiv.org/abs/2504.19608v3

Riassunto

Questo articolo studia la frequenza $K_i$s ($i\in[4,n]$) nel problema del commesso viaggiatore simmetrico (TSP) per identificare gli archi nel circuito hamiltoniano ottimale (OHC). La frequenza $K_i$ è calcolata attraverso i percorsi ottimali di $i$ vertici corrispondenti ai $\binom{i}{2}$ endpoint dati all'interno di $K_i$ in $K_n$. Nella frequenza $K_i$, la frequenza di un arco è il numero di percorsi ottimali di $i$ vertici che contengono quell'arco. Lo studio rivela che: gli archi OHC hanno frequenza maggiore di $\frac{1}{2}\binom{i}{2}$ nella frequenza $K_i$ corrispondente, mentre gli archi ordinari hanno frequenza minore di questo valore; la frequenza attesa degli archi OHC è maggiore di $\frac{i^2-4i+7}{2}$, mentre gli archi ordinari hanno frequenza minore di 2; quando $i \geq [0.3660n + 5.5849]$, la frequenza media degli archi ordinari è minore di $\frac{1}{2}\binom{i}{2}$. Sulla base di questi risultati, è proposto un algoritmo di programmazione dinamica con complessità temporale $O(n^62^{0.3660n})$.

Contesto di ricerca e motivazione

Contesto del problema

Il problema del commesso viaggiatore (TSP) è un problema classico NP-completo nell'ottimizzazione combinatoria. Dato un grafo completo $K_n$ con $n$ vertici, l'obiettivo è trovare il circuito hamiltoniano più breve che visiti tutti i vertici esattamente una volta. Per il TSP simmetrico, le distanze degli archi $(u,v)$ e $(v,u)$ sono uguali.

Limitazioni dei metodi esistenti

1. Alta complessità temporale degli algoritmi esatti: algoritmi come la programmazione dinamica di Bellman e Held-Karp richiedono tempo $O(n^22^n)$
2. Mancanza di garanzie teoriche nei metodi euristici: sebbene algoritmi euristici come LKH funzionino bene in pratica, mancano di fondamenti teorici
3. Difficoltà nell'identificare le caratteristiche strutturali degli archi: gli archi OHC non hanno caratteristiche significative nelle distanze, rendendo difficile distinguerli dagli archi ordinari

Motivazione della ricerca

Ricerche precedenti hanno dimostrato che gli archi OHC possono essere identificati efficacemente sulla base della frequenza $K_4$s, ma manca uno studio sistematico del caso più generale della frequenza $K_i$s ($i > 4$). Questo articolo mira a:

1. Stabilire limiti teorici tra gli archi OHC e gli archi ordinari nelle frequenze $K_i$s
2. Analizzare le leggi di variazione della frequenza e della probabilità degli archi al variare di $i$
3. Progettare algoritmi efficienti per l'identificazione di OHC basati sulle caratteristiche di frequenza

Contributi principali

1. Stabilimento di teoria dei limiti inferiori di frequenza: dimostrazione che gli archi OHC hanno frequenza maggiore di $\frac{1}{2}\binom{i}{2}$ nella frequenza $K_i$, mentre gli archi ordinari hanno frequenza minore di questo valore
2. Analisi delle leggi di variazione della frequenza: rivelazione che la frequenza degli archi OHC aumenta o rimane stabile al crescere di $i$, mentre la frequenza degli archi ordinari diminuisce monotonicamente
3. Determinazione del punto critico: dimostrazione che quando $i \geq [0.3660n + 5.5849]$, gli archi OHC e gli archi ordinari possono essere completamente distinti
4. Proposta di algoritmo efficiente: algoritmo di tempo $O(n^62^{0.3660n})$ basato sulle caratteristiche di frequenza
5. Fornitura di condizioni di decremento probabilistico: criterio di decremento probabilistico per l'identificazione degli archi ordinari $p_{i+1}(g) < [1-\frac{2}{i(i-1)}]p_i(g)$

Dettagli del metodo

Definizione del compito

Input: grafo completo $K_n$ con $n$ vertici e funzione di distanza degli archi $d(u,v)$Output: circuito hamiltoniano ottimale OHC Vincoli: TSP simmetrico, cioè $d(u,v) = d(v,u)$

Concetti fondamentali

Percorso ottimale di $i$ vertici (OP^i)

Dati $i$ vertici in $K_i$ e endpoint fissi, il percorso ottimale di $i$ vertici è il percorso più breve che visita tutti gli $i$ vertici esattamente una volta. Ogni $K_i$ contiene OP^i con $\binom{i}{2}$ coppie di endpoint diverse.

Frequenza $K_i$

La frequenza $K_i$ ha gli stessi vertici e archi del corrispondente $K_i$, ma i pesi degli archi sono sostituiti dal numero di volte che l'arco appare nei $\binom{i}{2}$ OP^i (frequenza).

Quadro teorico

Teorema 3.3 (Limite inferiore della frequenza degli archi OHC)

Per $K_i$ ($i \geq 4$) contenente $\binom{i}{2}$ OP^i, la frequenza degli archi OHC nella corrispondente frequenza $K_i$ è maggiore di $\frac{1}{2}\binom{i}{2}$.

Schema della dimostrazione:

• Quando $i=4$, verifica attraverso enumerazione di tutte le possibili frequenze $K_4$
• Per $i>4$, utilizzo del metodo di induzione, dimostrazione della monotonicità della frequenza degli archi OHC nell'estensione da $K_i$ a $K_{i+1}$

Teorema 3.4 (Limite superiore della frequenza degli archi ordinari)

La frequenza degli archi ordinari nella frequenza $K_i$ è minore di $\frac{1}{2}\binom{i}{2}$, e la frequenza attesa nel migliore dei casi medi è minore di $\frac{i+2}{2}$.

Teorema 4.1 (Limiti di frequenza degli archi OHC in $K_n$)

Per gli archi OHC in $K_n$, nella qualsiasi frequenza $K_i$ che contiene l'arco, la frequenza nel peggiore dei casi medi è maggiore di $\frac{1}{2}\binom{i}{2}$.

Progettazione dell'algoritmo

Algoritmo di identificazione basato sulla frequenza

1. Calcolo della frequenza $K_i$: per i valori di $i$ selezionati, calcolo della frequenza di tutti i $K_i$
2. Classificazione degli archi: classificazione degli archi in base alla soglia di frequenza $\frac{1}{2}\binom{i}{2}$
3. Rilevamento del decremento probabilistico: utilizzo della condizione $p_{i+1}(g) < [1-\frac{2}{i(i-1)}]p_i(g)$ per identificare gli archi ordinari

Analisi della complessità temporale

• Il calcolo di un singolo OP^i di $K_i$ richiede tempo $O(i^42^i)$
• Per $i = [0.3660n + 5.5849]$, la complessità temporale totale è $O(n^62^{0.3660n})$

Configurazione sperimentale

Set di dati

1. Istanze TSP su piccola scala: istanze costruite con $n \in [4,14]$ e sottografi di Oliver30
2. Istanze TSP reali: 48 istanze da TSPLIB, incluse:
   • TSP euclideo: att48, eil51, pr76, ecc.
   • TSP ATT: att532, ecc.
   • TSP GEO: multiple istanze di distanza geografica
   • TSP Matrix: si535, si1032, ecc.

Metriche di valutazione

• Accuratezza della frequenza: distribuzione della frequenza degli archi OHC e degli archi ordinari
• Effetto di separazione: proporzione di archi correttamente classificati utilizzando la soglia di frequenza
• Efficienza dell'algoritmo: tempo di calcolo e complessità spaziale

Dettagli di implementazione

• Utilizzo della programmazione dinamica per il calcolo di OP^i
• Per istanze su larga scala, campionamento casuale di 1000 $K_i$ per il calcolo della frequenza media
• Implementazione in C++, esecuzione su un notebook con CPU 2.3GHz e 4GB di memoria

Risultati sperimentali

Verifica dei limiti di frequenza

Risultati su istanze su piccola scala

Per istanze con $n \in [4,14]$:

• Frequenza degli archi OHC: la frequenza minima è sempre maggiore di $\frac{7}{18}\binom{i}{2}$, nella maggior parte dei casi maggiore di $\frac{1}{2}\binom{i}{2}$
• Frequenza degli archi ordinari: la frequenza massima è minore di $\frac{1}{2}\binom{i}{2}$, la frequenza media è prossima a 2
• Rapporto di frequenza: il rapporto medio tra frequenza degli archi OHC e degli archi ordinari cresce da 4 ($n=4$) a 37.3 ($n=14$)

Risultati su istanze TSP reali

Per istanze TSPLIB:

• La frequenza del primo arco OHC più piccolo è nella maggior parte dei casi maggiore di $f_{lb} = \frac{1}{2}\binom{i}{2}$
• La frequenza del secondo arco OHC più piccolo è quasi sempre maggiore di $f_{lb}$
• La frequenza media degli archi OHC $f_{avg} > f_{oavg} = \frac{i^2-4i+7}{2}$

Effetto della classificazione degli archi

Classificazione basata sulla soglia di frequenza

Utilizzo del 1°, 5°, 10°, 15°, 20° arco OHC più piccolo come soglia:

• Soglia del 1° più piccolo: conservazione del 20%-30% degli archi ordinari (istanze piccole), proporzione più bassa nelle istanze grandi
• Soglia del 5° più piccolo: proporzione di archi ordinari conservati scende al di sotto del 15% (istanze piccole), al di sotto del 10% (istanze medie)
• Con l'aumento della soglia, il numero di archi ordinari conservati diminuisce rapidamente

Effetto della condizione di decremento probabilistico

Utilizzo della condizione $p_i(g) - p_{i+1}(g) > \frac{2p_i(g)}{i(i-1)}$:

• Identificazione di circa il 90% degli archi ordinari nella transizione $i=4 \to 5$
• Identificazione di tutti gli archi ordinari nella transizione $i=5 \to 6$ ($n \leq 10$)
• Metodo più efficiente rispetto al metodo della soglia di frequenza, con carico computazionale minore

Leggi di variazione della frequenza

Variazione della frequenza degli archi OHC

• Monotonicità: la probabilità $p_i(e)$ aumenta o rimane stabile al crescere di $i$
• Valore di picco: la frequenza raggiunge il picco a $P_0 = \frac{n}{2}+2$ (per $n$ pari) o $P_0 = \frac{n+1}{2}+1$ (per $n$ dispari)
• Limite di errore: quando la probabilità diminuisce, soddisfa $p_{i+1}(e) \geq [1-\frac{2}{i(i-1)}]p_i(e)$

Variazione della frequenza degli archi ordinari

• Decremento monotono: la probabilità $p_i(g)$ diminuisce monotonicamente al crescere di $i$
• Rapido declino: l'entità del decremento è solitamente maggiore di $\frac{2p_i(g)}{i(i-1)}$
• Punto critico: quando $i \geq [0.3660n + 5.5849]$, la frequenza media è minore di $\frac{1}{2}\binom{i}{2}$

Lavori correlati

Algoritmi esatti per TSP

• Programmazione dinamica: algoritmo $O(n^22^n)$ di Bellman (1962) e Held-Karp (1962)
• Branch and bound: algoritmi per TSP asimmetrico su larga scala di Carpaneto et al.
• Metodo dei piani di taglio: risoluzione di istanze con 85.900 città di Applegate et al.

Algoritmi euristici per TSP

• Algoritmo Lin-Kernighan: algoritmo classico di ricerca locale
• Algoritmo LKH: versione migliorata basata su $\alpha$-measure
• Metodo dello pseudo-backbone edge: metodo di percorsi di tour di alta qualità proposto da Jäger et al.

Metodi di frequenza

• Frequenza $K_4$: primo metodo basato su quadrilateri di frequenza proposto da Wang e Remmel (2016)
• Modello di distribuzione binomiale: stabilimento di modello probabilistico per la frequenza degli archi
• Condizioni necessarie e sufficienti: condizioni necessarie e sufficienti per gli archi OHC basate sulla frequenza $K_4$ fornite da Wang (2019)

Conclusioni e discussione

Conclusioni principali

1. Limiti teorici: stabilimento di limiti rigorosi tra gli archi OHC e gli archi ordinari nella frequenza $K_i$
2. Leggi di variazione: rivelazione di diversi modelli di variazione della frequenza degli archi al variare di $i$
3. Efficienza dell'algoritmo: proposta di algoritmo di identificazione con complessità temporale migliore rispetto ai metodi tradizionali
4. Praticità: verifica dell'efficacia del metodo su vari tipi di istanze TSP

Limitazioni

1. Complessità computazionale: sebbene il termine esponenziale sia migliorato, rimane difficile per istanze su scala molto grande
2. Casi speciali: l'efficacia del metodo potrebbe diminuire per istanze con numerosi archi di peso uguale
3. Errore di campionamento: l'utilizzo di campionamento casuale per istanze su larga scala potrebbe introdurre errori
4. Requisiti di memoria: necessità di memorizzare numerosi $K_i$ e OP^i, complessità spaziale relativamente elevata

Direzioni future

1. Ottimizzazione dell'algoritmo: ulteriore riduzione della complessità temporale, in particolare del termine costante
2. Parallelizzazione: sfruttamento dell'indipendenza del calcolo della frequenza per l'ottimizzazione parallela
3. Metodi approssimati: sviluppo di algoritmi approssimati basati sulle caratteristiche di frequenza
4. Estensione dell'applicazione: estensione del metodo al TSP asimmetrico e ad altri problemi di ottimizzazione combinatoria

Valutazione approfondita

Punti di forza

1. Rigore teorico: fornitura di prove matematiche complete e analisi teorica
2. Esperimenti completi: copertura di istanze da piccola scala a grande scala, di vari tipi
3. Innovazione del metodo: primo studio sistematico delle proprietà e dell'applicazione della frequenza $K_i$s
4. Valore pratico: fornitura di algoritmi implementabili e limiti di complessità temporale espliciti

Insufficienze

1. Lunghezza della scrittura: lunghezza eccessiva dell'articolo, parte del contenuto potrebbe essere sintetizzato
2. Complessità della notazione: numerosi simboli matematici, leggibilità da migliorare
3. Scala degli esperimenti: limitazione della capacità computazionale, scala massima dell'istanza relativamente piccola
4. Confronto insufficiente: mancanza di confronto diretto delle prestazioni con altri algoritmi esatti

Impatto

1. Contributo teorico: fornitura di nuova prospettiva per la ricerca sulle proprietà strutturali del TSP
2. Valore dell'algoritmo: fornitura di algoritmo esatto efficace per intervalli di dimensioni specifici
3. Ispirazione del metodo: il metodo di analisi della frequenza potrebbe essere applicabile ad altri problemi di ottimizzazione combinatoria
4. Difficoltà di implementazione: il metodo è relativamente complesso, l'applicazione pratica richiede una certa competenza tecnica

Scenari applicabili

1. TSP su scala media: particolarmente adatto per esigenze di risoluzione esatta con $n \leq 100$
2. Ricerca teorica: fornitura di strumenti per l'analisi strutturale del TSP
3. Fase di preprocessing: utilizzo come preprocessing di selezione degli archi per TSP su larga scala
4. Ricerca didattica: fornitura di casi di studio per l'insegnamento dell'ottimizzazione combinatoria

Bibliografia

Questo articolo cita 25 importanti riferimenti bibliografici, inclusi:

• Bellman (1962), Held & Karp (1962): lavori fondamentali dell'algoritmo di programmazione dinamica per TSP
• Lin & Kernighan (1973): algoritmo euristico classico LK
• Helsgaun (2000, 2009): serie di algoritmi LKH
• Wang & Remmel (2016): lavoro originale del metodo di frequenza $K_4$
• Applegate et al. (2009): record di risoluzione di TSP su larga scala

Valutazione complessiva: questo è un articolo di ottimizzazione combinatoria con teoria approfondita e esperimenti dettagliati, che ha apportato importanti contributi nella ricerca sulle proprietà strutturali degli archi del TSP. Sebbene vi sia ancora spazio per miglioramenti in termini di efficienza dell'algoritmo e semplicità della scrittura, il suo valore teorico e l'innovazione del metodo meritano riconoscimento.