Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Algoritmi - navigatore
Forum - Algoritmi - navigatore

Avatar
davidsf (Normal User)
Newbie


Messaggi: 19
Iscritto: 05/08/2008

Segnala al moderatore
Postato alle 15:47
Giovedì, 11/12/2008
a scuola, dato che sono uno di quelli che se ne intende d + d programmazione, mi han chiesto di sviluppare un programma per la navigazione nella mia città, però non so come diavolo fare, come faccio un algoritmo che mi permetta di arrivare dove voglio?

PM Quote
Avatar
eddiewrc (Member)
Expert


Messaggi: 560
Iscritto: 30/04/2006

Segnala al moderatore
Postato alle 16:39
Giovedì, 11/12/2008
son contento che tu te ne intenda perchè non è un problema semplice: bisogna avere una buona conoscenza della teoria dei grafi.

if (mai sentito parlare di grafi)
   wikipedia -> grafi, teoria dei

la mappa della città va rappresentata appunto tramite una struttura dati che si chiama grafo, cioè come un insieme di nodi e archi che li interconnettono.

una volta stabilito cosa rappresentare con un nodo (un luogo) e cosa con un arco (una strada, sentiero, ecc) per utilizzare le informazioni così immagazzinate sarà necessario risolvere il problema "trova il cammino minimo tra due qualsiasi nodi del grafo".

per fortuna di tutti noi (altrimenti non avremmo internet), questo problema è già stato risolto da un pezzo da E.W. Dijkstra, con un algoritmo greedy abbastanza semplice che tuttavia trova la soluzione ottima. (nel caso in cui il grafo NON abbia cicli di peso negativo).
questo algoritmo è famosissimo e lo puoi cercare su internet. se vuoi un mio consiglio fai un salto anche qui per capire meglio le cose:
http://links.math.rpi.edu/applets/appindex/graphtheory.html

if (chi diamine è Dijkstra?)
   {
     MALE!
     wikipedia -> dijkstra
}

i problemi che un "navigatore" deve risolvere sono ancora molti altri ma direi che se inizi ad arrivare fin qui sei a buon punto..
ciao!:k::rotfl:

PM Quote
Avatar
davidsf (Normal User)
Newbie


Messaggi: 19
Iscritto: 05/08/2008

Segnala al moderatore
Postato alle 13:57
Venerdì, 12/12/2008
avevo un pò intuito a grandi linee,
CHE ERA UN CASINO DELLA MADONNA XD

bè, ci sono librerie o pezzi di codice già fatti per il calcolo dei grafi?
mi andrebbe bene vb .net e c++.

Grazie mille, sei stato utilissimo, ma la teoria dei grafi si fa all'università?

PM Quote
Avatar
lorelapo (Ex-Member)
Expert


Messaggi: 355
Iscritto: 28/02/2007

Segnala al moderatore
Postato alle 17:17
Venerdì, 12/12/2008
Sì è un argomento abbastanza vasto e in largo studio da parte dei matematici comunque qua parliamo di algoritmi per le librerie chiedi in altre sezioni ma se hai bisogno di delucidazioni posta pure.:k:

PM Quote
Avatar
eddiewrc (Member)
Expert


Messaggi: 560
Iscritto: 30/04/2006

Segnala al moderatore
Postato alle 21:00
Sabato, 13/12/2008
di per se grafi e algoritmi per calcolo su grafi sono cosa abbastanza semplici... parti da un grafo piccolo (3 o 4 o 5 ) nodi e prova a ragionare su come immagazzinare i dati di una cartina in questa struttura dati (il grafo). risolto questo problema implementa dijkstra e non ci dovrebbero essere troppi problemi. serve solo qualche ragionamento teorico ogni tanto.

la teoria dei grafi è un campo smisurato che soprattutto ha migliaia di applicazioni possibili, per cui capita di studiarne qualche aspetto nei più svariati ambiti. ovviamente le conoscenze più dettagliate le ho avute dal corso di Algoritmi e strutture dati.

io ti consiglio di scrivere il programma in un linguaggio serio, possibilmente che abbia i puntatori.
ciao

PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 21:56
Sabato, 13/12/2008
Testo quotato

Postato originariamente da davidsf:

avevo un pò intuito a grandi linee,
CHE ERA UN CASINO DELLA MADONNA XD



Non è un casino... basta capire il problema.

Testo quotato


bè, ci sono librerie o pezzi di codice già fatti per il calcolo dei grafi?
mi andrebbe bene vb .net e c++.



Beh, sicuramente troverai qualche esempio già pronto, non so se troverai addirittura un'intera libreria, per implementare il grafo usi un adjacency matrix o un'adjacency list (Wikipedia...) e poi implementi l'algoritmo che ti hanno citato qui sopra. Fallo in VB.NET, se le performance estreme non sono una cosa necessaria.

Testo quotato


Grazie mille, sei stato utilissimo, ma la teoria dei grafi si fa all'università?



Si, fa parte delle lezioni sugli algoritmi. Alle superiori non ho mai sentito nessuno che l'ha studiata, a parte gli autodidatti.


Il mio blog: https://piero.dev
PM Quote
Avatar
gigisoft (Member)
Guru


Messaggi: 696
Iscritto: 11/10/2008

Segnala al moderatore
Postato alle 1:27
Sabato, 03/01/2009
Testo quotato

Postato originariamente da pierotofy:

[...]

Fallo in VB.NET, se le performance estreme non sono una cosa necessaria.

[...]




Humm... non so quanto sia grande la città in questione, però penso che verrà rappresentato comunque con un grafo abbastanza grande, per cui le performance potrebbero essere necessarie.
Luigi

PM Quote