Ciclo hamiltoniano negli stati del cubo di rubik
questo è un problema che mi è stato posto da un amico, del quale sto cercando da tempo la soluzione.
faccio una minuscola intro, giusto per spiegare due cosette
il problema è: esiste un ciclo (o almeno un cammino) hamiltoniano su \(G\)?
a causa delle dimensioni gigantesche di \(G\) e della bassa valenza dei vertici, non è possibile applicare i teoremi di dirac, ore, posa, bondy-chvatal.
ho provato approcci tipo "se è n-partito allora..."
per lo stesso motivo, non è possibile un'analisi al computer del problema (non credo esistano computer in grado di rappresentare quel grafo, e se esistono di sicuro non li danno a me).
ho visto che ci sono molte congetture aperte al riguardo, quindi mi sa che è un problema piuttosto ostico. tuttavia, questo grafo è abbastanza "carino", dopotutto. (sì, lo so, anche petersen è carino all'apparenza...)
per esempio, si potrebbe applicare una versione (magari meno generale) della congettura di Lovasz?
sono nelle vostre mani, grazie a tutti
faccio una minuscola intro, giusto per spiegare due cosette
siano gli stati i vertici di un grafo \(G\) e siano le mosse possibili gli archi di \(G\). il grafo è transitivo sui vertici ed ogni vertice ha valenza \(18\).
il problema è: esiste un ciclo (o almeno un cammino) hamiltoniano su \(G\)?
a causa delle dimensioni gigantesche di \(G\) e della bassa valenza dei vertici, non è possibile applicare i teoremi di dirac, ore, posa, bondy-chvatal.
ho provato approcci tipo "se è n-partito allora..."
per lo stesso motivo, non è possibile un'analisi al computer del problema (non credo esistano computer in grado di rappresentare quel grafo, e se esistono di sicuro non li danno a me).
ho visto che ci sono molte congetture aperte al riguardo, quindi mi sa che è un problema piuttosto ostico. tuttavia, questo grafo è abbastanza "carino", dopotutto. (sì, lo so, anche petersen è carino all'apparenza...)
per esempio, si potrebbe applicare una versione (magari meno generale) della congettura di Lovasz?
sono nelle vostre mani, grazie a tutti
Risposte
il problema è: esiste un ciclo (o almeno un cammino) hamiltoniano su \(G\)?
La risposta è: non possiamo saperlo.
Non so cosa sia un "gruppo di permutazioni", ma è intuibile dalla riduzione del problema del cubo di rubik in versione ad automi (mi pare più appropriato se si parla di stati) che tale problema ha dimensione esponenziale.
Se si mastica un po' di algoritmica, si sa che il problema del ciclo hamiltoniano è un problema "difficile" e di soluzione ottima o dire SI/NO non se ne parla. Se si trovasse una soluzione con una congettura qualunque (come proponi te) si potrebbe anche pensare a proporre qualche nuova congettura al famoso P=NP.
per lo stesso motivo, non è possibile un'analisi al computer del problema (non credo esistano computer in grado di rappresentare quel grafo, e se esistono di sicuro non li danno a me).
per la rappresentazione del grafo direi ci si può anche stare, ma il problema è di calcolo non rappresentazione.
Se vuoi trovare una soluzione non ottima di un ciclo hamiltoniano si potrebbe parlare di algoritmi approssimati (e qua penso tu punti) o altre tecniche algoritmiche, ma della domanda che poni non puoi dire nulla (in tempo umano).
Bella domanda! Non so niente riguardo alla matematica del cubo di rubik. Ho provato a googlare un po' e non ho trovato una risposta definitiva alla questione, che comunque alcuni si sono posti prima di te. Ho trovato però questa pagina e questo thread di SO che suggeriscono l'utilizzo dei codici di Gray per provare a dirimere la questione.
EDIT: comunque nel thread di SO (che è dedicato ad un problema simile al tuo) la seconda risposta, che però non ho verificato, dice che è possibile attraversare in diversi modi con i codici di gray il cubo, quindi esiste un ciclo hamiltoniano
@ham_burst: credo tu non abbia ben chiare le nozioni di complessità strutturale: il problema di trovare un ciclo hamiltoniano in un grafo è sì un problema NP-completo e quindi si congettura che non esista un algoritmo effciente in grado di risolverlo, ma in questo caso si sta parlando di una singola istanza del problema. Anche se tale istanza ha una dimensione enorme, la difficoltà del problema non implica affatto la difficoltà della singola istanza. Es.: si suppone non esista un algoritmo polinomiale per factoring; però se ti do il numero $2^{1000^1000}$, per quanto enorme sia, sono convinto tu riesca a scrivermi in maniera corretta un programma in grado di fattorizzare quel numero in un nanosecondo.
Anche perché seguendo il tuo ragionamento non potrebbero esistere i SAT-solver, eppure ci sono e lavorano anche con input di dimensioni veramente grandi. Attenzione però che anche se dov'essere esistere problemi le cui istanze sono per la maggior parte difficili (i cosiddetti "hard on average" su cui è basata praticamente tutta la crittografia moderna) non si potrebbe comunque fare la riduzione "difficile il problema, quindi risolvere un'istanza di elevate dimensioni significa mettere in crisi la congettura P=NP"; questo perché se un problema è in NP avrà un certificato di lunghezza polinomiale, chissà, magari sono fortunato e tra i miliardi di possibilità lo azzecco e risolvo il problema sulla singola istanza. Ma ciò non ci aiuta per risolvere il problema nella sua generalità.
EDIT: comunque nel thread di SO (che è dedicato ad un problema simile al tuo) la seconda risposta, che però non ho verificato, dice che è possibile attraversare in diversi modi con i codici di gray il cubo, quindi esiste un ciclo hamiltoniano
@ham_burst: credo tu non abbia ben chiare le nozioni di complessità strutturale: il problema di trovare un ciclo hamiltoniano in un grafo è sì un problema NP-completo e quindi si congettura che non esista un algoritmo effciente in grado di risolverlo, ma in questo caso si sta parlando di una singola istanza del problema. Anche se tale istanza ha una dimensione enorme, la difficoltà del problema non implica affatto la difficoltà della singola istanza. Es.: si suppone non esista un algoritmo polinomiale per factoring; però se ti do il numero $2^{1000^1000}$, per quanto enorme sia, sono convinto tu riesca a scrivermi in maniera corretta un programma in grado di fattorizzare quel numero in un nanosecondo.
Anche perché seguendo il tuo ragionamento non potrebbero esistere i SAT-solver, eppure ci sono e lavorano anche con input di dimensioni veramente grandi. Attenzione però che anche se dov'essere esistere problemi le cui istanze sono per la maggior parte difficili (i cosiddetti "hard on average" su cui è basata praticamente tutta la crittografia moderna) non si potrebbe comunque fare la riduzione "difficile il problema, quindi risolvere un'istanza di elevate dimensioni significa mettere in crisi la congettura P=NP"; questo perché se un problema è in NP avrà un certificato di lunghezza polinomiale, chissà, magari sono fortunato e tra i miliardi di possibilità lo azzecco e risolvo il problema sulla singola istanza. Ma ciò non ci aiuta per risolvere il problema nella sua generalità.
"Deckard":
@ham_burst: credo tu non abbia ben chiare le nozioni di complessità strutturale: il problema di trovare un ciclo hamiltoniano in un grafo è sì un problema NP-completo e quindi si congettura che non esista un algoritmo effciente in grado di risolverlo, ma in questo caso si sta parlando di una singola istanza del problema.
naaa e infatti hai ragione
più che non averle ben chiare è che avevo proprio accantonato la possibilità delle istanze... diciamo che avevo la nebbia autunnale in testa (e siamo anche in inverno)
Comunque se messa in questi termini di "istanza" ha anche più senso studiarci proprietà, congetture e teoremi
"Deckard":
Bella domanda! Non so niente riguardo alla matematica del cubo di rubik. Ho provato a googlare un po' e non ho trovato una risposta definitiva alla questione, che comunque alcuni si sono posti prima di te. Ho trovato però questa pagina e questo thread di SO che suggeriscono l'utilizzo dei codici di Gray per provare a dirimere la questione.
EDIT: comunque nel thread di SO (che è dedicato ad un problema simile al tuo) la seconda risposta, che però non ho verificato, dice che è possibile attraversare in diversi modi con i codici di gray il cubo, quindi esiste un ciclo hamiltoniano
grazie! grazie mille!
sì, lo sapevo che era np-completo, cercavo proprio una risposta come la tua
riguardo il problema di calcolo/rappresentazione, supponiamo che ogni vertice del grafo occupi un solo bit. il tuo pc ha 4,3*10^19 bit? il mio no...
"albertobosia":
riguardo il problema di calcolo/rappresentazione, supponiamo che ogni vertice del grafo occupi un solo bit. il tuo pc ha 4,3*10^19 bit? il mio no...
se parliamo solo di rappresentazione direi che non ci sono troppi problemi. Se per capirci dici di rappresentare i vertici come una stringa di bit, perciò un intero e mettiamo tutta l'informazione del grafo si può capire: $10^19 ~~ 2^63$ cioè in $8Byte$ mettiamo l'intera informazione.
Poi se passiamo a livello di calcolo lo spazio del problema che sia esponenziale mi sembra ovvio, ma la rappresentazione dell'intero grafo, in altri problemi simili, nel momento del calcolo non è obbligatorio averla, ci sono tecniche che esplorano solo lo stato locale per poi spostarsi alla ricerca di una soluzione migliore (ricerca locale) senza memorizzare tutti gli stati.
Ma non ho capito esattamente cosa vuoi fare: ti basta semplicemente sapere se esiste o meno un ciclo hamiltoniano (e in questo caso non c'è bisogno di usare un computer che non riuscirebbe a darti la risposta in tempi sensati, ma bisogna dimostrarlo a mano ad es. usando i codici di Gray) oppure trovare questo ciclo hamiltoniano? Perché enumerare esplicitamente questo ciclo è praticamente impossibile: dovresti visitare un numero enorme di nodi. Quello che puoi fare al massimo è darne una rappresentazione implicita, ad esempio con un programma che dato in input uno stato del cubo ti calcoli lo stato successivo nel ciclo hamiltoniano. In questo caso non hai nessun bisogno di mantenere in memoria tutti gli stati del grafo se esiste una procedura ben definita che ti permette di passare da un vertice al successivo nel ciclo in modo immediato (non so se esista, però leggendo il commento che ti ho postato prima sembrerebbe di sì, bisognerebbe perdere un po' di tempo a verificarne la correttezza).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo