검색 및 문제 해결

많은 문제를 검색 문제라고 표현할 수 있습니다. 이를 위해서는 대안 선택과 그 결과를 공식화하는 것부터 시작해야 합니다.

실제 검색: A에서 B로 이동

여러분이 외국 도시의 특정 주소(예: 호텔)에 있고 대중교통을 이용해 다른 주소(예: 좋은 레스토랑)로 이동하고 싶다고 상상해 보세요. 여러분은 무엇을합니까? 여러분도 많은 사람들과 같다면 스마트폰을 꺼내서 목적지를 입력하고 지시에 따르기 시작합니다.

이 질문은 검색 및 계획 문제 클래스에 속합니다. 비슷한 문제는 자율주행차와 게임용 AI를 통해 해결되어야 합니다. 예를 들어, 체스 게임에서 A에서 B로 말을 가져오는 것보다 상대방으로부터 자신의 말을 안전하게 지키는 것이 더 어렵습니다.

문제를 해결하는 방법에는 여러 가지가 있는 경우가 많으며, 그 중 일부는 시간, 노력, 비용 또는 기타 기준 측면에서 더 바람직할 수 있습니다. 서로 다른 검색 기술은 서로 다른 솔루션으로 이어질 수 있으며 고급 검색 알고리즘을 개발하는 것은 확립된 연구 분야입니다.

우리는 실제 검색 알고리즘에 초점을 맞추지 않을 것입니다. 대신, 우리는 문제 해결 과정의 첫 번째 단계인 선택과 그 결과를 정의하는 단계를 강조합니다. 이는 종종 사소하지 않고 신중한 사고가 필요할 수 있습니다. 또한 우리의 목표가 무엇인지, 즉 언제 문제가 해결되었다고 생각할 수 있는지 정의해야 합니다. 이 작업이 완료되면 초기 상태에서 목표까지 이어지는 일련의 작업을 찾을 수 있습니다.

이 장에서는 두 가지 종류의 문제에 대해 설명합니다.

• 하나의 "에이전트"만 있는 정적 환경에서 검색 및 계획
• 2인 플레이어("에이전트")가 서로 경쟁하는 게임

이러한 범주는 가능한 모든 실제 시나리오를 다루지는 않지만 주요 개념과 기술을 보여주기에는 충분히 일반적입니다.

내비게이션이나 체스 게임과 같은 복잡한 검색 작업을 다루기 전에 AI를 통해 문제를 해결할 수 있는 방법에 대한 이해를 높이기 위해 훨씬 단순화된 모델부터 시작하겠습니다.

장난감 문제: 닭 건너기

아이디어를 설명하기 위해 간단한 퍼즐부터 시작하겠습니다. 노 젓는 보트에 탄 로봇은 세 가지 화물(여우, 닭, 닭 사료 자루)을 강을 건너 이동해야 합니다. 여우는 기회가 있으면 닭을 먹고, 닭은 기회가 있으면 닭 사료를 먹지만 둘 다 바람직한 결과는 아닙니다. 로봇은 동물이 근처에 있을 때 동물이 해를 끼치는 것을 방지할 수 있지만 로봇만이 노 젓는 배를 작동할 수 있고 화물 중 두 개만 로봇과 함께 노 젓는 배에 실을 수 있습니다. 로봇은 어떻게 모든 화물을 강의 반대편 강둑으로 옮길 수 있습니까?

우리는 로봇, 노 젓는 배, 여우, 닭, 닭 모이 등 다섯 가지 움직일 수 있는 물체가 식별되었음을 참고하여 퍼즐을 모델링할 것입니다. 원칙적으로는 5명 각각이 강 양쪽에 있을 수 있지만 로봇만이 노 젓는 배를 조종할 수 있기 때문에 두 사람은 항상 같은 쪽에 있게 됩니다. 따라서 각각에 대해 두 가지 가능한 위치를 가진 네 가지가 있으며, 이는 16개의 조합을 만들고 이를 상태라고 부릅니다.

닭 교차 퍼즐의 상태

