TigerCow.Door


안녕하세요. 이번 포스팅에서는 전방 연쇄(Forward chaining)와 후방 연쇄(Backward chaining)에 대해서 알아보겠습니다. 


1. 전방 연쇄(Forward chaining)


먼저 전방 연쇄란, 기존의 알려진 사실들로 하여금 새로운 사실을 추리하면서 나아가는 방법입니다. 이름처럼 원래 알고 있는 것을 바탕으로 앞으로 나아가는 방법이죠. 즉, 한 문장, 함의에 대한 모든 전제가 알려져 있는 사실이라면 그것에 대한 결론을 새로운 사실로써 지식기지에 추가합니다.


예를 들어, A라는 사실과 B라는 사실을 알고 있을 때, 지식기지에 AB=>C 가 있다면 C를 하나의 사실로써 추가할 수 있습니다.

이러한 과정을 통해 알고자 하는 사실 Q에 도달하거나 더 이상 추리가 불가능 할때 까지 반복합니다.

아래의 알고리즘을 살펴보면 전방연쇄가 선형시간으로 실행되는 것을 확인할 수 있습니다.



전방연쇄는 위에서 언급한 바와 같이 진행되며 이를 보면 연역법과 비슷하다는 것을 알 수 있습니다.

이러한 전방연쇄는 건전하며 완결적입니다.

전방연쇄가 건전하다는 것은 쉽게 확인할 수 있는데, 모든 추리는 본질적으로 전건 긍정의 적용이기 때문입니다.

그리고 함축된 원자적 문장들이 모두 유도되기 때문에 완결적임을 알 수 있습니다.

전방연쇄를 아래 그림을 통해 확인하면 보다 쉽게 이해할 수 있습니다.



위의 그림에서 알려진 사실들은 A와 B입니다. 그리고 그래프는 AND-OR 그래프로써 여러 링크가 하나의 호로써 결합된 것은 AND, 논리곱을 의미하며 여러 링크가 호 없이 결합된 것은 OR, 논리합을 의미합니다. 논리곱을 증명하기 위해서는 연결된 모든 링크가 증명해야 하며 논리합에 대해서는 최소 하나의 링크가 참일때 참을 알 수 있습니다.

그림에 대한 이해를 해본다면, 먼저 알려진 사실 A와 B를 통해 AB=>L 에서 L이라는 사실을 추가합니다. 그리고 BL=>M

을 통해 M이라는 사실을 추가하고 이어서 LM=>P를 통해서 P라는 사실을 추가합니다. 그리고 P=>Q를 통해 Q라는 사실 또한 추가할 수 있습니다.



2. 후방 연쇄(Backward chaining)


이번에는 후방 연쇄(Backward chaining)에 대해서 알아보겠습니다. 후방연쇄는 그 단어에서도 알 수 있듯이 먼저 확인하고자 하는 사실 Q로부터 시작하여 Q를 사실로써 추가하기 위해 지식기지에서 결론이 Q인 함의, 문장을 찾습니다.

예를 들어, Q라는 사실을 확인하고자 하고 지식 기지에 MN=>Q 이 있다면 이제 우리는 각각 M, N에 대해서 동일하게 후방 연쇄를 진행합니다. 그리고 원래 알고 있던 사실, A와 B에 도달 했을 때 그 반복을 멈추게 됩니다.




전방연쇄에서 사용되었던 예시를 통해 후방 연쇄의 과정을 살펴보겠습니다.

먼저 Q라는 사실을 확인하려고 합니다. 지식기지에 P=>Q가 있으므로 우리는 P에 대한 후방연쇄를 진행합니다.

그리고 지식기지에 LM=>P가 있으므로 다시 L와 M에 대해서 후방연쇄를 진행합니다.

먼저 L에 대해서 진행하면, 지식기지에 AP=>L과 AB=>L이 있습니다. 이때 A와 B는 우리가 미리 알고있는 사실이기 때문에 L에 대한 후방연쇄는 AB=>L을 통해서 증명됩니다.

그리고 이제 M에 대해서 후방연쇄를 진행하면, 지식기지에서 BL=>M을 확인하고 B는 우리가 이미 알고 있는 사실이며 L은 방금 위에서 후방연쇄를 통해 추가된 사실이기 때문에 M 또한 후방연쇄를 통해 사실로써 추가합니다.

그럼 다시 LM=>P가 후방연쇄를 통해 P가 사실로써 추가될 수 있으며, P=>Q 또한 후방연쇄를 통해 증명되었기에 Q를 사실로써 추가할 수 있습니다.

이러한 후방 연쇄의 효율적인 구현은 선형 시간으로 전방 연쇄와 같습니다.


헌데 후방 연쇄는, 목표 지향적 추론(goal-directed reasoning)의 한 형태로써 종종 후방 연쇄의 비용이 지식 기지 크기의 선형적인 시간보다 훨씬 적을 수 있습니다. 그 이유는, 후방 연쇄가 추론 과정에서 오직 유관한 사실들만 확인하기 때문입니다.




전방 연쇄와 후방 연쇄에 대해 비교한다면,


