DAA-퀵 가이드

알고리즘은 계산, 데이터 처리 및 자동화 된 추론 작업을 수행하는 문제를 해결하기위한 일련의 작업 단계입니다. 알고리즘은 제한된 시간과 공간 내에서 표현할 수있는 효율적인 방법입니다.

알고리즘은 매우 간단하고 효율적인 방법으로 특정 문제의 솔루션을 표현하는 가장 좋은 방법입니다. 특정 문제에 대한 알고리즘이 있으면 모든 프로그래밍 언어로 구현할 수 있습니다.algorithm is independent from any programming languages.

알고리즘 설계

알고리즘 설계의 중요한 측면은 최소한의 시간과 공간을 사용하여 문제를 효율적으로 해결하는 효율적인 알고리즘을 만드는 것입니다.

문제를 해결하기 위해 다른 접근 방식을 따를 수 있습니다. 그들 중 일부는 시간 소비 측면에서 효율적일 수있는 반면 다른 접근 방식은 메모리 효율적일 수 있습니다. 그러나 시간 소비와 메모리 사용을 동시에 최적화 할 수 없다는 점을 명심해야합니다. 더 짧은 시간에 실행되는 알고리즘이 필요한 경우 더 많은 메모리에 투자해야하며 더 적은 메모리로 실행하는 알고리즘이 필요한 경우 더 많은 시간이 필요합니다.

문제 개발 단계

다음 단계는 계산 문제를 해결하는 데 사용됩니다.

문제 정의
모델 개발
알고리즘 사양
알고리즘 설계
알고리즘의 정확성 확인
알고리즘 분석
알고리즘 구현
프로그램 테스트
Documentation

알고리즘의 특성

알고리즘의 주요 특징은 다음과 같습니다.

알고리즘에는 고유 한 이름이 있어야합니다.
알고리즘은 입력 및 출력 집합을 명시 적으로 정의해야합니다.
알고리즘은 명확한 작업으로 잘 정렬되어 있습니다.
알고리즘은 한정된 시간 내에 중지됩니다. 알고리즘은 무한대로 실행되어서는 안됩니다. 즉, 알고리즘은 어느 시점에서 끝나야합니다.

의사 코드

의사 코드는 일반 텍스트와 관련된 모호함이없고 특정 프로그래밍 언어의 구문을 알 필요없이 알고리즘에 대한 높은 수준의 설명을 제공합니다.

실행 시간은 Pseudocode를 사용하여 알고리즘을 계산할 수있는 기본 작업 집합으로 표현함으로써보다 일반적인 방식으로 추정 할 수 있습니다.

알고리즘과 의사 코드의 차이점

알고리즘은 특정 작업을 수행하기 위해 Turing-complete 컴퓨터 기계에 의해 실행될 수있는 프로세스를 설명하는 몇 가지 특정 특성이있는 공식적인 정의입니다. 일반적으로 "알고리즘"이라는 단어는 컴퓨터 과학의 모든 고급 작업을 설명하는 데 사용할 수 있습니다.

반면에 의사 코드는 알고리즘에 대한 비공식적이고 (종종 기초적인) 사람이 읽을 수있는 설명으로 많은 세부 정보를 남깁니다. 의사 코드를 작성하는 것은 스타일의 제한이 없으며 유일한 목적은 자연어에서 훨씬 현실적인 방식으로 알고리즘의 고급 단계를 설명하는 것입니다.

예를 들어, 다음은 삽입 정렬 알고리즘입니다.

Algorithm: Insertion-Sort 
Input: A list L of integers of length n  
Output: A sorted list L1 containing those integers present in L 
Step 1: Keep a sorted list L1 which starts off empty  
Step 2: Perform Step 3 for each element in the original list L  
Step 3: Insert it into the correct position in the sorted list L1.  
Step 4: Return the sorted list 
Step 5: Stop

다음은 Insertion-Sort 알고리즘에서 위에서 언급 한 높은 수준의 추상 프로세스를보다 현실적인 방식으로 설명하는 방법을 설명하는 의사 코드입니다.

for i <- 1 to length(A) 
   x <- A[i] 
   j <- i 
   while j > 0 and A[j-1] > x 
      A[j] <- A[j-1] 
      j <- j - 1 
   A[j] <- x

이 튜토리얼에서 알고리즘은 C, C ++, Java, Python 및 기타 프로그래밍 언어와 많은 측면에서 유사한 의사 코드의 형태로 제공됩니다.

알고리즘의 이론적 분석에서는 점근 적 의미에서 복잡도를 추정하는 것이 일반적입니다. 즉, 임의로 큰 입력에 대한 복잡도 함수를 추정하는 것입니다. 용어"analysis of algorithms" Donald Knuth가 만들었습니다.

알고리즘 분석은 특정 계산 문제를 해결하는 데 필요한 알고리즘 리소스에 대한 이론적 추정을 제공하는 계산 복잡성 이론의 중요한 부분입니다. 대부분의 알고리즘은 임의 길이의 입력으로 작동하도록 설계되었습니다. 알고리즘 분석은 알고리즘을 실행하는 데 필요한 시간과 공간 리소스의 양을 결정하는 것입니다.

일반적으로 알고리즘의 효율성 또는 실행 시간은 입력 길이와 단계 수를 관련시키는 함수로 표시됩니다. time complexity또는 메모리 볼륨 (로 알려진 space complexity.

분석의 필요성

이 장에서는 알고리즘 분석의 필요성과 하나의 계산 문제가 다른 알고리즘으로 해결 될 수 있으므로 특정 문제에 대해 더 나은 알고리즘을 선택하는 방법에 대해 설명합니다.

특정 문제에 대한 알고리즘을 고려함으로써 우리는이 알고리즘의 도움으로 유사한 유형의 문제를 해결할 수 있도록 패턴 인식을 개발할 수 있습니다.

이러한 알고리즘의 목적은 동일하지만 알고리즘은 종종 서로 상당히 다릅니다. 예를 들어, 숫자 세트는 다른 알고리즘을 사용하여 정렬 할 수 있습니다. 하나의 알고리즘에 의해 수행되는 비교 횟수는 동일한 입력에 대해 다른 알고리즘에 따라 다를 수 있습니다. 따라서 이러한 알고리즘의 시간 복잡도는 다를 수 있습니다. 동시에 각 알고리즘에 필요한 메모리 공간을 계산해야합니다.

알고리즘 분석은 필요한 시간과 크기 (구현 중 저장을위한 메모리 크기) 측면에서 알고리즘의 문제 해결 능력을 분석하는 프로세스입니다. 그러나 알고리즘 분석의 주요 관심사는 필요한 시간 또는 성능입니다. 일반적으로 다음 유형의 분석을 수행합니다.

Worst-case − 모든 크기 인스턴스에서 수행되는 최대 단계 수 a.
Best-case − 모든 크기 인스턴스에서 수행되는 최소 단계 수 a.
Average case − 모든 크기 인스턴스에서 수행 된 평균 단계 수 a.
Amortized − 크기 입력에 적용되는 일련의 연산 a 시간이 지남에 따라 평균.

문제를 해결하려면 프로그램이 메모리가 제한되어 있지만 적절한 공간이 사용 가능한 시스템에서 실행되거나 그 반대 일 수 있으므로 시간과 공간 복잡성을 고려해야합니다. 이 맥락에서 비교하면bubble sort 과 merge sort. 버블 정렬에는 추가 메모리가 필요하지 않지만 병합 정렬에는 추가 공간이 필요합니다. 버블 정렬의 시간 복잡도는 병합 정렬에 비해 높지만 메모리가 매우 제한된 환경에서 프로그램을 실행해야하는 경우 버블 정렬을 적용해야 할 수 있습니다.

알고리즘의 리소스 소비를 측정하기 위해이 장에서 설명하는 다양한 전략이 사용됩니다.

점근 분석

함수의 점근 적 동작 f(n) 의 성장을 나타냅니다 f(n) 같이 n 커집니다.

우리는 일반적으로 작은 값을 무시합니다. n, 우리는 일반적으로 큰 입력에서 프로그램이 얼마나 느려질 지 추정하는 데 관심이 있기 때문입니다.

좋은 경험 법칙은 점근 성장률이 느릴수록 알고리즘이 더 좋다는 것입니다. 항상 사실은 아니지만.

예를 들어, 선형 알고리즘 $f(n) = d * n + k$ 항상 2 차보다 점근 적으로 낫습니다. $f(n) = c.n^2 + q$.

반복 방정식 풀기

반복은 더 작은 입력에 대한 값의 관점에서 함수를 설명하는 방정식 또는 부등식입니다. 재발은 일반적으로 분할 및 정복 패러다임에 사용됩니다.

고려하자 T(n) 크기 문제에 대한 실행 시간 n.

문제 크기가 충분히 작 으면 다음과 같이 말합니다. n < c 어디 c 상수이고, 간단한 솔루션은 일정한 시간이 걸립니다. θ(1). 문제의 분할로 인해 크기가있는 여러 하위 문제가 발생하는 경우$\frac{n}{b}$.

문제를 해결하기 위해 필요한 시간은 a.T(n/b). 분할에 필요한 시간을 고려하면D(n) 하위 문제의 결과를 결합하는 데 필요한 시간은 C(n), 반복 관계는 다음과 같이 나타낼 수 있습니다.

$$T(n)=\begin{cases}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\theta(1) & if\:n\leqslant c\\a T(\frac{n}{b})+D(n)+C(n) & otherwise\end{cases}$$

반복 관계는 다음 방법을 사용하여 해결할 수 있습니다.

Substitution Method −이 방법에서 우리는 경계를 추측하고 수학적 귀납법을 사용하여 우리의 가정이 옳다는 것을 증명합니다.
Recursion Tree Method −이 방법에서는 각 노드가 비용을 나타내는 반복 트리가 형성됩니다.
Master’s Theorem − 이것은 반복 관계의 복잡성을 찾는 또 다른 중요한 기술입니다.

상각 된 분석

상각 분석은 일반적으로 일련의 유사한 작업이 수행되는 특정 알고리즘에 사용됩니다.

상각 분석은 일련의 작업 비용을 별도로 제한하는 대신 전체 시퀀스의 실제 비용에 대한 제한을 제공합니다.
상각 분석은 평균 사례 분석과 다릅니다. 확률은 상각 분석에 포함되지 않습니다. 상각 분석은 최악의 경우 각 작업의 평균 성능을 보장합니다.

디자인과 분석은 밀접한 관련이 있기 때문에 분석 도구 일뿐 아니라 디자인에 대한 사고 방식입니다.

집계 방법

집계 방법은 문제에 대한 글로벌 뷰를 제공합니다. 이 방법에서n 작업에 최악의 시간이 소요됨 T(n)전체적으로. 그런 다음 각 작업의 상각 된 비용은T(n)/n. 다른 작업에 다른 시간이 걸릴 수 있지만이 방법에서는 다양한 비용이 무시됩니다.

회계 방법

이 방법에서는 실제 비용에 따라 다른 작업에 다른 요금이 할당됩니다. 작업의 상각 된 비용이 실제 비용을 초과하면 차액이 대변으로 객체에 할당됩니다. 이 크레딧은 상각 된 비용이 실제 비용보다 적은 후속 작업에 대한 지불을 지원합니다.

실제 비용과 상각 된 비용이 i^th 작업은 $c_{i}$ 과 $\hat{c_{l}}$, 다음

$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}\geqslant\displaystyle\sum\limits_{i=1}^n c_{i}$$

잠재적 인 방법

이 방법은 선불 작업을 크레딧으로 간주하는 대신 선불 작업을 잠재적 에너지로 나타냅니다. 이 에너지는 향후 운영 비용을 지불하기 위해 방출 될 수 있습니다.

우리가 수행하면 n 초기 데이터 구조로 시작하는 작업 D₀. 고려해 보겠습니다.c_i 실제 비용으로 D_i 데이터 구조로 i^th조작. 잠재적 함수 Ф는 실수 Ф (D_i), 관련 잠재력 D_i. 상각 된 비용$\hat{c_{l}}$ 정의 할 수 있습니다.

$$\hat{c_{l}}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1})$$

따라서 총 상각 비용은

$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}=\displaystyle\sum\limits_{i=1}^n (c_{i}+\Phi (D_{i})-\Phi (D_{i-1}))=\displaystyle\sum\limits_{i=1}^n c_{i}+\Phi (D_{n})-\Phi (D_{0})$$

동적 테이블

테이블에 할당 된 공간이 충분하지 않으면 테이블을 더 큰 크기의 테이블에 복사해야합니다. 마찬가지로 테이블에서 많은 수의 멤버가 지워진 경우 더 작은 크기로 테이블을 재 할당하는 것이 좋습니다.

상각 분석을 사용하면 상각 된 삽입 및 삭제 비용이 일정하며 동적 테이블의 사용되지 않은 공간이 전체 공간의 일정한 비율을 초과하지 않음을 보여줄 수 있습니다.

이 튜토리얼의 다음 장에서는 점근 표기법에 대해 간략하게 설명합니다.

알고리즘 설계에서 알고리즘의 복잡도 분석은 필수적인 측면입니다. 주로 알고리즘의 복잡성은 성능, 작동 속도, 느린 속도와 관련이 있습니다.

알고리즘의 복잡성은 데이터 처리에 필요한 메모리 양과 처리 시간 측면에서 알고리즘의 효율성을 설명합니다.

알고리즘의 복잡성은 두 가지 관점에서 분석됩니다. Time 과 Space.

시간 복잡성

입력 크기 측면에서 알고리즘을 실행하는 데 필요한 시간을 설명하는 함수입니다. "시간"은 수행 된 메모리 액세스 수, 정수 간 비교 수, 내부 루프가 실행되는 횟수 또는 알고리즘이 소요되는 실시간 양과 관련된 다른 자연 단위를 의미 할 수 있습니다.

공간 복잡성

알고리즘에 대한 입력 크기 측면에서 알고리즘이 사용하는 메모리 양을 설명하는 함수입니다. 우리는 종종 입력 자체를 저장하는 데 필요한 메모리를 계산하지 않고 "추가"메모리가 필요하다고 말합니다. 다시 말하지만,이를 측정하기 위해 자연 (그러나 고정 길이) 단위를 사용합니다.

사용되는 공간이 최소화되고 명확하기 때문에 공간 복잡성은 때때로 무시되지만 때로는 시간만큼 중요한 문제가됩니다.

점근 표기법

알고리즘의 실행 시간은 명령어 세트, 프로세서 속도, 디스크 I / O 속도 등에 따라 달라집니다. 따라서 알고리즘의 효율성을 점근 적으로 추정합니다.

알고리즘의 시간 함수는 다음과 같이 표현됩니다. T(n), 어디 n 입력 크기입니다.

알고리즘의 복잡성을 나타 내기 위해 다양한 유형의 점근 표기법이 사용됩니다. 알고리즘의 실행 시간 복잡도를 계산하기 위해 다음 점근 표기법이 사용됩니다.

O − 빅 오
Ω − 빅 오메가
θ − 빅 세타
o − 리틀 오
ω − 리틀 오메가

O : 점근 상한

'O'(Big Oh)는 가장 일반적으로 사용되는 표기법입니다. 기능f(n) 표현할 수있는 순서입니다 g(n) 그건 O(g(n)), 양의 정수 값이있는 경우 n 같이 n₀ 및 양의 상수 c 그런-

$f(n)\leqslant c.g(n)$ ...에 대한 $n > n_{0}$ 모든 경우에

