Ciao a tutti
Qualcuno riuscirebbe a spiegarmi una soluzione adatta a questo problema?
https://cms.di.unipi.it/#/task/ois_miglia/statement
Grazie mille
Riassumendo il problema: dato un grafo pesato, devi trovare un percorso composto da esattamente K archi che parta ed arrivi nel nodo 0, con lunghezza massima.
Cerchiamo di definire la funzione f(u,k), funzione che ritorna la lunghezza del massimo percorso che parte dal nodo u, attraversa k archi e termina nel nodo 0.
Chiaramente f(0,0) = 0, in quanto non possiamo percorrere archi; siamo costretti a rimanere fermi, quindi la risposta è 0.
Possiamo anche osservare che f(v,0) \nexists \forall v \neq 0. Infatti non esistono percorsi che attraversano 0 archi che partono da un nodo v\neq0 ed arrivano in 0. Per comoditĂ , visto che dobbiamo massimizzare la funzione, possiamo decidere che f(v,0) = -\infty \forall v \neq 0.
Ora possiamo definire f(u,k) = \max_{v: (u,v) \in E} f(v,k-1)+d(u,v) dove d(u,v) è la lunghezza dell’arco che va da u a v.
La risposta al problema è quindi -chiaramente- f(0,K).
La complessità ? la funzione ricorsiva così come è potrebbe essere esponenziale, ma è semplice vedere come ci siano soltanto |V|\cdot K diverse chiamate alla funzione, è quindi possiamo usare la memoizzazione. Calcolare f(v,k) ha complessità pari al grado di v, quindi la complessità totale è O(|E|\cdot K).
1 Mi Piace
Grazie mille, bellissima soluzione