전방연쇄는 기존의 사실들로써 과정을 시작하는, data-driven 입니다.

반대로 후방연쇄는 확인하고자 하는 목표부터 과정을 시작하는, goal-driven 입니다.

후방 연쇄에서의 설명처럼, 후방연쇄는 해결하고자 하는 문제, 확인하고자 하는 목표에 대해 유관한 것들만 접근하게 되므로 그 복잡도가 지식기지에 있는 크기의 선형시간보다 훨씬 작을 수 있습니다.


이렇게 해서 전방 연쇄(Forward chaining)와 후방 연쇄(Backward chaining)에 대해서 알아보았습니다.

추가적으로 궁금하신 점이나 내용에 대한 피드백은 언제나 댓글을 이용해주세요 :)


블로그 이미지

Tigercow.Door

Back-end / Python / Database / AI / Algorithm / DeepLearning / etc

댓글을 달아 주세요


안녕하세요.

지난 포스팅에서는 명제 정리 증명에 있어서 필요한 몇가지 개념에 대해서 알아보았습니다.

이번에는 증명을 이끌어 내는데 사용할 수 있는 추리 규칙(Inference rule)에 대해서 알아보도록 하겠습니다.


1. 전건 긍정(Modus Ponens)


증명이라는 것은 어떤 원하는 목표로 향해가는 결론들, 문장들의 사슬입니다.

그러한 증명을 만들어 내는데 사용되는 가장 잘 알려진 규칙은 아래와 같이 표기하는 전건 긍정(Modus Ponens)입니다.



위의 표기는, 와  형태의 임의의 문장들이 주어졌을 때, 문장 를 추리할 수 있다는 것입니다.



2. 논리곱 소거(AND-elimination)


또 다른 유용한 추리규칙으로는 논리곱 소거(AND-elimination)이 있습니다.

논리곱으로 주어진 문장에서 임의의 논리곱 성분을 추리할 수 있음을 뜻하며 다음과 같이 표기합니다.



와 같은 논리곱 문장의 참(True) 또는 거짓(False)를 알고 있기 때문에, 임의의 논리곱 성분( 또는 ) 또한 알 수 있습니다.



3. 건전한 추리(Sound inference)


 와 의 가능한 진릿값들을 생각해본다면 전건 긍정과 논리곱 소거 모두 전적으로 건전한 추리임을 알수 있기 때문에, 위에서 알아본 두가지 추리규칙을 통해 전체적인 모형을 열거하지 않고도 건전한 추리를 이끌어 낼 수 있습니다.


지난 포스팅에서 모형점검방식으로 다루어 보았던 웜푸스 세계에 대해서 이 추리 규칙들과 동치들을 활용해보도록 하겠습니다.


- [1,1]에 구덩이가 없다.

   R1 : 


- 에이전트가 하나의 칸에 존재함 그 이웃칸에 구덩이가 있으면, 그리고 오직 그럴때에만 미풍을 지각할 수 있다.

   R2 : 

   R3 : 


- 앞의 문장들은 모든 웜푸스 세계에서 참이다. 이제 에이전트가 있는 특정한 세계에서 처음 방문한 두 칸에 대한 미풍 지각을 위한 문장들을 명시한다.

   R4 : 

   R5 : 


출처: http://doorbw.tistory.com/39?category=679148 [Tigercow.Door]


목표는 [1,2]에 구덩이가 없음을, 즉 가 참임을 증명하는 것입니다.


우선 R2에서 상호조건 소거를 적용하여 다음을 얻도록 합니다.

R6 : 


그리고 위에서 알아본 논리곱 소거를 이용해서 다음을 얻습니다.

R7 : 


이어서, R7에 대한 대우 명제를 통해 논리적 동치 명제를 얻습니다.

R8 : 


그리고 R8과 사전에 지식기지에 있던 R4로 전건 긍정을 적용하여 다음을 얻을 수 있습니다.

R9 : 


그리고 드모르간 법칙을 적용하여 다음과 같은 결론을 얻을 수 있습니다.

R10 : 


R10을 통해 [1,2]와 [2,1]에는 구덩이가 없다는 것을 알 수 있습니다.


이러한 증명을 손으로 직접 이끌어 내었지만, 임의의 검색 알고리즘을 이용해서 증명을 구성하는 일련의 단계들을 찾아내는 것도 가능합니다. 증명 문제를 다음과 같이 정의하기만 하면 됩니다.


초기상태(Initial-State) : 초기 지식 기반

동작들(Actions) : 추리 규칙의 상단 절반에 부합하는 모든 문장에 적용되는 모든 추리 규칙에 해당하는 동작들의 집합

결과(Result) : 한 동작의 결과는 문장을 추리 규칙의 하단 절반에 추가하는 것

목표(Goal) : 목표는 증명하고자 하는 문장을 담은 상태


즉, 증명을 찾는 것은 모든 모형들을 열거하는 방법의 한 대안입니다. 실제 문제들에서는 증명을 찾는 것이 더 효율적인 경우가 많은데, 이는 증명과 무관한 명제들은 무시할 수 있기 때문입니다.



