[수학] 강건너기 퍼즐과 그래프이론

최근에 퀴즈 포스팅을 위해 여러가지 퀴즈 책과 논리책 수학책(?) 을 보고 있는데

오늘은 그 중 강건너기퍼즐 의 일반화에 꼳혀버렸다.

강건너기 퍼즐문제란, 위키피다아의 예시를 가져와 보면,

1 . 여우, 거위, 콩자루 문제 : 농부가 여우, 거위, 콩자루를 가지고 강을 건너려고 한다. 농부가 없을 때, 여우와 거위가 같이 있으면 여우는 거위를 잡아먹고, 거위와 콩자루가 같이 있으면 거위는 콩자루를 먹어 치운다. 노를 저을 수 있는 것은 농부 뿐이며, 한 번에 한 품목만 옮길 수 있다고 할 때, 아무 피해없이 세 품목을 모두 강 건너로 옮겨야 한다.

2 . 선교사와 식인종 문제 : 선교사 세 명과 식인종 세 명이 강을 건너려고 한다. 강의 어느 쪽이든 선교사보다 식인종의 수가 많게 되면 식인종은 선교사를 해친다. 그러나 선교사와 식인종의 수가 같거나 선교사가 많으면 아무도 해치지 않는다. 한 번에 두 사람만 보트에 탈 수 있다고 할 때, 여섯 사람이 무사히 강을 건너도록 해야 한다.

일단 나는 선교사와 식인종 문제에 꼳혔다, 저 문제는 사실상 아이패드 게임이나 TV 예능에도 종종 나오는 문제니 ㅎㅎ [살짝 변형된 문제가 곧(?) 퀴즈 문제로 나올 예정이다]

위 문제의 정답은 이미 위키피디아-영어판 에 친절하게 나와있다. 영어가 불편하다면 이 페이지에서도 풀이를 확인 할 수 있다.

---

뭐 사실 답은 몇번 해보면 시행착오로 충분히 얻을 수 있는 것이니 답 자체는 문제가 되지 않았다. 문제는 저 문제의 일반화였다.

혹시 저 문제를 일반화 할 수는 없을까?

아니면 저 문제를 가장 효과적으로 풀 수 있는 방법은 없을까?

란 고민에 빠진 나는 검색을 통해서 일반화 pgr21

이런 일반화에 대해서 알았다.

아닛!

사실 컴공과 수업을 듣다보면 이런 퀴즈같은 문제들을 푸는 알고리즘을 제시하여라
코드를 짜라 같은 문제들이 숙제로 나오곤 하니 분명 학술적으로 누군가 연구를 했던 주제라고 생각이 들었긴 했다. [하지만 내 전공은 아닛.. 난 문과같은 이과였..]

대표적으로 한 컴공과의 수업 강의자료

그리고 좀 더 찾아보니

Then there is the Japanese Family River-Crossing puzzle with its extremely complex rules. Also worth noting is the popular Missionaries-and-Cannibals problem, found in many AI text books.

아아닛! AI textbook 과 알고리즘 책의 기본 문제 중 하나로도 나온다니

---

아 그래 나온다고 치자. 어떻게 푸는데? R-언어로 코드 짜서 푼다고 치는데
거기에 숨겨진 수학적 구조는 먼데?

바로 그래프 이론이다!

사실 저 선교사 퍼즐 문제는 그래프 이론 개론 책에 떡하니 연습문제로 등장한다.

대표적으로 Gary Chartrand 의Introductory Graph Theory 를 보라

사실 저 정도 문제면 수형도를 통해 쉽게 확인해 볼 수 있다.

아니면 initial state 와 finial state 를 그래프로 표현해서

참고

하지만 나의 목표는 이 문제만 푸는 것이 아니었기에..

검색을 통해서 여러 논문을 찾았다. 그 중

비교적 최신 논문(2014)에서 원하는 답을 찾았다. Transition graph 를 이용하여 강건너기 문제의 일반화에 대한 풀이법을 다루고 있다.

앞의 pgr 의 일반화와 일치한다.

Technical 하게는 처음 initial state 를 가지고 어떻게 evolve 하는가에 대한 것으로 edge expansion 을 통해 hamming distance 를 구하는 문제인데... [ㅋㅋㅋㅋ 일단 이런 이론들을 접해 본적이 거의 없기에 용어가 너무 불편하다. 그래프 이론 전공한 친구에게 이 논문을 던져줬는데 ㅋㅋㅋㅋ NP-complete problems 라고 오히려 나한테 더 요상한 자료들을 던져주더라... 지금 너가 이걸 제대로 이해하려면 그래프 이론 개론부터 다시 보고 오라고.... 최소 2년 잡고 파야된다고..... ;; ]

ㅋㅋㅋㅋ hamming distance 어디서 들어봤나 했더니 morse theory 에 나왔었네..

당시에 이런거 어디에 써먹냐 했더니.. ㅋㅋㅋㅋㅋ

discrete structure 에서 엄청 쓰이고 또 CS 쪽에서 엄청 쓰이고 있나보군...

아 관련 수업이야 기껏해야 이산수학만 들었는데

그것도 이산수학 수업을 발로 들었던 나로써는

논물을 봐도 증명과정을 따라가기가 너무 어렵다...

아 학교 다닐 때 morse theory 나

coding theory 이런 수업도 좀 듣고 할걸...

그래서 나의 올해 to do list 에 그래프 이론이 하나 추가가 되었다.

한동안은 poker ocw만 듣고 있었는데...

예전에 이산수학 수업을 들으며 잠깐 몇주 배운게 다인 그래프 이론..

학교 다닐때나 물론 졸업하고 나서도 내가 써먹을 곳이 없다고 무시(?)했던 그래프 이론

요즘들어서 실생활에 확률, 통계, 조합, 그래프, 이산수학 이런 것들이 녹아져 있다는 것을 피부로 느끼고 있다. [학교 다닐 때 뭐한거냐..]

요새 보니까 금융수학이니 보험수학, 경영수학..

이게 수학의 힘인가? ;;ㅋㅋㅋ

공부하자!