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?