4. 단조성(monotonicity)


논리 체계에서 마지막으로 살펴볼 것은 단조성(monotonicity)입니다. 이는 특정 지식기지에 정보, 문장이 추가된다면 이는 함축된 문장들의 집합이 항상 커지기만을 의미할 뿐이지, 추가된 것에 의해 이미 추리된 결론이나 기타 결론에 영향을 주지 않는다는 것입니다.

즉, 지식 기지에서 추리를 통해 얻어낸 결론 A가 존재할 때, 또 다른 단언 명제 B가 추가된다면 이는 추가적인 결론들을 이끌어내는데 도움이 될 수도 있겠지만, 이미 추리된 결론 A는 무효화되지 않습니다.

단조성을 통해 우리는 지식 기지에서 적절한 전제를 찾았다면 언제라도 추리 규칙들을 적용할 수 있음을 알 수 있습니다.

추리 규칙의 결론은 지식 기지에 있는 또 다른 지식과는 무관하게 옳아야 하기 때문입니다.


이렇게 하여 증명을 이끌어 내는 몇가지 추리규칙과 단조성에 대해서 알아보았습니다.

다음 포스팅에서는 분해증명에 대해서 알아보도록 하겠습니다.

블로그 이미지

Tigercow.Door

Back-end / Python / Database / AI / Algorithm / DeepLearning / etc

댓글을 달아 주세요


안녕하세요. 문범우입니다.

이번포스팅에서는 명제 논리와 모형 점검 방식에 대해서 알아보도록 하겠습니다.


1. 명제 논리(Propositional logic)


1-1. 구문(Syntax)


명제 논리의 구문(syntax)은 허용되는 문장들을 정의합니다. 즉, 어떻게 문장을 구성해야 하는지를 이야기합니다.

하나의 문장, 원자적 문장(atomic sentence)은 하나의 명제 기호(proposition symbol)로 구성됩니다. 그리고 그러한 기호는 참(true)이거나 거짓(false)인 하나의 명제를 나타 냅니다. 예를 들어 P, Q, R, North 등이 명제 기호입니다.

이때, 항상 고정적 의미를 가진 명제가 있는데 자주 보셨듯이 True와 False 입니다. True는 항상 참인 명제이며 False는 항상 거짓인 명제입니다.

또한 우리는 간단한 문장들을 괄호와 논리 접속사(logical connective)로 연결해서 복합 문장을 만들 수 있습니다.

일반적인 접속사(연산자)는 아래와 같습니다.


 (부정)

부정(negation)이라고 부른다. 

리터럴(literal)은 원자적 문장 또는 원자적 문장의 부정인데, 전자를 긍정 리터럴(positive literal), 후자를 부정 리터럴(negative literal)이라고 부른다.

(논리곱)

논리곱 성분(conjunction) 이라고 부른다.

또는 연언문이라고 부른다.

(논리합)

논리합 성분(disjunction) 이라고 부른다.

또는 선언문이라고 부른다. 역사적으로는 '또는'을 뜻하는 라틴어 'vel'에서 비롯되었다.

(함의)

함의(implication) 또는 조건부 문장이라고 부른다.

또한 함의 문장을 규칙(rule)이나 if-then 문장이라고 부르기도 한다.

 (동치)

동치, 상호조건(biconditional)이라고 부른다.

문장들을 이러한 접속사(연산자)를 이용하여 복합 문장을 만들어 내면 그 또한 문장입니다.




1-2. 의미론(Semantics)


명제 논리의 구문을 살펴보았으니, 이제 명제 논리의 의미론을 살펴보도록 하겠습니다.

의미론(semantics)이란 특정 모형에 대한 문장의 진리를 결정하는 규칙들을 정의합니다. 명제 논리에서 모형은 모든 명제 기호의 진릿값(truth value), 즉 참(true) 또는 거짓(false)을 고정하는 역할만 합니다.


명제 논리의 의미론은 주어진 모형에 대해 임의의 문장의 진릿값을 계산하는 방법을 명시해야 합니다. 모든 문장은 원자적 문장과 위에서 본 다섯가지 접속사로 구성됩니다. 따라서 원자적 문장의 진릿값을 계산하는 방법과 각 접속사로 만들어지는 문장의 진릿값을 계산하는 방법을 명시해야 합니다.

원자적 문장에 대한 의미론은 다음과 같습니다.


- True는 모든 모형에서 참이고 False는 모든 모형에서 거짓이다.

- 다른 모든 명제 기호의 진릿값은 반드시 모형 자체에 명시되어 있어야 한다.


복합 문장에 대해서는 다섯 가지 규칙이 존재합니다.

이러한 규칙들은 임의의 모형 m 안의 임의의 문장 P와 Q에 대해 성립합니다.


P는 오직 m에서 P가 거짓일 때에만 참이다.

- P Q는 오직 m에서 P와 Q가 모두 참일 때에만 참이다.

- P Q는 오직 m에서 P 또는 Q가 참일 때에만 참이다.