따라서 기능 g(n) 함수의 상한 f(n), 같이 g(n) 보다 빠르게 성장 f(n).

예

주어진 기능을 고려해 보겠습니다. $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

고려하면 $g(n) = n^3$,

$f(n)\leqslant 5.g(n)$ 모든 값에 대해 $n > 2$

따라서 복잡성 f(n) 다음과 같이 나타낼 수 있습니다. $O(g(n))$, 즉 $O(n^3)$

Ω : 점근 하한

우리는 말한다 $f(n) = \Omega (g(n))$ 상수가있을 때 c 그 $f(n)\geqslant c.g(n)$ 충분히 큰 가치 n. 여기n양의 정수입니다. 그것은 기능을 의미합니다g 함수의 하한입니다. f; 특정 값 이후n, f 아래로 가지 않을 것이다 g.

예

주어진 기능을 고려해 보겠습니다. $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$.

고려하면 $g(n) = n^3$, $f(n)\geqslant 4.g(n)$ 모든 값에 대해 $n > 0$.

따라서 복잡성 f(n) 다음과 같이 나타낼 수 있습니다. $\Omega (g(n))$, 즉 $\Omega (n^3)$

θ : 점근 타이트 바운드

우리는 말한다 $f(n) = \theta(g(n))$ 상수가있을 때 c₁ 과 c₂ 그 $c_{1}.g(n) \leqslant f(n) \leqslant c_{2}.g(n)$ 충분히 큰 가치 n. 여기n 양의 정수입니다.

이것은 기능을 의미합니다 g 기능에 대한 긴밀한 경계 f.

예

주어진 기능을 고려해 보겠습니다. $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

고려하면 $g(n) = n^3$, $4.g(n) \leqslant f(n) \leqslant 5.g(n)$ 모든 큰 값에 대해 n.

따라서 복잡성 f(n) 다음과 같이 나타낼 수 있습니다. $\theta (g(n))$, 즉 $\theta (n^3)$.

O-표기법

에 의해 제공되는 점근 상한 O-notation점근 적으로 꽉 조일 수도 있고 아닐 수도 있습니다. 경계$2.n^2 = O(n^2)$ 점근 적으로 빡빡하지만 경계는 $2.n = O(n^2)$ 아니다.

우리는 사용 o-notation 점근 적으로 빡빡하지 않은 상한을 나타냅니다.

우리는 공식적으로 정의합니다 o(g(n)) (n의 g의 little-oh) 세트로 f(n) = o(g(n)) 양의 상수 $c > 0$ 그리고 가치가 있습니다 $n_{0} > 0$, 그런 $0 \leqslant f(n) \leqslant c.g(n)$.

직관적으로 o-notation, 함수 f(n) 상대적으로 중요하지 않다 g(n) 같이 n무한대에 접근한다. 그건,

$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = 0$$

예

동일한 기능을 고려해 보겠습니다. $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

고려하면 $g(n) = n^{4}$,

$$\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^4}\right) = 0$$

따라서 복잡성 f(n) 다음과 같이 나타낼 수 있습니다. $o(g(n))$, 즉 $o(n^4)$.

ω – 표기법

우리는 사용 ω-notation점근 적으로 빡빡하지 않은 하한을 나타냅니다. 그러나 공식적으로 우리는ω(g(n)) (n의 g의 작은 오메가) 세트로 f(n) = ω(g(n)) 양의 상수 C > 0 그리고 가치가 있습니다 $n_{0} > 0$, $ 0 \ leqslant cg (n) <f (n) $.

예를 들면 $\frac{n^2}{2} = \omega (n)$,하지만 $\frac{n^2}{2} \neq \omega (n^2)$. 관계$f(n) = \omega (g(n))$ 다음 제한이 있음을 의미합니다.

$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = \infty$$

그건, f(n) 상대적으로 임의로 커집니다 g(n) 같이 n 무한에 접근합니다.

예

동일한 기능을 고려해 보겠습니다. $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

고려하면 $g(n) = n^2$,

$$\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^2}\right) = \infty$$

따라서 복잡성 f(n) 다음과 같이 나타낼 수 있습니다. $o(g(n))$, 즉 $\omega (n^2)$.

Apriori 및 Apostiari 분석

Apriori 분석은 특정 시스템에서 실행하기 전에 분석이 수행됨을 의미합니다. 이 분석은 이론적 모델을 사용하여 함수를 정의하는 단계입니다. 따라서 우리는 다른 메모리, 프로세서 및 컴파일러가있는 특정 시스템에서 실행하는 대신 알고리즘을보고 알고리즘의 시간 및 공간 복잡성을 결정합니다.

알고리즘의 Apostiari 분석은 시스템에서 알고리즘을 실행 한 후에 만 알고리즘 분석을 수행하는 것을 의미합니다. 그것은 시스템에 직접적으로 의존하며 시스템마다 변경됩니다.

업계에서는 소프트웨어가 일반적으로 업계에 존재하는 것과 다른 시스템에서 실행되는 익명의 사용자를 위해 만들어지기 때문에 Apostiari 분석을 수행 할 수 없습니다.

Apriori에서는 컴퓨터에서 컴퓨터로 바뀔 때 시간과 공간의 복잡성을 결정하기 위해 점근 표기법을 사용하는 이유입니다. 그러나 점근 적으로는 동일합니다.

이 장에서는 알고리즘에 필요한 공간의 양과 관련하여 계산 문제의 복잡성에 대해 설명합니다.

공간 복잡성은 시간 복잡성의 많은 특징을 공유하고 계산상의 어려움에 따라 문제를 분류하는 추가 방법으로 사용됩니다.

공간 복잡성이란 무엇입니까?

공간 복잡도는 알고리즘에 입력되는 양과 관련하여 알고리즘이 사용하는 메모리 (공간)의 양을 설명하는 함수입니다.

우리는 종종 extra memory입력 자체를 저장하는 데 필요한 메모리는 계산하지 않습니다. 다시 말하지만,이를 측정하기 위해 자연 (그러나 고정 길이) 단위를 사용합니다.

바이트를 사용할 수 있지만 사용 된 정수의 수, 고정 크기 구조의 수 등을 사용하는 것이 더 쉽습니다.

결국 우리가 생각 해낸 함수는 단위를 나타내는 데 필요한 실제 바이트 수와 무관합니다.

사용 된 공간이 최소화되고 명확하기 때문에 공간 복잡성이 무시되는 경우도 있지만 시간 복잡성만큼 중요한 문제가되는 경우도 있습니다.

정의

허락하다 M 결정 론적이다 Turing machine (TM)모든 입력에서 중지됩니다. 공간 복잡성M 기능입니다 $f \colon N \rightarrow N$, 어디 f(n) 테이프의 최대 셀 수이며 M 길이 입력을 스캔합니다. M. 공간의 복잡성이M 이다 f(n), 우리는 말할 수 있습니다 M 우주에서 달리다 f(n).

점근 표기법을 사용하여 Turing 기계의 공간 복잡성을 추정합니다.

허락하다 $f \colon N \rightarrow R^+$기능입니다. 공간 복잡성 클래스는 다음과 같이 정의 할 수 있습니다.

SPACE = {L | L is a language decided by an O(f(n)) space deterministic TM}

SPACE = {L | L is a language decided by an O(f(n)) space non-deterministic TM}

PSPACE 결정 론적 튜링 머신의 다항식 공간에서 결정할 수있는 언어 클래스입니다.

다시 말해, PSPACE = U_k SPACE (n^k)

Savitch의 정리

공간 복잡성과 관련된 가장 초기의 정리 중 하나는 Savitch의 정리입니다. 이 정리에 따르면 결정 론적 기계는 적은 공간을 사용하여 비 결정적 기계를 시뮬레이션 할 수 있습니다.

시간 복잡성의 경우 이러한 시뮬레이션에는 시간이 기하 급수적으로 증가해야합니다. 공간 복잡성의 경우이 정리는 다음을 사용하는 비 결정적 튜링 머신f(n) 공간은 다음을 사용하는 결정적 TM으로 변환 될 수 있습니다. f²(n) 우주.

따라서 Savitch의 정리는 모든 기능에 대해 $f \colon N \rightarrow R^+$, 어디 $f(n) \geqslant n$

NSPACE(f(n)) ⊆ SPACE(f(n))

복잡성 클래스 간의 관계

다음 다이어그램은 다양한 복잡성 클래스 간의 관계를 보여줍니다.

지금까지이 튜토리얼에서 P 및 NP 클래스에 대해 논의하지 않았습니다. 이것들은 나중에 논의 될 것입니다.

많은 알고리즘은 하위 문제를 반복적으로 처리하여 주어진 문제를 해결하기 위해 본질적으로 재귀 적입니다.

에 divide and conquer approach, 문제는 작은 문제로 나뉘고 작은 문제는 독립적으로 해결되며 마지막으로 작은 문제의 솔루션은 큰 문제에 대한 솔루션으로 결합됩니다.

일반적으로 분할 및 정복 알고리즘은 세 부분으로 구성됩니다.

Divide the problem 동일한 문제의 작은 인스턴스 인 여러 하위 문제로.
Conquer the sub-problems재귀 적으로 풀면됩니다. 충분히 작은 경우 하위 문제를 기본 사례로 해결합니다.
Combine the solutions 원래 문제에 대한 솔루션으로 하위 문제에.

Divide and Conquer Approach의 장단점

분할 및 정복 접근 방식은 하위 문제가 독립적이므로 병렬 처리를 지원합니다. 따라서이 기술을 사용하여 설계된 알고리즘은 다중 프로세서 시스템 또는 다른 시스템에서 동시에 실행될 수 있습니다.

이 접근 방식에서 대부분의 알고리즘은 재귀를 사용하여 설계되었으므로 메모리 관리가 매우 높습니다. 함수 상태를 저장해야하는 재귀 함수 스택이 사용됩니다.

분할 및 정복 접근법의 적용

다음은 분할 및 정복 접근 방식을 사용하여 해결되는 몇 가지 문제입니다.

숫자 시퀀스의 최대 값과 최소값 찾기
Strassen의 행렬 곱셈
병합 정렬
이진 검색

분할 정복 기법으로 해결할 수있는 간단한 문제를 생각해 보겠습니다.

문제 설명

알고리즘 분석의 Max-Min 문제는 배열에서 최대 값과 최소값을 찾는 것입니다.

해결책

주어진 배열에서 최대 및 최소 수를 찾으려면 numbers[] 크기 n, 다음 알고리즘을 사용할 수 있습니다. 먼저 우리는naive method 그리고 우리는 divide and conquer approach.

나이브 방법

Naïve 방법은 모든 문제를 해결하는 기본 방법입니다. 이 방법에서는 최대 및 최소 수를 별도로 찾을 수 있습니다. 최대 및 최소 수를 찾으려면 다음과 같은 간단한 알고리즘을 사용할 수 있습니다.

Algorithm: Max-Min-Element (numbers[]) 
max := numbers[1] 
min := numbers[1] 

for i = 2 to n do 
   if numbers[i] > max then  
      max := numbers[i] 
   if numbers[i] < min then  
      min := numbers[i] 
return (max, min)

분석

Naive 방법의 비교 횟수는 다음과 같습니다. 2n - 2.

나누기 및 정복 접근 방식을 사용하여 비교 횟수를 줄일 수 있습니다. 다음은 기술입니다.

접근 방식을 나누고 정복하십시오

이 접근 방식에서 어레이는 두 개의 절반으로 나뉩니다. 그런 다음 재귀 접근 방식을 사용하여 각 반쪽에서 최대 및 최소 숫자를 찾습니다. 나중에 각 절반의 최대 값 2 개와 각 절반의 최소값 2 개를 반환합니다.

이 주어진 문제에서 배열의 요소 수는 $y - x + 1$, 어디 y 보다 크거나 같음 x.

$\mathbf{\mathit{Max - Min(x, y)}}$ 배열의 최대 값과 최소값을 반환합니다. $\mathbf{\mathit{numbers[x...y]}}$.

