11 votos

¿Por qué es clasificación panqueques NP duro?

Un artículo publicado ayer (http://www.i-programmer.info/news/112-theory/3280-pancake-flipping-is-hard-np-hard.html) hace referencia a un nuevo estudio publicado en Arxiv (http://arxiv.org/abs/1111.0434v1) con el siguiente resumen:

Panqueque Flipping es el problema de ordenar una pila de panqueques de diferentes tamaños (es decir, una permutación), cuando el único permitido de operación para insertar una espátula en cualquier lugar en la pila y para voltear las tortitas por encima de ella (es decir, para realizar un prefijo de reversión). En el holocausto variante, uno de los lados de cada panqueque está marcado como quemado, y es necesario para terminar con todos los panqueques tener el holocausto, al lado de abajo. Informática el escenario óptimo para cualquier pila de panqueques y determinar el peor de los casos pila para cualquier tamaño de la pila han sido los retos a lo largo de más de tres décadas. Más allá de ser un intrigante problema combinatorio en sí mismo, también los rendimientos de las aplicaciones, por ejemplo en la computación paralela y la biología computacional. En este trabajo mostramos que la tortilla Voltear problema, en su estado original (sin quemar) variante, es NP-duro, por lo tanto responder a la cuestión de larga data de su complejidad computacional.

La premisa es que ni siquiera sabemos el límite máximo para el número de lanzamientos por una pila de más de 19. El instante en que leí esto, yo tenía la solución, y quiero que me diga por qué estoy equivocado.

El número máximo de lanzamientos por cualquier pila es 2 * (número de elementos - 1), y es sumamente trivial algoritmo a implementar.

El proceso es sólo una sola-o-dos-flip paso repetido hasta la terminación:

  • Punto de división está directamente debajo de la más grande sin clasificar pancake (a menos que su en la parte superior)
  • Flip uno lo lleva a la parte superior (a menos que su en la parte superior)
  • Punto de división #2 está directamente encima de la mayor debidamente ordenados panqueque
  • Flip dos correctamente tipo otro panqueque

Desde el PDF:

Figura 1: Ejemplos de eficiente volteretas. Secuencia 5; 2; 3; 1; 4 es que se puede ordenar de manera eficiente (en cuatro tirones), pero 5; 2; 3; 4; 1 no lo es.

No estoy de acuerdo...
52314. Los pasos a seguir con este enfoque son: 41325, 23145, 32145, 12345.
52341. Los pasos a seguir con este enfoque son: 14325, 41325, 23145, 32145, 12345.
Son realmente diciendo que 4 es eficiente, pero 5 no?

14voto

Mike Puntos 1113

Ellos están diciendo exactamente eso, es fácil ver que cualquier pila puede ser volteado en $2n-1$ volteretas como usted señala, pero la pregunta es, ¿cuál es el preciso bound? Tiene que ser aproximadamente lineal con un contador argumento ($k$ invierte solamente puede traer $O(n^k)$ configuraciones y hay $n!\approx n^ne^{-n}$ configuraciones de $n$ panqueques), pero conseguir la precisión constante en el término lineal es más difícil de lo que parece. La página de la Wikipedia sugiere que la constante es entre el$15/14$$18/11$, mejor que el ingenuo $2n$ enfoque.

Es casi más sorprendente que el problema ha sido abierto este tiempo - por ejemplo, muchos de manera eficiente-resolver puzzles como el $15$ puzzle tiene "fácil" de soluciones, pero difícil de límites en la búsqueda de soluciones óptimas. Encontrar configuraciones óptimas es a menudo difícil, y no es de extrañar que es difícil aquí.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X