- P Q는 m에서 P가 참이고 Q가 거짓이 아닌 한 참이다.

- P Q는 오직 m에서 P와 Q가 둘 다 참이거나 둘 다 거짓일 때에만 참이다.



이러한 규칙들은 복합 성분의 진릿값을 나열한 진리표(truth table)로 표현할 수 있습니다.



이러한 표를 이용하면 임의의 모형 m에 대한 임의의 문장 s의 진릿값을 간단한 재귀적 평가를 통해서 구할 수 있습니다.

즉, 아래와 같은 예시를 쉽게 참 또는 거짓을 구분할 수 있습니다.


논리곱, 논리합 등과 같은 논리 접속사에서는 일상적인 자연어로 이야기 할 때 다소 혼동되는 부분들이 있을 수 있습니다.

하나씩 살펴보도록 하겠습니다.


논리곱과 논리합, 부정의 진리표는 영어 문장에서의 해당 영어 단어 and, or, not의 의미를 잘 반영합니다. 그러나 헷갈리는 부분이 역시나 존재합니다.  라는 것은 P 또는 Q가 참일 때는 물론이고 둘 다 참일 때에도 참입니다. 하지만 단순히 or이라는 의미는 P 또는 Q가 참일 때 참이라는 의미만 가지고 있어서 헷갈릴 수 있습니다.

또한 이와는 다른 접속사인 '배타적 논리합(exclusive or, 줄여서 "xor")'은 두 논리합 성분이 모두 참일 때에는 거짓을 산출 합니다.

논리곱, 논리합, 부정은 크게 혼동되지는 않을 터이나 이제 설명드릴 함의와 같은 논리접속사에 대해서는 의미적으로 많은 혼동이 있을 수 있으니 천천히 이해하시길 바랍니다.


논리 접속사 (함의)에 대한 지리표는 언뜻 보면 "P가 Q를 함의한다" 또는 "만일 P이면 Q이다"라는 문장에 대한 우리의 직관적 이해와 잘 맞지 않는 것처럼 보입니다. 한 예시를 들어보도록 하겠습니다. 명제 논리에서는 P와 Q사이에 어떤 인과관계가 있어야 한다고 요구하지 않습니다. 즉, P와 Q사이에는 전혀 무관할 수 있습니다. "만일 5이 홀수이면 서울은 한국의 수도이다."는 일상 언어의 감각으로는 상당이 엉뚱합니다. 하지만 명제논리에서는 해당 복합 문장을 참이라고 말합니다.(통상적인 해석하에서) 복합 문장을 만들어 내는 각각의 문장에 대한 서로의 인과관계는 필요 없기 때문입니다.

또 다른 혼란스러운 점은, 전제가 거짓인 명제 논리 문장은 결론과는 무관하게 무조건 참입니다. 예를 들어, "만일 3이 짝수라면 범우는 똑똑하다."는 범우가 똑똑한지 똑똑하지 않은지와 상관없이 무조건 참인 문장입니다. 이상하게 느껴질지 모르겠지만, '만일 3이 짝수라면' 이라는 전제가 거짓이기 때문에 결론을 신경쓸 필요없이 해당 복합문장은 참이기 때문입니다.

이를 보다 의미적으로 쉽게 다가가기 위해서, PQ 라는 문장을 "만일 P가 참이면 나는 Q가 참이라고 주장한다. 참이 아니면 나는 어떠한 주장도 하지 않는다."라는 문장으로 생각하면 이해가 될 것 입니다. 이런 문장은 오직 P가 참이고 Q가 거짓일 때에만 거짓이기 때문입니다. 



1-3. 웜푸스 세계에서의 간단한 지식 기지


명제 논리의 구문과 의미론에 대해서 알아보았으니 이제 그것들을 기초로 하여 지난 포스트에서 살펴본, 웜푸스 세계의 지식 기지를 구축해 보도록 하겠습니다. 현재는 웜푸스 세계가 변하지 않는, 불변이(immutable) 측면들에 초점을 맞출 것이며 가변(mutable)적인 측면들은 나중에 살펴보겠습니다. 우선, 아래와 같은 명제 기호에 대한 정의를 가지고 시작하겠습니다.


는 만일 [x, y]에 구덩이가 있으면 참이다.

는 만일 [x, y]에 웜푸스가 있으면(죽음과 상관없이) 참이다.

는 만일 에이전트가 [x, y]에서 미풍을 지각하면 참이다.

는 만일 에이전트가 [x, y]에서 악취를 지각하면 참이다.


지난 포스트에서 우리는 (1,2)에 구덩이가 없음을 비공식적으로 유도하였습니다. 따라서 그에 해당 하는 문장인 을 공식적으로 유도하기 위해 명제 논리 문장들을 작성해 보도록 하겠습니다. Ri는 이후 편하게 문장을 사용할 수 있도록 문장에 각각의 문장을 나타냅니다.


- [1,1]에 구덩이가 없다.

   R1 : 


- 에이전트가 하나의 칸에 존재함 그 이웃칸에 구덩이가 있으면, 그리고 오직 그럴때에만 미풍을 지각할 수 있다.

   R2 : 

   R3 : 