Algorithm: Max - Min(x, y) 
if y – x ≤ 1 then  
   return (max(numbers[x], numbers[y]), min((numbers[x], numbers[y])) 
else 
   (max1, min1):= maxmin(x, ⌊((x + y)/2)⌋) 
   (max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y) 
return (max(max1, max2), min(min1, min2))

분석

허락하다 T(n) 에 의해 만들어진 비교의 수 $\mathbf{\mathit{Max - Min(x, y)}}$, 요소의 수 $n = y - x + 1$.

만약 T(n) 숫자를 나타내면 되풀이 관계는 다음과 같이 나타낼 수 있습니다.

$$T(n) = \begin{cases}T\left(\lfloor\frac{n}{2}\rfloor\right)+T\left(\lceil\frac{n}{2}\rceil\right)+2 & for\: n>2\\1 & for\:n = 2 \\0 & for\:n = 1\end{cases}$$

가정하자 n 힘의 형태입니다 2. 그 후,n = 2^k 어디 k 재귀 트리의 높이입니다.

그래서,

$$T(n) = 2.T (\frac{n}{2}) + 2 = 2.\left(\begin{array}{c}2.T(\frac{n}{4}) + 2\end{array}\right) + 2 ..... = \frac{3n}{2} - 2$$

Naïve 방법에 비해 분할 및 정복 접근 방식에서는 비교 횟수가 적습니다. 그러나 점근 표기법을 사용하면 두 가지 접근법 모두 다음과 같이 표현됩니다.O(n).

이 장에서는 병합 정렬에 대해 논의하고 복잡성을 분석합니다.

문제 설명

숫자 목록을 정렬하는 문제는 즉시 분할 및 정복 전략에 적합합니다. 목록을 두 개로 분할하고 각 절반을 재귀 적으로 정렬 한 다음 두 개의 정렬 된 하위 목록을 병합합니다.

해결책

이 알고리즘에서 숫자는 배열에 저장됩니다. numbers[]. 여기,p 과 q 하위 배열의 시작 및 끝 인덱스를 나타냅니다.

Algorithm: Merge-Sort (numbers[], p, r) 
if p < r then  
q = ⌊(p + r) / 2⌋ 
Merge-Sort (numbers[], p, q) 
    Merge-Sort (numbers[], q + 1, r) 
    Merge (numbers[], p, q, r)

Function: Merge (numbers[], p, q, r)
n₁ = q – p + 1 
n₂ = r – q 
declare leftnums[1…n₁ + 1] and rightnums[1…n₂ + 1] temporary arrays 
for i = 1 to n₁ 
   leftnums[i] = numbers[p + i - 1] 
for j = 1 to n₂ 
   rightnums[j] = numbers[q+ j] 
leftnums[n₁ + 1] = ∞ 
rightnums[n₂ + 1] = ∞ 
i = 1 
j = 1 
for k = p to r 
   if leftnums[i] ≤ rightnums[j] 
      numbers[k] = leftnums[i] 
      i = i + 1 
   else
      numbers[k] = rightnums[j] 
      j = j + 1

분석

Merge-Sort의 실행 시간을 다음과 같이 고려해 보겠습니다. T(n). 그 후,

$T(n)=\begin{cases}c & if\:n\leqslant 1\\2\:x\:T(\frac{n}{2})+d\:x\:n & otherwise\end{cases}$여기서 c 와 d 는 상수입니다.

따라서이 반복 관계를 사용하면

$$T(n) = 2^i T(\frac{n}{2^i}) + i.d.n$$

같이, $i = log\:n,\: T(n) = 2^{log\:n} T(\frac{n}{2^{log\:n}}) + log\:n.d.n$

$=\:c.n + d.n.log\:n$

따라서, $T(n) = O(n\:log\:n)$

예

다음 예에서는 Merge-Sort 알고리즘을 단계별로 보여주었습니다. 첫째, 모든 반복 배열은 하위 배열에 하나의 요소 만 포함될 때까지 두 개의 하위 배열로 나뉩니다. 이러한 하위 배열을 더 이상 분할 할 수없는 경우 병합 작업이 수행됩니다.

이 장에서는 나누기 및 정복 방법을 기반으로하는 또 다른 알고리즘에 대해 설명합니다.

문제 설명

이진 검색은 정렬 된 배열에서 수행 할 수 있습니다. 이 접근 방식에서 요소의 색인은x요소가 요소 목록에 속하는지 결정됩니다. 배열이 정렬되지 않은 경우 선형 검색을 사용하여 위치를 결정합니다.

해결책

이 알고리즘에서 우리는 요소가 x 배열에 저장된 일련의 숫자에 속합니다. numbers[]. 어디l 과 r 검색 작업을 수행해야하는 하위 배열의 왼쪽 및 오른쪽 인덱스를 나타냅니다.

Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then  
   return l  
else 
   m := ⌊(l + r) / 2⌋ 
   if x ≤ numbers[m]  then 
      return Binary-Search(numbers[], x, l, m) 
   else 
      return Binary-Search(numbers[], x, m+1, r)

분석

선형 검색 실행 O(n)시각. 이진 검색은 결과를 생성하는 반면O(log n) 시각

허락하다 T(n) 배열에서 최악의 경우 비교 횟수 n 집단.

그 후,

$$T(n)=\begin{cases}0 & if\:n= 1\\T(\frac{n}{2})+1 & otherwise\end{cases}$$

이 반복 관계 사용 $T(n) = log\:n$.

따라서 이진 검색은 $O(log\:n)$ 시각.

예

이 예에서는 요소 63을 검색합니다.

이 장에서는 먼저 일반적인 행렬 곱셈 방법에 대해 설명하고 나중에 Strassen의 행렬 곱셈 알고리즘에 대해 설명합니다.

문제 설명

두 개의 행렬을 고려해 보겠습니다. X 과 Y. 결과 행렬을 계산하고 싶습니다.Z 곱하여 X 과 Y.

나이브 방법

먼저 순진한 방법과 그 복잡성에 대해 설명합니다. 여기에서 우리는Z = X × Y. Naïve 방법을 사용하여 두 개의 행렬 (X 과 Y)는 행렬의 순서가 다음과 같으면 곱할 수 있습니다. p × q 과 q × r. 다음은 알고리즘입니다.

Algorithm: Matrix-Multiplication (X, Y, Z) 
for i = 1 to p do 
   for j = 1 to r do 
      Z[i,j] := 0 
      for k = 1 to q do 
         Z[i,j] := Z[i,j] + X[i,k] × Y[k,j]

복잡성

여기에서는 정수 연산이 O(1)시각. 세 가지가 있습니다for이 알고리즘의 루프와 하나는 다른 알고리즘에 중첩됩니다. 따라서 알고리즘은O(n³) 실행할 시간입니다.

Strassen의 행렬 곱셈 알고리즘

이러한 맥락에서 Strassen의 행렬 곱셈 알고리즘을 사용하면 시간 소비를 약간 개선 할 수 있습니다.

Strassen의 행렬 곱셈은 다음에서만 수행 할 수 있습니다. square matrices 어디 n 이다 power of 2. 두 행렬의 순서는 다음과 같습니다.n × n.

나누기 X, Y 과 Z 다음과 같이 4 개의 (n / 2) × (n / 2) 행렬로-

$Z = \begin{bmatrix}I & J \\K & L \end{bmatrix}$ $X = \begin{bmatrix}A & B \\C & D \end{bmatrix}$ 과 $Y = \begin{bmatrix}E & F \\G & H \end{bmatrix}$

Strassen의 알고리즘을 사용하여 다음을 계산합니다.

$$M_{1} \: \colon= (A+C) \times (E+F)$$

$$M_{2} \: \colon= (B+D) \times (G+H)$$

$$M_{3} \: \colon= (A-D) \times (E+H)$$

$$M_{4} \: \colon= A \times (F-H)$$

$$M_{5} \: \colon= (C+D) \times (E)$$

$$M_{6} \: \colon= (A+B) \times (H)$$

$$M_{7} \: \colon= D \times (G-E)$$

그때,

$$I \: \colon= M_{2} + M_{3} - M_{6} - M_{7}$$

$$J \: \colon= M_{4} + M_{6}$$

$$K \: \colon= M_{5} + M_{7}$$

$$L \: \colon= M_{1} - M_{3} - M_{4} - M_{5}$$

분석

$T(n)=\begin{cases}c & if\:n= 1\\7\:x\:T(\frac{n}{2})+d\:x\:n^2 & otherwise\end{cases}$여기서 c 와 d 는 상수입니다.

이 반복 관계를 사용하여 $T(n) = O(n^{log7})$

따라서 Strassen의 행렬 곱셈 알고리즘의 복잡성은 다음과 같습니다. $O(n^{log7})$.

모든 알고리즘 접근 방식 중에서 가장 간단하고 직접적인 접근 방식은 Greedy 방법입니다. 이 접근 방식에서는 향후 현재 결정의 영향에 대해 걱정하지 않고 현재 사용 가능한 정보를 기반으로 결정을 내립니다.

Greedy 알고리즘은 부분적으로 솔루션을 구축하여 즉각적인 이점을 제공하는 방식으로 다음 부분을 선택합니다. 이 접근 방식은 이전에 취한 선택을 결코 재고하지 않습니다. 이 접근 방식은 주로 최적화 문제를 해결하는 데 사용됩니다. Greedy 방법은 구현하기 쉽고 대부분의 경우 매우 효율적입니다. 따라서 Greedy 알고리즘은 글로벌 최적 솔루션을 찾기 위해 각 단계에서 로컬 최적 선택을 따르는 휴리스틱 기반 알고리즘 패러다임이라고 말할 수 있습니다.

많은 문제에서 합리적인 시간에 근사 (최적에 가까운) 솔루션을 제공하지만 최적의 솔루션을 생성하지 못합니다.

Greedy 알고리즘의 구성 요소

Greedy 알고리즘에는 다음과 같은 다섯 가지 구성 요소가 있습니다.

A candidate set −이 세트에서 솔루션이 생성됩니다.
A selection function − 솔루션에 추가 할 최적의 후보를 선택하는 데 사용됩니다.
A feasibility function − 후보자가 솔루션에 기여할 수 있는지 여부를 결정하는 데 사용됩니다.
An objective function − 솔루션 또는 부분 솔루션에 값을 할당하는 데 사용됩니다.
A solution function − 완전한 솔루션에 도달했는지 여부를 나타내는 데 사용됩니다.

적용 분야

탐욕스러운 접근 방식은 다음과 같은 많은 문제를 해결하는 데 사용됩니다.

Dijkstra의 알고리즘을 사용하여 두 정점 사이의 최단 경로 찾기.
Prim의 / Kruskal 알고리즘 등을 사용하여 그래프에서 최소 스패닝 트리 찾기

욕심 많은 접근이 실패하는 곳

많은 문제에서 Greedy 알고리즘은 최적의 솔루션을 찾지 못하고 최악의 솔루션을 생성 할 수 있습니다. Traveling Salesman 및 Knapsack과 같은 문제는이 방법으로 해결할 수 없습니다.

Greedy 알고리즘은 Knapsack 문제라고하는 잘 알려진 문제로 잘 이해 될 수 있습니다. 다른 알고리즘 접근 방식을 사용하여 동일한 문제를 해결할 수 있지만 Greedy 접근 방식은 Fractional Knapsack 문제를 적절한 시간에 합리적으로 해결합니다. 배낭 문제에 대해 자세히 논의하겠습니다.

배낭 문제

각각 가중치와 값이있는 항목 집합이 주어지면 총 가중치가 주어진 제한보다 작거나 같고 총 값이 가능한 한 커지도록 컬렉션에 포함 할 항목의 하위 집합을 결정합니다.

배낭 문제는 조합 최적화 문제에 있습니다. 실제 문제의 더 복잡한 수학적 모델에서 하위 문제로 나타납니다. 어려운 문제에 대한 일반적인 접근 방식 중 하나는 가장 제한적인 제약 조건을 식별하고 다른 제약 조건을 무시하고 배낭 문제를 해결하고 무시 된 제약 조건을 충족하도록 솔루션을 조정하는 것입니다.

응용

일부 제약과 함께 리소스 할당의 많은 경우 문제는 Knapsack 문제와 유사한 방식으로 파생 될 수 있습니다. 다음은 일련의 예입니다.

원자재 절단을위한 최소한의 낭비 방법 찾기
포트폴리오 최적화
재고 문제 절단

문제 시나리오

도둑이 상점을 강탈하고 있으며 W그의 배낭에. 매장에 n 개의 아이템이 있으며 무게는i^th 항목은 w_i 그리고 그 이익은 p_i. 도둑은 어떤 물건을 가져 가야합니까?

이러한 맥락에서 항목은 도둑이 최대 이익을 얻을 수있는 항목을 운반 할 수있는 방식으로 선택되어야합니다. 따라서 도둑의 목적은 이익을 극대화하는 것입니다.

항목의 특성에 따라 배낭 문제는 다음과 같이 분류됩니다.

분수 배낭
Knapsack

분수 배낭

이 경우 항목을 더 작은 조각으로 나눌 수 있으므로 도둑이 항목의 일부를 선택할 수 있습니다.

문제 진술에 따르면

있습니다 n 상점의 항목
무게 i^th 안건 $w_{i} > 0$
이익 i^th 안건 $p_{i} > 0$ 과
배낭의 용량은 W

이 버전의 배낭 문제에서는 항목을 더 작은 조각으로 나눌 수 있습니다. 그래서 도둑은x_i 의 i^th 안건.

$$0 \leqslant x_{i} \leqslant 1$$

그만큼 i^th 아이템이 무게에 기여 $x_{i}.w_{i}$ 배낭의 총 무게와 이익에 $x_{i}.p_{i}$ 총 이익에.

따라서이 알고리즘의 목적은

$$maximize\:\displaystyle\sum\limits_{n=1}^n (x_{i}.p_{}i)$$

제약에 따라

$$\displaystyle\sum\limits_{n=1}^n (x_{i}.w_{}i) \leqslant W$$

최적의 솔루션이 배낭을 정확하게 채워야한다는 것은 분명합니다. 그렇지 않으면 나머지 항목 중 하나의 일부를 추가하고 전체 수익을 늘릴 수 있습니다.

따라서 최적의 솔루션은 다음과 같이 얻을 수 있습니다.

$$\displaystyle\sum\limits_{n=1}^n (x_{i}.w_{}i) = W$$

이 맥락에서 먼저 우리는 값에 따라 해당 항목을 정렬해야합니다. $\frac{p_{i}}{w_{i}}$, 그래서 $\frac{p_{i}+1}{w_{i}+1}$ ≤ $\frac{p_{i}}{w_{i}}$. 여기,x 항목의 일부를 저장하는 배열입니다.

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if weight + w[i] ≤ W then  
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x

분석

제공된 항목이 이미 내림차순으로 정렬 된 경우 $\mathbf{\frac{p_{i}}{w_{i}}}$, whileloop는 시간이 걸립니다. O(n); 따라서 정렬을 포함한 총 시간은O(n logn).

예

배낭의 용량이 W = 60 제공된 항목 목록은 다음 표에 나와 있습니다.

안건	ㅏ	비	씨	디
이익	280	100	120	120
무게	40	10	20	24
비율 $(\frac{p_{i}}{w_{i}})$	7	10	6	5

제공된 항목이 기준으로 정렬되지 않기 때문에 $\mathbf{\frac{p_{i}}{w_{i}}}$. 정렬 후 항목은 다음 표와 같습니다.

안건	비	ㅏ	씨	디
이익	100	280	120	120
무게	10	40	20	24
비율 $(\frac{p_{i}}{w_{i}})$	10	7	6	5

해결책

에 따라 모든 항목을 정렬 한 후 $\frac{p_{i}}{w_{i}}$. 먼저 모든B 무게로 선택됩니다 B배낭의 용량보다 적습니다. 다음으로 항목A 배낭의 사용 가능한 용량이 무게보다 크므로 A. 지금,C다음 항목으로 선택됩니다. 단, 배낭의 남은 용량이 무게보다 적기 때문에 전체 품목을 선택할 수 없습니다.C.

따라서 C (예 : (60-50) / 20)이 선택됩니다.

이제 배낭의 용량은 선택한 항목과 동일합니다. 따라서 더 이상 항목을 선택할 수 없습니다.

선택한 항목의 총 무게는 10 + 40 + 20 * (10/20) = 60

그리고 총 이익은 100 + 280 + 120 * (10/20) = 380 + 60 = 440

이것이 최적의 솔루션입니다. 다른 조합의 항목을 선택하면 더 많은 이익을 얻을 수 없습니다.

문제 설명

작업 순서 문제에서 목표는 마감일 내에 완료되고 최대 이익을 제공하는 작업 순서를 찾는 것입니다.

해결책

고려해 보겠습니다. n마감일까지 작업이 완료되면 마감일 및 수익과 관련된 일자리가 주어집니다. 이러한 작업은 최대 수익이있는 방식으로 주문해야합니다.

주어진 모든 작업이 기한 내에 완료되지 않을 수 있습니다.

가정, 마감일 i^th 일 J_i 이다 d_i 이 직업에서 얻은 이익은 p_i. 따라서이 알고리즘의 최적 솔루션은 최대 수익을내는 실행 가능한 솔루션입니다.

그러므로, $D(i) > 0$ ...에 대한 $1 \leqslant i \leqslant n$.

처음에 이러한 작업은 이익에 따라 주문됩니다. $p_{1} \geqslant p_{2} \geqslant p_{3} \geqslant \:... \: \geqslant p_{n}$.

Algorithm: Job-Sequencing-With-Deadline (D, J, n, k) 
D(0) := J(0) := 0 
k := 1 
J(1) := 1   // means first job is selected 
for i = 2 … n do 
   r := k 
   while D(J(r)) > D(i) and D(J(r)) ≠ r do 
      r := r – 1 
   if D(J(r)) ≤ D(i) and D(i) > r then 
      for l = k … r + 1 by -1 do 
         J(l + 1) := J(l) 
         J(r + 1) := i 
         k := k + 1

분석

이 알고리즘에서 우리는 두 개의 루프를 사용하고 있습니다. 따라서이 알고리즘의 복잡성은$O(n^2)$.

예

다음 표에 표시된대로 주어진 작업 집합을 고려해 보겠습니다. 마감일 내에 완료되고 최대의 이익을 얻을 수있는 일련의 작업을 찾아야합니다. 각 작업은 마감일 및 이익과 관련이 있습니다.

일	J₁	J₂	J₃	J₄	J₅
마감 시간	2	1	삼	2	1
이익	60	100	20	40	20

해결책

이 문제를 해결하기 위해 주어진 일자리는 수익에 따라 내림차순으로 정렬됩니다. 따라서 정렬 후 작업은 다음 표와 같이 정렬됩니다.

일	J₂	J₁	J₄	J₃	J₅
마감 시간	1	2	2	삼	1
이익	100	60	40	20	20

이 작업 세트에서 먼저 J₂, 마감일 내에 완료 할 수 있으며 최대 수익에 기여합니다.

다음, J₁ 더 많은 이익을 제공하기 때문에 선택됩니다 J₄.
다음 시계에 J₄ 마감일이 지났으므로 선택할 수 없습니다. J₃ 기한 내에 실행되므로 선택됩니다.
작업 J₅ 기한 내에 실행할 수 없으므로 폐기됩니다.

따라서 솔루션은 일련의 작업 (J₂, J₁, J₃), 기한 내에 실행되고 최대 이익을 제공합니다.

이 시퀀스의 총 이익은 100 + 60 + 20 = 180.

길이가 다른 정렬 된 파일 세트를 하나의 정렬 된 파일로 병합합니다. 결과 파일이 최소 시간에 생성되는 최적의 솔루션을 찾아야합니다.

정렬 된 파일의 수를 지정하면 여러 가지 방법으로 하나의 정렬 된 파일로 병합 할 수 있습니다. 이 병합은 쌍으로 수행 할 수 있습니다. 따라서 이러한 유형의 병합을 다음과 같이 호출합니다.2-way merge patterns.

페어링에 따라 서로 다른 시간이 필요하므로이 전략에서는 여러 파일을 함께 병합하는 최적의 방법을 결정하려고합니다. 각 단계에서 가장 짧은 시퀀스 두 개가 병합됩니다.

병합하려면 p-record file 그리고 q-record file 아마도 필요하다 p + q 확실한 선택은 각 단계에서 가장 작은 두 파일을 병합하는 것입니다.

양방향 병합 패턴은 이진 병합 트리로 나타낼 수 있습니다. 일련의n 정렬 된 파일 {f₁, f₂, f₃, …, f_n}. 처음에 이것의 각 요소는 단일 노드 이진 트리로 간주됩니다. 이 최적의 솔루션을 찾기 위해 다음 알고리즘이 사용됩니다.

Algorithm: TREE (n)  
for i := 1 to n – 1 do  
   declare new node  
   node.leftchild := least (list) 
   node.rightchild := least (list) 
   node.weight) := ((node.leftchild).weight) + ((node.rightchild).weight)  
   insert (list, node);  
