Grafi e cammino semplice per 3 vertici
#1
Posted 06 July 2011 - 14:30
Devo trovare un cammino semplice tra due vertici X e Z passante per un vertice intermedio Y.
Algoritmo polinomiale in pseudocodice. Basta dire se esista, quindi una funzione booleana.
Attenzione al fatto che il cammino deve essere semplice, ovvero ogni vertice deve comparire una volta sola.
In b4: visita da X a Y, visita da Y a Z. E vi chiedo, per i cicli con z prima di Y?
#3
Posted 06 July 2011 - 14:34
scapezzola
#4
Posted 06 July 2011 - 14:43
Per evitare di visitare Z prima di Y basta marcarlo come non visitabile nel grafo da subito quando fai le visite da X->Y e smarcarlo una volta arrivato a Y.
#5 Guest__*
Posted 06 July 2011 - 14:54
#6
Posted 06 July 2011 - 15:01
mmm, però allora quando cerco il cammino tra Y e Z devo marcare non visitabile tutti gli altri vertici trovati nel cammino X->Y. Mi chiedo se esista un caso in cui ciò non mi permette di risolvere il problema, ma a naso direi di no...Il metodo più semplice è fare quello che dici, cioè X->Y, Y->Z.
Per evitare di visitare Z prima di Y basta marcarlo come non visitabile nel grafo da subito quando fai le visite da X->Y e smarcarlo una volta arrivato a Y.
EDIT Io faccio sta visita BFS o DFS che sia tra X e Y. Mi devo segnare i vertici appartenenti al cammino tra X e Y. Il problema è che l'albero che mi genero mi necessita un casino per poter trovare quei vertici, dato che poi lo devo rileggere e segnare solo quelli che mi vanno dalla sorgente fino a Y. Dico bene?
@instantempo
non ho idea di cosa rappresenti
#7
Posted 06 July 2011 - 15:08
non ho idea di cosa rappresenti
dovrebbe essere un teorema sulle probabilità condizionate
El sueño de la razón produce monstruos
#8
Posted 06 July 2011 - 15:19
So cosa è, ma non so cosa rappresenti in questo caso.
?[/url]":1g8c2frj]
non ho idea di cosa rappresenti
dovrebbe essere un teorema sulle probabilità condizionate
#9
Posted 06 July 2011 - 15:38
mmm, però allora quando cerco il cammino tra Y e Z devo marcare non visitabile tutti gli altri vertici trovati nel cammino X->Y. Mi chiedo se esista un caso in cui ciò non mi permette di risolvere il problema, ma a naso direi di no...
EDIT Io faccio sta visita BFS o DFS che sia tra X e Y. Mi devo segnare i vertici appartenenti al cammino tra X e Y. Il problema è che l'albero che mi genero mi necessita un casino per poter trovare quei vertici, dato che poi lo devo rileggere e segnare solo quelli che mi vanno dalla sorgente fino a Y. Dico bene?
In realtà un caso esiste, quello in cui un nodo W è l'unico modo per raggiungere sia Y che Z.
Comunque sì, devi farti un giro per il grafo a smarcare tutti i nodi che non siano sul percorso tra X e Y.
#10
Posted 06 July 2011 - 15:38
Ho scoperto che non risolve il problema.Il metodo più semplice è fare quello che dici, cioè X->Y, Y->Z.
Per evitare di visitare Z prima di Y basta marcarlo come non visitabile nel grafo da subito quando fai le visite da X->Y e smarcarlo una volta arrivato a Y.
Guarda questo grafo
Ipotesi: la visita iniziale mi trova come cammino XY quello passante per A e non per B.
Se mi segno Z e mi trovo X->A->Y, poi trovo Y->A->Z e non è semplice.
Se mi segno tutti i vertici del cammino tra X e Y per non usarli, ovviamente non trovo il cammino tra X e Z perchè non ho a disposizione A.
Il problema di fondo è beccare il cammino X-B-Y, ma quello è casuale, dipende dalla visita e dagli ordini delle liste di adiacenza. So?
EDIT abbiano postato insieme. Il tuo W sarebbe il mio A (anche se in reatà Y è raggiungibile anche da B, che ho inserito appunto per citare il problema dell'ultima riga, ovvero trovare il "giusto" cammino verso Y)
#11
Posted 06 July 2011 - 16:04
Ipotesi: la visita iniziale mi trova come cammino XY quello passante per A e non per B.
Se mi segno Z e mi trovo X->A->Y, poi trovo Y->A->Z e non è semplice.
Se mi segno tutti i vertici del cammino tra X e Y per non usarli, ovviamente non trovo il cammino tra X e Z perchè non ho a disposizione A.
Il problema di fondo è beccare il cammino X-B-Y, ma quello è casuale, dipende dalla visita e dagli ordini delle liste di adiacenza. So?
Precalcolare tutte le strade alternative X->Y e Y->Z, memorizzarle in una lista (od un albero per velocizzare la ricerca), e cercarne due che non collidano?
#12
Posted 06 July 2011 - 16:07
Aka: fissa un cammino X-Y; poi prova tutti i cammini Y-Z; se non soddisfa l'ipotesi passa al prox cammino X-Y.
?[/url]":35xqs0oa]
Ipotesi: la visita iniziale mi trova come cammino XY quello passante per A e non per B.
Se mi segno Z e mi trovo X->A->Y, poi trovo Y->A->Z e non è semplice.
Se mi segno tutti i vertici del cammino tra X e Y per non usarli, ovviamente non trovo il cammino tra X e Z perchè non ho a disposizione A.
Il problema di fondo è beccare il cammino X-B-Y, ma quello è casuale, dipende dalla visita e dagli ordini delle liste di adiacenza. So?
Precalcolare tutte le strade alternative X->Y e Y->Z, e cercare due che non collidano?
Aka: fai la permutazioni di tutti i bioparco elementi della lista di adiacenza.
E quindi, per concludere: come pensavo oggi all'esame mi hanno chiesto di risolvere in tempo polinomiale un problema np (che presumo sia completo non essendo hard ma non me ne tiene di dimostrarlo, anche perchè non ne sarei in grado).
Good, mi hanno solo chiesto di vincere un nobel insomma
#13
Posted 06 July 2011 - 16:07
#14
Posted 06 July 2011 - 16:09
Aka: fissa un cammino X-Y; poi prova tutti i cammini Y-Z; se non soddisfa l'ipotesi passa al prox cammino X-Y.
Aka: fai la permutazioni di tutti i bioparco elementi della lista di adiacenza.
E quindi, per concludere: come pensavo oggi all'esame mi hanno chiesto di risolvere in tempo polinomiale un problema np (che presumo sia completo ma non me ne tiene di dimostrarlo, anche perchè non ne sarei in grado).
Good, mi hanno solo chiesto di vincere un nobel insomma
Probabilmente esiste un metodo furbo, ma ora come ora non mi viene in mente.
#15
Posted 06 July 2011 - 16:12
All'esame eravamo in 20, nessuno ne è venuto a capo.
?[/url]":1zvvq8r3] Aka: fissa un cammino X-Y; poi prova tutti i cammini Y-Z; se non soddisfa l'ipotesi passa al prox cammino X-Y.
Aka: fai la permutazioni di tutti i bioparco elementi della lista di adiacenza.
E quindi, per concludere: come pensavo oggi all'esame mi hanno chiesto di risolvere in tempo polinomiale un problema np (che presumo sia completo ma non me ne tiene di dimostrarlo, anche perchè non ne sarei in grado).
Good, mi hanno solo chiesto di vincere un nobel insomma
Probabilmente esiste un metodo furbo, ma ora come ora non mi viene in mente.
Il prof, dopo che a 5 minuti dalla fine gli ho presentato questi problemi, non ne è venuto a capo.
Io e un altro (che siamo i best là in mezzo ) ci siamo stati a pensare altre e 4 ore e non ne siamo venuti a capo, ma stavamo riconducendolo a un K-Sat dopo varie analisi.
Mi pare dura che ci sia un modo "furbo", anche in tempo polinomiale.
In ogni caso, mi hai confermato il ragionamento che ho fatto, quindi il tuo contributo è stato più che positivo.
Se qualcuno ha qualche altra idea la condivida pure.
#16
Posted 06 July 2011 - 20:01
FIRMA FOTTUTAMENTE EDITATA. IL FOTTUTO STAFF.
Mai più giorni felici
#17
Posted 06 July 2011 - 20:02
niente allora
FIRMA FOTTUTAMENTE EDITATA. IL FOTTUTO STAFF.
Mai più giorni felici
#18
Posted 06 July 2011 - 22:35
Cavallo goloso?un algoritmo goloso?
Boh, per ora non ho altre idea, le ho provate a pensare tutte.
Il fatto che il prof ancora non mi abbia risposto alla mail mi fa ben sperare sulla mia teoria. Anche se sicuramente la piglio al culo per quanto riguarda il voto dell'esame, ma tant'è http://www.hwupgrade...tyle_emoticons/default/okay.png
#19
Posted 08 July 2011 - 19:10
30 all'esame vista anche la disamina fatta
#20
Posted 09 July 2011 - 13:37
Attenti al cane