우리는 주에 짧은 이름을 붙였습니다. 그렇지 않으면 주에 대해 이야기하는 것이 번거로울 것이기 때문입니다. 이제 시작 상태는 NNNN이고 목표 상태는 FFFF라고 말할 수 있습니다. "시작 상태에서 로봇은 가까운 쪽에 있고, 여우는 가까운 쪽에 있고, 닭도 가까운 쪽에 있고, 닭 모이도 가까운 쪽에 있고, 목표 상태에서 로봇은 먼 쪽에 있습니다." 등과 같은 것이 아닙니다.

이러한 상태 중 일부는 퍼즐 조건에 의해 금지됩니다. 예를 들어, NFFN 상태(로봇은 닭 모이와 가까운 쪽에 있지만 여우와 닭은 먼 쪽에 있다는 의미)에서 여우는 우리가 먹을 수 없는 닭을 먹게 됩니다. 따라서 NFFN, NFFF, FNNF, FNNN, NNFF 및 FFNN 상태를 배제할 수 있습니다(추론이 의심스러운 경우 각 상태를 확인할 수 있습니다). 이제 다음과 같은 10가지 상태가 남았습니다.

다음으로 우리는 어떤 상태 전환이 가능한지 알아낼 것입니다. 즉, 로봇이 일부 품목을 화물로 싣고 보트를 저을 때 각 경우의 결과 상태가 무엇인지 알아봅니다. 전환 다이어그램을 그리는 것이 가장 좋으며 모든 전환에서 첫 번째 문자가 N과 F 사이를 번갈아 가며 나타나기 때문에 N으로 시작하는 상태(로봇이 가까운 쪽에 있음)를 한 행에 그리고 F로 시작하는 상태를 다른 행에 그리는 것이 편리합니다.

이제 전환을 그려보겠습니다. 한 노드에서 다른 노드를 가리키도록 방향이 있는 화살표를 그릴 수 있지만 이 퍼즐에서는 전환이 대칭입니다. 로봇이 상태 NNNN에서 상태 FNFF로 행할 수 있다면 로봇은 FNFF에서 NNNN으로 반대 방향으로도 똑같이 잘 행할 수 있습니다. 따라서 방향이 없는 선으로 전환을 그리는 것이 더 간단합니다. NNNN부터 시작하여 FNFN, FNFF, FFNF 및 FFFN으로 이동할 수 있습니다.

그런 다음 나머지를 채웁니다.

이제 우리는 해결책에 더 가까워진 것 같지 않은 채 퍼즐에 대해 꽤 많은 작업을 수행했으며, 여러분이 "자연 지능"을 사용하여 이미 전체 퍼즐을 풀 수 있었을 것이라는 데는 거의 의심의 여지가 없습니다. 그러나 가능한 해결책의 수가 수천, 수백만으로 증가하는 보다 복잡한 문제의 경우 어려운 부분은 간단한 컴퓨터로 수행하기에 적합하기 때문에 우리의 체계적 또는 기계적 접근 방식이 빛을 발할 것입니다. 이제 대체 상태와 그 사이의 전환을 공식화했으므로 나머지는 기계적인 작업이 됩니다. 즉, 초기 상태 NNNN에서 최종 상태 FFFF까지의 경로를 찾는 것입니다.

다음 그림에는 그러한 경로 중 하나가 색칠되어 있습니다. 경로는 NNNN에서 FFFN(로봇이 여우와 닭을 반대쪽으로 가져감), NFNN(로봇이 시작 쪽에서 닭을 다시 가져옴), 마지막으로 FFFF(이제 로봇이 닭과 닭 사료를 반대쪽으로 이동할 수 있음)로 진행됩니다.

상태 공간, 전환 및 비용

계획 문제를 공식화하기 위해 상태 공간, 전환 및 비용과 같은 개념을 사용합니다.

연습문제

연습 5: 더 작은 노 젓는 배

이 퍼즐의 전통적인 버전에서는 로봇이 보트에 물건 하나만 넣을 수 있습니다. 상태 공간은 여전히 동일하지만 가능한 전환 수는 더 적습니다.

