Gin&&Tonic
01-09-2010, 19:32
Ragà qualcuno conosce la complessità del problema delle N regine.
View Full Version : Complessita-Problema delle N regine
marco.r
01-09-2010, 20:15
A giudicare dalla mia signature sembrerebbe molto complesso :mbe:.
Battute a parte, per poterti aiutare dovresti perlomeno esporre il problema come l'hai affrontato tu e dirci dove non ti trovi.
Battute a parte, per poterti aiutare dovresti perlomeno esporre il problema come l'hai affrontato tu e dirci dove non ti trovi.
WarDuck
01-09-2010, 20:32
Sbaglio o si risolve con back-tracking valutando l'insieme delle possibili soluzioni?
tuccio`
01-09-2010, 21:36
l'insieme delle possibili soluzioni ha cardinalità n! però
(be' un po' meno, ma comunque una soluzioni di backtracking per questo problema non può essere certo polinomiale.. boh comunque penso sia NP)
(be' un po' meno, ma comunque una soluzioni di backtracking per questo problema non può essere certo polinomiale.. boh comunque penso sia NP)
wingman87
01-09-2010, 23:39
Sul mio libro di intelligenza artificiale per questo specifico problema consiglia di utilizzare il min-conflicts algorithm (LINK (http://en.wikipedia.org/wiki/Min-conflicts_algorithm)) e la cosa non mi stupisce dopo aver visto la tabella con il numero di soluzioni del problema delle n regine (per vari n) in questa pagina: LINK (http://en.wikipedia.org/wiki/N-queens)
Sul libro dice che con questo algoritmo con 1000 regine, dopo l'assegnazione iniziale, sono richiesti in media 50 passi.
Solo che è un algoritmo che va "a culo" quindi non penso si possa calcolarne la complessità tanto facilmente.
Sul libro dice che con questo algoritmo con 1000 regine, dopo l'assegnazione iniziale, sono richiesti in media 50 passi.
Solo che è un algoritmo che va "a culo" quindi non penso si possa calcolarne la complessità tanto facilmente.
tuccio`
02-09-2010, 00:02
be' non credo possa definirsi una soluzione se c'è la possibilità che risponda "non lo so"
niente su cui basare un discorso sulla complessità
niente su cui basare un discorso sulla complessità
shinya
02-09-2010, 08:46
Sul mio libro di intelligenza artificiale per questo specifico problema consiglia di utilizzare il min-conflicts algorithm (LINK (http://en.wikipedia.org/wiki/Min-conflicts_algorithm)) e la cosa non mi stupisce dopo aver visto la tabella con il numero di soluzioni del problema delle n regine (per vari n) in questa pagina: LINK (http://en.wikipedia.org/wiki/N-queens)
Sul libro dice che con questo algoritmo con 1000 regine, dopo l'assegnazione iniziale, sono richiesti in media 50 passi.
Solo che è un algoritmo che va "a culo" quindi non penso si possa calcolarne la complessità tanto facilmente.
Non ho capito. Ma tu vuoi trovare UNA soluzione o TUTTE le soluzioni con N regine?
Perchè se le vuoi trovare tutte, mi pare che per N > 26 ancora non si sappia quante soluzioni esistono. http://oeis.org/classic/A000170
Se ne vuoi trovare una invece, un metodo stocastico può andare bene. Quello che hai detto tu mi sembra molto simile ad un hill climbing (ci sarà qualche differenza sottile che non colgo).
Sul libro dice che con questo algoritmo con 1000 regine, dopo l'assegnazione iniziale, sono richiesti in media 50 passi.
Solo che è un algoritmo che va "a culo" quindi non penso si possa calcolarne la complessità tanto facilmente.
Non ho capito. Ma tu vuoi trovare UNA soluzione o TUTTE le soluzioni con N regine?
Perchè se le vuoi trovare tutte, mi pare che per N > 26 ancora non si sappia quante soluzioni esistono. http://oeis.org/classic/A000170
Se ne vuoi trovare una invece, un metodo stocastico può andare bene. Quello che hai detto tu mi sembra molto simile ad un hill climbing (ci sarà qualche differenza sottile che non colgo).
wingman87
02-09-2010, 21:50
Non ho capito. Ma tu vuoi trovare UNA soluzione o TUTTE le soluzioni con N regine?
Perchè se le vuoi trovare tutte, mi pare che per N > 26 ancora non si sappia quante soluzioni esistono. http://oeis.org/classic/A000170
Se ne vuoi trovare una invece, un metodo stocastico può andare bene. Quello che hai detto tu mi sembra molto simile ad un hill climbing (ci sarà qualche differenza sottile che non colgo).
Nono, una sola. Ma il problema non è trovarne una? E' trovarle tutte?
Citavo il numero di soluzioni perché per l'appunto sono tantissime e quindi non è troppo difficile trovarle con un metodo semi-stocastico.
L'hill climbing non lo conosco, il nome però è evocativo :D
Perchè se le vuoi trovare tutte, mi pare che per N > 26 ancora non si sappia quante soluzioni esistono. http://oeis.org/classic/A000170
Se ne vuoi trovare una invece, un metodo stocastico può andare bene. Quello che hai detto tu mi sembra molto simile ad un hill climbing (ci sarà qualche differenza sottile che non colgo).
Nono, una sola. Ma il problema non è trovarne una? E' trovarle tutte?
Citavo il numero di soluzioni perché per l'appunto sono tantissime e quindi non è troppo difficile trovarle con un metodo semi-stocastico.
L'hill climbing non lo conosco, il nome però è evocativo :D
shinya
03-09-2010, 08:35
Nono, una sola. Ma il problema non è trovarne una? E' trovarle tutte?
Ah! Dipende da quanto ti vuoi inguaiare :D
Ah! Dipende da quanto ti vuoi inguaiare :D
Gin&&Tonic
03-09-2010, 15:39
ho risolto... in pratica dopo un certo valore x, con n>x non esiste una reale soluzione accettabile( per ora )...
la complessità computazionale del problema è esponenziale. Il record mondiale fino ad oggi raggiunto è su una scacchiera da 25X25, con ben 2.207.893.435.808.352 soluzioni, e un tempo cumulato di calcolo per trovarle che supera i 50 anni!
la complessità computazionale del problema è esponenziale. Il record mondiale fino ad oggi raggiunto è su una scacchiera da 25X25, con ben 2.207.893.435.808.352 soluzioni, e un tempo cumulato di calcolo per trovarle che supera i 50 anni!
gugoXX
04-09-2010, 13:20
La soluzione bruta per trovarle tutte direi che prevede O(N^8)
Dove N e' il numero di caselle, ovvero 64.
Per una soluzione bruta generica quindi saremmo su O((M^2)^M)
Dove M e' il lato della scacchiera.
Dove N e' il numero di caselle, ovvero 64.
Per una soluzione bruta generica quindi saremmo su O((M^2)^M)
Dove M e' il lato della scacchiera.
rеpne scasb
04-09-2010, 17:08
■
thomasBis
09-08-2014, 14:55
Ciao, mi trovo anch'io con un problema simile!
devo risolvere il problema delle n regine con l'alg. min conflicts scrivendo un piccolo programma in java. Il codice funziona e il problema viene risolto correttamente ma il tempo di esecuzione varia al variare di n (e non dovrebbe), cioè il numero di passi effettuati cresce quasi linearmente.
L'assegnamento iniziale viene fatto dando un valore casuale del dominio ad ogni regina, e le parità nei conflitti vengono risolte casualmente.
Utilizzo la funzione Random.nextInt(n) che mi dovrebbe garantire una distribuzione uniforme dei valori, è qui che sbaglio?
Grazie :)
devo risolvere il problema delle n regine con l'alg. min conflicts scrivendo un piccolo programma in java. Il codice funziona e il problema viene risolto correttamente ma il tempo di esecuzione varia al variare di n (e non dovrebbe), cioè il numero di passi effettuati cresce quasi linearmente.
L'assegnamento iniziale viene fatto dando un valore casuale del dominio ad ogni regina, e le parità nei conflitti vengono risolte casualmente.
Utilizzo la funzione Random.nextInt(n) che mi dovrebbe garantire una distribuzione uniforme dei valori, è qui che sbaglio?
Grazie :)
Freaxxx
09-08-2014, 22:31
i problemi non hanno "complessità computazionale", gli algoritmi hanno una data complessità, non i problemi che essi risolvono.
Ad essere pedagogici ed istruttivi bisognerebbe anche considerare solo la data implementazione per un dato algoritmo come soggetto per il calcolo della complessità, ad esempio un ciclo for mal scritto o inefficiente può tranquillamente fungere da moltiplicatore nel calcolo della complessità totale appesantendo di N ( dove N è il numero di iterazioni effettuate dal ciclo ) il tutto.
Ad essere pedagogici ed istruttivi bisognerebbe anche considerare solo la data implementazione per un dato algoritmo come soggetto per il calcolo della complessità, ad esempio un ciclo for mal scritto o inefficiente può tranquillamente fungere da moltiplicatore nel calcolo della complessità totale appesantendo di N ( dove N è il numero di iterazioni effettuate dal ciclo ) il tutto.
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.