Cómo sé que por aquí hay gente que sabe del tema, quiero abusar de vosotros para plantearos algo. Dado el problema de las n-reinas:
https://es.wikipedia.org/wiki/Problema_de_las_ocho_reinas
¿Un algoritmo que garantice una solución, en orden de complejidad k*n, aporta algo a la historia del problema? Según he leído por ahí, y la información me resulta confusa, la verdadera resolución consiste en encontrar todas las posibles combinaciones de posiciones válidas de las reinas. Pero un algoritmo como el que describo, ¿merecería la pena el esfuerzo de desarrollarlo, o ya existe algo parecido?
Me gustaría iniciar un debate con la gente que sabéis del tema sobre cuando se considerará resuelto el problema, y sobre si el algoritmo sería un aporte valioso.
Comentarios
#2 No creo que sea cierto lo del millón de dólares, lo siento. En todo caso podría preguntar a una persona que conozco que se dedica a algorítmica. Supongo que si tuvieras un algoritmo en tiempo logarítmico sí sería algo.
Y lo de si independiéntemente del tamaño puedes hacerlo con 10 operaciones, pues sí, yo lo publicaría tras una investigación del estado del asunto en arxive y similares.
#4 Gracias, muy interesante. Merecía la pena molestarte.
Voy a invocar a
Nick_el_Cadmio porque sabe de esto mucho más que yo
Y luego opino a la cuñada: creo que el problema está muy muerto, se conocen todas las soluciones, se ha generalizado a números mayores, se han programado versiones y algoritmos variopintos. Pero si te parece que tu algoritmo de veras tiene algo muy especial publícalo, porque al ser un problema famoso darle una vuelta de tortilla suele tener eco.
#1 Entonces, ¿Cuál es el que queda por resolver, que leo por ahí que ofrecen un millón si lo resuelves?
Que siempre exista solución, significa que hay un conjunto de patrones. Hay una ley desconocida que siempre se cumple. O un conjunto de ellas. Si encontrásemos un intervalo totalmente cubierto con patrones repetibles para [n + (k * i)], siendo k constante, podrías afirmar que puedes solucionar cualquier tablero sin backtracking, ni poda, ni una variable que dependa de n, por muy eficiente que sea. Por ejemplo:
1.- Creo tener un parón universal cuando n es par. Da igual su tamaño, en k operaciones, sé cual es una de las soluciones. Entre 3 y 10 preguntas... Demostrable encima.
2.- Cuando n es primo tengo otro, creo.
3.- Pero me da que existe un patrón universal impar, un patrón, una disposición de posiciones, que forma parte del conjunto de posibles soluciones en todos los n impares.
O sea... según escribía esto, CREO que he encontrado el patrón impar. Demostrable. , cuanto más grande es el tablero, es más fácil resolverlo. Creo que le he visto las orejas a la propiedad universal.
La pregunta es: ¿Aporta algo esto, que dando igual el tamaño "cuadrado" del tablero, con 10 operaciones, lo resuelvas?
#0 El problema de las n-reinas es un problema NP (no polinomial) completo que tiene orden de complejidad factorial (O(n!) - O((n+1)!)). Es decir, no se puede resolver con algoritmos tradicionales en un tiempo razonable (el método basado en Backtracking se utiliza para tableros pequeños, o para explicar el problema original de las 8 reinas), y las soluciones polinomiales no garantizan que se encuentre siempre solución. Para intentar resolver eso se utilizan heurísticas, y algoritmos como los algoritmos genéticos combinados con paralelismo (para compensar el gran número de operaciones que se debe realizar): http://www.wseas.us/e-library/conferences/2008/sofia/EC/ec-7.pdf
En #2 preguntas si aportaría algo resolver algo con 10 operaciones, pero en #0 hablas de k*n que, entendiendo 'k' como constante, sería un orden n. Por otro lado habría que calcular el coste de cada una de esas 10 operaciones. ¿Son operaciones constantes cada una de ellas? Entonces la resolución tendría un tiempo constante (o lineal, si es que se debe multiplicar por ello). Y la diferencia es importante: porque si lo que buscas es encontrar una solución —y no todas— deja de ser un problema combinatorio y ya hay soluciones triviales que se resuelven en tiempo lineal y que también dependen de la «paridad o imparidad» de n, para n>3:
https://en.wikipedia.org/wiki/Eight_queens_puzzle#Explicit_solutions
http://www.chegg.com/homework-help/questions-and-answers/poor-man-s-n-queens-problem-n-queens-arranged-n-x-n-chessboard-way-queen-checks-another-qu-q1009394
Ahora bien, he dicho de diferenciar entre un tiempo lineal y constante porque si fuera constante mejoraría lo que ya hay... pero no puede serlo, porque recoger la solución en este caso depende de n sí o sí, así que entiendo que el tiempo al que te refieres es k*n y no O(I) (siempre se representa como O(I) independientemente de que sean 10 operaciones o las que sean).
Yo lo que te recomendaría es:
—Prueba a programar la solución con algoritmos genéticos y otras técnicas heurísticas. No mejorarás nada, pero mola.
—Si quieres intentar mejorar tiempos de problemas para los que aún te pueden nombrar friki del año, échale un ojo al problema del viajante:
https://es.wikipedia.org/wiki/Problema_del_viajante
Si consigues mejorar los tiempos récord que hay te pueden proponer hasta para el premio Turing (en alguna universidad lo hacen). Eso sí, ya hay muchas soluciones basadas en heurísticas que consiguen tiempos muy buenos, ya que es uno de los problemas más estudiados que existen.
cc #1
#4 Si el número de patrones es finito, y sólo necesitas detectar los patrones, no depende de n, sino del número de patrones, que es independiente de n.
Está claro.. si esos "patrones" existiesen. Ya detecté uno, para los pares que no son de la forma n= 4 + 6 * i.
Eso es algo que nunca he entendido cuando se calculan complejidades. En el problema de la boda, siempre insisten en que la variable es el número de invitados, cuando en realidad la variable interesante es el número de relaciones.
Pero bueno, ya estoy desvariando... y casi siempre hablo por hablar. Es muy estimulante mogollón hablar con gente que sabe. GRACIAS.
#6 La cuestión es que para la complejidad tienes que contar lo que necesitas para la resolución del problema y obtención de la solución, y no sólo el «núcleo» de la resolución. Y no tiene por qué coincidir con la variable que es interesante o en la que centras el peso de la optimización.
En cualquier caso, desvariar estimula la imaginación y es bueno, y de hecho lo que has pensado y planteado tiene que ver con las soluciones explícitas que han planteado otros. Por eso te animo a que si tienes tiempo y ganas te dediques a aprender sobre el tiempo del viajante (que es uno de los problemas computacionales por excelencia que se suelen plantear como reto a alumnos y profesionales), las formas tradicionales de «resolverlo» y todas las heurísticas que hay. Conseguir un tiempo muy bueno, incluso no siendo el mejor de los que se han conseguido, ya es algo que se valora bastante. Además que lo divertido es el trasteo y el aprendizaje que hay por medio.
#7 Gracias .