아래 가능한 상태가 포함된 다이어그램을 시작점으로 사용하여 가능한 전환을 그립니다(연필과 종이를 사용하는 것이 없는 것보다 훨씬 쉽습니다).

상태 전이 다이어그램을 그린 후 NNNN에서 FFFF까지의 최단 경로를 찾고 그 경로에서 전이 횟수를 계산합니다.

답변을 최단 경로의 전환 수(12와 같은 단일 숫자)로 입력하세요. 솔루션에 대한 추가 설명을 포함하지 마십시오. 힌트: 상태 수를 세지 않고 전환 수를 계산하세요. 예를 들어 NNNN→FFNF→NFNF→FFFF 경로의 전환 수는 4가 아닌 3입니다.

01계산하거나 판단한 답을 입력하세요.

답안 확인하기

연습문제

연습 6: 하노이의 탑

또 다른 퍼즐을 풀겠습니다. 유명한 하노이 타워입니다. 우리 버전의 퍼즐에는 3개의 말뚝과 2개의 디스크가 포함됩니다. 하나는 크고 하나는 작습니다(실제로 디스크는 여러 개 있을 수 있지만 연습에서는 원리를 설명하는 데 2개면 충분합니다).

초기 상태에서는 두 디스크가 모두 첫 번째(가장 왼쪽) 말뚝에 쌓여 있습니다. 목표는 디스크를 세 번째 말뚝으로 옮기는 것입니다. 위에 다른 디스크가 없는 한 한 번에 하나의 디스크를 페그에서 다른 페그로 이동할 수 있습니다. 작은 디스크 위에 큰 디스크를 올려 놓을 수 없습니다.

이 그림은 초기 상태와 목표 상태를 보여줍니다. 또한 7개의 다른 상태도 있으므로 가능한 상태의 총 개수는 9개입니다. 큰 디스크를 배치하는 세 가지 방법과 각 디스크에 대해 작은 디스크를 배치하는 세 가지 방법이 있습니다.

여러분의 작업: 상태 다이어그램을 그립니다. 다이어그램에는 게임에서 가능한 9가지 상태가 모두 포함되어야 하며, 선으로 연결되어 있어야 합니다. 가능한 전환을 보여줍니다. 아래 그림은 상태 다이어그램의 전체 구조와 처음 세 가지 상태의 위치를 ​​보여줍니다. 그것은 다음을 보여줍니다 시작 상태(상단 모서리)에서 작은 디스크를 움직여 다른 두 가지 상태로 이동할 수 있습니다. 나머지 상태를 올바른 위치에 배치하여 상태 다이어그램을 완성하세요. 전환은 다시 대칭이며 다이어그램에서 옆으로(왼쪽 또는 오른쪽) 또는 위로 이동할 수도 있습니다.

펜과 종이를 사용하여 작업을 해결한 후 다이어그램에서 어떤 상태가 어떤 노드에 속하는지 선택하여 솔루션을 입력하세요. (힌트: 각 상태는 정확히 하나의 노드에 속합니다).

위 다이어그램의 각 노드(1~6)에 대해 아래에서 올바른 상태 A~F를 선택하세요.

01상자 1에는 어떤 상태가 있어야 합니까?

상태 A상태 B상태 C상태 D상태 E상태 F

02상자 2에는 어떤 상태가 있어야 합니까?

상태 A상태 B상태 C상태 D상태 E상태 F

03상자 3에는 어떤 상태가 있어야 합니까?

상태 A상태 B상태 C상태 D상태 E상태 F

04상자 4에는 어떤 상태가 있어야 합니까?

상태 A상태 B상태 C상태 D상태 E상태 F

05상자 5에는 어떤 상태가 있어야 합니까?

상태 A상태 B상태 C상태 D상태 E상태 F

06상자 6에는 어떤 상태가 있어야 합니까?

상태 A상태 B상태 C상태 D상태 E상태 F

답안 확인하기