Traveling Salesman Problem, 외판원 문제. 이번학기에 X줄 타면서 한과제... 대략 3박 4일 걸렸다.. 순수 코딩시간만 해도 머리가 잘 안돌아서 40시간쯤은 했.... 여튼...
위키피디아에서 말하기를..
Q: given a number of cities and the costs of traveling from any city to
any other city, what is the least-cost round-trip route that visits
each city exactly once and then returns to the starting city?
즉, 주어진 도시와 도시들 사이의 거리를 알때, 모든 도시를 한번씩 방문하여 제자리로 돌아 오는 최단 거리의 경로는 어떻게 될까?
두가지 방법으로 문제를 접근해 보았다. 1. Branch and Bound
Branch and Bound
꽤나 간단한 알고리즘 이다. 예를 들어 4개의 도시가 있다고 하고 각각의 거리를 아래의 표와 같이 나타내어보자.
A
B
C
D
A
2
7
9
B
2
5
4
C
7
5
1
D
9
4
1
우선 세도시를 선택한다. A,B,C 라하면. 세도시를 방문하는 법은 한가지 A-B-C 뿐이다. 즉, [A,B] + [B,C] + [C.A] = 2 + 5 + 7 = 14 이다.
여기서 D 도시를 경유하기 위해 최적의 위치를 찾는다. A,B 사이에 A,D,B 를 시도해보고 B,C 사이에 B,D,C 를 시도해보고 C,A 사이에 C,D,A 를 시도한후 거리가 최소가 되는 경우를 선택한다.
즉, B-D-C 에 넣어야 최단 경로가 된다.. 결론적으로 A-B-D-C 의 경로로 여행하게 된다.
이것을 모든 도시를 다 방문 했을때까지 반복 하면 되는것이다.
2. Christofides Algorithm
more..
Definition: (1) A heuristic algorithm to find a near-optimal solution to the traveling salesman problem. Step 1: find a minimum spanning tree T. Step 2: find a perfect matching M among vertices with odd degree. Step 3: combine the edges of M and T to make a multigraph G. Step 4: find an Euler cycle in G by skipping vertices already seen.
저 말대로 실행하면 된다 -_-; 물론... 드럽게 어렵다... (과제시간의 90% 는 이것때문에...)
완성작.
more..
기본적으로 들어 있는 Command 는 Node 와 Node 사이의 distance 를 입력 해놓은 것입니다.
오늘 수업하는데... 지금 말하는 내용은 온라인 렉쳐 노트에 안올라 올꺼라 협박 하시는 교수님 ㅠ 평소때 같은면 Handout 을 보고 끄덕끄덕 거렸겠지만.. 끼적끼적 필기를 시작하기 시작했다 -0-
내용은.. 트리구조를 이용해 텍스트 파일을 ASCII 로만 이루어진 텍스트 파일을 압축 하는 것이다. 즉 각 글자는 7bit 씩 쓰게 되는데, 빈도수가 높을수록 bit 를 최소화 하고 빈도수가 낮을수록 bit 를 높게 하여 파일의 용량을 줄이는것.. 아래는 필기한 전문.. (트리 그리느냐고 힘좀 썻다 -_-)
A B C D E F
4 2 6 5 8 1
Make each leaf nodes
smaller node to the left.
+----+
| 3 |
+----+
/ \
+----+ +----+
| F 1| | B 2|
+----+ +----+
Step 2..
+-------+
| 16 |
+-------+
/ \
0 / \ 1
/ \
+----+ +----+
| 11 | | 15 |
+----+ +----+
0 / \ 1 0 / \ 1
+----+ +----+ +----+ +----+
| D 5| | C 6| | 7 | | E 8|
+----+ +----+ +----+ +----+
0 / \ 1
+----+ +----+
| 3 | | A 4|
+----+ +----+
0 / \ 1
+----+ +----+
| F 1| | B 2|
+----+ +----+
Step 3.
(65)A 101
(66)B 1001
(67)C 01
(68)D 00
(69)E 11
(70)F 1000
BADCAB -> 1001 101 00 01 101 1001
[Prefix Property] - works since we started from the leaf node
Step. 4
Create End of file Char
since the file is saved in bytes the left bit will be filled with 0s
BADCAB will be
10011010 00110110 01______
000000
which would translate into BADCABDDD
so create eof char so it ends at the proper position.
.....
AAAABBCCCCCCDDDDDEEEEEEEE
After running the .code file says
68
00
67
01
256 --> EOF
1000 -->
66
1001
65
101
69
11
결론은..
숙제로 이걸 만들어 내라는것 -0- 프로그램 3개 제출해야 하는듯 -_- code 를 만들어내는 프로그램 하나 encode 시키는 프로그램 하나 decode 시키는 프로그램 하나.. 그래서 10점씩 해서 30점 줄려나;
