Newsgroup: it.comp.programmare
Titolo: Elaborazione su grafo [sono impantanato]

Dato un grafo G non orientato, dovrei trovare N percorsi diversi (il più
possibile disgiunti) che nel complesso tocchino tutti i nodi.
Ogni arco contiene un peso P e ogni nodo un valore V.
Ciascun percorso, deve avere al massimo un peso TotP (dato dalla somma dei
pesi P) e un valore (dato dalla somma dei valori V)
quanto più possibile vicino a TotV senza superarlo. Ogni percorso ha un suo
TotP e TotV.
Lo scopo del programma è quello che nel complesso di tutti gli N percorsi
diversi, TotV sia massimo mentre TotP sia minimo.
Bene o male me la so costruire una routine che calcoli il percorso più corto
o che prenda i nodi con valore più alto.
Il mio problema è che:
1) Dette routine le sò costruire solo per un percorso alla volta senza
tenere in considerazione gli altri.
2) Non sò come mettere assieme la routine che da una parte massimizza il
valore e nello stesso tempo minimizza il percorso.
Accettasi di tutto: suggerimenti, link, titoli di libri, santini,
benedizioni...
Grazie

 benedizioni...
Mi pare un problema NP completo, che necessita di un approccio non 
deterministico per la soluzione. Mi orienterei verso gli algoritmi genetici 
(ma qui passo la palla a chi ne sa di più).
Ciao!
-- 
---
*************** | Have you ever retired a human by mystake?
*** Azathot *** |
*************** | To contact me, ask me gently. Thanks.

 o che prenda i nodi con valore più alto.
Ottimo, allora sei a metà strada... per quanto riguarda i percorsi
disgiunti, puoi creare un array G[NumNodi] che tenga il conto del
numero di percorsi che già passano per quel nodo: quando lanci la
tua routine per trovare il primo percorso l'array è tutto a zero,
e quando il percorso è stato trovato fai un bel G[Nodo]++ ai nodi
visitati. Per i successivi percorsi la tua routine (probabilmente
userai il backtracking, credo) preferirà sempre, nella scelta dei
nodi da visitare, quello con il minor numero di passaggi, cioè con
il G[ProssimoNodo] più basso fra quelli disponibili. In questo
modo avrai la garanzia che gli N percorsi trovati saranno "il
più possibile disgiunti".
Insomma così dovresti considerare, nella scelta del prossimo
nodo da cui passare, tre parametri (P, V e G) invece di due
soltanto. Ovviamente dovrai trovare un compromesso: non credo
che esista, in generale, un percorso che abbia contemporaneamente
il TotP e TogG minimi e il TotV massimo possibili.
Come decidere... beh questi son XXXXX tuoi :o)

 il TotP e TogG minimi e il TotV massimo possibili.
Il problema è stabilire quale sia il  compromesso:
Il tutto dovrebbe servire ad organizzare i camioncini che spediscono la
merce dal fornitore in giro per i negozi.
TotP sono i km che fà, TotV sono i chili di merce consegnata.
Tutta la merce ci stà sull'insieme dei camioncini, il problema è come
distribuirla. Alla fine devo consegnare tutta la merce facendo meno
chilometri possibili. Se si trattasse di un solo camioncino non ci sono
problemi, non riesco a capirmi su come distribuirla tra i vari camion.
Ipotizzando di avere un grafo più o meno a ragnatela, con in centro la
radice, potrei fare che i camioncini si muovono secondo cerchi concentrici:
il primo camioncino i negozi più vicini, l'ultimo quelli alla periferia.
Oppure potrei dividere i percorsi a spicchi come le fette di una torta,
oppure una via di mezzo in base alle vicinanze dei nodi.
Grazie Mille.

 oppure una via di mezzo in base alle vicinanze dei nodi.
Beh se come detto imponi un criterio di minima sovrapposizione dei 
percorsi, bene o male la settorizzazione la otterrai automaticamente.
Ma da quello che dici il punto è che i nodi devono essere
coperti TUTTI esaustivamente, da un "mazzo" di N percorsi
mediamente il più possibile brevi (e che si avvicinino il
più possibile alla condizione di pieno carico in modo da
minimizzare N, aggiungerei): a questo punto, secondo me
non ti conviene più procedere un percorso alla volta ma è
meglio creare i percorsi tutti insieme, con un algoritmo
che ad ogni iterazione aggiunga un nuovo nodo a ciascuno
degli N percorsi, scegliendolo in modo tale che chilometraggio
e carico siano il più possibile uguali per tutti i percorsi:
in questo modo hai la garanzia che nessun veicolo farà "troppi"
chilometri (tanto, se in un certo punto bisogna arrivarci per
forza, qualcuno il viaggio lo deve pur fare...)
Qualche idea sull'algoritmo: non dovrebbe essere
obbligatorio aggiungere ad ogni iterazione un nuovo nodo
al percorso: se le possibili scelte ad un certo punto di
un percorso sono tutte "troppo brutte", cioè troppo lunghe
e/o con troppo o troppo poco carico, il percorso potrebbe
"saltare un turno" e non ricevere una nuova tappa, in modo
da far crescere prima gli altri: così avrai un percorso
circa della stessa lunghezza degli altri ma con meno tappe.
Può darsi benissimo che per un nodo passino più percorsi e
che non sia possibile evitarlo: in questo caso il nodo
dovrebbe ricordare quale percorso lo ha rifornito: ti dà
un grado di libertà in più per ripartire in modo ottimale
i carichi fra i mezzi.
Altra idea, se il backtracking completo su tutti i passi
fosse troppo pesante computazionalmente, è di eseguirlo
solo sulle ultime K scelte.
Ancora, una volta trovata delle soluzioni (sicuramente
sub-ottime) il programma potrebbe provare a raffinarle,
tentando di scambiare spezzoni fra due o più percorsi
di una soluzione (o fra soluzioni diverse) nel tentativo
di ottenere un'altra soluzione globalmente migliore.
Qui forse puoi usare un algoritmo genetico.

 Grazie
si direbbe un problema di programmazione lineare su grafi, ti consiglierei
di dare un'occhiata all'algoritmo del simplesso su grafi, potrebbe fare al
caso tuo. 
ciao 

 Qui forse puoi usare un algoritmo genetico.
Cosa intendi?
Potrebbe in qualche modo aiutarmi studiarmi un pochino le reti neurali e
automi cellulari che
se non sbaglio dovrebbero a servire per fare simulazioni?
Grazie



Inizialmente lo avevo scartato, proverò a rivederlo.
Grazie