Complessita-Problema delle N regine

[Gin&&Tonic]

Ragà qualcuno conosce la complessità del problema delle N regine.

[marco.r]

A giudicare dalla mia signature sembrerebbe molto complesso .


Battute a parte, per poterti aiutare dovresti perlomeno esporre il problema come l'hai affrontato tu e dirci dove non ti trovi.

[WarDuck]

Sbaglio o si risolve con back-tracking valutando l'insieme delle possibili soluzioni?

[tuccio`]

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)

[wingman87]

Sul mio libro di intelligenza artificiale per questo specifico problema consiglia di utilizzare il min-conflicts algorithm (LINK) 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
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`]

be' non credo possa definirsi una soluzione se c'è la possibilità che risponda "non lo so"

niente su cui basare un discorso sulla complessità

[shinya]

Originariamente inviato da wingman87

Sul mio libro di intelligenza artificiale per questo specifico problema consiglia di utilizzare il min-conflicts algorithm (LINK) 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
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]

Originariamente inviato da shinya

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

[shinya]

Originariamente inviato da wingman87

Nono, una sola. Ma il problema non è trovarne una? E' trovarle tutte?

Ah! Dipende da quanto ti vuoi inguaiare

[Gin&&Tonic]

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!

[gugoXX]

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.

[rеpne scasb]

■

[thomasBis]

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

[Freaxxx]

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.