Sab 17 Agosto, 14:55:57 - 2019

Autore Topic: Homework04 - Labirinto Tridimensionale  (Letto 6716 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline Lolbreaker

  • Studente
  • *
  • Post: 30
  • FeedBack: +1/-0
    • Mostra profilo
Re: Homework04 - Labirinto Tridimensionale
« Risposta #15 il: Mar 13 Dicembre, 01:25:45 - 2011 »
Quando lo carico su SPOJ mi da RunTime Error. Il mio problema è che non so quale sia la parte del codice che lo lancia... E' possibile avere un input che potrebbe generare tale eccezione?  ???

Offline Robert

  • Professore Ordinario
  • **
  • Post: 837
  • FeedBack: +87/-28
    • Mostra profilo
Re: Homework04 - Labirinto Tridimensionale
« Risposta #16 il: Mar 13 Dicembre, 11:10:19 - 2011 »
Quando lo carico su SPOJ mi da RunTime Error. Il mio problema è che non so quale sia la parte del codice che lo lancia... E' possibile avere un input che potrebbe generare tale eccezione?  ???

Potrebbe trattarsi di un overflow, prova a dargli in input un labirinto di 30 livelli con livelli 30X30 e tutti punti percorribili.

Offline Zoso

  • Studente di Dottorato
  • ***
  • Post: 205
  • FeedBack: +52/-7
  • Oh captain, my captain!
    • Mostra profilo
    • LineHeight
Re: Homework04 - Labirinto Tridimensionale
« Risposta #17 il: Mar 13 Dicembre, 11:40:05 - 2011 »
Qualcuno ha qualche input carino che vuole condividere?

Io ne posto un paio, molto banali:


Offline GhioHg

  • Ricercatore
  • ****
  • Post: 265
  • FeedBack: +43/-2
    • Mostra profilo
Re: Homework04 - Labirinto Tridimensionale
« Risposta #18 il: Mar 13 Dicembre, 18:03:48 - 2011 »
il file input4 mi compariva con gli spazi invece dei punti, lo riposto; da 59 come risultato?? ed invece input3 13??

GRAZIE MILLE PER GLI INPUT!! mi ero fermato ad input MOOOOLTO più banali 3 3 3 con 2 loop :D:D

Offline orlando

  • Neo-Laureato
  • **
  • Post: 53
  • FeedBack: +3/-1
    • Mostra profilo
Re: Homework04 - Labirinto Tridimensionale
« Risposta #19 il: Mer 14 Dicembre, 18:57:06 - 2011 »
ragazzi ma voi avete usato i grafi? thanks ;D

Offline finch89

  • Neo-Laureato
  • **
  • Post: 96
  • FeedBack: +16/-1
    • Mostra profilo
    • the loser.
Re: Homework04 - Labirinto Tridimensionale
« Risposta #20 il: Mer 14 Dicembre, 19:00:57 - 2011 »
ragazzi ma voi avete usato i grafi? thanks ;D

Sì io ho usato i grafi... anche perchè per trovare il percorso minimo credo si debbano usare necessariamente. Io ho risolto con una BFS (ricerca in ampiezza).

Comunque per quanto mi riguarda i risultati agli input sono INPUT3: 13, INPUT4/6:59 e INPUT5:50.
« Ultima modifica: Mer 14 Dicembre, 19:03:29 - 2011 da finch89 »

Offline orlando

  • Neo-Laureato
  • **
  • Post: 53
  • FeedBack: +3/-1
    • Mostra profilo
Re: Homework04 - Labirinto Tridimensionale
« Risposta #21 il: Mer 14 Dicembre, 19:46:26 - 2011 »
Sì io ho usato i grafi... anche perchè per trovare il percorso minimo credo si debbano usare necessariamente. Io ho risolto con una BFS (ricerca in ampiezza).

Comunque per quanto mi riguarda i risultati agli input sono INPUT3: 13, INPUT4/6:59 e INPUT5:50.

thanks

Offline Zoso

  • Studente di Dottorato
  • ***
  • Post: 205
  • FeedBack: +52/-7
  • Oh captain, my captain!
    • Mostra profilo
    • LineHeight
Re: Homework04 - Labirinto Tridimensionale
« Risposta #22 il: Mer 14 Dicembre, 20:56:08 - 2011 »
Confermo: 13, 59, 50.

Scusate per gli spazi!

Offline Zoso

  • Studente di Dottorato
  • ***
  • Post: 205
  • FeedBack: +52/-7
  • Oh captain, my captain!
    • Mostra profilo
    • LineHeight
Re: Homework04 - Labirinto Tridimensionale
« Risposta #23 il: Mer 14 Dicembre, 20:58:17 - 2011 »
Questi invece? Dovrebbero venire tutti e tre -1.

Offline Robert

  • Professore Ordinario
  • **
  • Post: 837
  • FeedBack: +87/-28
    • Mostra profilo
Re: Homework04 - Labirinto Tridimensionale
« Risposta #24 il: Mer 14 Dicembre, 21:42:43 - 2011 »
Ragazzi quale pensate sia il metodo migliore per trovare il cammino minimo?
Il mio programma funziona correttamente ma per input di una certa dimensione ci mette un secolo a stampare il risultato.

Offline Zoso

  • Studente di Dottorato
  • ***
  • Post: 205
  • FeedBack: +52/-7
  • Oh captain, my captain!
    • Mostra profilo
    • LineHeight
Re: Homework04 - Labirinto Tridimensionale
« Risposta #25 il: Gio 15 Dicembre, 00:04:16 - 2011 »
Il mio ragionamento è stato questo: sia BFS che Dijkstra trovano i cammini minimi, ma ci sono delle sostanziali differenze. Innanzi tutto, la BFS non tiene conto dei pesi sugli archi, dunque l'unica informazione che può sfruttare per garantire il cammino minimo è il numero di nodi che separano la sorgente dalla destinazione. Al contrario, Dijkstra nasce come un algoritmo per calcolare il cammino minimo di un grafo con archi pesati (purché il peso sia positivo): risolve dunque un problema simile alla BFS, che diventa uguale solo nel momento in cui gli archi hanno tutti il medesimo peso (come, cioè, avviene per un labirinto).

Detto ciò, andandomi a sfogliare il libro di algoritmi ho notato che il costo della BFS è leggermente inferiore di quello per Dijkstra. Per il primo algoritmo è O(|E| + |V|), mentre per il secondo è O(|E| + |V|log|V|). In realtà, questa è una semplificazione: Dijkstra ha un caso peggiore che è O(|V|²), riducibile al costo precedentemente riportato se e solo come struttura dati d'appoggio si sceglie una coda di priorità (PriorityQueue in Java) implementata con un Heap di Fibonacci (che, tuttavia, non mi risulta esistere nel Java Collection Framework).

I vari test (tantissimi a dir la verità, ho sudato davvero parecchio su questo Homework!) hanno confermato il minor impatto della BFS sui tempi di computazione. Oltre a dover effettuare meno controlli su ciascun nodo adiacente a quello corrente, la BFS ha semplicemente bisogno di una coda (o di una qualsiasi altra struttura dati che si comporti come tale). Per dirne una, scegliendo la LinkedList si hanno add e get(0) garantiti in tempo costante, mentre PriorityQueue dovrebbe (e sottolineo dovrebbe) avere tempi logaritmici (purché implementata come un d-Heap, cosa che onestamente non so).

Oh, ovviamente il fatto di usare la BFS non assicura di rispettare i limiti di tempo prestabiliti per questo Homework. O almeno, non è stato così per me.
« Ultima modifica: Gio 15 Dicembre, 10:47:56 - 2011 da Zoso »

Offline sylar91

  • Studente di Dottorato
  • ***
  • Post: 245
  • FeedBack: +14/-11
    • Mostra profilo
Re: Homework04 - Labirinto Tridimensionale
« Risposta #26 il: Gio 15 Dicembre, 00:15:24 - 2011 »
L'input 2c viene 14 non -1

Offline Zoso

  • Studente di Dottorato
  • ***
  • Post: 205
  • FeedBack: +52/-7
  • Oh captain, my captain!
    • Mostra profilo
    • LineHeight
Re: Homework04 - Labirinto Tridimensionale
« Risposta #27 il: Gio 15 Dicembre, 00:18:22 - 2011 »
Sicuro? L'uscita in input2c.txt è raggiungibile dalla sorgente, ma non dà verso l'esterno del labirinto. Potrei sbagliarmi, ma la frase "Il labirinto ha una sola uscita; per il resto è circondato da roccia su tutti i lati." mi ha fatto pensare a questo ulteriore vincolo.

Offline Robert

  • Professore Ordinario
  • **
  • Post: 837
  • FeedBack: +87/-28
    • Mostra profilo
Re: Homework04 - Labirinto Tridimensionale
« Risposta #28 il: Gio 15 Dicembre, 00:41:28 - 2011 »
Grazie mille per il tuo contributo Zoso ;)

Riguardo all'input2c.txt effettivamente anche io credo abbia come output 14.

Agilulfo

  • Visitatore
Re: Homework04 - Labirinto Tridimensionale
« Risposta #29 il: Gio 15 Dicembre, 00:51:14 - 2011 »
Sicuro? L'uscita in input2c.txt è raggiungibile dalla sorgente, ma non dà verso l'esterno del labirinto. Potrei sbagliarmi, ma la frase "Il labirinto ha una sola uscita; per il resto è circondato da roccia su tutti i lati." mi ha fatto pensare a questo ulteriore vincolo.

se proprio vogliamo essere pignoli, dà verso l'esterno da "sotto" :P
quindi 14 (come dicono gli altri) :D