return least (list);

이 알고리즘의 끝에서 루트 노드의 가중치는 최적의 비용을 나타냅니다.

예

주어진 파일 f ₁ , f ₂ , f ₃ , f ₄ 및 f ₅ 를 각각 20, 30, 10, 5 및 30 개의 요소로 고려해 보겠습니다 .

제공된 순서에 따라 병합 작업을 수행하면

M₁ = merge f₁ and f₂ => 20 + 30 = 50

M₂ = merge M₁ and f₃ => 50 + 10 = 60

M₃ = merge M₂ and f₄ => 60 + 5 = 65

M₄ = merge M₃ and f₅ => 65 + 30 = 95

따라서 총 작업 수는

50 + 60 + 65 + 95 = 270

이제 더 나은 해결책이 있습니까?

오름차순으로 크기에 따라 숫자를 정렬하면 다음과 같은 순서를 얻습니다.

f₄, f₃, f₁, f₂, f₅

따라서이 시퀀스에서 병합 작업을 수행 할 수 있습니다.

M₁ = merge f₄ and f₃ => 5 + 10 = 15

M₂ = merge M₁ and f₁ => 15 + 20 = 35

M₃ = merge M₂ and f₂ => 35 + 30 = 65

M₄ = merge M₃ and f₅ => 65 + 30 = 95

따라서 총 작업 수는

15 + 35 + 65 + 95 = 210

분명히 이것은 이전보다 낫습니다.

이 맥락에서 우리는 이제이 알고리즘을 사용하여 문제를 풀 것입니다.

초기 설정

1 단계

2 단계

3 단계

4 단계

따라서 솔루션은 15 + 35 + 60 + 95 = 205 번의 비교를 사용합니다.

동적 프로그래밍은 최적화 문제에도 사용됩니다. 나누기 및 정복 방법과 마찬가지로 동적 프로그래밍은 하위 문제의 솔루션을 결합하여 문제를 해결합니다. 또한 동적 프로그래밍 알고리즘은 각 하위 문제를 한 번만 해결 한 다음 그 답을 표에 저장하므로 매번 답을 다시 계산하는 작업을 피할 수 있습니다.

문제의 두 가지 주요 속성은 주어진 문제가 동적 프로그래밍을 사용하여 해결 될 수 있음을 시사합니다. 이러한 속성은overlapping sub-problems and optimal substructure.

중복되는 하위 문제

Divide-and-Conquer 접근 방식과 유사하게 Dynamic Programming은 솔루션을 하위 문제에 결합합니다. 주로 하나의 하위 문제 해결이 반복적으로 필요한 경우에 사용됩니다. 계산 된 솔루션은 테이블에 저장되므로 다시 계산할 필요가 없습니다. 따라서이 기술은 중첩되는 하위 문제가있는 경우에 필요합니다.

예를 들어, 이진 검색에는 겹치는 하위 문제가 없습니다. 피보나치 수의 재귀 프로그램에는 많은 하위 문제가 중복됩니다.

최적의 하위 구조

주어진 문제는 하위 문제의 최적 솔루션을 사용하여 주어진 문제에 대한 최적의 솔루션을 얻을 수있는 경우 최적의 하위 구조 속성을 갖습니다.

예를 들어, 최단 경로 문제에는 다음과 같은 최적의 하부 구조 속성이 있습니다.

노드가 x 소스 노드의 최단 경로에 있습니다. u 대상 노드로 v, 다음에서 가장 짧은 경로 u ...에 v 가장 짧은 경로의 조합입니다. u ...에 x및 최단 경로 x ...에 v.

Floyd-Warshall 및 Bellman-Ford와 같은 표준 All Pair Shortest Path 알고리즘은 동적 프로그래밍의 전형적인 예입니다.

동적 프로그래밍 접근법의 단계

동적 프로그래밍 알고리즘은 다음 네 단계를 사용하여 설계되었습니다.

최적 솔루션의 구조를 특성화합니다.
최적 솔루션의 값을 재귀 적으로 정의합니다.
일반적으로 상향식 방식으로 최적 솔루션의 가치를 계산합니다.
계산 된 정보에서 최적의 솔루션을 구성합니다.

동적 프로그래밍 접근법의 응용

매트릭스 체인 곱셈
가장 긴 공통 하위 시퀀스
여행하는 세일즈맨 문제

이 튜토리얼에서는 앞서 Greedy 접근 방식을 사용하여 Fractional Knapsack 문제에 대해 논의했습니다. Greedy 접근 방식이 Fractional Knapsack에 대한 최적의 솔루션을 제공함을 보여주었습니다. 그러나이 장에서는 0-1 배낭 문제와 그 분석을 다룹니다.

0-1 배낭에서는 아이템이 깨질 수 없으므로 도둑이 아이템 전체를 가져 가거나 그대로 두어야합니다. 이것이 0-1 배낭이라고 부르는 이유입니다.

따라서 0-1 Knapsack의 경우 x_i 다음 중 하나 일 수 있습니다. 0 또는 1, 다른 제약 조건은 동일하게 유지됩니다.

0-1 배낭은 Greedy 접근 방식으로 해결할 수 없습니다. 탐욕스러운 접근 방식은 최적의 솔루션을 보장하지 않습니다. 많은 경우에 Greedy 접근 방식은 최적의 솔루션을 제공 할 수 있습니다.

다음 예는 우리의 성명을 확립합니다.

예 -1

배낭의 용량이 W = 25이고 항목이 다음 표에 표시된 것과 같다고 가정 해 보겠습니다.

안건	ㅏ	비	씨	디
이익	24	18	18	10
무게	24	10	10	7

단위 중량 당 이익을 고려하지 않고 (p_i/w_i)이 문제를 해결하기 위해 Greedy 접근 방식을 적용하면 첫 번째 항목 A이 최대 기여로 선택됩니다 _난의 모든 요소들 사이에서 엄마 이익.

항목 선택 후 A, 더 이상 항목이 선택되지 않습니다. 따라서이 주어진 항목 세트에 대한 총 이익은24. 반면 항목을 선택하면 최적의 솔루션을 얻을 수 있습니다.B 그리고 C, 여기서 총 이익은 18 + 18 = 36입니다.

예 -2

전체 이익을 기준으로 항목을 선택하는 대신이 예에서는 비율 p _i / w _i를 기준으로 항목을 선택 합니다. 배낭의 용량이 W = 60이고 항목이 다음 표와 같다고 가정 해 보겠습니다 .

안건	ㅏ	비	씨
가격	100	280	120
무게	10	40	20
비율	10	7	6

Greedy 접근 방식 사용, 첫 번째 항목 A선택됩니다. 그런 다음 다음 항목B선택됩니다. 따라서 총 이익은100 + 280 = 380. 그러나이 인스턴스의 최적 솔루션은 항목을 선택하여 얻을 수 있습니다.B 과 C, 총 이익은 280 + 120 = 400.

따라서 Greedy 접근 방식이 최적의 솔루션을 제공하지 못할 수 있다는 결론을 내릴 수 있습니다.

0-1 Knapsack을 해결하려면 Dynamic Programming 접근법이 필요합니다.

문제 설명

도둑이 상점을 강탈하고 최대 수행 할 수 _난 의 말의 무게를W그의 배낭에. 있습니다n 품목 및 무게 i^th 항목은 w_i 이 항목을 선택하면 얻는 이익은 p_i. 도둑은 어떤 물건을 가져 가야합니까?

동적 프로그래밍 방식

허락하다 i 최적의 솔루션에서 가장 높은 번호의 항목 S ...에 대한 W불화. 그때S^' = S - {i} 최적의 솔루션입니다 W - w_i 달러와 솔루션의 가치 S 이다 V_i 더하기 하위 문제의 가치.

이 사실을 다음 공식으로 표현할 수 있습니다. c[i, w] 항목에 대한 솔루션이 1,2, … , i상기 최대 _I 침묵 무게w.

알고리즘은 다음 입력을받습니다.

최대 _난 엄마 무게W
항목 수 n
두 시퀀스 v = <v₁, v₂, …, v_n> 과 w = <w₁, w₂, …, w_n>

Dynamic-0-1-knapsack (v, w, n, W) 
for w = 0 to W do 
   c[0, w] = 0 
for i = 1 to n do 
   c[i, 0] = 0 
   for w = 1 to W do 
      if w_i ≤ w then 
         if v_i + c[i-1, w-w_i] then 
            c[i, w] = v_i + c[i-1, w-w_i] 
         else c[i, w] = c[i-1, w] 
      else 
         c[i, w] = c[i-1, w]

취할 항목 세트는 테이블에서 추론 할 수 있습니다. c[n, w] 최적의 값이 나온 곳을 거꾸로 추적합니다.

만약 C [I, w] = C [I-1, w] 다음 아이템i 솔루션의 일부가 아니며 계속 추적합니다. c[i-1, w]. 그렇지 않으면 항목i 솔루션의 일부이며 계속 추적합니다. c[i-1, w-W].

분석

이 알고리즘은 테이블 c 에 ( n + 1). ( w + 1) 항목 이 있으므로 θ ( n , w ) 시간 이 걸리며 , 여기서 각 항목은 계산하는 데 θ (1) 시간이 필요합니다.

가장 긴 일반적인 하위 시퀀스 문제는 주어진 문자열에 존재하는 가장 긴 시퀀스를 찾는 것입니다.

하위 시퀀스

시퀀스 S = <s ₁ , s ₂ , s ₃ , s ₄ ,…, s _n >을 생각해 봅시다 .

S에 대한 시퀀스 Z = <z ₁ , z ₂ , z ₃ , z ₄ ,…, z _m >은 일부 요소의 S 삭제에서 파생 될 수있는 경우에만 S의 하위 시퀀스라고합니다.

공통 하위 시퀀스

가정 해 봅시다. X 과 Y유한 요소 집합에 대한 두 개의 시퀀스입니다. 우리는 말할 수 있습니다Z 다음의 일반적인 하위 시퀀스입니다. X 과 Y, 만약 Z 둘 다의 하위 시퀀스입니다. X 과 Y.

가장 긴 공통 하위 시퀀스

일련의 시퀀스가 제공되는 경우 가장 긴 공통 하위 시퀀스 문제는 최대 길이 인 모든 시퀀스의 공통 하위 시퀀스를 찾는 것입니다.

가장 긴 공통 하위 시퀀스 문제는 고전적인 컴퓨터 과학 문제이며, diff-utility와 같은 데이터 비교 프로그램의 기초이며 생물 정보학에 응용됩니다. 또한 SVN 및 Git과 같은 개정 제어 시스템에서 개정 제어 파일 모음에 대한 여러 변경 사항을 조정하기 위해 널리 사용됩니다.

나이브 방법

허락하다 X 길이의 순서 m 과 Y 일련의 길이 n. 모든 하위 시퀀스 확인X 그것이 하위 시퀀스인지 여부 Y, 발견 된 가장 긴 공통 하위 시퀀스를 반환합니다.

있습니다 2^m 하위 시퀀스 X. 시퀀스의 하위 시퀀스인지 여부에 관계없이 시퀀스 테스트Y 소요 O(n)시각. 따라서 순진한 알고리즘은O(n2^m) 시각.

동적 프로그래밍

하자 X = <x ₁ , X ₂ , X ₃ , ..., X의 _m > 과 Y = <Y ₁ , Y ₂ , Y ₃ , ..., Y _n은 > 서열 될. 요소의 길이를 계산하기 위해 다음 알고리즘이 사용됩니다.

이 절차에서 테이블 C[m, n] 행 주요 순서와 다른 테이블로 계산됩니다. B[m,n] 최적의 솔루션을 구성하기 위해 계산됩니다.

Algorithm: LCS-Length-Table-Formulation (X, Y)
m := length(X) 
n := length(Y) 
for i = 1 to m do 
   C[i, 0] := 0 
for j = 1 to n do 
   C[0, j] := 0 
for i = 1 to m do 
   for j = 1 to n do 
      if x_i = y_j 
         C[i, j] := C[i - 1, j - 1] + 1 
         B[i, j] := ‘D’ 
      else 
         if C[i -1, j] ≥ C[i, j -1] 
            C[i, j] := C[i - 1, j] + 1 
            B[i, j] := ‘U’ 
         else 
         C[i, j] := C[i, j - 1]
         B[i, j] := ‘L’ 
return C and B

Algorithm: Print-LCS (B, X, i, j)
if i = 0 and j = 0 
   return  
if B[i, j] = ‘D’ 
   Print-LCS(B, X, i-1, j-1) 
   Print(x_i) 
else if B[i, j] = ‘U’ 
   Print-LCS(B, X, i-1, j) 
else 
   Print-LCS(B, X, i, j-1)

이 알고리즘은 가장 긴 공통 하위 시퀀스를 인쇄합니다. X 과 Y.

분석

테이블을 채우려면 외부 for 루프 반복 m 시간과 내부 for 루프 반복 n타임스. 따라서 알고리즘의 복잡성은 O (m, n)입니다 .m 과 n 두 문자열의 길이입니다.

예

이 예에서는 두 개의 문자열이 있습니다. X = BACDB 과 Y = BDCB 가장 긴 공통 하위 시퀀스를 찾습니다.

알고리즘 LCS-Length-Table-Formulation (위에 언급 된대로)에 따라 테이블 C (왼쪽에 표시됨) 및 테이블 B (오른쪽에 표시됨)를 계산했습니다.

표 B에서는 'D', 'L', 'U'대신 대각선 화살표, 왼쪽 화살표 및 위쪽 화살표를 사용하고 있습니다. 테이블 B를 생성 한 후 LCS는 기능 LCS-Print에 의해 결정됩니다. 결과는 BCB입니다.