- 앞의 문장들은 모든 웜푸스 세계에서 참이다. 이제 에이전트가 있는 특정한 세계에서 처음 방문한 두 칸에 대한 미풍 지각을 위한 문장들을 명시한다.

   R4 : 

   R5 : 


이렇게 하여 기본적인 지식 기지를 구축해 보았습니다.



1-4. 웜푸스 세계에서의 간단한 추리 절차(모형 점검 방식)


우리의 목표는 지식기지(KB)에서 KB|=a 인 문장 a가 존재하는지를 알아내는 것 입니다.

즉, 위에서 구축한 KB가 를 함축하는지 알아내야 합니다.

이를 알아내기 위해서 진행할 첫 번째 추리 알고리즘은 함축의 정의를 직접 구현하는, 모형 점검 접근방식의 알고리즘입니다.

다시말해 이번에 살펴볼 추리 절차는 모든 모형들을 나열하면서 이에 대해 지식 기지(KB)가 참인지 거짓인지 확인합니다. 그리고 지식 기지가 참인 모든 모형들에서 문장 a가 참인지 점검합니다. 


웜푸스 세계로 돌아 간다면 유관한 명제 기호는  입니다. 명제 기호가 총 7개 이므로 가능한 모형은 총 128개(2의 7승)입니다. 이를 전부 나열했을때 지식 기지가 참인 것을 확인하면 총 3가지의 모형을 볼 수 있습니다.



지식기지가 참이 되는 세가지 모형을 보면 우리가 알아내려한 가 참인 것을 알 수 있습니다. 따라서 (1,2)에는 구덩이가 없습니다. 반면 는 세가지 모형 중 둘에서는 참이고 하나에서는 거짓이므로 (2,2)에 구덩이가 있는지 없는지 알 수 없습니다.


이러한 추리 방법은 이전에 비공식적으로 (1,2)에 구덩이가 없다는 것을 추리한 것보다 보다 엄밀한 추리 방법입니다. 알고리즘에서 함축의 정의를 직접적으로 구현 하기때문에 건전합니다.(sound) 그리고 KB와 a에 대해 작동하고 반드시 종료되므로 완결적(complete) 입니다. 알고리즘이 반드시 종료된다는 것은, 확인할 모형의 개수가 유한하기 때문입니다.


하지만 확인할 모형의 개수가 유한하다는 것은 '적다'라는 의미와는 다릅니다. KB와 a의 기호가 총 n개 일떄 확인해야 할 모형은 총 2^n개 입니다. 따라서 알고리즘의 시간 복잡도는 O(2^n)입니다. 그렇다면 보다 많은 경우에서 우리가 확인한 것보다 더 많은 모형을 확인해야 할 것입니다. 따라서 우리는 훨씬 효율적인 알고리즘들을 뒤에서 살펴보겠습니다.


아래는 표준적인 논리 동치 관계들을 나타내는 것으로써 각각의 문장들로 인한 복합문장들의 참 또는 거짓을 구별할 때 사용됩니다.


이렇게 하여 명제 논리와 모형 점검 방식에 대해 알아보았습니다.

다음 포스팅에서는 정리 증명(theorem proving)을 이용해서 함축 관계를 확인하는 방법을 살펴보도록 하겠습니다.

궁금한 점이나 내용에 대한 피드백은 댓글을 이용해주세요 :)



블로그 이미지

Tigercow.Door

Back-end / Python / Database / AI / Algorithm / DeepLearning / etc

댓글을 달아 주세요

안녕하세요.

이번에는 python을 이용한 CSP algorithm 중 하나인 Einstein's puzzle(아인슈타인 퍼즐) 해결 코드를 작성해 보겠습니다.



먼저 아인슈타인 퍼즐에 대해 소개해 드릴게요.

아인슈타인의 퍼즐은 아래와 같은 문제입니다.


* 문제의 배경

1. 색깔이 서로 다른 5채의 집이 일렬로 지어져 있다.

2. 각 집에는 서로 다른 국적의 사람이 살고 있다.

3. 다섯 사람은 서로 다른 음료를 마시고, 서로 다른 담배를 피며, 서로 다른 동물을 기른다.


* 15개의 정보

1. 영국인은 빨간 집에서 산다.

2. 스웨덴인은 개를 기른다.

3. 덴마크인은 차를 마신다.

4. 초록집은 하얀집의 왼쪽 집이다.

5. 초록집에 사는 사람은 커피를 마신다.

6. 펠몰 담배를 피는 사람은 새를 기른다.

7. 노란집에 사는 사람은 던힐 담배를 피운다.

8. 한 가운데 집에 사는 사람은 우유를 마신다.

9. 노르웨이 인은 첫번째 집에 산다.

10. 블렌드 담배를 피우는 사람은 고양이를 기르는 사람 옆 집에 산다.

11. 말을 기르른 사람은 던힐 담배를 피우는 사람 옆 집에 산다.

12. 블루매스터 담배를 피는 사람은 맥주를 마신다.

