Ricerca su grafi fully connected

[daniele.conti.si]

Ciao ragazzi è la prima volta che scrivo qui sul forum! Sono veramente disperato, devo risolvere questo problema:

ho un database dove sono indicati posizione, tempo di visita e tipo di un migliaio di punti di interesse culturale della provincia di Siena. io devo realizzare la struttura di un programma mobile dove l'utente inserisce il tempo che ha a disposizione e che tipo di beni vuole visitare (bene archittetonici, musei, religiosi..) con la loro percentuale(0.5,0.2,0.3 per esempio) e ovviamente la posizione attuale. Quindi devo essere soggetto a questi 2 vincoli (e anche che il numero di posti visitati per esempio sia minore di 100, ma quello è semplice). Il problema è che non so trovare un algoritmo di ricerca (o non so impostarlo) che mi trovi il percorso che mi soddisfa (o ci va più vicino) alle mie richieste, voi cosa utilizzereste??

[daniele.conti.si]

forse ho trovato una soluzione... basta che mi creo un albero dove i nodi non sono i singoli punti di interesse, ma sono direttamente i percorsi e poi verifico tutte le condizioni che voglio con anche una ricerca in ampiezza per esempio...cmq sono ben accetti suggerimenti!

[hamming_burst]

un bel problema...

cosa indica la percentuale?

[daniele.conti.si]

indica la percentuale di beni che voglio visitare! per esempio se voglio visitare musei, chiese, e paesaggi però sono un fotografo e mi interessano molto di più i paesaggi dovrò inserire per esempio che vorrò visitare [0.1 0.1 0.8] rispettivamente! ma questo non è un problema perchè basta fare lo scarto quadratico elemento per elemento e minimizzare quello! il problema è come trovare questo minimo!

[hamming_burst]

Si può interpretare in alcuni modi. Chiariamo alcuni punti
- quello che vuoi massimizzare il numero di posti visitati secondo le preferenze
- la percentuale sta a significare che vuoi rimanere più tempo in un tal posto, è solo un parametro indipendente dal tempo

Io lo vederei come un problema dello zaino 0-1. Ma il tempo di visita lo puoi spezzare in frazioni?

[daniele.conti.si]

di massimizzare il numero di posti non era indicato ma male non dovrebbe fare! la percentuale indica la mia preferenza nel visitare quel posto! è indipendente dal tempo! cioè se dico che ho 100 minuti e voglio vedere in egual percentuale chiese monumenti e paesaggi, se faccio 80 minuti una chiesa 10 un monumento e 10 un paesaggio va bene!

[daniele.conti.si]

però ora che pensavo allo zaino... a ogni oggetto inserito mi cambiano i dati, perchè io mi sposto e a quel punto mi cambiano le distanze e quindi i minuti che mi ci vogliono! funziona lo stesso? te chiedi se lo posso spezzare in frazioni per omettere il vincolo di interezza? ma tanto il tempo di visita è gia nel database quindi quello è fisso, cosi come il tempo che ci vuole per percorrere una certa distanza una volta calcolata (in primo approccio non guardo se è autostrada,superstrada....)