ㅏ spanning tree 모든 정점이 최소 간선 수로 연결된 무 방향 그래프의 하위 집합입니다.

모든 정점이 그래프로 연결되어 있으면 스패닝 트리가 하나 이상 존재합니다. 그래프에는 스패닝 트리가 둘 이상있을 수 있습니다.

속성

스패닝 트리에는주기가 없습니다.
모든 정점은 다른 정점에서 도달 할 수 있습니다.

예

다음 그래프에서 강조 표시된 모서리는 스패닝 트리를 형성합니다.

최소 스패닝 트리

ㅏ Minimum Spanning Tree (MST)가능한 최소 총 간선 가중치와 함께 모든 정점을 연결하는 연결된 가중치 무 방향 그래프의 간선 하위 집합입니다. MST를 도출하기 위해 Prim의 알고리즘 또는 Kruskal의 알고리즘을 사용할 수 있습니다. 따라서이 장에서는 Prim의 알고리즘에 대해 설명합니다.

우리가 논의했듯이 하나의 그래프에는 둘 이상의 스패닝 트리가있을 수 있습니다. 만일 거기에n 정점의 수, 스패닝 트리는 n - 1가장자리 수. 이 맥락에서 그래프의 각 모서리가 가중치와 연관되고 스패닝 트리가 둘 이상있는 경우 그래프의 최소 스패닝 트리를 찾아야합니다.

또한 중복 가중치 간선이있는 경우 그래프에 최소 스패닝 트리가 여러 개있을 수 있습니다.

위의 그래프에서 최소 스패닝 트리는 아니지만 스패닝 트리를 보여주었습니다. 이 스패닝 트리의 비용은 (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38입니다.

Prim의 알고리즘을 사용하여 최소 스패닝 트리를 찾습니다.

프림의 알고리즘

Prim의 알고리즘은 최소 스패닝 트리를 찾는 탐욕스러운 접근 방식입니다. 이 알고리즘에서 MST를 형성하기 위해 임의의 정점에서 시작할 수 있습니다.

Algorithm: MST-Prim’s (G, w, r) 
for each u є G.V 
   u.key = ∞ 
   u.∏ = NIL 
r.key = 0 
Q = G.V 
while Q ≠ Ф 
   u = Extract-Min (Q) 
   for each v є G.adj[u] 
      if each v є Q and w(u, v) < v.key 
         v.∏ = u 
         v.key = w(u, v)

Extract-Min 함수는 최소 에지 비용으로 정점을 반환합니다. 이 기능은 최소 힙에서 작동합니다.

예

Prim의 알고리즘을 사용하면 모든 정점에서 시작할 수 있습니다. 정점에서 시작하겠습니다. 1.

꼭지점 3 정점에 연결됨 1 최소 엣지 비용으로 엣지 (1, 2) 스패닝 트리에 추가됩니다.

다음으로 가장자리 (2, 3) 이것은 모서리 사이의 최소값으로 간주됩니다. {(1, 2), (2, 3), (3, 4), (3, 7)}.

다음 단계에서 우리는 (3, 4) 과 (2, 4)최소 비용으로. 가장자리(3, 4) 무작위로 선택됩니다.

비슷한 방식으로 가장자리 (4, 5), (5, 7), (7, 8), (6, 8) 과 (6, 9)선택됩니다. 모든 정점을 방문하면 이제 알고리즘이 중지됩니다.

스패닝 트리의 비용은 (2 + 2 + 3 + 2 + 5 + 2 + 3 + 4) = 23입니다.이 그래프에는 다음보다 적은 비용을 가진 스패닝 트리가 더 이상 없습니다. 23.

Dijkstra의 알고리즘

Dijkstra의 알고리즘 은 모든 간선이 음이 아닌 방향성 가중치 그래프 G = (V, E) 에서 단일 소스 최단 경로 문제를 해결합니다 (즉, 각 간선에 대해 w (u, v) ≥ 0 (u, v ) Є E ).

다음 알고리즘에서는 하나의 함수를 사용합니다. Extract-Min(), 가장 작은 키로 노드를 추출합니다.

Algorithm: Dijkstra’s-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
S := Ф 
Q := G.V 
while Q ≠ Ф 
   u := Extract-Min (Q) 
   S := S U {u} 
   for each vertex v Є G.adj[u] 
      if v.d > u.d + w(u, v) 
         v.d := u.d + w(u, v) 
         v.∏ := u

분석

이 알고리즘의 복잡성은 Extract-Min 함수의 구현에 전적으로 의존합니다. 최소 추출 함수가 선형 검색을 사용하여 구현 된 경우이 알고리즘의 복잡성은 다음과 같습니다.O(V² + E).

이 알고리즘에서 최소 힙을 사용하면 Extract-Min() 함수는 노드를 반환하도록 작동합니다. Q 가장 작은 키를 사용하면이 알고리즘의 복잡성을 더 줄일 수 있습니다.

예

정점을 고려합시다 1 과 9각각 시작 및 대상 정점으로. 처음에 시작 정점을 제외한 모든 정점은 ∞로 표시되고 시작 정점은0.

꼭지점	머리 글자	Step1 V ₁	2 단계 V ₃	Step3 V ₂	₄ 단계 V ₄	5 단계 V ₍₅₎	Step6 V ₇	Step7 V ₈	Step8 V ₆
1	0	0	0	0	0	0	0	0	0
2	∞	5	4	4	4	4	4	4	4
삼	∞	2	2	2	2	2	2	2	2
4	∞	∞	∞	7	7	7	7	7	7
5	∞	∞	∞	11	9	9	9	9	9
6	∞	∞	∞	∞	∞	17	17	16	16
7	∞	∞	11	11	11	11	11	11	11
8	∞	∞	∞	∞	∞	16	13	13	13
9	∞	∞	∞	∞	∞	∞	∞	∞	20

따라서 정점의 최소 거리 9 정점에서 1 이다 20. 그리고 경로는

1 → 3 → 7 → 8 → 6 → 9

이 경로는 선행 정보를 기반으로 결정됩니다.

Bellman Ford 알고리즘

이 알고리즘은 유 방향 그래프의 단일 소스 최단 경로 문제를 해결합니다. G = (V, E)가장자리 가중치가 음수 일 수 있습니다. 또한 음의 가중치주기가없는 경우이 알고리즘을 적용하여 최단 경로를 찾을 수 있습니다.

Algorithm: Bellman-Ford-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
for i = 1 to |G.V| - 1 
   for each edge (u, v) Є G.E 
      if v.d > u.d + w(u, v) 
         v.d := u.d +w(u, v) 
         v.∏ := u 
for each edge (u, v) Є G.E 
   if v.d > u.d + w(u, v) 
      return FALSE 
return TRUE

분석

첫번째 for 루프는 초기화에 사용되며 O(V)타임스. 다음for 루프 실행 |V - 1| 가장자리를 통과합니다.O(E) 타임스.

따라서 Bellman-Ford 알고리즘은 O(V, E) 시각.

예

다음 예제는 Bellman-Ford 알고리즘이 단계별로 작동하는 방법을 보여줍니다. 이 그래프에는 음의 에지가 있지만 음의주기가 없으므로이 기술을 사용하여 문제를 해결할 수 있습니다.

초기화시 소스를 제외한 모든 정점은 ∞로 표시되고 소스는 0.

첫 번째 단계에서 소스에서 도달 할 수있는 모든 정점은 최소 비용으로 업데이트됩니다. 따라서 정점a 과 h 업데이트됩니다.

다음 단계에서 정점 a, b, f 과 e 업데이트됩니다.

동일한 논리에 따라이 단계에서 정점 b, f, c 과 g 업데이트됩니다.

여기, 정점 c 과 d 업데이트됩니다.

따라서 정점 사이의 최소 거리 s 및 정점 d 이다 20.

이전 정보에 따르면 경로는 s → h → e → g → c → d입니다.

다단계 그래프 G = (V, E) 정점이 분할 된 방향 그래프입니다. k (어디 k > 1) 분리 된 부분 집합의 수 S = {s₁,s₂,…,s_k}에지 (u, v) 가 E에있는 경우 u Є s _i 및 v Є s _{1 + 1 (} 파티션의 일부 하위 집합에 대해) 및 |s₁| = |s_k| = 1.

정점 s Є s₁ 불린다 source 그리고 정점 t Є s_k 불린다 sink.

G일반적으로 가중 그래프로 간주됩니다. 이 그래프에서 모서리 비용 (i, j) 은 c (i, j)로 표시 됩니다. 따라서 소스로부터의 경로 비용은s 가라 앉다 t 이 경로의 각 모서리 비용의 합계입니다.

다단계 그래프 문제는 소스에서 최소 비용으로 경로를 찾는 것입니다. s 가라 앉다 t.

예

다단계 그래프의 개념을 이해하려면 다음 예제를 고려하십시오.

공식에 따라 비용을 계산해야합니다. (i, j) 다음 단계 사용

1 단계 : 비용 (K-2, j)

이 단계에서는 3 개의 노드 (노드 4, 5. 6)가 다음과 같이 선택됩니다. j. 따라서이 단계에서 최소 비용을 선택할 수있는 세 가지 옵션이 있습니다.

비용 (3, 4) = 최소 {c (4, 7) + 비용 (7, 9), c (4, 8) + 비용 (8, 9)} = 7

비용 (3, 5) = 최소 {c (5, 7) + 비용 (7, 9), c (5, 8) + 비용 (8, 9)} = 5

비용 (3, 6) = 최소 {c (6, 7) + 비용 (7, 9), c (6, 8) + 비용 (8, 9)} = 5

2 단계 : 비용 (K-3, j)

단계 k-3 = 2에는 두 개의 노드, 2와 3이 있기 때문에 두 개의 노드가 j로 선택됩니다. 따라서 값 i = 2 및 j = 2 및 3입니다.

비용 (2, 2) = 최소 {c (2, 4) + 비용 (4, 8) + 비용 (8, 9), c (2, 6) +

비용 (6, 8) + 비용 (8, 9)} = 8

비용 (2, 3) = {c (3, 4) + 비용 (4, 8) + 비용 (8, 9), c (3, 5) + 비용 (5, 8) + 비용 (8, 9), c (3, 6) + 비용 (6, 8) + 비용 (8, 9)} = 10

3 단계 : 비용 (K-4, j)

비용 (1, 1) = {c (1, 2) + 비용 (2, 6) + 비용 (6, 8) + 비용 (8, 9), c (1, 3) + 비용 (3, 5) + 비용 (5, 8) + 비용 (8, 9))} = 12

c (1, 3) + 비용 (3, 6) + 비용 (6, 8 + 비용 (8, 9))} = 13

따라서 최소 비용을 갖는 경로는 1→ 3→ 5→ 8→ 9.

문제 설명

여행자는 목록에서 모든 도시를 방문해야합니다. 모든 도시 간의 거리가 알려져 있고 각 도시는 한 번만 방문해야합니다. 그가 각 도시를 정확히 한 번 방문하고 원래 도시로 돌아 오는 최단 경로는 무엇입니까?

해결책

출장 세일즈맨 문제는 가장 악명 높은 계산 문제입니다. 무차별 대입 방식을 사용하여 가능한 모든 투어를 평가하고 최상의 투어를 선택할 수 있습니다. 에 대한n 그래프의 정점 수에는 (n - 1)! 가능성의 수.

다항식 시간 알고리즘이 없지만 동적 프로그래밍 접근 방식을 사용하는 무차별 대입 대신 솔루션을 더 짧은 시간에 얻을 수 있습니다.

그래프를 생각 해보자 G = (V, E), 어디 V 도시의 집합이며 E가중치가 적용된 가장자리 집합입니다. 가장자리e(u, v) 그 정점을 나타냅니다 u 과 v연결되어있다. 정점 사이의 거리u 과 v 이다 d(u, v), 음이 아니어야합니다.

우리가 도시에서 시작했다고 가정합니다. 1 일부 도시를 방문한 후 이제 우리는 도시에 있습니다. j. 따라서 이것은 부분 여행입니다. 우리는 확실히 알아야합니다j, 다음에 방문하기 가장 편리한 도시가 결정되기 때문입니다. 우리는 또한 지금까지 방문한 모든 도시를 알아야 반복하지 않습니다. 따라서 이것은 적절한 하위 문제입니다.

일부 도시의 경우 S Є {1, 2, 3, ... , n} 그것은 포함 1, 및 j Є S, 허락하다 C(S, j) 각 노드를 방문하는 최단 경로의 길이 S 정확히 한 번, 시작 1 그리고 끝 j.

언제 |S| > 1, 우리는C(S, 1) = ∝ 경로는 다음에서 시작하고 끝날 수 없으므로 1.

자, 표현하자 C(S, j)작은 하위 문제의 관점에서. 우리는 시작해야합니다1 그리고 끝 j. 다음 도시를 선택해야합니다.

$$C(S, j) = min \:C(S - \lbrace j \rbrace, i) + d(i, j)\:where\: i\in S \: and\: i \neq jc(S, j) = minC(s- \lbrace j \rbrace, i)+ d(i,j) \:where\: i\in S \: and\: i \neq j $$

Algorithm: Traveling-Salesman-Problem 
C ({1}, 1) = 0 
for s = 2 to n do 
   for all subsets S Є {1, 2, 3, … , n} of size s and containing 1 
      C (S, 1) = ∞ 
   for all j Є S and j ≠ 1 
      C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j} 
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)

분석

기껏해야 $2^n.n$하위 문제와 각각 해결하는 데 선형 시간이 걸립니다. 따라서 총 실행 시간은$O(2^n.n^2)$.

예

다음 예에서는 출장 판매원 문제를 해결하는 단계를 설명합니다.

위의 그래프에서 다음 표가 준비됩니다.

	1	2	삼	4
1	0	10	15	20
2	5	0	9	10
삼	6	13	0	12
4	8	8	9	0

S = Φ

$$\small Cost (2,\Phi,1) = d (2,1) = 5\small Cost(2,\Phi,1)=d(2,1)=5$$

$$\small Cost (3,\Phi,1) = d (3,1) = 6\small Cost(3,\Phi,1)=d(3,1)=6$$

$$\small Cost (4,\Phi,1) = d (4,1) = 8\small Cost(4,\Phi,1)=d(4,1)=8$$

S = 1

$$\small Cost (i,s) = min \lbrace Cost (j,s – (j)) + d [i,j]\rbrace\small Cost (i,s)=min \lbrace Cost (j,s)-(j))+ d [i,j]\rbrace$$

$$\small Cost (2,\lbrace 3 \rbrace,1) = d [2,3] + Cost (3,\Phi,1) = 9 + 6 = 15cost(2,\lbrace3 \rbrace,1)=d[2,3]+cost(3,\Phi ,1)=9+6=15$$

$$\small Cost (2,\lbrace 4 \rbrace,1) = d [2,4] + Cost (4,\Phi,1) = 10 + 8 = 18cost(2,\lbrace4 \rbrace,1)=d[2,4]+cost(4,\Phi,1)=10+8=18$$

$$\small Cost (3,\lbrace 2 \rbrace,1) = d [3,2] + Cost (2,\Phi,1) = 13 + 5 = 18cost(3,\lbrace2 \rbrace,1)=d[3,2]+cost(2,\Phi,1)=13+5=18$$

$$\small Cost (3,\lbrace 4 \rbrace,1) = d [3,4] + Cost (4,\Phi,1) = 12 + 8 = 20cost(3,\lbrace4 \rbrace,1)=d[3,4]+cost(4,\Phi,1)=12+8=20$$

