TSP e Ciclo Hamiltoniano
Salve,
chiedo un chiarimento su alcuni problemi.
In rete si trovano tante di quei documenti su questi problemi, TSP (commesso viaggiatore) e ciclo hamiltoniano, che non si capisce più nulla.
Ho trovati tanti blabla inutili, perciò chiedo a voi di chiarirmi qualche dubbio, senza dimostrazioni ma solo questioni di nomenclatura.
- Commesso Viaggiatore generico è un problem NP-completo (senza dimostrazione).
domanda: E' un grafo completo pesato, e i pesi possono essere qualunque cosa, e non vale la disuguaglianza euclidea. E' un problema di ottimizzazione, cioè dice se esiste un ciclo hamiltonia di peso minimo.
- Commesso Viaggiatore metrico
domanda: è sempre un problema NP-completo? Ma la differenza da quello generico è sempre un grafo completo pesato, ma vale la disuguaglianza triangolare sul piano ed ha un algoritmo 2-approssimato.
- Ciclo hamiltoniano è NP-completo
è sempre un grafo completo ed è un problema decisionale?
la faccenda principale questi problemi sono definiti solo su grafi completi? perchè ogni volta leggo: "prendiamo un grafo completo.."
ma la dimostrazione del commesso viaggiatore generico che non ha algoritmi p(n)-approssimati usa grafi sparsi e fa una riduzione al ciclo hamiltoniano su un grafo completo (cioè aggiugne archi di peso stratosferico) per trovare un giro.
Ringrazio chi chiarisce questi dubbi.
chiedo un chiarimento su alcuni problemi.
In rete si trovano tante di quei documenti su questi problemi, TSP (commesso viaggiatore) e ciclo hamiltoniano, che non si capisce più nulla.
Ho trovati tanti blabla inutili, perciò chiedo a voi di chiarirmi qualche dubbio, senza dimostrazioni ma solo questioni di nomenclatura.
- Commesso Viaggiatore generico è un problem NP-completo (senza dimostrazione).
domanda: E' un grafo completo pesato, e i pesi possono essere qualunque cosa, e non vale la disuguaglianza euclidea. E' un problema di ottimizzazione, cioè dice se esiste un ciclo hamiltonia di peso minimo.
- Commesso Viaggiatore metrico
domanda: è sempre un problema NP-completo? Ma la differenza da quello generico è sempre un grafo completo pesato, ma vale la disuguaglianza triangolare sul piano ed ha un algoritmo 2-approssimato.
- Ciclo hamiltoniano è NP-completo
è sempre un grafo completo ed è un problema decisionale?
la faccenda principale questi problemi sono definiti solo su grafi completi? perchè ogni volta leggo: "prendiamo un grafo completo.."
ma la dimostrazione del commesso viaggiatore generico che non ha algoritmi p(n)-approssimati usa grafi sparsi e fa una riduzione al ciclo hamiltoniano su un grafo completo (cioè aggiugne archi di peso stratosferico) per trovare un giro.
Ringrazio chi chiarisce questi dubbi.
Risposte
Io conosco le questioni "discorsivamente" in altro modo:
Il Problema del Commesso Viaggiatore è quello di trovare un percorso che colleghi tutte le località dove il commesso viaggiatore ha clienti, passando da ciascuna una sola volta e tornando al punto di partenza (dove il commesso viaggiatore abita). In termini di grafi, consiste nel trovare un ciclo hamiltoniano, che è un problema NP-completo.
Il Problema del Percorso Minimo è quello di trovare il percorso più breve che colleghi tutte le località, per esempio l'autobus che deve passare per tutti i paesi; in questo caso le strade sono già date. In termini di grafi, consiste nel trovare un ciclo hamiltoniano di peso minimo di un grafo etichettato (non orientato), ed è anch'esso un problema NP-completo.
Ovviamente non sono definiti solo su grafi completi. Ma sono problemi affini, e la loro generalizzazione sui grafi completi li rende più facili da affrontare, anche se da un punto di vista computazionale non otteniamo alcun vantaggio. Per dire:
- trovare un ciclo hamiltoniano in un grafo equivale a etichettare (sugli spigoli) il grafo originale con 0 per ogni spigolo e 1 per ogni spigolo aggiunto, e cercare un ciclo hamiltoniano di peso 0.
- trovare un ciclo hamiltoniano minimo in un grafo dato equivale a completare il grafo ed etichettare gli spigoli aggiunti con un numero grandissimo (normalmente: almeno due volte la somma delle etichette già presenti), e procedere c.s.
E in questo modo due problemi apparentemente differenti possono essere affrontati con gli stessi algoritmi
Il Problema del Commesso Viaggiatore è quello di trovare un percorso che colleghi tutte le località dove il commesso viaggiatore ha clienti, passando da ciascuna una sola volta e tornando al punto di partenza (dove il commesso viaggiatore abita). In termini di grafi, consiste nel trovare un ciclo hamiltoniano, che è un problema NP-completo.
Il Problema del Percorso Minimo è quello di trovare il percorso più breve che colleghi tutte le località, per esempio l'autobus che deve passare per tutti i paesi; in questo caso le strade sono già date. In termini di grafi, consiste nel trovare un ciclo hamiltoniano di peso minimo di un grafo etichettato (non orientato), ed è anch'esso un problema NP-completo.
Ovviamente non sono definiti solo su grafi completi. Ma sono problemi affini, e la loro generalizzazione sui grafi completi li rende più facili da affrontare, anche se da un punto di vista computazionale non otteniamo alcun vantaggio. Per dire:
- trovare un ciclo hamiltoniano in un grafo equivale a etichettare (sugli spigoli) il grafo originale con 0 per ogni spigolo e 1 per ogni spigolo aggiunto, e cercare un ciclo hamiltoniano di peso 0.
- trovare un ciclo hamiltoniano minimo in un grafo dato equivale a completare il grafo ed etichettare gli spigoli aggiunti con un numero grandissimo (normalmente: almeno due volte la somma delle etichette già presenti), e procedere c.s.
E in questo modo due problemi apparentemente differenti possono essere affrontati con gli stessi algoritmi
ti rigrazio
ma te diversifichi ulteriormente il problema:
- TSP con graco pesato
- TSP con grafo generico che equivale ad un ciclo hamiltoniano.
secondo me quello che chiami Commesso Viaggiatore è il problema del Ciclo Hamiltoniano, invece quello del Percorso Minimo è il TSP. Ma comunque mi hai chiarito il dubbio principale che i problemi sono usati su grafi completi solo per semplificare le cose. Tank
ma te diversifichi ulteriormente il problema:
- TSP con graco pesato
- TSP con grafo generico che equivale ad un ciclo hamiltoniano.
secondo me quello che chiami Commesso Viaggiatore è il problema del Ciclo Hamiltoniano, invece quello del Percorso Minimo è il TSP. Ma comunque mi hai chiarito il dubbio principale che i problemi sono usati su grafi completi solo per semplificare le cose. Tank
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo