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 유리 에너지를 생성
2. 한 에너지가 1 불 + 1 공기
등

등을 요구해야합니다. 이것은 사실 단순한 나무 산책입니다.

OTOH, 에너지 + 유리가 ("용융 유리 잔"이 아닌) 전구라는 것을 알기를 원하면 문제를 해결할 기회가 없습니다. 당신은 아마도 에너지 + 유리 = 전구에 동의하는 2 명의 게이머를 얻을 수 없습니다!

Answer 2

그래프로 문제를 쉽게 모델링하고 완벽한 검색 알고리즘으로 솔루션을 찾을 수 있습니다. 경험이 없으면 automated planning을 살펴 보는 것도 도움이됩니다. 복잡성 및 검색 알고리즘에 대한 소개 기능도 포함되어 있으므로 해당 텍스트에 연결됩니다.