13. 독일인은 프린스 담배를 피운다.

14. 노르웨이인은 파란 집 옆 집에 산다.

15. 블렌드 담배를 피우는 사람은 생수를 마시는 사람과 이웃이다.


위의 문제 배경과 15개의 정보가 있을때, '물고기를 기르는 사람의 국적은 무엇인가'?

(문제 출처: https://web.stanford.edu/~laurik/fsmbook/examples/Einstein%27sPuzzle.html)



이론적인 문제 풀이 방식은 아래와 같은 순서로 풀이가 가능합니다.

먼저 15개의 정보 중에서 확실히 알 수 있는 사실들을 이용한다. 15개의 정보 중에서 8, 9, 14번의 정보는 순서대로 하여 확실히 특정 사실을 알 수 있는 정보이다. 세가지 정보를 이용하면 위의 표와 같이 알 수 있다.


두번째로는 특정 조건들을 결합하여 이용한다. 먼저 4번 정보와 5번 정보를 이용하였다. 4번 정보를 통해 초록집은 하얀 집의 왼쪽 집임을 만족시켜야 한다. 4번 정보를 다르게 해석하면, 초록집의 오른쪽 집은 하얀 집이다. , 1, 2, 5번은 초록집이 될 수 없다. 그리고 5번 정보를 이용하면 초록 집은 3번이 될 수 없다. 따라서 남은 것은 4번뿐이므로 초록집은 4번이다. 또한 4번 집사람은 커피를 마시고 5번집은 하얀집이다. 다음 1번 정보를 확인하면, 2,4,5번 집은 이미 색이 있으므로 빨간집이 아니며 1번집은 노르웨이사람이 살고 있으므로 1번도 아니다. 3번 집이 빨간집이며 영국사람이 산다. 이어서 남은 1번은 자연스럽게 노란색 집이되며 7번 정보를 통해 1번집 사람은 던힐담배를 피운다. 또한 11번 정보를 통해 2번 집 사람은 말을 기른다.



이제 주어진 조건들을 응용하여 추리한다. 3번 정보와 12번 정보를 해석한다. 현재 남은 음료는 생수, , 맥주이다. 3번 정보에서 덴마크인이 차를 마신다고 하였으므로 노르웨이인은 생수 또는 맥주를 마실 것이다. 12번 정보에서 블루매스터 담배를 피우는 사람은 맥주를 마신다고 하였는데, 노르웨이인은 던힐 담배를 피우므로 맥주를 마시지 않는다. 즉 노르웨이인은 생수를 마신다. 또한 15번 정보를 통해서 2번 집 사람은 블렌드 담배를 피운다.

다시 12번 정보를 확인한다. 2번 집 사람은 차 또는 맥주를 마실 텐데 12번 정보에서 블루매스터 담배를 피는 사람이 맥주를 마신다고 하였다. 2번 집 사람은 블렌드 담배를 피우므로 맥주를 마시지 않고 차를 마신다. 그리고 남은 맥주는 당연히 5번 집 사람이 마시고, 5번 집 사람은 블루매스터 담배를 핀다. 이어서 3번 정보를 통해 차를 마시는 2번 집 사람은 덴마크인이다. 




마지막으로 남은 조건들로 추리를 완성한다. 먼저 13번 정보를 확인한다. 독일인은 4번 또는 5번집에 살텐데 5번 집 사람은 블루매스터 담배를 핀다. 따라서 13번 정보를 통해 독일인은 4번집에 살며 프린스 담배를 피운다. 이어서 5번집 사람은 스웨덴인이며, 3번집 사람은 펠몰담배를 핀다.

다음 6번 정보를 통해 펠몰담배를 피는 3번집 사람은 새를 기른다. 또한 2번 정보를 통해 5번 집에 사는 스웨덴인은 개를 기른다.

마지막으로 10번 정보를 통해서 3번 집사람은 이미 새를 키우는 것을 알았으므로 1번집 사람이 고양이를 기른다. 최종적으로 남은 4번집 사람은 물고기를 기른다.




이렇게 해서 아인슈타인의 퍼즐을 해결할 수 있습니다.

이러한 문제를 CSP(Constraint Satisfaction Problems: 제약조건 만족문제)라고 합니다.


아인슈타인 퍼즐을 해결하기 위해 2가지 정도의 알고리즘을 생각해볼 수 있습니다.

첫번째로는, 모든 경우의 수(5^25 or (5!)^5 둘 다 매우 큰 수 입니다...)를 고려하여 그 중 하나를 꺼내 정보와 비교하는 방법.

해당 방법은, 모든 경우의 수를 (5!)^5 으로 고려했을때 경우의 수가 약 240억개 입니다.

우리들의 컴퓨터로는 해결하기가 매우 힘들 수 있죠..


그래서 생각한 것이 두번째 알고리즘 입니다.

두번째 알고리즘은 각각을 카테고리 또는 조건으로 나누어 해결하는 방법입니다.

즉, A라는 조건을 다수의 배열 중 만족하는 배열을 찾아내는 것이 아니라 다수의 배열을 선언하기 전에 A라는 조건을 먼저 대입하고

이를 만족하는 배열 a가 있다면 a를 다음 조건, B에 대입하여 확인해나갑니다.

이렇게 해결을 진행하면 결국 DFS 방법으로 해결방법을 찾아나간다는 것을 아실 수 있습니다.


python으로 코드를 작성하기 위해 검색하던 중, python에서 제공하는 강력한 함수를 찾았습니다.

바로, python-constraint 함수 입니다.

함수에 대한 추가적인 사항은 아래 링크를 참고하시면 좋을 것 같습니다.

https://labix.org/python-constraint

https://pypi.python.org/pypi/python-constraint


python-constraint 함수를 통해, 직접 변수를 설정하고 제약조건을 추가하여 문제를 해결할 수 있습니다.

생각보다 code가 매우 간단해질 수 있어서 꼭 한번 다시 공부해보고 싶은 함수입니다.

추가적인 질문 이나 궁금사항은 댓글로 달아주시거나 이메일 주세요!


전체적인 python code와 실행결과는 아래와 같습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Houses
# 1 2 3 4 5
 
from constraint import *
problem = Problem()
 
nationality = ["영국""스웨덴""독일""노르웨이""덴마크"]
pet = ["개""고양이""새""말""물고기"]
cigarette = ["던힐""블렌드"
"펠몰""프린스""블루매스터"]
colour = ["빨강""초록""노랑""파랑""하양"]
beverage = ["커피""우유""맥주""생수""차"]
 
criteria = nationality + pet + cigarette + colour + beverage
problem.addVariables(criteria,[1,2,3,4,5])
 
problem.addConstraint(AllDifferentConstraint(), nationality)
problem.addConstraint(AllDifferentConstraint(), pet)
problem.addConstraint(AllDifferentConstraint(), cigarette)
problem.addConstraint(AllDifferentConstraint(), colour)
problem.addConstraint(AllDifferentConstraint(), beverage)
 
problem.addConstraint(lambda e, r: e == r, ["영국","빨강"])#1
problem.addConstraint(lambda s, d: s == d, ("스웨덴","개"))#2
problem.addConstraint(lambda c, g: c == g, ("커피","초록"))#5
problem.addConstraint(lambda u, t: u == t, ("덴마크","차"))#3
problem.addConstraint(lambda g, i: g-== 1, ("하양","초록"))#4
problem.addConstraint(lambda o, s: o == s, ("펠몰","새"))#6
problem.addConstraint(lambda k, y: k == y, ("던힐","노랑"))#7
problem.addConstraint(InSetConstraint([3]), ["우유"])#8
problem.addConstraint(InSetConstraint([1]), ["노르웨이"])#9
problem.addConstraint(lambda c, f: abs(c-f) == 1, ("블렌드","고양이"))#10
problem.addConstraint(lambda k, h: abs(k-h) == 1, ("던힐","말"))#11
problem.addConstraint(lambda l, o: l == o, ["블루매스터","맥주"])#12
problem.addConstraint(lambda j, p: j == p, ["독일","프린스"])#13
problem.addConstraint(lambda k, h: abs(k-h) == 1, ("노르웨이","파랑"))#14
 
solution = problem.getSolutions()[0]
 
for i in range(1,6):
  for x in solution:
    if solution[x] == i:
      print (str(i), x)
cs



블로그 이미지

Tigercow.Door

Back-end / Python / Database / AI / Algorithm / DeepLearning / etc

댓글을 달아 주세요

많은 사람들에게 유명한
missionaries and cannibals problem
(선교사와 식인종 문제)

강의 왼쪽에 선교사 3명과 식인종 3명이 있고 모두를 강 오른쪽으로 건너게끔 해야한다.
1. 강의 왼쪽이나 오른쪽에서 선교사의 수보다 식인종의 수가 많으면 안된다.
2. 보트에는 최대 2명이 탑승할 수 있으며 최소1명이 탑승해야 움직일 수 있다.

학교 AI시간에 각 state와 action에 대해서 제출하라는 과제가 있었는데 그것을 통해 DFS algorithm을 응용하여 python으로 구현해보았다.
분명히 잘못된 부분이나 부족한 부분이 있을 것 같은데
일단 포스팅을 진행하고 천천히 더 공부해야 겠다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
import copy
# 전역변수 선언
state = [1,[3,3],[0,0]]
action = [1,0,0]
goal = [2,[0,0],[3,3]]
visited = []
stack = []
temp = []
 
# 함수선언
# 왼쪽에서 오른쪽으로 가는 움직임 반환
def LtoRaction():
  return [[1,1,1],[1,1,0],[1,2,0],[1,0,1],[1,0,2]]
 
# 오른쪽에서 왼쪽으로 가는 움직임 반환
def RtoLaction():
  return [[2,1,1],[2,1,0],[2,2,0],[2,0,1],[2,0,2]]
 
# 스테이트와 액션에 맞게 움직이기
def move(state,action):
  after_state = [0,[0,0],[0,0]]
  after_state = copy.deepcopy(state)
  if (action[0== state[0]):
    # 보트가 왼쪽에서 오른쪽으로 움직이는 행동
    if (after_state[0]==1):
      after_state[0= 2      
      after_state[1][0= after_state[1][0- action[1]
      after_state[1][1= after_state[1][1- action[2]
      after_state[2][0= after_state[2][0+ action[1]
      after_state[2][1= after_state[2][1+ action[2]
    # 보트가 오른쪽에서 왼쪽으로 움직이는 행동
    elif (after_state[0]==2):
      after_state[0= 1            
      after_state[1][0= after_state[1][0+ action[1]
      after_state[1][1= after_state[1][1+ action[2]
      after_state[2][0= after_state[2][0- action[1]
      after_state[2][1= after_state[2][1- action[2]
 
    return after_state
 
  else:
    print("@ @ @ 보트의 위치와 action의 시작 위치가 맞지 않습니다.@ @ @")
    return 0
 
# 올바른 움직임 인지 체크
def check(after_state):
  left = after_state[1]
  right = after_state[2]
  # 선교사 또는 식인종의 수가 음수이면 잘못된 것
  if (left[0]<0)or(left[1]<0)or(right[0]<0)or(right[1]<0):
    return -1
  # 선교사 또는 식인종의 수가 4를 넘으면 잘못된 것
  elif (left[0]>=4)or(left[1]>=4)or(right[0]>=4)or(right[1]>=4):
    return -1
  # 왼쪽, 오른쪽 모두 선교사의 숫자가 식인종보다 크거나 많아야함
  elif (left[0]>=left[1]) and (right[0]>=right[1]):
    return 1
  # 왼쪽 선교사의 숫자가 0일때 오른쪽의 선교사의 숫자가 3이면 정상
  elif (left[0]==0and (right[0]==3):
    return 2
  # 왼쪽 선교사의 숫자가 3일때 오른쪽의 선교사의 숫자가 0이면 정상
  elif (left[0]==3and (right[0]==0):
    return 2
  else:
    return -3
 
# 목표에 도달했을때 과정 출력
def done(list):
  print("끝!",list)
  temp = []
  num = -1
  while list:
    temp = list.pop(0)
    num += 1
    if (temp[0]==1):
      print("Moon.B.W   * * * * * 현재상태 * * * * *",num,"번째 움직임")
      print(" --------------------------------------------------")
      print("|                  ||~~~~~~~~~~||                  |")
      print("|   선교사 : %d명   ||~~~~~~~~~~||   선교사 : %d명   |"%(temp[1][0],temp[2][0]))
      print("|                  ||<->~~~~~~~||                  |")    
      print("|   식인종 : %d명   ||~~~~~~~~~~||   식인종 : %d명   |"%(temp[1][1],temp[2][1]))
      print("|                  ||~~~~~~~~~~||                  |")
      print(" --------------------------------------------------")
    
    elif (temp[0]==2):
      print("Moon.B.W   * * * * * 현재상태 * * * * *",num,"번째 움직임")
      print(" --------------------------------------------------")
      print("|                  ||~~~~~~~~~~||                  |")
      print("|   선교사 : %d명   ||~~~~~~~~~~||   선교사 : %d명   |"%(temp[1][0],temp[2][0]))
      print("|                  ||~~~~~~~<->||                  |")
      print("|   식인종 : %d명   ||~~~~~~~~~~||   식인종 : %d명   |"%(temp[1][1],temp[2][1]))
      print("|                  ||~~~~~~~~~~||                  |")
      print(" --------------------------------------------------")
  print("움직인 횟수 :",num,"번")
 
# 깊이 우선 탐색으로 솔루션 찾기
def DFS():
  global stack, visited, goal
  while stack:
    none = 0
    # 하나의 노드를 꺼내서 탐색 시작
    now_state = stack.pop()
    state = copy.deepcopy(now_state)
    # 기록
    visited.extend([now_state])
    # 보트가 왼쪽에 있는 상태
    if (now_state[0]==1):
      if (now_state == goal):
        print("탐색 성공!")
        done(visited)
        return 0
      else:
        available_action = LtoRaction()
        while(available_action):
          action = available_action.pop()
          after_state = move(now_state,action)
          can = check(after_state)
          if (can>0):
            if after_state not in visited:
              none = 1
              stack.extend([after_state])
          else:
            pass
        if (none==0):
          visited.pop()
 
    # 보트가 오른쪽에 있는 상태
    elif (now_state[0]==2):
      if (now_state == goal):
        print("탐색 성공!")
        done(visited)
        return 0
      else:
        available_action = RtoLaction()
        while(available_action):
          action = available_action.pop()
          after_state = move(now_state,action)
          can = check(after_state)
          if (can>0):
            if after_state not in visited:
              none = 1
              stack.extend([after_state])
          else:
            pass
        if (none==0):
          visited.pop()
 
# 실행
stack.extend([state])
DFS()
cs



블로그 이미지

Tigercow.Door

Back-end / Python / Database / AI / Algorithm / DeepLearning / etc

댓글을 달아 주세요