$$\small Cost (4,\lbrace 3 \rbrace,1) = d [4,3] + Cost (3,\Phi,1) = 9 + 6 = 15cost(4,\lbrace3 \rbrace,1)=d[4,3]+cost(3,\Phi,1)=9+6=15$$

$$\small Cost (4,\lbrace 2 \rbrace,1) = d [4,2] + Cost (2,\Phi,1) = 8 + 5 = 13cost(4,\lbrace2 \rbrace,1)=d[4,2]+cost(2,\Phi,1)=8+5=13$$

S = 2

$$\small Cost(2, \lbrace 3, 4 \rbrace, 1)=\begin{cases}d[2, 3] + Cost(3, \lbrace 4 \rbrace, 1) = 9 + 20 = 29\\d[2, 4] + Cost(4, \lbrace 3 \rbrace, 1) = 10 + 15 = 25=25\small Cost (2,\lbrace 3,4 \rbrace,1)\\\lbrace d[2,3]+ \small cost(3,\lbrace4\rbrace,1)=9+20=29d[2,4]+ \small Cost (4,\lbrace 3 \rbrace ,1)=10+15=25\end{cases}= 25$$

$$\small Cost(3, \lbrace 2, 4 \rbrace, 1)=\begin{cases}d[3, 2] + Cost(2, \lbrace 4 \rbrace, 1) = 13 + 18 = 31\\d[3, 4] + Cost(4, \lbrace 2 \rbrace, 1) = 12 + 13 = 25=25\small Cost (3,\lbrace 2,4 \rbrace,1)\\\lbrace d[3,2]+ \small cost(2,\lbrace4\rbrace,1)=13+18=31d[3,4]+ \small Cost (4,\lbrace 2 \rbrace ,1)=12+13=25\end{cases}= 25$$

$$\small Cost(4, \lbrace 2, 3 \rbrace, 1)=\begin{cases}d[4, 2] + Cost(2, \lbrace 3 \rbrace, 1) = 8 + 15 = 23\\d[4, 3] + Cost(3, \lbrace 2 \rbrace, 1) = 9 + 18 = 27=23\small Cost (4,\lbrace 2,3 \rbrace,1)\\\lbrace d[4,2]+ \small cost(2,\lbrace3\rbrace,1)=8+15=23d[4,3]+ \small Cost (3,\lbrace 2 \rbrace ,1)=9+18=27\end{cases}= 23$$

S = 3

$$\small Cost(1, \lbrace 2, 3, 4 \rbrace, 1)=\begin{cases}d[1, 2] + Cost(2, \lbrace 3, 4 \rbrace, 1) = 10 + 25 = 35\\d[1, 3] + Cost(3, \lbrace 2, 4 \rbrace, 1) = 15 + 25 = 40\\d[1, 4] + Cost(4, \lbrace 2, 3 \rbrace, 1) = 20 + 23 = 43=35 cost(1,\lbrace 2,3,4 \rbrace),1)\\d[1,2]+cost(2,\lbrace 3,4 \rbrace,1)=10+25=35\\d[1,3]+cost(3,\lbrace 2,4 \rbrace,1)=15+25=40\\d[1,4]+cost(4,\lbrace 2,3 \rbrace ,1)=20+23=43=35\end{cases}$$

최소 비용 경로는 35입니다.

비용에서 시작 {1, {2, 3, 4}, 1}, 우리는 최소값을 얻습니다 d [1, 2]. 언제s = 3, 1에서 2까지 (비용은 10) 경로를 선택한 다음 뒤로 이동합니다. 언제s = 2, 우리는 최소값을 얻습니다 d [4, 2]. 2에서 4까지 (비용은 10) 경로를 선택한 다음 뒤로 이동합니다.

언제 s = 1, 우리는 최소값을 얻습니다 d [4, 3]. 경로 4에서 3 (비용은 9)을 선택하면 다음으로 이동합니다.s = Φ단계. 우리는 최소값을 얻습니다.d [3, 1] (비용은 6입니다).

이진 검색 트리 (BST)는 키 값이 내부 노드에 저장되는 트리입니다. 외부 노드는 널 노드입니다. 키는 사전 순으로 정렬됩니다. 즉, 각 내부 노드에 대해 왼쪽 하위 트리의 모든 키가 노드의 키보다 작고 오른쪽 하위 트리의 모든 키가 더 큽니다.

각 키를 검색하는 빈도를 알면 트리의 각 노드에 액세스하는 데 예상되는 비용을 계산하기가 매우 쉽습니다. 최적의 이진 검색 트리는 BST로, 각 노드를 찾는 데 예상되는 최소 비용이 있습니다.

BST에서 요소의 검색 시간은 O(n)반면 Balanced-BST 검색 시간은 O(log n). 또한 최적 비용 이진 검색 트리에서 검색 시간을 개선 할 수 있습니다. 가장 자주 사용되는 데이터는 루트에 배치하고 루트 요소에 더 가깝게 배치하고 가장 자주 사용하지 않는 데이터는 잎과 잎에 배치합니다.

여기에서는 최적 이진 검색 트리 알고리즘이 제시됩니다. 먼저, 제공된 세트에서 BST를 구축합니다.n 고유 키 수 < k₁, k₂, k₃, ... k_n >. 여기서 우리는 키에 액세스 할 확률이K_i 이다 p_i. 일부 더미 키 (d₀, d₁, d₂, ... d_n) 키 세트에없는 값에 대해 일부 검색이 수행 될 수 있으므로 추가됩니다. K. 우리는 각 더미 키에 대해d_i 접근 가능성은 q_i.

Optimal-Binary-Search-Tree(p, q, n) 
e[1…n + 1, 0…n],  
w[1…n + 1, 0…n], 
root[1…n + 1, 0…n]  
for i = 1 to n + 1 do 
   e[i, i - 1] := q_i - 1 
   w[i, i - 1] := q_i - 1  
for l = 1 to n do 
   for i = 1 to n – l + 1 do 
      j = i + l – 1 e[i, j] := ∞ 
      w[i, i] := w[i, i -1] + p_j + q_j 
      for r = i to j do 
         t := e[i, r - 1] + e[r + 1, j] + w[i, j] 
         if t < e[i, j] 
            e[i, j] := t 
            root[i, j] := r 
return e and root

분석

알고리즘에는 O (n³) 시간, 세 중첩 이후 for루프가 사용됩니다. 이러한 각 루프는 최대n 가치.

예

다음 트리를 고려할 때 비용은 2.80이지만 이것이 최적의 결과는 아닙니다.

마디	깊이	개연성	기부
k ₁	1	0.15	0.30
k ₂	0	0.10	0.10
k ₃	2	0.05	0.15
k ₄	1	0.10	0.20
k ₅	2	0.20	0.60
d ₀	2	0.05	0.15
d ₁	2	0.10	0.30
d ₂	삼	0.05	0.20
d ₃	삼	0.05	0.20
d ₄	삼	0.05	0.20
d ₅	삼	0.10	0.40
Total			2.80

최적의 솔루션을 얻기 위해이 장에서 설명하는 알고리즘을 사용하여 다음 표가 생성됩니다.

다음 표에서 열 인덱스는 i 행 인덱스는 j.

이자형	1	2	삼	4	5	6
5	2.75	2.00	1.30	0.90	0.50	0.10
4	1.75	1.20	0.60	0.30	0.05
삼	1.25	0.70	0.25	0.05
2	0.90	0.40	0.05
1	0.45	0.10
0	0.05

w	1	2	삼	4	5	6
5	1.00	0.80	0.60	0.50	0.35	0.10
4	0.70	0.50	0.30	0.20	0.05
삼	0.55	0.35	0.15	0.05
2	0.45	0.25	0.05
1	0.30	0.10
0	0.05

뿌리	1	2	삼	4	5
5	2	4	5	5	5
4	2	2	4	4
삼	2	2	삼
2	1	2
1	1

이 테이블에서 최적의 트리를 형성 할 수 있습니다.

힙에는 여러 유형이 있지만이 장에서는 이진 힙에 대해 설명합니다. ㅏbinary heap완전한 이진 트리와 유사한 데이터 구조입니다. 힙 데이터 구조는 아래에 설명 된 순서 지정 속성을 따릅니다. 일반적으로 힙은 배열로 표시됩니다. 이 장에서 우리는H.

힙의 요소가 배열에 저장되므로 시작 인덱스를 다음과 같이 고려합니다. 1, 부모 노드의 위치 i^th 요소는 다음에서 찾을 수 있습니다. ⌊ i/2 ⌋. 왼쪽 자식과 오른쪽 자식i^th 노드가 위치에 있습니다. 2i 과 2i + 1.

바이너리 힙은 다음 중 하나로 더 분류 될 수 있습니다. max-heap 또는 min-heap 주문 속성을 기반으로합니다.

최대 힙

이 힙에서 노드의 키 값은 가장 높은 하위의 키 값보다 크거나 같습니다.

그 후, H[Parent(i)] ≥ H[i]

최소 힙

평균 힙에서 노드의 키 값은 가장 낮은 자식의 키 값보다 작거나 같습니다.

그 후, H[Parent(i)] ≤ H[i]

이 컨텍스트에서 Max-Heap과 관련된 기본 작업은 아래와 같습니다. 힙에서 요소를 삽입하고 삭제하려면 요소를 다시 정렬해야합니다. 그 후,Heapify 함수를 호출해야합니다.

배열 표현

완전한 이진 트리는 레벨 순서 순회를 사용하여 요소를 저장하는 배열로 나타낼 수 있습니다.

배열로 표현 될 힙 (아래 그림 참조)을 고려해 보겠습니다. H.

시작 색인을 다음과 같이 고려하십시오. 0, 레벨 순서 순회를 사용하면 요소가 다음과 같이 배열에 유지됩니다.

Index	0	1	2	삼	4	5	6	7	8	...
elements	70	30	50	12	20	35	25	4	8	...

이 컨텍스트에서 힙에 대한 작업은 Max-Heap과 관련하여 표현됩니다.

index에서 요소의 부모 인덱스를 찾으려면 i, 다음 알고리즘 Parent (numbers[], i) 사용.

Algorithm: Parent (numbers[], i) 
if i == 1 
   return NULL 
else 
   [i / 2]

인덱스에있는 요소의 왼쪽 자식 인덱스 i 다음 알고리즘을 사용하여 찾을 수 있습니다. Left-Child (numbers[], i).

Algorithm: Left-Child (numbers[], i) 
If 2 * i ≤ heapsize 
   return [2 * i] 
else 
   return NULL

인덱스에있는 요소의 오른쪽 자식 인덱스 i 다음 알고리즘을 사용하여 찾을 수 있습니다. Right-Child(numbers[], i).

Algorithm: Right-Child (numbers[], i) 
if 2 * i < heapsize 
   return [2 * i + 1] 
else 
   return NULL

힙에 요소를 삽입하려면 처음에 새 요소가 배열의 마지막 요소로 힙 끝에 추가됩니다.

이 요소를 삽입 한 후 힙 속성이 위반 될 수 있으므로 추가 된 요소를 부모와 비교하고 추가 된 요소를 한 수준 위로 이동하여 위치를 부모와 교체하여 힙 속성을 복구합니다. 이 과정을percolation up.

부모가 여과 요소보다 크거나 같을 때까지 비교가 반복됩니다.

Algorithm: Max-Heap-Insert (numbers[], key) 
heapsize = heapsize + 1 
numbers[heapsize] = -∞ 
i = heapsize 
numbers[i] = key 
while i > 1 and numbers[Parent(numbers[], i)] < numbers[i] 
   exchange(numbers[i], numbers[Parent(numbers[], i)]) 
   i = Parent (numbers[], i)

분석

처음에는 요소가 배열 끝에 추가됩니다. 힙 속성을 위반하면 요소가 부모와 교환됩니다. 나무의 높이는log n. 최고log n 여러 작업을 수행해야합니다.

따라서이 기능의 복잡성은 O(log n).

예

아래에 표시된 것처럼 새 요소 5를 추가해야하는 최대 힙을 고려해 보겠습니다.

처음에는이 배열 끝에 55 개가 추가됩니다.

삽입 후 힙 속성을 위반합니다. 따라서 요소는 부모와 교체해야합니다. 스왑 후 힙은 다음과 같습니다.

다시 말하지만, 요소는 힙의 속성을 위반합니다. 따라서 부모와 교체됩니다.

이제 멈춰야합니다.

Heapify 메서드는 왼쪽 및 오른쪽 하위 트리가있는 배열의 요소를 재정렬합니다. i^th 요소는 힙 속성을 따릅니다.

Algorithm: Max-Heapify(numbers[], i) 
leftchild := numbers[2i] 
rightchild := numbers [2i + 1] 
if leftchild ≤ numbers[].size and numbers[leftchild] > numbers[i] 
   largest := leftchild 
else 
   largest := i 
if rightchild ≤ numbers[].size and numbers[rightchild] > numbers[largest] 
   largest := rightchild 
if largest ≠ i 
   swap numbers[i] with numbers[largest] 
   Max-Heapify(numbers, largest)

제공된 배열이 힙 속성을 따르지 않는 경우 다음 알고리즘을 기반으로 힙이 빌드됩니다. Build-Max-Heap (numbers[]).

Algorithm: Build-Max-Heap(numbers[]) 
numbers[].size := numbers[].length 
fori = ⌊ numbers[].length/2 ⌋ to 1 by -1 
   Max-Heapify (numbers[], i)

Extract 메소드는 힙의 루트 요소를 추출하는 데 사용됩니다. 다음은 알고리즘입니다.

Algorithm: Heap-Extract-Max (numbers[]) 
max = numbers[1] 
numbers[1] = numbers[heapsize] 
heapsize = heapsize – 1 
Max-Heapify (numbers[], 1) 
return max

예

앞에서 논의한 동일한 예를 고려해 보겠습니다. 이제 우리는 요소를 추출하려고합니다. 이 메서드는 힙의 루트 요소를 반환합니다.

루트 요소를 삭제하면 마지막 요소가 루트 위치로 이동합니다.

이제 Heapify 함수가 호출됩니다. Heapify 후에 다음 힙이 생성됩니다.

버블 정렬은 필요한 경우 인접한 요소를 반복적으로 교환하여 작동하는 기본 정렬 알고리즘입니다. 교환이 필요하지 않은 경우 파일이 정렬됩니다.

이것은 모든 정렬 알고리즘 중에서 가장 간단한 기술입니다.

Algorithm: Sequential-Bubble-Sort (A) 
fori← 1 to length [A] do 
for j ← length [A] down-to i +1 do 
   if A[A] < A[j - 1] then 
      Exchange A[j] ↔ A[j-1]

이행

voidbubbleSort(int numbers[], intarray_size) { 
   inti, j, temp; 
   for (i = (array_size - 1); i >= 0; i--) 
   for (j = 1; j <= i; j++) 
      if (numbers[j - 1] > numbers[j]) { 
         temp = numbers[j-1]; 
         numbers[j - 1] = numbers[j]; 
         numbers[j] = temp; 
      } 
}

분석

여기서 비교 횟수는 다음과 같습니다.

1 + 2 + 3 +...+ (n - 1) = n(n - 1)/2 = O(n²)

분명히 그래프는 n² 거품 종류의 본질.

이 알고리즘에서 비교 횟수는 데이터 세트, 즉 제공된 입력 요소가 정렬 된 순서인지 역순인지 또는 무작위인지 여부와 관계가 없습니다.

