오늘은 Travelling Salesman Problem 코딩공부를 시작하는 날이예요~^^*
근데요~^^* 지구 곳곳을 여행하는 외판원은 지구온난화 현상도 환경재난의 현장도 그리고 이를 극복해 보려는 사람들의 용기와 노력도 목격하곤 할 것 같아요~^^*.
이른 아침, 공연 1 작품 감상하시고 계셔요~^^* 코딩공부 정리해서 돌아올게요~, 쓩~^^*
네~^^*
오늘은, 여러 도시들을 이동하는 경로들에 대한 경우의 수를 살펴 보도록 할게요~^^*
왜!!! 컴퓨터는 도시들을 연결했을 때 가장 짧은 총 이동경로를 찾아내는 것을 사람의 눈보다도 더 어려워하는지…그 이유가 혹시….???
(1)A이고 B이고 C인 경우와
(2) A이거나 B이거나 C인 경우는
서로 다른 것 같아요~^^*
첫번째 선택에 따라 다음 선택이 결정되는 관계는 곱셈의 관계
선택들이 서로 독립적인 관계는 덧셈의 관계에 놓이는 것 같은데요~^^*
그런데요~~^^*
우리가 앞으로 공부할 Travelling Salesman Problem에서 도시들을 연결하는 경우는 곱셈의 관계와 덧셈의 관계 둘 다 적용되는 것 같아요.
A라는 도시 한 곳을 여행하는 경우의 수는?
<< A >>
경우의 수: 1 A와 B라는 도시 두 곳을 연결해서 여행하는 경우의 수는?
<< A -> B >>
<< B -> A >>
경우의 수: 2
(1)첫 번째 도시: A 또는 B가 선택되기 때문에 => 1 + 1 = 2
(2)두 번째 도시: 단 하나의 도시가 남았기 때문에 => 1
첫 번째 도시 선택에 따라 두 번째 도시가 결정되기 때문에
=> (1),(2) 두 경우 수의 관계는 곱셈의 관계
=> 총 경우의 수: 2 * 1 = 2 A와 B와 C라는 도시 세 곳을 연결해서 여행하는 경우의 수는?
<< A -> B -> C >>
<< A -> C -> B >>
<< B -> A -> C >>
<< B -> C -> A >>
<< C -> A -> B >>
<< C -> B -> A >>
경우의 수: 6
(1)첫 번째 도시: A 또는 B 또는 C가 선택되기 때문에 => 1+1+1 = 3
(2)두 번째 도시: 남은 두 개의 도시 중 어느 하나가 선택되기 때문에 => 1+1 = 2
(3)세 번째 도시: 단 하나의 도시가 남았기 때문에 => 1
첫 번째 도시 선택에 따라 두 번째 도시가 결정되고,
두 번째 도시 선택에 따라 세 번째 도시가 결정되기 때문에
=> (1),(2), (3) 세 경우 수의 관계는 곱셈의 관계
=> 총 경우의 수: 3 * 2 * 1 = 6A와 B와 C와 D라는 도시 네 곳을 연결해서 여행하는 경우의 수는?
<< A -> B -> C -> D >>
<< A -> B -> D -> C >>
<< A -> C -> B -> D >>
<< A -> C -> D -> B >>
<< A -> D -> B -> C >>
<< A -> D -> C -> B >>
<< B -> A -> C -> D >>
<< B -> A -> D -> C >>
<< B -> C -> A -> D >>
<< B -> C -> D -> A >>
<< B -> D -> A -> C >>
<< B -> D -> C -> A >>
<< C -> A -> B -> D >>
<< C -> A -> D -> B >>
<< C -> B -> A -> D >>
<< C -> B -> D -> A >>
<< C -> D -> A -> B >>
<< C -> D -> B -> A >>
<< D -> A -> B -> C >>
<< D -> A -> C -> B >>
<< D -> B -> A -> C >>
<< D -> B -> C -> A >>
<< D -> C -> A -> C >>
<< D -> C -> C -> A >>
경우의 수: 24
(1)첫 번째 도시: A 또는 B 또는 C 또는 D가 선택되기 때문에 => 1+1+1+1 = 4
(2)두 번째 도시: 남은 세 도시 중 어느 하나가 선택되기 때문에 => 1+1+1 = 3
(3)세 번째 도시: 남은 두 도시 중 어느 하나가 선택되기 때문에 => 1+1 = 2
(4)네 번째 도시: 단 하나의 도시가 남았기 때문에 => 1
첫 번째 도시의 선택에 따라 두 번째 도시가 선택되고,
두 번째 도시의 선택에 따라 세 번째 도시가 선택되고,
세 번째 도시의 선택에 따라 네 번째 도시가 선택되기 때문에
=> (1), (2), (3), (4) 네 경우 수의 관계는 곱셈의 관계
=> 4 * 3 * 2 * 1 = 241 = 1
2*1 = 2
3*2*1 = 6
4*3*2*1 = 24
5*4*3*2*1 = 120
6*5*4*3*2*1 = 720
와우!!! 6개의 도시를 연결하는 경우의 수는 무려 720이 되네요.
이것은??? 이것은?? 이것은? 바로! 바로!! 바로!!! 팩!토!리!얼!~~^^*
그러면 10개의 도시를 연결하는 경우의 수는?
와우!!! 10! = 10×9×8×…×2×1 = 3,628,800
네~^^*
사람의 눈은 거리를 계산하지 않더라도 두 도시 사이의 거리의 크기를 시각적으로 가늠할 수 있지만~~
컴퓨터는 눈이 없어서…..시각적으로 선택하지 못하고…모든 도시들을 연결하는 모든 경우를 다 계산한 다음, 가장 짧은 총 거리를 가진 경우를 하나 선택하게 되어서….
도시 10개를 연결해 보려고만 해도…무려…3백6십2만8천8백 경우 모두 그 총 거리를 계산해 봐야하기 때문에….
컴퓨터가 힘들어 할 수 있을 것 같아요….
30! = 265,252,859,812,191,058,636,308,480,000,000
음…어떻게 읽어야 할 지도 잘 모르겠네요…
사람의 눈이 참 소중하고 감사한 것 같아요….
어머! 근데요!!
어쩌다보니!! 말이예요!!
오늘 우리는요!!!
Factorial 팩토리얼과 친해지는 시간을 함께 가져본 것 같아요~~^^*
오늘 저와 함께 Travelling Salesman Problem 여행하는 외판원 문제 속의 Factorial 팩토리얼을 발견해 주셔서 감사합니다~^^*
근데요~~^^* 오늘요~~^^*
코딩공부를 하다보니 우리 신체기관의 소중함도 다시 새기게 되고요~^^* Factorial에 관련된 재미난 사실들도 알게 되고요~^^*
코딩공부 참~~~^^* 재미있는 것 같아요~~~^^* 그죠~~~^^*?
가끔 아리송해서 머리도 심장도 다치는 듯 어렵기도 하지만…결국 너무 재미있어서 다가가게 되는 매력둥이~~^^* 우우웅~^^*
바로 우리의 코딩공부~~^^*
매력둥이 코딩공부와의 즐거운 시간~~~!!! 내일도 저와 함께 나누실 거죠~~^^*?
네~~^^* 좋아요~~^^* 고마워요~~^^*
내일 또 만나요, 그럼~~~^^*
오늘도~~^^*
멋진 아침!
반가운 만남과 기쁨 나누는 하루 보내시고요~^^*
뿌듯하고 따뜻한 밤 코~~^^* 하시기 바래요~~^^*
네~~^^* 꿈은 이루어 집니다~~^^*
Silverback9 
댓글 남기기