[Java-Pseudocodice] Caricare dati da un file in un grafo

[guylmaster]

Avrei un problemino più che altro algoritmico nel realizzare una funzione in java.

Dunque ho una mappa rappresentata su un file nel seguente modo:

Lat/Lon 3.99,   4.00,   4.01,   
44.01,  8.00,   8.00,   8.00,
44.00,  8.00,   4.00,   8.00,
43.99,  8.00,   8.00,   8.00,
43.98,  4.00,   8.00,   8.00,
43.97,  8.00,   8.00,   8.00,

Praticamente la prima colonna sono le latitudini, la prima riga le longitudini e i valori in mezzo ci dicono che cosa ce in quel punto (a me interessa schematizzare tutto in mare o terra ma vabbè).

Ora devo cercare di mettere tutto nei nodi di un grafo tenendo presente che:

- Fissero un valore K che rappresenterà quanti punti della mappa devo rappresentare in ogni nodo del grafo, questo valore sarà a discrezione dell'utente ma sarà uguale per ogni nodo della mappa;

- Nella rappresentazione dei nodi ho comunque sia un centroide che gli rappresenta che il range di valori di coordinate (dispongo poi di funzioni per calcolare la distanza tra due punti ed anche per sapere due punti come sono orientati uno con l'altro);

- Gli archi che ogni nodo avrà saranno 8 e saranno del tipo: Nord, Nord-Est, Est, Sud-Est, Sud, Sud-Ovest..

Ora il mio problema principale e che le mappe contengono migliaia e migliaia di punti, quindi le prove che ho fatto sono miseramente fallite perché su mappe "piccole" tutto filava liscio, su mappe grandi arrivavo a computazioni lunghe (vorrei qualcosa che non debba superare il minuto di computazione).

Voi cosa suggerite? Vi dico cosa ho provato a fare io:

- Prendo in fila i K punti (benchè sarebbe più opportuno prenderne a forma di quadrato, del tipo se ne ho 4 prendere due punti dalla prima riga e due punti dalla seconda), ed inizio a caricare i nodi nel grafo. Dopo mi faccio ritornare l'insieme dei nodi del grafo, per ogni nodo ordino tutti gli altri per direzione e per ogni direzione prendo il più vicino.
Ecco questa sembrava veloce da implementare ma ha avuto complessità computazione troppo elevata;

- Quest'altra prova sebbene invece aveva una complessità computazionale migliore non restituitiva bene tutti gli archi. Ovvero prendevo un nodo, cercavo di approssimare le coordinate dei nodi che dovevano stargli attorno e poi se quei nodi esistevano tiravo gli archi. Ho avuto ovviamente problemi ad approssimare le distanze perché innanzi tutto se approssimo un nodo con 4 punti di fila il nodo posizionato accanto sarà molto più distante di quello posizionato sotto e questo mi sballava un po' tutti i calcoli.

Siete liberissimi di deridermi ma se avete qualche idea, anche uno pseudocodice che secondo voi potrebbe funzionare a grandi linee è sicuramente ben accetto

Vi ringrazio in anticipo,
guylmaster.

[banryu79]

Sinceramente ho capito poco della situazione, però posso darti un consiglio (probabilmente banale): profila sempre ogni tentativo di soluzione che produci, così puoi vedere dove sta il collo di bottiglia più importante a runtime (magari i tempi di esecuzione sono "splamati", e magari invece scopri che il "grosso" si concentra in 2-3 metodi) e a quel punto hai un'idicazione utile per provare a produrre una soluzione che sia computazionalmente migliore in termini di tempo di esecuzione.

[guylmaster]

Originariamente inviato da banryu79

Sinceramente ho capito poco della situazione, però posso darti un consiglio (probabilmente banale): profila sempre ogni tentativo di soluzione che produci, così puoi vedere dove sta il collo di bottiglia più importante a runtime (magari i tempi di esecuzione sono "splamati", e magari invece scopri che il "grosso" si concentra in 2-3 metodi) e a quel punto hai un'idicazione utile per provare a produrre una soluzione che sia computazionalmente migliore in termini di tempo di esecuzione.

Lo faccio in parole povere:
Sto rappresentando una mappa dei mari tramite un grafo. Parlando di mari tutti i nodi sono connessi tra loro ciò che cambia è il peso sull'arco.

Il collo di bottiglia è principalmente sul fatto di dover inserire tutti questi archi. Mi è quindi stato consigliato semplicemente di non tracciare nessun arco, ma semplicemente se ogni nodo del grafo è connesso con i suoi vicini di calcolarci semplicemente i nodi attorno mediante le coordinate.

Quindi a questo punto più che un grafo diventerà una matrice, o qualcosa di simile (un grafo a scacchiera).

[banryu79]

Originariamente inviato da guylmaster

Sto rappresentando una mappa dei mari tramite un grafo. Parlando di mari tutti i nodi sono connessi tra loro ciò che cambia è il peso sull'arco.

Il collo di bottiglia è principalmente sul fatto di dover inserire tutti questi archi. Mi è quindi stato consigliato semplicemente di non tracciare nessun arco, ma semplicemente se ogni nodo del grafo è connesso con i suoi vicini di calcolarci semplicemente i nodi attorno mediante le coordinate.

Quindi a questo punto più che un grafo diventerà una matrice, o qualcosa di simile (un grafo a scacchiera)

Ok, ma raccontaci un po' che tipo di elaborazioni devi fare con questa "mappa dei mari" perchè senza sapere cosa stai cercando di ottenere alla fine della fiera è difficile darti dei consigli circostanziati.
Quale è il problema che devi risolvere?