Re: vi offro occasione di dimostrare la vostra cultura sulla teoria dei grafi :-

Thompson wrote:
> beccoblu ha scritto:
>
>> 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.
>
> 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.
[ Auf dieses Posting antworten ]