Robot Tour Optimization - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:24:15Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:24 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[알고리즘 설계와 분석#문제\|알고리즘 설계와 분석]]		상위 문서: [[알고리즘 설계와 분석#문제\|알고리즘 설계와 분석]]

2025년 9월 5일 (금) 22:49에 Pinkgo님의 편집

2025-09-05T22:49:26Z

← 이전 판		2025년 9월 5일 (금) 22:49 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]
	이전 문서: [[알고리즘 설계와 분석#문제\|알고리즘 설계와 분석]]		상위 문서: [[알고리즘 설계와 분석#문제\|알고리즘 설계와 분석]]

	==개요==		==개요==

2025년 9월 5일 (금) 22:48에 Pinkgo님의 편집

2025-09-05T22:48:09Z

← 이전 판		2025년 9월 5일 (금) 22:48 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]
	이전 문서: [[알고리즘 설계와 분석]]		이전 문서: [[알고리즘 설계와 분석#문제\|알고리즘 설계와 분석]]

	==개요==		==개요==

2025년 9월 5일 (금) 22:46에 Pinkgo님의 편집

2025-09-05T22:46:38Z

← 이전 판		2025년 9월 5일 (금) 22:46 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]
			이전 문서: [[알고리즘 설계와 분석]]

	==개요==		==개요==

Pinkgo: /* A Correct Algorithm: Exhaustive Search */

2025-09-04T02:19:29Z

A Correct Algorithm: Exhaustive Search

← 이전 판		2025년 9월 4일 (목) 02:19 판
43번째 줄:		43번째 줄:
	<math>d = cost(P_i)</math> and <math>P_{min} = P_i </math>		<math>d = cost(P_i)</math> and <math>P_{min} = P_i </math>
	Return <math>P_{min}</math>		Return <math>P_{min}</math>
	위 알고리즘을 이해하는 것은 어렵지 않다. 하지만 해당 알고리즘의 문제는 매우 느리다는 것이다. 시간 복잡도가 O(n!)이기 때문에,		위 알고리즘을 이해하는 것은 어렵지 않다. 하지만 해당 알고리즘의 문제는 매우 느리다는 것이다. 시간 복잡도가 O(n!)이기 때문에, 만약 입력의 크기 10을 넘어간다면 실행하는 것은 점점 불가능에 가까워 진다. 따라서 이는 정확하지만(correct), 효율적이지는 않은(not efficient) 알고리즘이다.

	==각주==		==각주==

Pinkgo: /* A Correct Algorithm: Exhaustive Search */

2025-09-04T02:16:54Z

A Correct Algorithm: Exhaustive Search

← 이전 판		2025년 9월 4일 (목) 02:16 판
39번째 줄:		39번째 줄:
	가장 직관적이고 정확함을 보장할 수 있는 알고리즘은 존재하는 모든 경우의 수에 대하여 모두 조사하는 것이다. 이는 아래와 같은 수도 코드에 따라 작동한다.		가장 직관적이고 정확함을 보장할 수 있는 알고리즘은 존재하는 모든 경우의 수에 대하여 모두 조사하는 것이다. 이는 아래와 같은 수도 코드에 따라 작동한다.
	<math>d=\infty</math>		<math>d=\infty</math>
	For each of the <math>n!</math> permutations <math>~~\prod_i~~</math> of the <math>n</math> points		For each of the <math>n!</math> permutations <math>P_i</math> of the <math>n</math> points //n개의 항으로 이루어진 n!개의 순열에 대하여,
	If (<math>~~\prod_i~~ \le d</math>) then		If (<math>P_i \le d</math>) then //최소값을 찾는다.
	<math>d = cost(~~\prod_i~~)</math> and <math>P_{min} = ~~\prod_i~~ </math>		<math>d = cost(P_i)</math> and <math>P_{min} = P_i </math>
	Return ~~Pmin~~		Return <math>P_{min}</math>
			위 알고리즘을 이해하는 것은 어렵지 않다. 하지만 해당 알고리즘의 문제는 매우 느리다는 것이다. 시간 복잡도가 O(n!)이기 때문에,

	==각주==		==각주==

Pinkgo: /* 알고리즘 */

2025-09-04T02:13:35Z

알고리즘

@@ 20번째 줄: / 20번째 줄: @@
   Return to <math>p_0</math> from <math>p_i</math>
 하지만 이러한 단순한 접근법은 틀렸다. Figure 1은 이를 증명하는 반례이다.
 ===Closest Pair Tour===
@@ 43번째 줄: / 35번째 줄: @@
 해당 알고리즘의 장점은 구현이 간단하고 직관적이므로 많은 상황에서 “그럴듯한” 해를 빨리 만든다는 것이다. 하지만 최적의 해를 보장하지 않으므로 구조에 따라 나쁜 해를 만들 수 있다는 단점이 있다. 해당 알고리즘의 시간 복잡도를 계산하면, 각 단계 마다 끝점의 쌍을 전수조사 하므로 대략 O(n<sup>3</sup>)이라고 볼 수 있다. 그 이유는 n개의 단계에서 각 단계의 비용이 후보쌍의 수에 비례하므로 O(n<sup>2</sup>)만큼 소요되기 때문이다.
 ==각주==

Pinkgo: /* Nearest Neighbor Tour */

2025-09-04T02:12:21Z

Nearest Neighbor Tour

← 이전 판		2025년 9월 4일 (목) 02:12 판
20번째 줄:		20번째 줄:
	Return to <math>p_0</math> from <math>p_i</math>		Return to <math>p_0</math> from <math>p_i</math>
	하지만 이러한 단순한 접근법은 틀렸다. Figure 1은 이를 증명하는 반례이다.		하지만 이러한 단순한 접근법은 틀렸다. Figure 1은 이를 증명하는 반례이다.

			===A Correct Algorithm: Exhaustive Search===
			가장 직관적이고 정확함을 보장할 수 있는 알고리즘은 존재하는 모든 경우의 수에 대하여 모두 조사하는 것이다. 이는 아래와 같은 수도 코드에 따라 작동한다.
			<math>d=\infty</math>
			For each of the <math>n!</math> permutations <math>\prod_i</math> of the <math>n</math> points
			If (<math>\prod_i \le d</math>) then
			<math>d = cost(\prod_i)</math> and <math>P_{min} = \prod_i </math>
			Return Pmin

	===Closest Pair Tour===		===Closest Pair Tour===

Pinkgo: /* Closest Pair Tour */

2025-09-04T02:06:56Z

Closest Pair Tour

← 이전 판		2025년 9월 4일 (목) 02:06 판
31번째 줄:		31번째 줄:
	Connect <math>(x_m, y_m)</math> by an edge //해당 두 접점을 이어 같은 체인에 속하도록 한다.		Connect <math>(x_m, y_m)</math> by an edge //해당 두 접점을 이어 같은 체인에 속하도록 한다.
	Connect the two endpoints by an edge.		Connect the two endpoints by an edge.
			[[파일:Figure 2. Closest Pair Tour is Wrong.png\|대체글=Figure 2. Closest Pair Tour is Wrong\|섬네일\|Figure 2. Closest Pair Tour is Wrong]]
	이는 figure 1의 경우에는 잘 맞아 떨어지는 것을 관찰할 수 있다. 하지만 이는 Figure 2의 경우에 대해서는 실패를 한다는 것을 관찰할 수 있다. 즉, 해당 알고리즘은 최선의 결과를 보장하지 않는다. 이를 통해서 알 수 있는 것은, 지역적으로 가장 가까운 연결이 항상 전역적으로 좋은(최적) 경로를 보장하진 않는다는 것이다.		이는 figure 1의 경우에는 잘 맞아 떨어지는 것을 관찰할 수 있다. 하지만 이는 Figure 2의 경우에 대해서는 실패를 한다는 것을 관찰할 수 있다. 즉, 해당 알고리즘은 최선의 결과를 보장하지 않는다. 이를 통해서 알 수 있는 것은, 지역적으로 가장 가까운 연결이 항상 전역적으로 좋은(최적) 경로를 보장하진 않는다는 것이다.

	해당 알고리즘의 장점은 구현이 간단하고 직관적이므로 많은 상황에서 “그럴듯한” 해를 빨리 만든다는 것이다. 하지만 최적의 해를 보장하지 않으므로 구조에 따라 나쁜 해를 만들 수 있다는 단점이 있다. 해당 알고리즘의 시간 복잡도를 계산하면, 각 단계 마다 끝점의 쌍을 전수조사 하므로 대략 O(n<sup>3</sup>)이라고 볼 수 있다. 그 이유는 n개의 단계에서 각 단계의 비용이 후보쌍의 수에 비례하므로 (n<sup>2</sup>)만큼 소요되기 때문이다.		해당 알고리즘의 장점은 구현이 간단하고 직관적이므로 많은 상황에서 “그럴듯한” 해를 빨리 만든다는 것이다. 하지만 최적의 해를 보장하지 않으므로 구조에 따라 나쁜 해를 만들 수 있다는 단점이 있다. 해당 알고리즘의 시간 복잡도를 계산하면, 각 단계 마다 끝점의 쌍을 전수조사 하므로 대략 O(n<sup>3</sup>)이라고 볼 수 있다. 그 이유는 n개의 단계에서 각 단계의 비용이 후보쌍의 수에 비례하므로 O(n<sup>2</sup>)만큼 소요되기 때문이다.

	==각주==		==각주==

Pinkgo: /* Closest Pair Tour */

2025-09-04T02:05:47Z

Closest Pair Tour

← 이전 판		2025년 9월 4일 (목) 02:05 판
31번째 줄:		31번째 줄:
	Connect <math>(x_m, y_m)</math> by an edge //해당 두 접점을 이어 같은 체인에 속하도록 한다.		Connect <math>(x_m, y_m)</math> by an edge //해당 두 접점을 이어 같은 체인에 속하도록 한다.
	Connect the two endpoints by an edge.		Connect the two endpoints by an edge.
			이는 figure 1의 경우에는 잘 맞아 떨어지는 것을 관찰할 수 있다. 하지만 이는 Figure 2의 경우에 대해서는 실패를 한다는 것을 관찰할 수 있다. 즉, 해당 알고리즘은 최선의 결과를 보장하지 않는다. 이를 통해서 알 수 있는 것은, 지역적으로 가장 가까운 연결이 항상 전역적으로 좋은(최적) 경로를 보장하진 않는다는 것이다.

			해당 알고리즘의 장점은 구현이 간단하고 직관적이므로 많은 상황에서 “그럴듯한” 해를 빨리 만든다는 것이다. 하지만 최적의 해를 보장하지 않으므로 구조에 따라 나쁜 해를 만들 수 있다는 단점이 있다. 해당 알고리즘의 시간 복잡도를 계산하면, 각 단계 마다 끝점의 쌍을 전수조사 하므로 대략 O(n<sup>3</sup>)이라고 볼 수 있다. 그 이유는 n개의 단계에서 각 단계의 비용이 후보쌍의 수에 비례하므로 (n<sup>2</sup>)만큼 소요되기 때문이다.

	==각주==		==각주==