Newsgroup: it.scienza.informatica
Titolo: Suggerimento percorso consigliato

Dovrei realizzare un metodo che mi consenta la creazione di un percorso
consigliato all'interno del museo, cioč ogni stanza del museo č
contrassegnata da un periodo storico, un visitatore quando entra nel museo
rilascia il periodo storico preferito, il metodo prende il periodo storico e
fornisce un percorso che parte con l'ingresso e finisce con l'uscita e al
cui interno ci sono tutte le stanze con il periodo storico preferito
dall'utente(ovviamente ogni stanza č caratterizzata da un periodo storico).
Io ho implementato l'algoritmo di Dijkstra per determinare il percorso
minimo tra 2 stanze del museo senza perň che c'entrino nulla i periodi
storici associati alle stanze, potrebbe essermi utile partire da questo?
Qualcuno ha qualche idea?
Grazie.


Qualcuno forse ti potra' dare qualche suggerimento piu'
appropriato, perche' questo problema e' abbastanza interessante
da essere probabilmente stato studiato in passato, ed avere anche
un nome suo.
Non avendo tempo di farti una ricerca bibliografica, ti butto li'
qualche osservazione.
Nella sua generalita' questo problema mi sembra NP-completo,
perche' il Problema del Commesso Viaggiatore (TSP) e' un suo
sottoproblema, che si ottiene "scegliendo" tutte le stanze e
ponendo la distanza ingresso-uscita uguale a 0.
Quindi direi che la ricerca della soluzione ottima se le stanze
sono tante e quelle scelte sono tante (ovvero un numero non costante...)
e' in generale dispendiosa.
Naturalmente se le stanze scelte sono solo, per esempio, 3, allora
puoi considerare le possibili sequenze (I,S1,S2,S3,U) (I,S2,S3,S1,U), 
etc. e vedere quella che ti costa meno (dove ogni distanza intermedia , 
tipo S1-S3 o S2-U la calcoli con lo shortest path).
Io suggerirei di usare una euristica, che anche se non garantisce
di trovare il percorso minimo, dovrebbe essere sufficientemente buona
considerando che e' molto semplice, anche da implementare.
L'euristica che ti suggerisco e' di tipo "greedy", ovvero procede pe 
passi successivi, e ad ogni passo fa la cosa migliore che puo' fare.
Quindi, dato il grafo di tutte le stanze e le stanze prescelte,
diciamo S1,S2,...,Sk, e l'ingresso I e l'uscita U, io procederei
cosi':
0) trovo lo shortest path tra I e U.
i) dato il set di stanze non ancora inserite, cerco quella
che si puo' inserire nel path corrente con il minimo
costo aggiuntivo, e la inserisco e aggiorno il path.
Il risultato di questa euristica dipende anche dallo
shortest path scelto inizialmente, nel caso ce ne sia piu' di uno.
Non sarebbe una cattiva idea provare a caso piu' di uno shortest
path iniziale e scegliere la soluzione finale migliore trovata.
Alternativamente potresti usare una tecnica di ricerca locale iterata:
stabilisci un percorso iniziale da I a U in qualche modo
(per esempio con il metodo precedente, oppure partendo da I e aggiungendo
ogni volta la stanza S piu' vicina all'endpoint del path che stai
costruendo, fino ad aggiungere U),
e poi applichi una ricerca locale iterata,
cioe', ad esempio, provi a scambiare tutte le coppie non adiacenti
di Stanze S sul percorso, effettuando lo scambio se porta un
miglioramento e fermandoti quando nessuno scambio ti porta piu'
miglioramenti.
ciao,
g.

> minimo tra 2 stanze del museo senza però che c'entrino nulla i periodi

A me non sembra che Piotre abbia chiesto il "cammino minimo che prende 
tutte le stanze che interessano un certo periodo storico".
Lui dice:
"Il metodo prende il periodo storico e fornisce **un** percorso che 
parte con l'ingresso e finisce con l'uscita e al cui interno ci sono 
tutte le stanze con il periodo storico preferito dall'utente."
Pertanto sono più d'accordo con la scelta proposta che hai messo qui 
sotto... ("Alternativamente potresti ...").
Ovviamente poi dipende da quanto come varia il rapporto tra 
STANZEINTERESSATE/STANTETOTALI.
Se si avvicina ad uno il problema sale di complessità.
Potresti anche scegliere l'algoritmo dinamicamente in funzione di quel 
rapporto!
Altrimenti se statisticamente risulta che è un valore + vicino allo 0 
puoi adottare "l'alternativa".
Cioè, parti da I.
Calcoli tutti gli shortset paths per le stanze interessate. Scegli il 
più vicino (sia "Sj")
Calcoli tutti gli shortset paths per tutte le stanze interessat etranne 
le stanze già visitate.
ecc.ecc.
Non credo sia una soluzione ottimale (termini di tempo) ma non è 
difficile da implementare.
Inoltre c'è anche da dire un'altra cosa.
Anche io penso molto alla complessità quando si parla di algoritmi, è 
pur vero però che bisogna anche studiarli nel dominio in cui vengono 
applicati. Intendo dire che per quanto possa essere grande 
verosimilmente un museo e per quanto possano essere veloci i calcolatori 
oggi ... insomma... ci si può stare larghi.
Certo, non sarebbe un algoritmo portabile, nel senso che se lo vorresti 
utilizzare per un altro dominio dovresti stare attento alla sua 
grandezza, però...
Poi dipende se stai facendo un esame universitario e ti impongono di 
stare sotto certe soglie di complessità... allora è un altro paio di 
maniche. Noi credo ti abbiamo suggerito delle soluzioni veloci e pratiche.
Ciao, buon lavoro.
