Esto se inspiró realmente en el Solitario, pero algunas personas reaccionaron con ``oh, es como las torres de Hanoi, ¿no?'' así que intentaré plantear el problema en términos de discos aquí.
Empecemos. Hay n discos en la línea real, uno de tamaño 1 en la posición $x_1$ uno de tamaño 2 en la posición $x_2$ ..., y uno de tamaño n en la posición $x_n$ . Tu objetivo es hacer una torre con todos los n discos, consumiendo la menor cantidad de energía posible en el proceso. Puedes mover una torre cuya base sea un disco de tamaño k sólo encima del disco de tamaño k+1 (que puede ser la parte superior de otra minitorre). La energía que consumes para realizar dicho movimiento es la distancia recorrida por la minitorre movida. Por ejemplo, la energía consumida por el primer movimiento es $|x_k-x_{k+1}|$ .
Ahora, te gustaría escribir un programa que te diga si la energía que tienes es suficiente para realizar la tarea. Sólo tiene que decir Y o N. (Si la respuesta es Y, entonces claramente la lista de movimientos es prueba suficiente de que la respuesta es correcta, por lo que el problema es NP. Si la respuesta es N, no tiene sentido ni siquiera intentar la tarea: estás demasiado cansado).
¿Cuál es el programa más rápido que puedes encontrar? ¿Es el problema NP-completo? Si ayuda, considera una simplificación que restrinja $x_k$ que sean racionales, enteros, enteros en un rango determinado, etc.
Aquí hay un límite superior: $O(n2^n)$ . Representar el estado inicial mediante la lista $x_1$ , $x_2$ ,... , $x_n$ . Un movimiento afecta al estado borrando un número de esta lista y la energía consumida por el movimiento es la diferencia absoluta entre el número borrado y el que viene después. Está claro que hay $2^n$ estados con un máximo de $n$ movimientos cada uno. (Ver la entrada de mi blog para ver un ejemplo de ejecución de este algoritmo si no está claro. La descripción allí es en términos de tarjetas).
Nota: Algunos de los comentarios que aparecen a continuación se refieren a versiones anteriores de las preguntas. Consulte el historial de ediciones si le parecen confusas.
