Es este un problema NP?

Question

En primer lugar voy a decir que no sé mucho acerca de la teoría y tal. Pero me preguntaba si esto era un problema NP o NP-completo. Suena específicamente como un caso especial del problema de la suma de subconjuntos.

De todos modos, no es este juego que he estado jugando recientemente llamado Alchemy lo que llevó a este pensamiento. Básicamente usted comienza con 4 elementos básicos y combinarlos para hacer otros elementos.

Así, por ejemplo, se trata de un corto "receta" si se quiere para la fabricación de elementos

fire=basic element
water=basic element
air=basic element
earth=basic element
sand=earth+earth
glass=sand+fire
energy=fire+air
lightbulb=energy+glass

Así que digamos que una computadora podría crear sólo los 4 elementos básicos, pero podría crear varios conjuntos de los elementos. Así que escribir un programa para hacer cualquier elemento mediante la combinación de otros elementos. ¿Cómo este programa procesar la lista el crear una bombilla?

Es claramente el fuego + aire = energía, tierra tierra + = arena, arena + fuego = vidrio, cristal de energía + = bombilla.

Pero no puedo pensar en ninguna manera de escribir un programa para procesar una lista y darse cuenta de eso sin hacer un método de tipo fuerza bruta y repasando cada elemento y comprobar su receta.

Es esto un problema NP? O estoy simplemente no es capaz de resolver esto?

Answer 1

  

¿Cómo sería este proceso programa de la lista de la creación de una bombilla?

Sin duda, que acaba de ejecutar las definiciones hacia atrás; p.ej.

1. Creación de una bombilla requiere energía 1 + 1 vaso
2. Creación de una energía requiere 1 + 1 fuego de aire

y así sucesivamente. Se trata efectivamente de un simple paseo árbol.

otoh, si desea que el equipo para averiguar que significa energía + bombilla de vidrio (en lugar de "masa de vidrio fundido"), usted tiene ninguna posibilidad de resolver el problema. Es probable que no podría conseguir 2 jugadores de acuerdo en que la energía + vidrio = bombilla!

Answer 2

Se puede modelar fácilmente su problema como un gráfico y buscar una solución con cualquier algoritmo de búsqueda completa. Si usted no tiene ninguna experiencia, es posible que también ayuda a la mirada en automatizado de planificación . Estoy ligarse a ese texto, ya que también cuenta con una introducción sobre la complejidad y los algoritmos de búsqueda.