The Dark Side of Hardware Upgrade Forum

Ho un grafo G orientato rappresentato con liste di adiacenza.

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?

scapezzola

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.

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?


@instantempo
non ho idea di cosa rappresenti

dovrebbe essere un teorema sulle probabilità condizionate

So cosa è, ma non so cosa rappresenti in questo caso.

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.

Ho scoperto che non risolve il problema.

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)

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?

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 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

EDIT double

Probabilmente esiste un metodo furbo, ma ora come ora non mi viene in mente.

All'esame eravamo in 20, nessuno ne è venuto a capo.

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.

un algoritmo goloso?

ah no, è orientato.

niente allora

Cavallo 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'è

Il prof ha confermato la mia teoria

30 all'esame vista anche la disamina fatta

Però mi ha appena detto che se voglio la lode devo portargli Karp e Fulkerson che non ha fatto a tempo a spiegarli anche se erano da programma.






So solo che riguardano il flusso, sapete darmi un grado di difficoltà rispetto a vertex cover, dijkstra e comunque la roba più comune?

Edmonds-Karp è una modifica del Ford-Fulkerson, non sono proprio algoritmi diversi IIRC.
Diciamo che ford fulkerson è sul livello di Dijkstra, una volta capito bene il problema del flusso.

Ok, nel caso nei prossimi giorni studiando non capissi qualcosa verró qui. Per ora l'attenzione è tutta concentrata sui SGBDR.