Test10 HW8REC impossibile?

DGreat (1210 points)
7 11 23
asked May 26, 2020 in Recupero HW8 by DGreat (1,210 points)
edited May 26, 2020 by DGreat
Salve professore / ciao a tutti ragazzi,

Scrivo per chiedere se il test 10 dell'hw8rec è funzionante o no.

Ho riscontrato un problema: tutte le parole sono unite tra di loro, sono "allooppate".

In pratica la parola 18 dovrebbe essere l'ultima e quindi non connessa a nulla essendo l'ultima (se vi va a fare "intersezione" con le altre parole nessun'altra parola deve iniziare con la parola 18) e invece e' connessa ad un'altra parola. Tutte le parole quindi risultano connesse tra loro ed è impossibile stabilire qual è l'ordine giusto (a differenza degli altri test dove la parola finale si poteva trovare).

Di conseguenza mi risulta impossibile completare il test.

Suggerimenti?

P.S. modificando la "destinazione" per l'appunto, mentre debuggo, inserendo manualmente 18 come valore di destinazione, il mio programma trova e restituisce la strada giusta.

Siamo sicuri che il test sia giusto?

3 Answers

Best answer
EffeGi (1530 points)
0 1 5
answered Jun 5, 2020 by EffeGi (1,530 points)
selected Jun 5, 2020 by DGreat

Update:

seguendo la strada del professore sono riuscito a superare i 10 test. Con il suggerimento di concatenare le parole che "forzatamente" hanno una sola destinazione (e le destinazioni una sola sorgente) le combinazioni si riducono notevolmente e non vi è alcun problema per il timeout. Ho speso non pochi giorni per la risoluzione .

La mia strategia è stata quella di usare i dizionari per raccolgiere quante più informazioni possibili dalla prima suddivisione (posizione, successiva, sovrapposizione con la successiva e precedenti), con quelle mi sono creato le sequenze concatenate forzate e ridotto il dizionario complessivo.

Devono essere inseriti accorgimenti per evitare gli errori con il primo e con l'ultimo termine (qualora vengano trovati preventivamente), ma questi errori possono essere risolti all'occorrenza!

Spero di aver aiutato!

andrea.sterbini (172780 points)
513 935 1789
answered May 26, 2020 by andrea.sterbini (172,780 points)
Il test è giusto, da nessuna parte è detto che le parole non possono essere tutte connettibili tra loro.
Quello che è vero, però, è che esiste una sola soluzione che concatena tutte le parole.
Vanno esaminate più possibili "soluzioni" per trovare quella giusta

E infatti inserendo 18 come ultima trovi la "strada" giusta, basta provarle tutte
DGreat (1210 points)
7 11 23
commented May 26, 2020 by DGreat (1,210 points)
Il discorso è che ho strutturato l'hw come un grafo e il nodo sorgente è ovviamente ogni nodo, quindi provo tutti i nodi sorgente, ma il nodo destinazione viene stabilito all'inizio. Non trovando la destinazione mi è impossibile procedere.

Potrebbe esserci una soluzione a questo o per risolvere questo problema dovrei cambiare l'hw?
EffeGi (1530 points)
0 1 5
commented May 26, 2020 by EffeGi (1,530 points)
Inserito come risposta
EffeGi (1530 points)
0 1 5
answered May 26, 2020 by EffeGi (1,530 points)

Anche io ho strutturato il problema come un grafo, nello specifico è un DCG (Directed Cycle Graph), quindi ho cercato il Percorso Hamiltoniano che copre tutti i nodi del grafo...

 

In teoria funziona (se non fosse per il timeout di 1 sec), il problema è che si configura come un problema NP-Completo, ovvero non esite (o non è stato trovato ancora) un algoritmo in grado di risolvere il problema in un tempo polinomiale...

Mi sto perdendo nella teoria dei grafi per il test 10 

L'unica idea che mi è venuta in mente, potrebbe essere quella di individuare i cicli all'interno del grafo, cosicchè si potrebbe creare una classe di equivalenza tra i nodi del ciclo... Ossia qualunque nodo del ciclo, mi permette di raggiungere tutti gli altri del ciclo. Quindi o trovare i cicli ed i percorsi tra i cicli, oppure appendere il ciclo alla fine della sequenza trovata (sempre se si hanno a disposizione tutti i nodi del ciclo, o raggiungibili in senso orario/antiorario).

Altrimenti la soluzione è consegnare l'HW con 9/10 blush

DGreat (1210 points)
7 11 23
commented May 28, 2020 by DGreat (1,210 points)

Ecco, a proposito di ciò io ho pensato "bene, se non trovassi alcun nodo destinazione posso mettere scorrere sorgente e scorrere destinazione cosi sicuramente prima o poi "lo becca""

Il problema di questa soluzione è che da un tempo lineare (scorrendo solo n "sorgenti", come faccio attualmente) passiamo ad un tempo quadratico poiche devo andare a richiamare la funzione ricorsiva per ogni sorgente, per ogni destinazione

Faccio un esempio: ho 0 1 2 3 4 5 6 7, se so qual è la destinazione (es. 6) e il percorso giusto fosse 4 3 2 0 1 5 7 6 l mio programma proverà a lanciare la ricorsione in questo modo:
 

SORGENTE DESTINAZIONE
0 6
1 6
2 6
3 6
4 6

E qui si fermerebbe. Quindi ho analizzato n elementi.

Invece se volessi rendere anche la destinazione variabile, a parità di condizioni verrebbe qualcosa come
00 01 02 03 04 05 06 07 - 10 11 12 13 14 15 16 17 - 20 21 22 23 24 25 26 27 - 30 31 32 33 34 35 36 37 - 40 41 42 43 44 45 46 e qui si ferma

Va da sè che "provandole tutte", da 5 cicli si passa a 39 iterazioni, quasi 8 volte il lavoro.

Ecco perchè, almeno secondo me, il problema attualmente è impossibile da risolvere per come l'abbiamo strutturato

E
Edward (25950 points)
2 4 172
commented May 28, 2020 by Edward (25,950 points)
È corretta l'intuizione di trovare i cicli nel grafo, infatti questi si chiamano strongly connected components.
Vi consiglio di dare un'occhiata all'algoritmo di Kosaraju, una volta ottenuto un grafo più piccolo trovare il percorso hamiltoniano sarà più veloce.
Questo ovviamente renderà il problema più complesso da scrivere ma sarà più veloce.
EffeGi (1530 points)
0 1 5
commented Jun 2, 2020 by EffeGi (1,530 points)
Ho seguito la strada dei SCC con l'algoritmo di Kosaraju, che sembra funzionare nel trovare i gruppi di parole connesse, tuttavia nel test più lungo vengono trovati solamente 2 SCC, ossia una parola da sola forma un SCC e le altre tutte assieme l'altro SCC, rendendo quasi inutile l'algoritmo... sbaglio la scrittura del codice?

Inoltre non è possibile lavorare sui SCC sigolarmente, perchè le connessioni tra i vari gruppi devono essere tenute in considerazione... non riesco a capire
andrea.sterbini (172780 points)
513 935 1789
commented Jun 2, 2020 by andrea.sterbini (172,780 points)

tenete presente che se esistono due parole XA e AY che si collegano in un unico modo, ed inoltre non esiste nessun'altra parola che si collega ad XA, possono essere sostituite dalla singola parola XAY riducendo il numero di parole totali 

E
Edward (25950 points)
2 4 172
commented Jun 2, 2020 by Edward (25,950 points)
L'indizio del professore potrebbe essere d'aiuto se vuoi seguire una strada diversa.

Adesso non ricordo di preciso al 100% come l'ho risolto (ricordo che mi è venuto abbastanza complicato ed ho dovuto modificarlo svariate volte perchè non consideravo tutti i casi), ma l'idea era che una volta trovati i SCC ottenevi un nuovo grafo, e trovavi il percorso hamiltoniano in questo grafo. Una volta trovato sai già da quale nodo partire (o meglio, il possibile gruppo di nodi), e devi trovare i possibili percorsi hamiltoniani in quel gruppo di nodi, ma devi tenere solo quelli che si collegano al gruppo di nodi successivo nel percorso ridotto. Nell'ultimo test esce abbastanza semplice perchè nel primo gruppo c'è solamente il nodo 26, quindi sai che devi partire da quel nodo per cercare il percorso hamiltoniano completo, quindi devi solamente trovare il percorso nel secondo gruppo (ma partendo dai nodi raggiunti dal nodo 26).
EffeGi (1530 points)
0 1 5
commented Jun 3, 2020 by EffeGi (1,530 points)

Hai colto perfettamente quello che chiedevo ed il nodo 26 è l'incriminato frown!

Ora l'algoritmo di Kosaraju mi funziona meglio e trova anche più SCC... provo ad unire le due idee insieme per aumentare l'efficienza complessiva.

Magari effettuare una compressione del numero di parole nella suddivisione iniziale con l'idea del professore, poi implementare l'algoritmo sulle parole (diminuite in numero)... vediamo che ne esce fuori!

Aggiorno il post quando ho trovato lo step successivo o rimango nuovamente bloccato!

Grazie per i suggerimenti!