Teoria dell'NP-completezza.
Sto studiando la materia per un corso universitario,e mi affascina molto. Vi propongo due problemi non banali ma neanche impossibili se uno conosce le basi dell'argomento.
Tassista disonesto: Avete una città, formata da $n$ quartieri, tutti distanti (per semplicità) $1$ kilometro (o litro, o anno-luce, non cambia). Siete un tassista che dovete accompagnare un cliente dal quartiere $i$ al quartiere $j$, e volete farlo cercando di guadagnare il più possibile, senza però che il cliente se ne accorga, quindi non dovete ripassare per lo stesso quartiere più volte. La versione decisionale del problema è la seguente: Dati un insieme di $n$ quartieri e un intero $k$, dire se esiste un cammino da il quartiere $i$ al quartiere $j$ lungo ALMENO $k$ che non ripassi per nessun quartiere già visitato.
Dimostrare che tale problema appartiene a $NP-C$, ovvero che appartiene a NP (esiste un efficiente verificatore) e che ogni altro problema di NP si può ridurre polinomialmente a lui.
Tassista onesto: Avete la stessa città, solo che stavolta siete un sant'uomo, che vuol ondurre il cliente alla meta percorrendo la minor distanza possibile. La versione decisionale è la seguente:Dati un insieme di $n$ quartieri e un intero $k$, dire se esiste un cammino da il quartiere $i$ al quartiere $j$ lungo AL MASSIMO $k$ che non ripassi per nessun quartiere già visitato.
Dimostrare che tale problema appartiene a $P$, cioè che esiste un algoritmo di complessità polinomiale rispetto alla dimensione dell'input che risolve il problema.
Buon divertimento!
Tassista disonesto: Avete una città, formata da $n$ quartieri, tutti distanti (per semplicità) $1$ kilometro (o litro, o anno-luce, non cambia). Siete un tassista che dovete accompagnare un cliente dal quartiere $i$ al quartiere $j$, e volete farlo cercando di guadagnare il più possibile, senza però che il cliente se ne accorga, quindi non dovete ripassare per lo stesso quartiere più volte. La versione decisionale del problema è la seguente: Dati un insieme di $n$ quartieri e un intero $k$, dire se esiste un cammino da il quartiere $i$ al quartiere $j$ lungo ALMENO $k$ che non ripassi per nessun quartiere già visitato.
Dimostrare che tale problema appartiene a $NP-C$, ovvero che appartiene a NP (esiste un efficiente verificatore) e che ogni altro problema di NP si può ridurre polinomialmente a lui.
Tassista onesto: Avete la stessa città, solo che stavolta siete un sant'uomo, che vuol ondurre il cliente alla meta percorrendo la minor distanza possibile. La versione decisionale è la seguente:Dati un insieme di $n$ quartieri e un intero $k$, dire se esiste un cammino da il quartiere $i$ al quartiere $j$ lungo AL MASSIMO $k$ che non ripassi per nessun quartiere già visitato.
Dimostrare che tale problema appartiene a $P$, cioè che esiste un algoritmo di complessità polinomiale rispetto alla dimensione dell'input che risolve il problema.
Buon divertimento!
Risposte
una cosa non mi è chiara: che cosa significa "tutti distanti 1"? vuol dire
il quartiere i dista dal quartiere j "1" per ogni i e per ogni j ?
come sono disposti i quartieri?
ciao.
il quartiere i dista dal quartiere j "1" per ogni i e per ogni j ?
come sono disposti i quartieri?
ciao.
I quartieri non hanno una dislocazione particolare, intendili se vuoi come incroci semaforici, e le distanze valgono uno nel senso che per ogni $i$ e per ogni $j$, se i quartieri $i$ e $j$ sono collegati da una strada, allora tale strada è lunga $1$. Ma non è detto che esista una tale strada, altrimenti il problema del tassista onesto sarebbe sempre risolubile per ogni $k$ intero positivo.
Il grafo che rappresenta questo problema non è quindi un grafo completo, a differenza per esempio di quello rappresentante un'istanza del TSP, problema del commesso viaggiatore.
Se hai domande chiedi pure.
Precisazione: $k$ è un intero positivo.
Il grafo che rappresenta questo problema non è quindi un grafo completo, a differenza per esempio di quello rappresentante un'istanza del TSP, problema del commesso viaggiatore.
Se hai domande chiedi pure.
Precisazione: $k$ è un intero positivo.
non riesco a non pensare alla "metrica di Mosca"... 1 punto centrale e tante strade lunghe 1/2 che si dipartono dal centro...
solo che io intendo distanza 1 per strada più breve che collega 2 quartieri lunga 1.
se dici "non è detto che esista una tale strada"... francamente mi spiazza.
che cosa intendi? solo che non è detto che esistano k*(k-1)/2 collegamenti, immagino...
solo che io intendo distanza 1 per strada più breve che collega 2 quartieri lunga 1.
se dici "non è detto che esista una tale strada"... francamente mi spiazza.
che cosa intendi? solo che non è detto che esistano k*(k-1)/2 collegamenti, immagino...
Non so cosa ci sia di non chiaro, a Mosca non ci sono mai stato...
Dall'incrocio $i$ partono $s_i$ strade, $s_i<=n-1$,ognuna lunga $1$ kilometro, che portano a $s_i$ incroci $x_1, x_2, ...x_s_i$, da ognuno dei quali partono $s_x_i$ (intero minore uguale di n) altre strade, sempre lunghe $1$. Se vuoi gli incroci sono nodi di un grafo non completo pesato, con tutti i pesi uguali a $1$. Da ogni nodo partono un numero varaibile di archi, al massino $n-1$. Ovviamente in tutto gli archi possono essere meno di $((n),(2))$. Cosi va meglio? Ma si perde molto del gusto del tassista!
Dall'incrocio $i$ partono $s_i$ strade, $s_i<=n-1$,ognuna lunga $1$ kilometro, che portano a $s_i$ incroci $x_1, x_2, ...x_s_i$, da ognuno dei quali partono $s_x_i$ (intero minore uguale di n) altre strade, sempre lunghe $1$. Se vuoi gli incroci sono nodi di un grafo non completo pesato, con tutti i pesi uguali a $1$. Da ogni nodo partono un numero varaibile di archi, al massino $n-1$. Ovviamente in tutto gli archi possono essere meno di $((n),(2))$. Cosi va meglio? Ma si perde molto del gusto del tassista!
così ho una visione di un normalissimo grafo connesso (magari ad albero, ma non necessariamente), ma non mi spiego come fa ad essere 1 la distanza tra $i$ ed uno dei successivi incroci collegati con $x_1$, ad esempio.
per questo ho chiesto in precedenza se dist(i,j) dovesse essere 1 per ogni i e per ogni j...
non so se è chiaro il mio dubbio.
per questo ho chiesto in precedenza se dist(i,j) dovesse essere 1 per ogni i e per ogni j...
non so se è chiaro il mio dubbio.
"adaBTTLS":.
così ho una visione di un normalissimo grafo connesso (magari ad albero, ma non necessariamente), ma non mi spiego come fa ad essere 1 la distanza tra $i$ ed uno dei successivi incroci collegati con $x_1$,
Non è detto che i nodi $i$ e $x_1$ siano collegati da un arco. Puoi comunque arrivare dal nodo $i$ al nodo$x_1$ passando da altri nodi (incroci), se attraversi altri $t$ nodi prima di raggiungere $x_1$ avrai percorso $t+1$ kilometri. Ne percorri solo $1$ se e solo se c'è un arco fra i due nodi, ossia una strada fra i due incroci. Nesunso ha detot che per ogni i e per ogni j i nodi i e j sono collegati. Forse sono stato poco chiaro in precedenza. Esempio:
Un nodo indica un incrocio e ogni arco una strada lunga $1$ kilometro.
Esiste un percorso del tassista onesto da $1$ a $9$ lungo al massimo $3$ kilometri? Si, tale percorso è 1-2-4-9.
Non esiste invece alcun percorso lungo al massimo $2$ kilometri.
Esiste un modo, sullo stesso punto di partenza e di arrivo, di far guadagnare al tassista disonesto almeno l'equivalente di $6$ kilometri? Si ,e tale percorso è 1-5-6-2-3-8-9
Mi dispiace di non riuscire a spiegarmi, non è un buon segno.
quindi si tratta semplicemente di un grafo connesso con n nodi ed un numero di archi (non precisato) compreso tra (n-1) e n*(n-1)/2.
ogni arco misura 1. la distanza tra due nodi è quindi [NO comunque 1, ma] pari al numero degli archi che "DEVONO essere percorsi" per arrivare ad uno partendo dall'altro.
non credo si possa dare una risposta in termini numerici.
se l'argomento è informatica, ha qualche cosa a che fare con algoritmi (tipo PRIM e KRUSKAL)?
... ai miei tempi (ormai sono passati 20 anni "abbondanti"...) ho presentato una tesina su questi argomenti per il corso di "teoria della programmazione per le macchine calcolatrici"... se si tratta proprio di questo, "tolgo il disturbo".
ciao.
ogni arco misura 1. la distanza tra due nodi è quindi [NO comunque 1, ma] pari al numero degli archi che "DEVONO essere percorsi" per arrivare ad uno partendo dall'altro.
non credo si possa dare una risposta in termini numerici.
se l'argomento è informatica, ha qualche cosa a che fare con algoritmi (tipo PRIM e KRUSKAL)?
... ai miei tempi (ormai sono passati 20 anni "abbondanti"...) ho presentato una tesina su questi argomenti per il corso di "teoria della programmazione per le macchine calcolatrici"... se si tratta proprio di questo, "tolgo il disturbo".
ciao.
"adaBTTLS":
quindi si tratta semplicemente di un grafo connesso con n nodi ed un numero di archi (non precisato) compreso tra (n-1) e n*(n-1)/2.
ogni arco misura 1. la distanza tra due nodi è quindi [NO comunque 1, ma] pari al numero degli archi che "DEVONO essere percorsi" per arrivare ad uno partendo dall'altro.
non credo si possa dare una risposta in termini numerici.
se l'argomento è informatica, ha qualche cosa a che fare con algoritmi (tipo PRIM e KRUSKAL)?
... ai miei tempi (ormai sono passati 20 anni "abbondanti"...) ho presentato una tesina su questi argomenti per il corso di "teoria della programmazione per le macchine calcolatrici"... se si tratta proprio di questo, "tolgo il disturbo".
ciao.
Si hai capito mi dispiace non essermi spiegato prima. Conosci il sinigificato di NP-COMPLETO? DI NP? Sennò su wikipedia c'è quanto basta.
Le cose che hai detto te non ho idea di cosa siano, per questi problemi si tratta di:
-trovare un algoritmo di tempo polinomiale rispetto alla dimensione dell'input che risolva il problema del tassita onesto.
-dimostrare che il problema del tassista disonesto è NP-completo, dimostrare cioè che un altro problema NP-COMPLETO si può ridurre polinomialmente a lui.
grazie. se ci fosse qualcosa di poco chiaro nei miei vecchi testi, ricorrerò a wikipedia.
approfitto per chiederti un'ultima cosa:
hai detto che non si torna in un quartiere dove si è già passati: questo esclude che si possa ripercorrere almeno una parte di un arco già percorso (magari in senso inverso) perché al contrario di quanto avevo ipotizzato inizialmente è da escludere un grafo che mi ricordava la "metrica di Mosca"? mi spiego meglio:
il grafico non è "intrecciato", ma ad ogni bivio c'è un quartiere...
visto che non so fare i grafici, ti descrivo a parole uno semplice che, mentre doveva essere l'unico plausibile secondo l'errata interpretazione, in realtà dovrebbe essere da escludere: n quartieri ai vertici di un poligono di n lati, inscritto in una circonferenza di raggio 1/2 ed n strade che collegano i vari quartieri con il centro (dove non c'è un quartiere).
grazie per l'attenzione e la pazienza. ciao.
approfitto per chiederti un'ultima cosa:
hai detto che non si torna in un quartiere dove si è già passati: questo esclude che si possa ripercorrere almeno una parte di un arco già percorso (magari in senso inverso) perché al contrario di quanto avevo ipotizzato inizialmente è da escludere un grafo che mi ricordava la "metrica di Mosca"? mi spiego meglio:
il grafico non è "intrecciato", ma ad ogni bivio c'è un quartiere...
visto che non so fare i grafici, ti descrivo a parole uno semplice che, mentre doveva essere l'unico plausibile secondo l'errata interpretazione, in realtà dovrebbe essere da escludere: n quartieri ai vertici di un poligono di n lati, inscritto in una circonferenza di raggio 1/2 ed n strade che collegano i vari quartieri con il centro (dove non c'è un quartiere).
grazie per l'attenzione e la pazienza. ciao.
"adaBTTLS":
grazie. se ci fosse qualcosa di poco chiaro nei miei vecchi testi, ricorrerò a wikipedia.
approfitto per chiederti un'ultima cosa:
hai detto che non si torna in un quartiere dove si è già passati: questo esclude che si possa ripercorrere almeno una parte di un arco già percorso (magari in senso inverso) perché al contrario di quanto avevo ipotizzato inizialmente è da escludere un grafo che mi ricordava la "metrica di Mosca"? mi spiego meglio:
il grafico non è "intrecciato", ma ad ogni bivio c'è un quartiere...
visto che non so fare i grafici, ti descrivo a parole uno semplice che, mentre doveva essere l'unico plausibile secondo l'errata interpretazione, in realtà dovrebbe essere da escludere: n quartieri ai vertici di un poligono di n lati, inscritto in una circonferenza di raggio 1/2 ed n strade che collegano i vari quartieri con il centro (dove non c'è un quartiere).
grazie per l'attenzione e la pazienza. ciao.
Non , questo grafo non c'incastra nulla con l'istanza del problema. Ogni arco collega un nodo a un solo altro nodo, e una volta partito dal nodo di partenza arriva "a destinazione" senza biforcarsi in alcun modo.
OK. tutto chiaro. l'argomento (ambito di applicazione) è quello che pensavo. gli algoritmi citati però riguardano un'altra cosa (minimo albero ricoprente).
prossimamente, quando avrò un po' di tempo, vedrò se può interessarmi ed essere alla mia portata. ciao.
prossimamente, quando avrò un po' di tempo, vedrò se può interessarmi ed essere alla mia portata. ciao.
hint:
altro hint:
altro hint:
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo