Newsgroup: it.lavoro.informatica
Titolo: vi offro occasione di dimostrare la vostra cultura sulla teoria dei grafi :-)

ciao a tutti
la teoria dei grafi l'ho incrociata solo di sfuggita, per cui se scrivo
cazzate dal punto di vista della terminologia, chiedo venia in anticipo.
cmq:
 - il grafo completo (mi pare si dica così: ciascun nodo è connesso
direttamente a tutti gli altri)
 - ogni arco ha un suo peso, noto in partenza
 - mi serve il cammino minimo per la copertura di tutti i nodi
orbene, che algoritmo si usa? mi dicono "algoritmo di kruskal", ma non con
troppa convinzione.
qualcuno mi sa aiutare?
d.
-- 
Sai quelli che dicono: «Uno torna la sera a casa stanco...».
«Che strazio questo che torna sempre a casa stanco. Lo detesto.
Ma non tornare a casa! Sei stanco? Muori!»  ###  E. Vaime
http://www.pilardeimeli.net/blog

  - il grafo completo
il grafo E' completo


  - mi serve il cammino minimo per la copertura di tutti i nodi
Puoi usare lo stesso arco, o lo stesso nodo, piu' volte?
per esempio, se hai un sacco di archi di peso 1000000 e qualcuno di
peso 1, sarebbe
meglio usare quelli da 1 per quanto possibile, anche piu' volte.

i pesi possono essere negativi?

 
commesso viaggiatore
-- 
FabMind

 commesso viaggiatore
In quello non c'e' la limitazione che devi visitare ogni nodo
esattamente una volta?


Faccio sommessamente notare che Beccoblu ha scritto cammino minimo.

 d.
Kruskal trova l'albero ricoprente di peso minimo, ossia coprire tutti i
nodi del grafo con gli archi  la cui somma dei pesi è più piccola
possibile. Se devi trovare un cammino minimo da un nodo ad un'altro puoi
usare Dijkstra ,se i pesi degli archi sono tutti positivi,  o Ford
(Shortest-Path) altrimenti. Nota che devi selezionare un nodo sorgente s e
trovi l'albero dei cammini minimi da s a qualsiasi altro nodo. Se la
sorgente cambia devi riapplicare l'algoritmo.
 
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 Faccio sommessamente notare che Beccoblu ha scritto cammino minimo.
E "cammino" esclude il riutilizzo dei nodi? (in inglese un "path" non
puo' avere nodi ripetuti,
un "walk" si'. Almeno secondo la mia copia di Bollobas)

Adam Atkinson ha scritto:



Esattamente. Se i pesi degli archi sono tutti positivi, un percorso da un
nodo ad un'altro sarà perforza aciclico, dunque un cammino. 


 Esattamente. Se i pesi degli archi sono tutti positivi, un percorso MINIMO 


 nodo ad un'altro sarà perforza aciclico, dunque un cammino.
Non seguo. Un "cammino" non ha nodi ripetuti per definizione?
Se abbiamo uno spanning tree fatto da archi di lunghezza 1, e tutti
gli altri archi hanno
lunghezza 10^9, se fosse permesso riutilizzerei gli archi dello
spanning tree per andare
dappertutto.

 dappertutto.
Questo è un caso estermo, ma in generale l'albero ricoprente, radicato in
s, non è equivalente a quello dei cammini minimi, sempre radicato in s.
Sono due problemi diversi. 


 Sono due problemi diversi.
In ogni caso, sono d'accordo che il problema o e' quello del commesso
viaggiatore
o e' talmente simile che non c'e' comunque speranza.

 inglese viene scritto "acycle-path".
Scritto cosě significherebbe piů o meno "pista ciclabile" :-)
Semmai si parla di /acyclic-path/.
Ciao.

 Kruskal trova l'albero ricoprente di peso minimo, 
anche detto minimum spanning tree (o alberi di connessione minima).
Sempre nella categoria degli algoritmi greedy vedi anche l'algoritmo di 
Prim.
Per una implementazione della ricerca di un albero ricoprente di peso minimo
vedi, per esempio qui:
http://it.wikipedia.org/wiki/Algoritmo_Generico_per_la_creazione_di_un_MST
Se non puoi/vuoi passare più volte per lo stesso nodo stai sbattendo la 
testa su un
problema NP-completo (come dice giustamente fabmind vedi il problema del 
commesso
viaggiatore) e non ti rimane che la strada dell'enumerazione di tutti i 
possibili cammini...
operazione computazionalmente molto onerosa.
ciao! :)
G.