Considere el siguiente problema:
Deja que un -wheel puede definir como una lista ligada circularmente índice de números enteros. Por ejemplo…
{3, 4, 9, -1, 6}
... es un 5 ruedas con 3 en la posición 0, 4 en la posición 1, y así sucesivamente. Una rueda soporta la operación de rotación, de modo que una rotación de un paso convertiría la rueda anterior en ...
{6, 3, 4, 9, -1}
... ahora con 6 en la posición 0, 3 en la posición 1, y así sucesivamente. Deje sea un conjunto ordenado de distinta -Ruedas. Dado un poco de y un número entero , encuentre una serie de rotaciones tales que ...
En otras palabras, si dispusiera las ruedas como una matriz, la suma de cada columna sería . Suponga que está construido de modo que la solución sea única hasta las rotaciones de cada elemento (es decir, hay exactamente soluciones únicas que consisten en tomar una solución y luego rotar cada rueda en por el mismo número de pasos).
La solución trivial a este problema implica simplemente verificar cada rotación posible. Aquí hay un pseudocódigo para eso:
function solve(wheels, index)
if wheels are solved:
return true
if index >= wheels.num_wheels:
return false
for each position 1..k:
if solve(index + 1) is true:
return true
else:
rotate wheels[index] by 1
solve(wheels, 0)
Esta es una solución bastante lenta (algo así como ) Me pregunto si es posible resolver este problema más rápido, y también si hay un nombre para ello.
fuente
Respuestas:
Para la mayor parte de esta respuesta, analizo la versión de decisión del problema, en la que se da una instancia que tiene como máximo una solución (la "promesa"), y usted debe decidir si tiene alguna solución o no.
Puede reducir la PARTICIÓN a su problema (ejercicio). (PARTICIÓN es el problema de determinar si un conjunto de enteros se puede dividir en dos partes con la misma suma). Es cierto que esto no necesariamente satisface la condición de que la solución sea única.
Con un poco más de trabajo, puede (directamente) reducir SAT a (la versión de decisión de) su problema, y tal vez eso se pueda hacer de tal manera que si la instancia SAT tiene una solución única, entonces también lo hace la instancia resultante de tu problema. En ese caso, obtenemos que la versión de decisión no se puede resolver en polytime a menos que NP = RP, lo que se considera poco probable.
Tenga en cuenta que si la versión de decisión (más exactamente, la versión prometida) del problema no se puede resolver en polytime, entonces ningún algoritmo puede resolver todas las instancias SÍ en polytime: si lo hizo, podría ejecutarlo hasta el tiempo de ejecución asignado, y verifique la solución (si el algoritmo se detuvo a tiempo).
fuente