메모리 요구 사항

위에 언급 된 알고리즘에서 버블 정렬에 추가 메모리가 필요하지 않음이 분명합니다.

예

Unsorted list:

5	2	1	4	삼	7	6

1 ^일의 반복 :

5 > 2 swap

2	5	1	4	삼	7	6

5 > 1 swap

2	1	5	4	삼	7	6

5 > 4 swap

2	1	4	5	삼	7	6

5 > 3 swap

2	1	4	삼	5	7	6

5 < 7 no swap

2	1	4	삼	5	7	6

7 > 6 swap

2	1	4	삼	5	6	7

2 ^차 반복 :

2 > 1 swap

1	2	4	삼	5	6	7

2 < 4 no swap

1	2	4	삼	5	6	7

4 > 3 swap

1	2	삼	4	5	6	7

4 < 5 no swap

1	2	삼	4	5	6	7

5 < 6 no swap

1	2	삼	4	5	6	7

3 ^번째 , 4 ^번째 , 5 ^번째 및 6 ^번째 반복 에는 변경이 없습니다 .

드디어,

the sorted list is

1	2	삼	4	5	6	7

삽입 정렬은 오름차순 또는 내림차순으로 숫자를 정렬하는 매우 간단한 방법입니다. 이 방법은 증분 방법을 따릅니다. 게임을 할 때 카드를 정렬하는 기술과 비교할 수 있습니다.

정렬해야하는 숫자는 다음과 같이 알려져 있습니다. keys. 다음은 삽입 정렬 방법의 알고리즘입니다.

Algorithm: Insertion-Sort(A) 
for j = 2 to A.length 
   key = A[j] 
   i = j – 1 
   while i > 0 and A[i] > key 
      A[i + 1] = A[i] 
      i = i -1 
   A[i + 1] = key

분석

이 알고리즘의 실행 시간은 주어진 입력에 따라 크게 달라집니다.

주어진 숫자가 정렬되면이 알고리즘은 O(n)시각. 주어진 숫자가 역순이면 알고리즘은 다음에서 실행됩니다.O(n²) 시각.

예

Unsorted list:

2	13	5	18	14

1^st iteration:

키 = a [2] = 13

a [1] = 2 <13

스왑, 스왑 없음

2	13	5	18	14

2^nd iteration:

키 = a [3] = 5

a [2] = 13> 5

5와 13 스왑

2	5	13	18	14

다음으로, a [1] = 2 <13

스왑, 스왑 없음

2	5	13	18	14

3^rd iteration:

키 = a [4] = 18

a [3] = 13 <18,

a [2] = 5 <18,

a [1] = 2 <18

스왑, 스왑 없음

2	5	13	18	14

4^th iteration:

키 = a [5] = 14

a [4] = 18> 14

18 및 14 스왑

2	5	13	14	18

다음으로, a [3] = 13 <14,

a [2] = 5 <14,

a [1] = 2 <14

그래서 스왑 없음

2	5	13	14	18

드디어,

the sorted list is

2	5	13	14	18

이러한 유형의 정렬을 Selection Sort반복적으로 요소를 정렬하여 작동합니다. 다음과 같이 작동합니다. 먼저 배열에서 가장 작은 요소를 찾아 첫 번째 위치의 요소와 교환 한 다음 두 번째로 작은 요소를 찾아 두 번째 위치의 요소와 교환하고 전체 배열이 될 때까지이 방식으로 계속합니다. 정렬.

Algorithm: Selection-Sort (A) 
fori ← 1 to n-1 do 
   min j ← i; 
   min x ← A[i] 
   for j ←i + 1 to n do 
      if A[j] < min x then 
         min j ← j 
         min x ← A[j] 
   A[min j] ← A [i] 
   A[i] ← min x

선택 정렬은 가장 간단한 정렬 기술 중 하나이며 작은 파일에 매우 적합합니다. 각 항목이 실제로 최대 한 번 이동하므로 매우 중요한 응용 프로그램이 있습니다.

섹션 정렬은 매우 큰 개체 (레코드)와 작은 키가있는 파일을 정렬하기 위해 선택하는 방법입니다. 배열이 이미 내림차순으로 정렬되어 있고 오름차순으로 정렬하려는 경우 최악의 경우가 발생합니다.

그럼에도 불구하고 선택 정렬 알고리즘에 필요한 시간은 정렬 할 배열의 원래 순서에 크게 민감하지 않습니다. A[j] < min x 모든 경우에 정확히 동일한 횟수로 실행됩니다.

선택 정렬은 배열의 정렬되지 않은 부분에서 최소 요소를 찾는 데 대부분의 시간을 소비합니다. 선택 정렬과 버블 정렬의 유사성을 명확하게 보여줍니다.

버블 정렬은 각 단계에서 남아있는 최대 요소를 선택하지만 배열의 정렬되지 않은 부분에 순서를 부여하는 데 약간의 노력을 낭비합니다.
선택 정렬은 최악의 경우와 평균적인 경우 모두 2 차적이며 추가 메모리가 필요하지 않습니다.

각각 i ...에서 1 ...에 n - 1, 하나의 교환이 있으며 n - i 비교, 그래서 총 n - 1 교환 및

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 비교.

이러한 관찰은 입력 데이터가 무엇이든 관계없이 유지됩니다.

최악의 경우 2 차가 될 수 있지만 평균적인 경우이 수량은 O(n log n). 그것은running time of Selection sort is quite insensitive to the input.

이행

Void Selection-Sort(int numbers[], int array_size) { 
   int i, j; 
   int min, temp;  
   for (i = 0; I < array_size-1; i++) { 
      min = i; 
      for (j = i+1; j < array_size; j++) 
         if (numbers[j] < numbers[min]) 
            min = j; 
      temp = numbers[i]; 
      numbers[i] = numbers[min]; 
      numbers[min] = temp; 
   } 
}

예

Unsorted list:

5	2	1	4	삼

1 ^일의 반복 :

최소 = 5

2 <5, 최소 = 2

1 <2, 최소 = 1

4> 1, 최소 = 1

3> 1, 최소 = 1

5와 1 스왑

1	2	5	4	삼

2 ^차 반복 :

최소 = 2

2 <5, 최소 = 2

2 <4, 최소 = 2

2 <3, 최소 = 2

스왑 없음

1	2	5	4	삼

세 ^번째 반복 :

최소 = 5

4 <5, 최소 = 4

3 <4, 최소 = 3

5와 3 스왑

1	2	삼	4	5

4 ^번째 반복 :

최소 = 4

4 <5, 최소 = 4

스왑 없음

1	2	삼	4	5

드디어,

the sorted list is

1	2	삼	4	5

분할 정복 원칙에 따라 사용됩니다. 빠른 정렬은 구현하기 어렵지 않기 때문에 많은 상황에서 선택되는 알고리즘입니다. 좋은 범용 정렬이며 실행 중에 상대적으로 적은 리소스를 소비합니다.

장점

작은 보조 스택 만 사용하므로 제자리에 있습니다.
그것은 필요합니다 n (log n) 정렬 시간 n 항목.
내부 루프가 매우 짧습니다.
이 알고리즘은 철저한 수학적 분석을 거쳐 성능 문제에 대해 매우 정확한 진술을 할 수 있습니다.

단점

재귀 적입니다. 특히 재귀를 사용할 수없는 경우 구현이 매우 복잡합니다.
최악의 경우 2 차 (즉, n2) 시간이 필요합니다.
그것은 깨지기 쉽습니다. 즉, 구현의 단순한 실수가 눈에 띄지 않게되어 성능이 저하 될 수 있습니다.

빠른 정렬은 주어진 배열을 분할하여 작동합니다. A[p ... r] 비어 있지 않은 두 개의 하위 배열로 A[p ... q] 과 A[q+1 ... r] 모든 키에 A[p ... q] 모든 키보다 작거나 같음 A[q+1 ... r].

그런 다음 두 개의 하위 배열이 빠른 정렬에 대한 재귀 호출을 통해 정렬됩니다. 파티션의 정확한 위치는 주어진 배열과 인덱스에 따라 다릅니다.q 분할 절차의 일부로 계산됩니다.

Algorithm: Quick-Sort (A, p, r) 
if p < r then 
   q Partition (A, p, r) 
   Quick-Sort (A, p, q) 
   Quick-Sort (A, q + r, r)

전체 배열을 정렬하려면 초기 호출은 Quick-Sort (A, 1, length[A])

첫 번째 단계로 빠른 정렬은 배열의 항목 중 하나를 선택하여 피벗으로 정렬합니다. 그런 다음 어레이는 피벗의 양쪽에서 분할됩니다. 피벗보다 작거나 같은 요소는 왼쪽으로 이동하고 피벗보다 크거나 같은 요소는 오른쪽으로 이동합니다.

어레이 분할

파티셔닝 절차는 하위 배열을 제자리에 다시 정렬합니다.

Function: Partition (A, p, r) 
x ← A[p] 
i ← p-1 
j ← r+1 
while TRUE do 
   Repeat j ← j - 1 
   until A[j] ≤ x  
   Repeat i← i+1 
   until A[i] ≥ x  
   if i < j then  
      exchange A[i] ↔ A[j] 
   else  
      return j

분석

Quick-Sort 알고리즘의 최악의 복잡성은 다음과 같습니다. O(n²). 그러나이 기술을 사용하면 평균적인 경우 일반적으로 출력을O(n log n) 시각.

Radix sort많은 사람들이 많은 이름 목록을 알파벳으로 분류 할 때 직관적으로 사용하는 작은 방법입니다. 구체적으로 이름 목록은 각 이름의 첫 글자에 따라 먼저 정렬됩니다. 즉, 이름이 26 개의 클래스로 정렬됩니다.

직관적으로 가장 중요한 숫자를 기준으로 숫자를 정렬 할 수 있습니다. 그러나 기수 정렬은 최하위 자릿수부터 정렬하여 직관적으로 작동하지 않습니다. 첫 번째 패스에서 모든 숫자는 최하위 숫자로 정렬되고 배열로 결합됩니다. 그런 다음 두 번째 패스에서 전체 숫자가 두 번째 최하위 자릿수에서 다시 정렬되고 배열로 결합됩니다.

Algorithm: Radix-Sort (list, n) 
shift = 1 
for loop = 1 to keysize do 
   for entry = 1 to n do 
      bucketnumber = (list[entry].key / shift) mod 10 
      append (bucket[bucketnumber], list[entry]) 
   list = combinebuckets() 
   shift = shift * 10

분석

각 키는 가장 긴 키의 각 숫자 (또는 키가 알파벳 인 경우 문자)에 대해 한 번 확인됩니다. 따라서 가장 긴 키에m 숫자가 있고 n 키, 기수 정렬에는 순서가 있습니다. O(m.n).

그러나이 두 값을 살펴보면 키의 수에 비해 키의 크기가 상대적으로 작습니다. 예를 들어 6 자리 키가 있다면 백만 개의 다른 레코드를 가질 수 있습니다.

여기서 우리는 키의 크기가 중요하지 않으며이 알고리즘은 선형 복잡도입니다. O(n).

예

다음 예는 7 개의 3 자리 숫자에서 기수 정렬이 작동하는 방법을 보여줍니다.

입력	1 ^차 패스	2 ^차 패스	3 ^차 패스
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

위의 예에서 첫 번째 열은 입력입니다. 나머지 열은 증가하는 유효 숫자 위치에 대한 연속 정렬 후 목록을 표시합니다. 기수 정렬 코드는 배열의 각 요소가A 의 n 요소는 d 숫자, 여기서 숫자 1 최하위 숫자이고 d 가장 높은 순서의 숫자입니다.

수업을 이해하려면 P 과 NP, 먼저 계산 모델을 알아야합니다. 따라서이 장에서는 두 가지 중요한 계산 모델에 대해 설명합니다.

결정 론적 계산과 클래스 P

결정 론적 튜링 머신

이러한 모델 중 하나는 결정 론적 단일 테이프 튜링 머신입니다. 이 기계는 유한 상태 제어, 읽기-쓰기 헤드 및 무한 시퀀스의 양방향 테이프로 구성됩니다.

다음은 결정 론적 단일 테이프 튜링 머신의 개략도입니다.

결정 론적 튜링 머신을위한 프로그램은 다음 정보를 지정합니다.

유한 테이프 기호 세트 (입력 기호 및 공백 기호)
유한 한 상태 집합
전환 기능

알고리즘 분석에서 결정 론적 하나의 테이프 튜링 머신에 의해 다항식 시간에 문제를 해결할 수있는 경우 문제는 P 클래스에 속합니다.

비 결정적 계산과 클래스 NP

비 결정적 튜링 머신

계산 문제를 해결하기위한 또 다른 모델은 비 결정적 튜링 머신 (NDTM)입니다. NDTM의 구조는 DTM과 유사하지만 여기에는 하나의 쓰기 전용 헤드와 관련된 추측 모듈이라는 추가 모듈이 하나 있습니다.

다음은 회로도입니다.

비 결정적 튜링 머신으로 다항식 시간에 문제를 해결할 수있는 경우 문제는 NP 클래스에 속합니다.

무 방향 그래프에서 clique주어진 그래프의 완전한 하위 그래프입니다. 완전한 하위 그래프는이 하위 그래프의 모든 정점이이 하위 그래프의 다른 모든 정점에 연결되어 있음을 의미합니다.

Max-Clique 문제는 그래프의 최대 clique를 찾는 계산 문제입니다. Max clique는 많은 실제 문제에서 사용됩니다.

정점이 사람들의 프로필을 나타내고 가장자리가 서로 아는 사람을 그래프로 나타내는 소셜 네트워킹 응용 프로그램을 고려해 보겠습니다. 이 그래프에서 파벌은 서로를 아는 사람들의 하위 집합을 나타냅니다.

최대 파벌을 찾기 위해 모든 하위 집합을 체계적으로 검사 할 수 있지만 이러한 종류의 무차별 대입 검색은 수십 개 이상의 정점으로 구성된 네트워크에 너무 많은 시간이 소요됩니다.

Algorithm: Max-Clique (G, n, k) 
S := Φ 
for i = 1 to k do 
   t := choice (1…n)  
   if t Є S then 
      return failure 
   S := S ∪ t  
for all pairs (i, j) such that i Є S and j Є S and i ≠ j do 
   if (i, j) is not a edge of the graph then  
      return failure 
return success

분석

Max-Clique 문제는 비 결정적 알고리즘입니다. 이 알고리즘에서 먼저 우리는k 별개의 정점을 찾은 다음 이러한 정점이 완전한 그래프를 형성하는지 테스트하려고합니다.

이 문제를 해결하기위한 다항식 시간 결정 알고리즘은 없습니다. 이 문제는 NP-Complete입니다.

예

다음 그래프를 살펴보십시오. 여기서 정점 2, 3, 4 및 6을 포함하는 하위 그래프는 완전한 그래프를 형성합니다. 따라서이 하위 그래프는clique. 제공된 그래프의 최대 전체 하위 그래프이므로4-Clique.

무 방향 그래프의 정점 커버 G = (V, E) 정점의 하위 집합입니다. V^' ⊆ V 그런 경우 가장자리 (u, v) 의 가장자리입니다 G, 다음 중 하나 u 에 V 또는 v 에 V^' 아니면 둘다.

주어진 무 방향 그래프에서 최대 크기의 정점 커버를 찾습니다. 이 최적의 vertexcover는 NP-complete 문제의 최적화 버전입니다. 그러나 최적에 가까운 정점 커버를 찾는 것은 그리 어렵지 않습니다.

