Это проблема NP?

Question

Во-первых, я собираюсь сказать, что я не знаю много о теории и такой. Но мне было интересно, была ли это проблема NP или NP-полной проблемы. Это конкретно звучит как специальный случай проблемной проблемы подмножества.

Во всяком случае, есть эта игра, которую я играл недавно под названием Alchemy, которая вызвала эту мысль. В основном вы начинаете с 4 основных элементов и объедините их, чтобы сделать другие элементы.

Так, например, это короткий «рецепт», если вы будете делать элементы

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

Итак, допустим, компьютер может создать только 4 основных элемента, но он может создать несколько наборов элементов. Таким образом, вы пишете программу, чтобы создать любой элемент, объединив другие элементы. Как эта программа обработает список создания лампочки?

Это явно огонь + воздух = энергия, земля + земля = песок, песок + огонь = стекло, энергия + стекло = лампочка.

Но я не могу подумать о каком-либо способе написать программу для обработки списка и постановка, не выполняя метод грубой силы и переходом на каждый элемент и проверку его рецепта.

Это проблема NP? Или я просто не могу понять это?

Answer 1

Как эта программа обработает список создания лампочки?

Конечно, вы просто запускаете определения назад; например

1. Для создания лампочки требуется 1 энергия + 1 стекло
2. Создание энергии требует 1 огня + 1 воздух

и так далее. Это фактически простая прогулка по дереву.

OTOH, если вы хотите, чтобы компьютер выяснил, что Energy + Glass означает LightBulb (а не «Blob из расплавленного стекла»), у вас нет шансов решения проблемы. Вы, вероятно, не могли получить 2 геймеров, чтобы согласиться с тем, что Energy + Glass = LightBulb!

Answer 2

Вы можете легко моделировать вашу проблему как график и искать решение с любым полным алгоритмом поиска. Если у вас нет опыта, это может также помочь посмотреть автоматическое планирование. Анкет Я ссылаюсь на этот текст, потому что в нем также есть введение в алгоритмы сложности и поиска.