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

Question

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

Во всяком случае, есть одна игра, в которую я недавно играл, под названием Алхимия, которая подтолкнула эту мысль. В основном вы начинаете с 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, если вы хотите, чтобы компьютер выяснил, что энергия + стекло означает лампочку (а не «шарик расплавленного стекла»), у вас нет шансов решитьпроблема.Вы, вероятно, не могли заставить двух игроков согласиться с тем, что энергия + стекло = лампочка!

Answer 2

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