APPROX-VERTEX_COVER (G: Graph) c ← { } E^' ← E[G] 
while E^' is not empty do 
   Let (u, v) be an arbitrary edge of E^' c ← c U {u, v} 
   Remove from E^' every edge incident on either u or v 
return c

예

주어진 그래프의 가장자리 집합은 다음과 같습니다.

{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,8),(3,5),(8,5)}

이제 임의의 가장자리 (1,6)를 선택하여 시작합니다. 정점 1 또는 6에 입사하는 모든 모서리를 제거하고 덮기 위해 모서리 (1,6)을 추가합니다.

다음 단계에서는 무작위로 다른 모서리 (2,3)를 선택했습니다.

이제 다른 모서리 (4,7)를 선택합니다.

다른 모서리 (8,5)를 선택합니다.

따라서이 그래프의 정점 커버는 {1,2,4,5}입니다.

분석

이 알고리즘의 실행 시간이 O(V + E), 인접 목록을 사용하여 E^'.

컴퓨터 과학에서는 일부 값을 최대화하거나 최소화하는 것이 목적인 경우 많은 문제가 해결되지만 다른 문제에서는 해결책이 있는지 여부를 찾으려고합니다. 따라서 문제는 다음과 같이 분류 할 수 있습니다.

최적화 문제

최적화 문제는 목표가 일부 값을 최대화하거나 최소화하는 것입니다. 예를 들면

주어진 그래프를 색칠하는 데 필요한 최소 색상 수 찾기.
그래프에서 두 꼭지점 사이의 최단 경로 찾기.

결정 문제

대답이 예 또는 아니오 인 많은 문제가 있습니다. 이러한 유형의 문제는 decision problems. 예를 들면

주어진 그래프를 4 색으로 만 색칠 할 수 있는지 여부.
그래프에서 Hamiltonian주기를 찾는 것은 결정 문제가 아니지만 그래프를 확인하는 것은 Hamiltonian인지 아닌지 결정 문제입니다.

언어는 무엇입니까?

모든 결정 문제에는 예 또는 아니오의 두 가지 대답 만있을 수 있습니다. 따라서 의사 결정 문제는 특정 입력에 대해 '예'라고 대답하면 언어에 속할 수 있습니다. 언어는 대답이 예인 입력의 총합입니다. 이전 장에서 논의 된 대부분의 알고리즘은polynomial time algorithms.

입력 크기 n, 알고리즘의 최악의 경우 시간 복잡성이 O(n^k), 어디 k 상수이고 알고리즘은 다항식 시간 알고리즘입니다.

Matrix Chain Multiplication, Single Source Shortest Path, All Pair Shortest Path, Minimum Spanning Tree 등과 같은 알고리즘은 다항식 시간으로 실행됩니다. 그러나 출장 영업 사원, 최적의 그래프 색상 지정, 해밀턴 사이클, 그래프에서 가장 긴 경로 찾기, 다항식 시간 알고리즘이 알려지지 않은 부울 공식 충족과 같은 많은 문제가 있습니다. 이러한 문제는 다음과 같은 흥미로운 종류의 문제에 속합니다.NP-Complete 상태를 알 수없는 문제.

이 맥락에서 우리는 다음과 같이 문제를 분류 할 수 있습니다.

P- 클래스

클래스 P는 다항식 시간에 풀 수있는 문제로 구성됩니다. 즉, 이러한 문제는 시간 내에 해결 될 수 있습니다. O(n^k) 최악의 경우 k 일정합니다.

이러한 문제를 tractable, 다른 사람은 intractable or superpolynomial.

공식적으로 알고리즘은 다항식 시간 알고리즘입니다. p(n) such that the algorithm can solve any instance of size n in a time O(p(n)).

Problem requiring Ω(n⁵⁰) time to solve are essentially intractable for large n. Most known polynomial time algorithm run in time O(n^k) for fairly low value of k.

The advantages in considering the class of polynomial-time algorithms is that all reasonable deterministic single processor model of computation can be simulated on each other with at most a polynomial slow-d

NP-Class

The class NP consists of those problems that are verifiable in polynomial time. NP is the class of decision problems for which it is easy to check the correctness of a claimed answer, with the aid of a little extra information. Hence, we aren’t asking for a way to find a solution, but only to verify that an alleged solution really is correct.

Every problem in this class can be solved in exponential time using exhaustive search.

P versus NP

Every decision problem that is solvable by a deterministic polynomial time algorithm is also solvable by a polynomial time non-deterministic algorithm.

All problems in P can be solved with polynomial time algorithms, whereas all problems in NP - P are intractable.

It is not known whether P = NP. However, many problems are known in NP with the property that if they belong to P, then it can be proved that P = NP.

If P ≠ NP, there are problems in NP that are neither in P nor in NP-Complete.

The problem belongs to class P if it’s easy to find a solution for the problem. The problem belongs to NP, if it’s easy to check a solution that may have been very tedious to find.

Stephen Cook presented four theorems in his paper “The Complexity of Theorem Proving Procedures”. These theorems are stated below. We do understand that many unknown terms are being used in this chapter, but we don’t have any scope to discuss everything in detail.

Following are the four theorems by Stephen Cook −

Theorem-1

If a set S of strings is accepted by some non-deterministic Turing machine within polynomial time, then S is P-reducible to {DNF tautologies}.

Theorem-2

The following sets are P-reducible to each other in pairs (and hence each has the same polynomial degree of difficulty): {tautologies}, {DNF tautologies}, D3, {sub-graph pairs}.

Theorem-3

For any T_Q(k) of type Q, $\mathbf{\frac{T_{Q}(k)}{\frac{\sqrt{k}}{(log\:k)^2}}}$ is unbounded
There is a T_Q(k) of type Q such that $T_{Q}(k)\leqslant 2^{k(log\:k)^2}$

Theorem-4

If the set S of strings is accepted by a non-deterministic machine within time T(n) = 2ⁿ, and if T_Q(k) is an honest (i.e. real-time countable) function of type Q, then there is a constant K, so S can be recognized by a deterministic machine within time T_Q(K8ⁿ).

First, he emphasized the significance of polynomial time reducibility. It means that if we have a polynomial time reduction from one problem to another, this ensures that any polynomial time algorithm from the second problem can be converted into a corresponding polynomial time algorithm for the first problem.
Second, he focused attention on the class NP of decision problems that can be solved in polynomial time by a non-deterministic computer. Most of the intractable problems belong to this class, NP.
Third, he proved that one particular problem in NP has the property that every other problem in NP can be polynomially reduced to it. If the satisfiability problem can be solved with a polynomial time algorithm, then every problem in NP can also be solved in polynomial time. If any problem in NP is intractable, then satisfiability problem must be intractable. Thus, satisfiability problem is the hardest problem in NP.
Fourth, Cook suggested that other problems in NP might share with the satisfiability problem this property of being the hardest member of NP.

A problem is in the class NPC if it is in NP and is as hard as any problem in NP. A problem is NP-hard if all problems in NP are polynomial time reducible to it, even though it may not be in NP itself.

If a polynomial time algorithm exists for any of these problems, all problems in NP would be polynomial time solvable. These problems are called NP-complete. The phenomenon of NP-completeness is important for both theoretical and practical reasons.

Definition of NP-Completeness

A language B is NP-complete if it satisfies two conditions

B is in NP
Every A in NP is polynomial time reducible to B.

If a language satisfies the second property, but not necessarily the first one, the language B is known as NP-Hard. Informally, a search problem B is NP-Hard if there exists some NP-Complete problem A that Turing reduces to B.

The problem in NP-Hard cannot be solved in polynomial time, until P = NP. If a problem is proved to be NPC, there is no need to waste time on trying to find an efficient algorithm for it. Instead, we can focus on design approximation algorithm.

NP-Complete Problems

Following are some NP-Complete problems, for which no polynomial time algorithm is known.

Determining whether a graph has a Hamiltonian cycle
Determining whether a Boolean formula is satisfiable, etc.

NP-Hard Problems

The following problems are NP-Hard

The circuit-satisfiability problem
Set Cover
Vertex Cover
Travelling Salesman Problem

In this context, now we will discuss TSP is NP-Complete

TSP is NP-Complete

The traveling salesman problem consists of a salesman and a set of cities. The salesman has to visit each one of the cities starting from a certain one and returning to the same city. The challenge of the problem is that the traveling salesman wants to minimize the total length of the trip

Proof

To prove TSP is NP-Complete, first we have to prove that TSP belongs to NP. In TSP, we find a tour and check that the tour contains each vertex once. Then the total cost of the edges of the tour is calculated. Finally, we check if the cost is minimum. This can be completed in polynomial time. Thus TSP belongs to NP.

Secondly, we have to prove that TSP is NP-hard. To prove this, one way is to show that Hamiltonian cycle ≤_p TSP (as we know that the Hamiltonian cycle problem is NPcomplete).

Assume G = (V, E) to be an instance of Hamiltonian cycle.

Hence, an instance of TSP is constructed. We create the complete graph G^' = (V, E^'), where

$$E^{'}=\lbrace(i, j)\colon i, j \in V \:\:and\:i\neq j$$

Thus, the cost function is defined as follows −

$$t(i,j)=\begin{cases}0 & if\: (i, j)\: \in E\\1 & otherwise\end{cases}$$

Now, suppose that a Hamiltonian cycle h exists in G. It is clear that the cost of each edge in h is 0 in G^' as each edge belongs to E. Therefore, h has a cost of 0 in G^'. Thus, if graph G has a Hamiltonian cycle, then graph G^' has a tour of 0 cost.

Conversely, we assume that G^' has a tour h^' of cost at most 0. The cost of edges in E^' are 0 and 1 by definition. Hence, each edge must have a cost of 0 as the cost of h^' is 0. We therefore conclude that h^' contains only edges in E.

We have thus proven that G has a Hamiltonian cycle, if and only if G^' has a tour of cost at most 0. TSP is NP-complete.

The algorithms discussed in the previous chapters run systematically. To achieve the goal, one or more previously explored paths toward the solution need to be stored to find the optimal solution.

For many problems, the path to the goal is irrelevant. For example, in N-Queens problem, we don’t need to care about the final configuration of the queens as well as in which order the queens are added.

Hill Climbing

Hill Climbing is a technique to solve certain optimization problems. In this technique, we start with a sub-optimal solution and the solution is improved repeatedly until some condition is maximized.

The idea of starting with a sub-optimal solution is compared to starting from the base of the hill, improving the solution is compared to walking up the hill, and finally maximizing some condition is compared to reaching the top of the hill.

Hence, the hill climbing technique can be considered as the following phases −

Constructing a sub-optimal solution obeying the constraints of the problem
Improving the solution step-by-step
Improving the solution until no more improvement is possible

Hill Climbing technique is mainly used for solving computationally hard problems. It looks only at the current state and immediate future state. Hence, this technique is memory efficient as it does not maintain a search tree.

Algorithm: Hill Climbing 
Evaluate the initial state. 
Loop until a solution is found or there are no new operators left to be applied: 
   - Select and apply a new operator 
   - Evaluate the new state: 
      goal -→ quit 
      better than current state -→ new current state

Iterative Improvement

In iterative improvement method, the optimal solution is achieved by making progress towards an optimal solution in every iteration. However, this technique may encounter local maxima. In this situation, there is no nearby state for a better solution.

This problem can be avoided by different methods. One of these methods is simulated annealing.

Random Restart

This is another method of solving the problem of local optima. This technique conducts a series of searches. Every time, it starts from a randomly generated initial state. Hence, optima or nearly optimal solution can be obtained comparing the solutions of searches performed.

Problems of Hill Climbing Technique

Local Maxima

If the heuristic is not convex, Hill Climbing may converge to local maxima, instead of global maxima.

Ridges and Alleys

If the target function creates a narrow ridge, then the climber can only ascend the ridge or descend the alley by zig-zagging. In this scenario, the climber needs to take very small steps requiring more time to reach the goal.

Plateau

A plateau is encountered when the search space is flat or sufficiently flat that the value returned by the target function is indistinguishable from the value returned for nearby regions, due to the precision used by the machine to represent its value.

Complexity of Hill Climbing Technique

This technique does not suffer from space related issues, as it looks only at the current state. Previously explored paths are not stored.

For most of the problems in Random-restart Hill Climbing technique, an optimal solution can be achieved in polynomial time. However, for NP-Complete problems, computational time can be exponential based on the number of local maxima.

Applications of Hill Climbing Technique

Hill Climbing technique can be used to solve many problems, where the current state allows for an accurate evaluation function, such as Network-Flow, Travelling Salesman problem, 8-Queens problem, Integrated Circuit design, etc.

Hill Climbing is used in inductive learning methods too. This technique is used in robotics for coordination among multiple robots in a team. There are many other problems where this technique is used.

Example

This technique can be applied to solve the travelling salesman problem. First an initial solution is determined that visits all the cities exactly once. Hence, this initial solution is not optimal in most of the cases. Even this solution can be very poor. The Hill Climbing algorithm starts with such an initial solution and makes improvements to it in an iterative way. Eventually, a much shorter route is likely to be obtained.

꼭지점	머리 글자	Step1 V ₁	2 단계 V ₃	Step3 V ₂	₄ 단계 V ₄	5 단계 V ₍₅₎	Step6 V ₇	Step7 V ₈	Step8 V ₆
1	0	0	0	0	0	0	0	0	0
2	∞	5	4	4	4	4	4	4	4
삼	∞	2	2	2	2	2	2	2	2
4	∞	∞	∞	7	7	7	7	7	7
5	∞	∞	∞	11	9	9	9	9	9
6	∞	∞	∞	∞	∞	17	17	16	16
7	∞	∞	11	11	11	11	11	11	11
8	∞	∞	∞	∞	∞	16	13	13	13
9	∞	∞	∞	∞	∞	∞	∞	∞	20

입력	1 ^차 패스	2 ^차 패스	3 ^차 패스
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

꼭지점	머리 글자	Step1 V ₁	2 단계 V ₃	Step3 V ₂	₄ 단계 V ₄	5 단계 V ₍₅₎	Step6 V ₇	Step7 V ₈	Step8 V ₆
1	0	0	0	0	0	0	0	0	0
2	∞	5	4	4	4	4	4	4	4
삼	∞	2	2	2	2	2	2	2	2
4	∞	∞	∞	7	7	7	7	7	7
5	∞	∞	∞	11	9	9	9	9	9
6	∞	∞	∞	∞	∞	17	17	16	16
7	∞	∞	11	11	11	11	11	11	11
8	∞	∞	∞	∞	∞	16	13	13	13
9	∞	∞	∞	∞	∞	∞	∞	∞	20

입력	1 ^차 패스	2 ^차 패스	3 ^차 패스
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

꼭지점	머리 글자	Step1 V ₁	2 단계 V ₃	Step3 V ₂	₄ 단계 V ₄	5 단계 V ₍₅₎	Step6 V ₇	Step7 V ₈	Step8 V ₆
1	0	0	0	0	0	0	0	0	0
2	∞	5	4	4	4	4	4	4	4
삼	∞	2	2	2	2	2	2	2	2
4	∞	∞	∞	7	7	7	7	7	7
5	∞	∞	∞	11	9	9	9	9	9
6	∞	∞	∞	∞	∞	17	17	16	16
7	∞	∞	11	11	11	11	11	11	11
8	∞	∞	∞	∞	∞	16	13	13	13
9	∞	∞	∞	∞	∞	∞	∞	∞	20

입력	1 ^차 패스	2 ^차 패스	3 ^차 패스
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839