Algoritmo per calcolare la media lunghezza di un semplice percorso
-
29-09-2020 - |
Domanda
Dato un grafico collegato e due nodi s e T, possono esserci molti percorsi semplici diversi (senza cicli) da s a t.C'è un algoritmo efficiente per trovare la lunghezza media di questi percorsi?
Soluzione
Immagino che tu sappia già che un algoritmo polinomiale per il conteggio del numero di percorsi semplici tra due nodi implicherebbe P= NP, questo risultato è dovuto a Valiant (la complessità dei problemi di enumerazione e affidabilità, 1979).
Ora immagina, aspettando di scoprire una contraddizione, che potresti calcolare $ \ text {avg} (g, u, v) $ in tempo polinomiale. .
Let $ G + L $ Sii il grafico derivante dall'aggiunta di un semplice percorso di lunghezza $ l $ tra $ U $ e $ V $ in $ g $ . Questo nuovo percorso è realizzato in $ L-1 $ Nuovi nodi e non interferisce con qualsiasi percorso precedente da $ U $ a $ V $ , fornito $ l \ geq 2 $ .
quindi, $ \ text {avg} (G + 3, u, v) - \ text {avg} (G + 2, u, v) $ = $ 1 / (\ # \ testo {percorsi} (g, u, v) +1) $ , da cui è possibile ottenere $ \ # \ testo {percorsi} (g, u, v) $ in tempo polinomiale. Ma sappiamo che questo non ci si può aspettare che sia fatto in tempo polinomiale, una contraddizione.