출처: http://sdolnote.tistory.com/entry/LinearityNonlinearityFunction


공과대학을 입학하고 수업을 들을 때, 
가장 많이 듣는 말 중 하나는 선형(Linearity)과 비선형(Non-linearity)일 것이다.

선형이라는 것은 직선이 아닐 지라도 직선의 특징을 가지고 있다는 것이고
여기서 말하는 직선의 특징은
중첩의 원리(principle of superposition
)또는 선형성의 원리(
Linearity principle)이다.

이런 선형성이라는 말은 함수에 적용이 될 수도 있고,
선형으로 결합되어있는 어떤 것에도 적용이 될 수 있다.

여기서 선형으로 결합되어 있다는 어떤 것중에 대표적인 예는 선형 상미분방정식일 것이다.
이것에 대해서는 먼저 선형함수에 대해서 설명을 하고 이후의 포스팅에서 설명하도록 하겠다.



먼저 아래와 같은 것이 선형함수이다.



위에서 적힌 것처럼 어떤 선형함수에 6을 집어넣었을 때의 함수값을
같은 함수에 1과 5을 넣었을 때의 함수값을 합한 값으로 알 수 있다.

위 선형함수의 대표적인 예로는 y=3x값은 것이 있고, 실제로 그래프를 그려보면 직선의 형태를 가진다.

이를 중첩의 원리라고 하며, 이는 선형함수를 예측가능하게 만들어 준다.

여기서 예측이 가능하다는 말은 매우 중요한 말로... 기억해두는 것이 좋다.



그리고 아래가 비선형함수의 예일 것이다.


위에서 보는 것처럼 비선형함수는 중첩의 원리가 성립하지 않으므로,
함수의 수식이 알려지지 않았을 때, 함수값을 예측하기가 매우 어렵다는 특징이 있다.

별로 어려운 함수는 아니지만, 비선형함수의 예 중 하나는 y=3x2이다.

이것도 역시 그래프를 그려보면, 직선이 아니란 것을 알 수 있을 것이다.

출처: http://darkpgmr.tistory.com/133


기본적인 함수 최적화(optimization) 방법 중 하나인 gradient descent 방법에 관한 글입니다.


Gradient descent 방법은 미분의 개념을 최적화 문제에 적용한 대표적 방법 중 하나로서 함수의 local minimum을 찾는 방법 중 하나입니다. Gradient descent 방법을 다른 말로 steepest descent 방법이라고도 부릅니다.



1. Gradient descent 방법의 직관적 이해


자신이 한치앞도 잘 안보이는 울창한 밀림에 있을 때 산 정상으로 가기 위한 방법은 간단합니다. 비록 실제 산 정상이 어디에 있는지는 모르지만 현재 위치에서 가장 경사가 가파른 방향으로 산을 오르다 보면 언젠가는 산 정상에 다다르게 될 것입니다.


또는 이와 반대로 깊은 골짜기를 찾고 싶을 때에는 가장 가파른 내리막 방향으로 산을 내려가면 될 것입니다.


이와 같이 어떤 함수의 극대점을 찾기 위해 현재 위치에서의 gradient 방향으로 이동해 가는 방법을 gradient ascent 방법, 극소점을 찾기 위해 gradient 반대 방향으로 이동해 가는 방법을 gradient descent 방법이라 부릅니다.



2. Gradient(그레디언트)


(gradient의 개념에 대해서는 Gradient, Jacobian 행렬, Hessian 행렬, Laplacian 글에서 설명한 바 있지만 설명의 연속성을 위해서 이곳에 다시 관련 내용을 적습니다)


어떤 다변수 함수 f(x1,x2,...,xn)이 있을 때, f의 그레디언트(gradient)는


 --- (1)


와 같이 정의됩니다. 즉, 그레디언트(gradient)는 위 식과 같이 각 변수로의 일차 편미분 값으로 구성되는 벡터입니다. 그리고 이 벡터는 f의 값이 가장 가파르게 증가하는 방향을 나타냅니다. 또한 벡터의 크기는 그 증가의 가파른 정도(기울기)를 나타냅니다.


예를 들어, f(x,y) = x2 + y2의 그레디언트(gradient)를 구해보면


 --- (2)


이므로, (1,1)에서 f값이 최대로 증가하는 방향은 (2,2), 그 기울기는 ∥(2,2)∥= sqrt(8) 입니다.


<그림 1> f(x,y) = x2 + y2 그래프


또한 반대로 그레디언트(gradient)에 음수를 취하면 즉, -▽f는 f값이 가장 가파르게 감소하는 방향을 나타내게 됩니다.


이러한 그레디언트의 특성은 어떤 함수를 지역적으로 선형근사(linear approximation)하거나 혹은 함수의 극점(최대값, 최소값 지점)을 찾는 용도로 활용될 수 있습니다.



3. Gradient descent 방법


최적화 알고리즘 중 하나로 널리 알려진 gradient descent 방법은 이러한 그레디언트의 특성을 이용하여 어떤 비용함수의 값을 최소화시키기 위한 파라미터 값을 아래와 같이 점진적으로 찾는 방법입니다.


 --- (3)


즉, 어떤 초기값 x0 = (x10,...,xn0)부터 시작하여 위 식에 따라 gradient 반대 방향으로 x를 조금씩 이동시키면 f(x)가 극소가 되는 x를 찾을 수 있다는 방법이 gradient descent 방법입니다.


☞ 만일 함수의 극소점이 아니라 극대점을 찾는 것이 목적이라면 식 (3) 대신에 아래의 식 (4)를 이용하여 x를 업데이트합니다 (gradient ascent 방법)


 --- (4)


<그림 2> gradient descent 방법 (그림출처: 위키피디아)


식 (3)에서 λ는 알고리즘의 수렴속도를 조절하는 파라미터로서 step size 또는 learning rate라 불립니다.


Gradient descent 방법의 문제점은 쉽게 생각할 수 있듯이 local minimum에 빠지는 것입니다. 즉, 이쪽이 산 정상인줄 알고 열심히 올라갔더니 막상 여기는 작은 언덕 정도이고 바로 옆에 훨씬 높은 산이 있는 경우입니다.


Gradient descent 방법의 또 하나의 문제점은 해에 근접할수록 |∇f|가 0에 가까워지기 때문에 수렴속도가 느려진다는 것입니다. 그렇다고 수렴속도를 조절하는 step size 파라미터 λ를 너무 크게 하면 알고리즘이 발산할 수 있는 문제점이 있습니다 (step size를 자동으로 adaptive하게 조절하는 방법도 있는 것 같습니다).



4. Gradient descent 방법의 이해와 활용


Gradient descent 방법에 대해서는 그 기본적인 개념만 이해하고 있으면 된다고 생각합니다. 그 핵심은 함수의 극대값 또는 극소값을 구하기 위해 현재 위치에서 함수값의 변화가 가장 큰 방향으로 이동한다는 것이므로 함수값의 변화가 가장 큰 방향을 구할 수만 있다면 다양한 문제에 똑같은 개념을 적용할 수 있습니다.


[일변수 스칼라 함수의 극대, 극소 구하기]

즉, 다변수 스칼라 함수(scalar-valued function of multiple variables)의 경우에는 gradient(그레디언트)를 이용하여 최대 증가 방향을 찾았지만 일변수 함수의 경우에는 통상적인 일차 미분값 f'(x)을 이용하면 될 것입니다. 예를 들어, f(x) = x2 + 3x + 1가 극소가 되는 점 및 극소값을 구하고 싶다면 식을 다음과 같이 세울 수 있습니다.


 --- (5)


[비선형 연립방정식의 풀이]

선형연립방정식으로 주어지는 Least Square 문제는 [선형대수학 #5] 선형연립방정식 풀이 글에서 설명한 바와 같이 SVD나 Pseudo-inverse를 이용하여 계산할 수 있습니다. 그리고 비선형연립방정식으로 주어지는 Least Square 문제는 뉴턴법/뉴턴-랩슨법의 이해와 활용(Newton's method) 글에서 설명한 Gauss-Newton 법으로 풀 수 있습니다. 여기서는 비선형연립방정식으로 주어지는 Least Square 문제를 gradient descent 방법으로 푸는 방법에 대해 살펴보겠습니다.


 --- (6)


식 (6)을 동시에 만족시키는 x = (x1,...,xn)을 구하는 문제는 결국 아래의 E를 최소화시키는 x를 구하는 LS(Least Square) 문제로 볼 수 있습니다.


 --- (7)


단, F = [f1 ... fm]T는 F:Rn→Rm인 다변수 벡터 함수.


어떤 초기값(식 (7)의 E를 극소로 만드는 x에 대한 초기 추정값) x0 = (x10,...,xn0)부터 시작하여 아래와 같은 gradient descent 탐색을 반복하면 E의 극소점을 근사적으로 찾을 수 있습니다.


 --- (8)


그런데 ▽E를 직접 구하여 식 (8)을 적용해도 되지만, E = FTF 로부터 ▽E = 2JFTF 이므로 아래 식과 같이 F의 Jacobian인 JF를 이용하여 해를 탐색해도 됩니다.


 --- (9)



5. 뉴턴 방법과 비교


Newton 방법은 뉴턴법/뉴턴-랩슨법의 이해와 활용(Newton's method) 글에서 설명한 바 있습니다만, 방정식(f = 0)의 해를 점진적으로 찾는 방법입니다. 즉, gradient descent 방법은 함수의 극대, 극소를 찾는 방법이고 Newton 방법은 함수값이 0이 되는 해를 찾는 방법입니다. 하지만 그 내부의 원리는 거의 유사하며(일차미분의 원리가 사용됨) 함수 f의 극대, 극소를 구하기 위해 gradient descent 방법을 직접 적용해도 되지만, f가 극대, 극소인 점은 f' = 0인 점이기도 하므로 뉴턴법으로 f' = 0인 점을 구해도 됩니다.


정리해 보면, 똑같은 함수 최적화 문제를 gradient descent 방법으로도 풀 수 있고, 뉴텁법(Newton's method)이나 가우스-뉴턴법(Gauss-Newton method)으로도 풀 수 있음을 알수 있습니다. 어떤 방법이 더 효율적인지는 저도 잘 모릅니다. 다만, 한가지 gradient descent 방식과 가우스-뉴턴법의 차이를 살펴보면 gradient descent 방법은 step size 파리미터 λ가 필요한 반면에 뉴턴법(뉴턴-랩슨법)이나 가우스-뉴턴법의 경우는 step size 파라미터가 필요 없다는 점입니다. 그 이유는 뉴턴법 계열에서는 현재의 함수값과 미분값(기울기)으로부터 step size를 자동으로 결정하기 때문입니다. 또한, 뉴턴법 또는 가우스-뉴턴법은 해를 찾는 수렴속도가 빠르고 해 근처에서 수렴속도가 급격히 느려지는 문제점도 없습니다. 따라서, 개인적인 생각으로는 (확실치는 않지만) 함수 최적화 문제에 있어서 gradient descent 방법보다는 뉴턴법 계열이 좀더 효율적이지 않나 생각됩니다. 하지만 뉴턴법으로는 f'(x) = 0인 x를 구하기 때문에 극대, 극소를 구분하여 찾을 수 없고, 또한  f'(x) = 0이라 해서 반드시 f가 해당 지점에서 극점인 것은 아니므로 Hessian 테스트 등과 결합하여 사용해야 할 것입니다.


☞ Hessian 테스트는 f'(x)=0인 지점에서 Hessian 행렬의 고유값들을 구한 후 고유값들의 부호를 조사하여 극대, 극소 여부를 판별하는 테스트임. 자세한 내용은 Gradient, Jacobian 행렬, Hessian 행렬, Laplacian 글을 참조하기 바랍니다.

출처:http://fermium.tistory.com/833


"경사하강법"이란 함수의 기울기로 최소값을 찾아내는 알고리즘으로,

뉴럴네트워크를 공부하면서 나오는 기초 알고리즘 중의 하나이다.

값을 찾기위한 경사하강법의 수식은 아래와 같다.


여기서  (nabla) 는 벡터공간에 대한 스칼라 장의 구배를 의미한다. 


간편한 프로그래밍의 예를 들기위해 사용을 할 것은 2차함수이므로, 

x항에 대한 편미분 항 이외는 무시 할 수 있다.


따라서 아래와 같이 간략하게 나타낼 수 있다.


여기서 는 학습계수로써, 값을 크게 할 수록 반복계산 횟수는 짧아지지만, 

결과값에 최대한 근접하기 위해서 결과가 진동을 하게 된다.


이와는 반대로, 값을 작게 하면 결과는 좀 더 정확하게 나오지만, 

값을 찾기까지의 시간이 더 오래걸린다.


따라서, 자기가 해결하고 싶은 상황에 따라서 값을 구하는 것을 많이 궁리 할 필요가 있다.


만약에 아래와 같은 2차 방정식이 있다고 가정하자.


위의 수식을 그래프로 표현하면 아래와 같이 나온다.


물론 그냥 눈으로 봐도 최소값이 무엇인 지는 쉽게 알 수 있는 문제이지만,

간단한 예를 들기 위해서 수식을 정했다.


이 식에 경사하강법을 적용하기 위해서, 수식에 대해서 편미분을 취해 주면 아래와 같이 된다.


따라서, 위의 값을 경사하강법 식에 적용하면 아래와 같은 수식으로 나타낼 수 있다.


이 식을 사용해서 평가함수가 최소가 되는 x의 값을 구하는 프로그램은 아래와 같다.

(소스는 c 언어로 작성했다.)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//
//  main.c
//  SteepestDescentMethod
//
//  Created by 초인로크 on 6/17/16.
//  Copyright © 2016 초인로크. All rights reserved.
//
 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
 
double random_number(){
    
    return ((double)(rand()%RAND_MAX)/(double)RAND_MAX);
   
}
 
double function(double x){
    
    return (x + 4)*(x + 4);
    
}
 
int main(int argc, const char * argv[]) {
    
    srand((unsigned int)time(NULL));
    
    int i;
    double alpha = 0.1, x = 0.0;
    
    x = 50 - random_number() * 50;
    
    for(i=0;i<100;i++){
        
        x += -2 * alpha * (x + 4);
        printf("%d: The x:%lf, Results:%lf\n",i,x,function(x));
        
    }
    
    return 0;
    
}
cs


입력값 x는 랜덤하게 결정해 주었으며, 값은 0.1을 이용하였다.

위의 소스를 실행하면 아래와 같은 결과를 확인 할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
0: The x:8.040129, Results:144.964707
1: The x:5.632103, Results:92.777413
2: The x:3.705683, Results:59.377544
3: The x:2.164546, Results:38.001628
4: The x:0.931637, Results:24.321042
5: The x:-0.054691, Results:15.565467
6: The x:-0.843752, Results:9.961899
7: The x:-1.475002, Results:6.375615
8: The x:-1.980002, Results:4.080394
9: The x:-2.384001, Results:2.611452
10: The x:-2.707201, Results:1.671329
11: The x:-2.965761, Results:1.069651
12: The x:-3.172609, Results:0.684576
13: The x:-3.338087, Results:0.438129
14: The x:-3.470470, Results:0.280403
15: The x:-3.576376, Results:0.179458
16: The x:-3.661100, Results:0.114853
17: The x:-3.728880, Results:0.073506
18: The x:-3.783104, Results:0.047044
19: The x:-3.826483, Results:0.030108
20: The x:-3.861187, Results:0.019269
21: The x:-3.888949, Results:0.012332
22: The x:-3.911160, Results:0.007893
23: The x:-3.928928, Results:0.005051
24: The x:-3.943142, Results:0.003233
25: The x:-3.954514, Results:0.002069
26: The x:-3.963611, Results:0.001324
27: The x:-3.970889, Results:0.000847
28: The x:-3.976711, Results:0.000542
29: The x:-3.981369, Results:0.000347
30: The x:-3.985095, Results:0.000222
31: The x:-3.988076, Results:0.000142
32: The x:-3.990461, Results:0.000091
33: The x:-3.992369, Results:0.000058
34: The x:-3.993895, Results:0.000037
35: The x:-3.995116, Results:0.000024
36: The x:-3.996093, Results:0.000015
37: The x:-3.996874, Results:0.000010
38: The x:-3.997499, Results:0.000006
39: The x:-3.997999, Results:0.000004
40: The x:-3.998400, Results:0.000003
41: The x:-3.998720, Results:0.000002
42: The x:-3.998976, Results:0.000001
43: The x:-3.999181, Results:0.000001
44: The x:-3.999344, Results:0.000000
45: The x:-3.999476, Results:0.000000
46: The x:-3.999580, Results:0.000000
47: The x:-3.999664, Results:0.000000
48: The x:-3.999731, Results:0.000000
49: The x:-3.999785, Results:0.000000
50: The x:-3.999828, Results:0.000000
51: The x:-3.999863, Results:0.000000
52: The x:-3.999890, Results:0.000000
53: The x:-3.999912, Results:0.000000
54: The x:-3.999930, Results:0.000000
55: The x:-3.999944, Results:0.000000
56: The x:-3.999955, Results:0.000000
57: The x:-3.999964, Results:0.000000
58: The x:-3.999971, Results:0.000000
59: The x:-3.999977, Results:0.000000
60: The x:-3.999982, Results:0.000000
61: The x:-3.999985, Results:0.000000
62: The x:-3.999988, Results:0.000000
63: The x:-3.999991, Results:0.000000
64: The x:-3.999992, Results:0.000000
65: The x:-3.999994, Results:0.000000
66: The x:-3.999995, Results:0.000000
67: The x:-3.999996, Results:0.000000
68: The x:-3.999997, Results:0.000000
69: The x:-3.999998, Results:0.000000
70: The x:-3.999998, Results:0.000000
71: The x:-3.999998, Results:0.000000
72: The x:-3.999999, Results:0.000000
73: The x:-3.999999, Results:0.000000
74: The x:-3.999999, Results:0.000000
75: The x:-3.999999, Results:0.000000
76: The x:-3.999999, Results:0.000000
77: The x:-4.000000, Results:0.000000
78: The x:-4.000000, Results:0.000000
79: The x:-4.000000, Results:0.000000
80: The x:-4.000000, Results:0.000000
81: The x:-4.000000, Results:0.000000
82: The x:-4.000000, Results:0.000000
83: The x:-4.000000, Results:0.000000
84: The x:-4.000000, Results:0.000000
85: The x:-4.000000, Results:0.000000
86: The x:-4.000000, Results:0.000000
87: The x:-4.000000, Results:0.000000
88: The x:-4.000000, Results:0.000000
89: The x:-4.000000, Results:0.000000
90: The x:-4.000000, Results:0.000000
91: The x:-4.000000, Results:0.000000
92: The x:-4.000000, Results:0.000000
93: The x:-4.000000, Results:0.000000
94: The x:-4.000000, Results:0.000000
95: The x:-4.000000, Results:0.000000
96: The x:-4.000000, Results:0.000000
97: The x:-4.000000, Results:0.000000
98: The x:-4.000000, Results:0.000000
99: The x:-4.000000, Results:0.000000
Program ended with exit code: 0
cs


눈에서도 확인 할 수 있듯이 Results가 최소로 나오는 x값은 -4 가 되겠다.


위키피디아의 문헌을 붙여두니 설명을 더 보고싶은 분은 참고 하시길 바란다.

위키백과 - 경사 하강법



여기에 작성하는 모든 포스팅 들은 스스로의 지식의 정리와, 지식의 공유 차원에서 정리한 것입니다.

학교의 레포트나 과제등은, 본인 스스로가 공부를 해서 직접 제출 하도록 합시다.

출처: http://m.blog.naver.com/msnayana/220776380373


컨벌루션 신경망 ( Convolutional Neural Networks, CNN ) ~ 개요

딥러닝 알고리즘중에서 

영상과 음성에서 좋은 성능을 보이는 알고리즘으로 CNN이 있다.

이  합성곱신경망(컨벌루션 신경망,CNN)은  전처리를 추가한 다층퍼셉트론의 한종류이지만

​2차원 데이타의 입력이 용이하고 훈련이 용이하고  적은 매개변수라는 장점이 있어 많이 사용된다.

또한

최근엔 CNN과 거의 비슷한 합성곱 심층 신뢰신경망(Convolutional Deep Belief Network, CDBN)

이  개발되어  이 알고리즘의  활용성이 많이 높아 진상태이다.

단순하게 표현하면

CNN은  신경망에 기존의 필터기술을 병합하여

신경망이 2차원 영상을 잘 습득할수 있도록 ​최적화시킨 방법(알고리즘)이다.

​용어에서 보듯이 먼저 컨벌류션(합성곱)의  의미를 이해해야 한다.

​CNN은  용어처름

컨벌류션(기존 영상처리의 필터)기능과 신경망을 결합시켜 성능을 발휘토록 만든 구조이다.  

간단히 표현하면 

       컨벌류션(합성곱) + 신경망 = CNN   이다.

 좀 더 세분화하면

 컨벌류션과 sub-sampling 을 반복하여 데이타량을 줄이고 왜곡시켜  신경망에서 분류케 만든다.

일반적으로  모델은​

 특징추출 +  분류행위 =  부류결과  라는 형식으로 동작하는데

  특징추출은 컨벌류션으로 하고, 분류행위는 신경망으로 한 것이다. ​

그래서 먼저 컨벌류션을 이해해야 한다.

이 기법은 기존의 영상처리에서 잘 사용하는 기능으로 영상필터로 사용된 기술이다.

​영상처리에서 컨벌루션이란 가중치를 갖는 마스크를 이용해서 영상처리를 하는 것을 의미하는데
입력 영상에 마스크를 씌운다음, 입력 영상의 픽셀값과 마스크의 가중치를
각각 곱한 후 그 합을 출력영상의 픽셀값으로 정하는 것을 말한다. 
영상처리에 사용되는 마스크를 필터, 윈도 또는 커널이라고 한다.

​위 과정을 세분화 시켜 아래에서 살펴보면

​입력영상에 윈도우를 이동하면서 계산하는데

계산은 ​ 위처름 해당영역에 윈도우값을 곱하여 합한결과를 적어 나간다.

​이것이 컨벌루션으로 이렇게 하면  아래같은 결과를 만들수 있다.

​이것은 기존의 필터 기술로서 원하는 영상을  추출하고자 할때 사용하는데 특징추출이 주 목적이다.

​기존의 영상필터는 커널(윈도우)이 고정값을 사용했는데

여기서는 ​ 필터값도 학습에의해 바뀌도록 설계되어  있다.

그리고

​추출할때는 다양한 여러장을  추출하여  강인한 특징(왜곡,변형같은 환경변화에 잘 적응하는)을

유도하는데  이것을 feature maps이라 한다.  아래 처름..

​아래 그림은

컨벌류션과 subsampling을 반복하면서 영상을 줄여나가는 기본기능을 도식했다.​

​이렇게 계속 줄여나가면 특징이 남게되고

​신경망의 각 입력단자에 바로 접속이 가능한 일차원의 fully connected가 나오고

이것을 신경망 입력단자에 연결시켜 학습시킨다.

​subsampling은 화면의 크기를 줄이는 과정인데 

아래의 방법인 max pool 을 사용한다(해당영역의 최대치를 선택기법)

​위 그림처름 4개중  가장 큰수를 선택하는데 이것은 뉴런이 가장큰신호에 반응하는 것과 유사하다.

이렇게 하면 노이즈가 감소하고 속도도 빠라지고 영상의 분별력이 좋아진다고 한다 

Fully Connected는 ​

2차원 영상을 컨벌류션과 서브​샘플링없이 바로 신경망의 입력에 붙인 다면

학습시간증가, 망의 크기, 변수의 개수가 많아지는  문제가 발생한다.

이렇게 되면 오버피팅과 지역해수렴등의 다양한 문제에 봉착하여 사용이 어렵다. ​

줄이고 줄여 1차원 행렬이 되도록 하여 신경망의 입력단에 각각 하나씩 하여 모두를 매핑한다. 

이렇게 하여 구성한 방법은 아래와 같이 된다.

​위 그림은

컨벌류션과 서브샘플링으로  2차원영상이 특징만 남기고 줄여 1차원 행렬로 바뀌는 과정이다.​

 

​그 과정은

​ 1) 특징추출

 2) topology변화에 영향이 적도록 처리

 3) 분류

 라는 순서로 처리 됨을 알수 있다.​

​ 아래 그림 처름..

​CNN은 layer를 많이 하면 계산량은 늘어나지만 성능은 좋아 진다고 알려져 있다.

​microsoft는 152개의 layer를 적용한 CNN을 만들었다고 한다.

 

이 CNN으로 아래 그림에서 개와 고양이를 골라 낸다.

그것도 아주 잘...​

​다음엔 CNN을 세부적으로 살펴 볼까 한다.

 

마지막 수정일
2016. 9. 12. (본문 내용 업데이트)

출처: http://blog.naver.com/powersilk/10168065952


[경로탐색 알고리즘]

큐를 이용한 너비우선탐색 알고리즘(BFS - Breath First Search)



 

O. 들어가며

 

경로탐색 또는 길찾기 알고리즘을 공부할 때에 가장 기본적으로 이해하고 알고있어야 할 알고리즘은 깊이우선탐색(Depth First Search)과 너비우선탐색(Breath First Search)이다. 물론 실제 게임에서의 경로찾기는 A*알고리즘 등 최단경로 찾기 알고리즘을 사용한다. 혹은 네비게이션 맵을 이용하여 그래프를 구성하고 경로찾기를 구현하는 경우도 많이 있다. 이유는 A* 알고리즘이나 네비게이션 방법이 탐색 속도에서 훨씬 빠르기 때문이다. 이외에도 유전알고리즘이나 뉴럴네트워크와 같은 휴리스틱 알고리즘을 이용하기도 한다. 

 

그러나 스택을 이용하는 깊이우선탐색이나 큐를 이용하는 너비우선탐색은 자료구조 및 알고리즘에서 기본이 되는 부분이기 때문에 반드시 이해하고 알고있어야 하는 부분이다. 여기서는 큐를 이용한 너비우선탐색 알고리즘을 다루도록 한다. 먼저 큐에 대한 설명을 간단히 하고, 큐를 이용한 너비우선탐색 알고리즘이 어떻게 동작하는지 살펴보도록 하겠다.

 

O. 큐(Queue)

 

큐는 스택과 함께 자료구조에서 꼭 이해하고 있어야할 부분 중의 하나이다. 큐는 FIFO(First-In, First-Out), 즉, 선입선출 방식의 자료구조이다. 프로그램으로 구현할 때에는 tail(or rear)에서 데이터 삽입이 진행되고, front에서 데이터가 삭제된다. 배열을 이용한 큐의 추상자료형은 다음과 같다.

 

 

 

 

enqueue(int item) 메쏘드는 tail 위치에 데이터를 추가하는 기능이고, dequeue() 메쏘드는 front 위치의 데이터를 제거하는 기능이다. 큐를 프로그램 코드로 작성하는 것은 큐에 대한 포스팅에서 자세히 다루도록 하겠다.

 

 

O. 너비우선탐색 (Breath First Search)

 

너비우선탐색은 시작 노드를 먼저 방문한 후 시작 노드에 인접한 모든 노드들을 우선 방문하는 방법으로 트리 또는 그래프에서 동일한 레벨에 있는 노드를 먼저 탐색하는 방법이다. 이에 따라 출발 노드에서 목표 노드까지의 최단 경로 찾기가 가능하다. 그러나 그래프의 사이즈가 클 경우 탐색 가지가 급격히 증가함에 따라 메모리 소모가 크며, 최악의 경우 모든 경로를 탐색하게 된다.

 

너비우선탐색은 큐를 이용하여 구현할 수 있다. 시작노드를 방문하고, 큐에 삽입한 후 큐가 빈 상태가 되거나 목적노드를 방문할 때까지 큐의 front에 있는 노드를 삭제한 후 이 노드와 인접한 노드들을 다시 모두 큐에 삽입한다. 이때 큐에 삽입되는 노드들의 Parent 노드는 큐에서 제거되는 노드로 설정한다. 이런 과정을 거치면 각 노드들의 Parent 노드가 결정되고, 목표노드에서부터 시작노드까지 Parent 노드들을 거꾸로 찾아가면 최종 경로를 찾을 수 있다. 이를 그림으로 설명하면 다음과 같다.

 

그래프가 다음과 같고 A를 시작노드로 하고, F를 목적노드로 할 때, 큐와 각 노드들의 Parent 노드 정보를 초기화 한다.

 

 

 

 

노드 A를 방문하고 이를 큐에 삽입한다. 그리고, A노드의 Parent 노드를 A로 설정한다.

이 때 A를 방문했다고 표시한다.

 

 

 

 

큐의 front에 있는 노드 A를 삭제하고, A와 인접한 노드 B와 G를 큐에 차례로 삽입한다. 같은 방법으로 노드 B와 노드 G의 Parent 노드를 큐에서 삭제된 노드 A로 설정한다. 노드 B와 G가 큐에 삽입될 때, 노드 B와 G를 방문했다고 표시한다.

 

 

 

위와 같은 방법으로 큐의 front에 있는 노드 B를 삭제하고, 이 노드와 인접한 노드 C와 E를 차례로 큐에 삽입한다. 이 때 노드 C와 E의 Parent 노드는 방금 전 큐에서 삭제된 노드 B가 된다.

 

 

 

최종적으로 목적 노드인 F를 방문한 후의 결과는 다음과 같다.

 

 

목적 노드까지 방문한 후에는 Parent 정보를 이용하여 시작노드까지의 경로를 거꾸로 탐색하면 된다. 목적 노드인 F의 Parent 노드는 노드 E가 되고, 노드 E의 Parent 노드는 B가 되며, 노드 B의 Parent 노드는 A가 된다. 즉, F->E->B->A가 되며 실제 프로그램에서는 이를 거꾸로 처리하면 시작노드 A에서 목적노드 F까지의 경로를 찾을 수 있다. 최종 결과의 모습은 다음과 같다.

 

 

 

 

 

O. 너비우선탐색 알고리즘

 

위에서 설명한 너비우선탐색의 알고리즘은 다음과 같다.

 

 

 

큐를 생성. 시작노드를 큐에 삽입하고 방문한 것으로 표시한다. 큐가 비어있지 않고 목적노드를 찾지 못하면 큐에서 front에 있는 노드를 얻어오고 이 노드와 인접한 모든 노드들을 큐에 삽입한다. 큐에 노드를 삽입할 때 삽입되는 노드들은 방문했다고 표시한다. 또한, 이 코드에서는 기술되지 않았지만, 큐에 삽입되는 모든 노드들의 Parent 노드들은 front에서 얻어온 노드로 설정한다.

 

 

O. 실행결과

 

아래 동영상은 자료구조 시간에 구현한 결과로 큐를 이용한 너비우선탐색 알고리즘을 이용하여 목적노드까지 탐색하는 과정을 나타내고 있다. 맵은 타일맵으로 구성되어 있으며, 검정색 타일은 벽을, 녹색 타일은 오브젝트로 하였다. 빨간 원이 너비우선탐색을 이용하여 탐색해가는 과정을 나타내고 있다.

 

 



O. 마치며


이번 포스팅에서는 큐를 이용한 너비우선탐색 알고리즘을 살펴보았다. 스택과 큐는 반드시 이해하고 알아야할 자료구조 중의 하나이다. 또한 너비우선탐색은 큐를 이용한 응용 중에 하나이며 깊이우선탐색과 더불어 길찾기알고리즘의 기본이 되는 알고리즘이다. 따라서 너비우선탐색 알고리즘의 동작원리를 이해하는 것은 매우 중요하다.

 

다음 포스팅에서는 지금까지 여러번 언급하였지만, 너비우선탐색 알고리즘과 함께 길찾기의 기본 알고리즘 중의 하나인 깊이우선탐색 알고리즘에 대해 살펴보도록 하겠다.


출처: http://hyeonstorage.tistory.com/324


vector 컨테이너는 대표적인 시퀀스 컨테이너로 배열과 비슷하여 사용이 쉬우며 자주 사용된다.


vector는 임의 접근 반복자(Random Access Iterator)를 지원하는 배열 기반 컨테이너이다.

vector의 가장 큰 특징 중 하나는 원소가 하나의 메모리 블록에 연속하게 저장된다는 것이다.


그렇다 보니 원소가 추가되거나 삽입될 때 메모리 재할당이 발생할 수 있고 상당한 비용을 지불하게 된다.

그래서 메모리 할당 크기를 알 수 있게 capacity() 함수를 제공하며 한번에 메모리를 할당할 수 있는 reserve() 함수도 제공된다.


원소가 연속하게 저장되므로 [] 연산자 또는 at 으로 읽기에는 빠르지만  insert(), erase(), push_back() 등은 비효율적으로 동작한다.


템플릿 형식

 template<typename T, typename Allocator = allocator<T>>

class vector

T는 vector 컨테이너 원소의 형식 



생성자 

 vector v

v는 빈 컨테이너이다. 

 vector v(n)

v는 기본값으로 초기화된 n개의 원소를 갖는다. 

 vector v(n,x)

v는 x 값으로 초기화된 n개의 원소를 갖는다. 

 vector v(v2)

v는 v2 컨테이너의 복사본이다.(복사 생성자 호출) 

 vector v(b,e)

v는 반복자 구간 [b,e)로 초기화된 원소를 갖는다. 



멤버함수 

 v.assign(n,x)

v에 x 값으로 n개의 원소를 할당한다. 

 v.assign(b,e)

 v를 반복자 구간 [b,e)로 할당한다.

 v.at(i)

v의 i번째 원소를 참조한다. 

 v.back()

v의 마지막 원소를 참조한다. 

 p=v.begin()

p는 v의 첫 원소를 가리키는 반복자 

 x=v.capacity()

x는 v에 할당된 공간의 크기 

 v.clear()

v의 모든 원소를 제거한다. 

 v.empty()

v가 비었는지 조사한다. 

 p=v.end()

p는 v의 끝을 표식하는 반복자 

 p=v.erase(p)

p가 가리키는 원소를 제거한다. q는 다음 원소를 가리킨다. 

 q=v.erase(b,e)

반복자 구간 [b,e)의 모든 원소를 제거한다. q는 다음 원소 

 v.front()

v의 첫 번째 원소를 참조한다. 
 q=v.insert(p,x)

p가 가리키는 위치에 x 값을 삽입한다. q는 삽입한 원소를 가리키는 반복자다. 

 v.insert(p,n,x)

p가 가리키는 위치에 n개의 x 값을 삽입한다. 
 v.insert(p,b,e)

p가 가리키는 위치에 반복자 구간 [b,e)의 원소를 삽입한다. 

 x=v.max_size()

x는 v가 담을 수 있는 최대 원소의 개수(메모리의 크기) 

 v.pop_back()

v의 마지막 원소를 제거한다. 
 v.push_back()v의 끝에 x를 추가한다. 

 p=v.rbegin()

p는 v의 역 순차열의 첫 원소를 가리키는 반복자다. 
 p=v.rend()

p는 v의 역 순차열의 끝을 표식하는 반복자 

 v.reserve(n)n개의 원소를 저장할 공간을 예약한다. 

 v.resize(n)

v의 크기를 n으로 변경하고 확장되는 공간의 값을 기본값으로 초기화 한다. 

 v.resize(n,x)

v의 크기를 n으로 변경하고 확장되는 공간의 값을 x 값으로 초기화한다. 
 v.size()v의 원소 갯수 

 v.swap(v2)

v와 v2를 swap한다. 



연산자 

 v1==v2

v1과 v2의 모든 원소가 같은가? (bool) 

 v1!=v2

v1과 v2의 모든 원소 중 하나라도 다른 원소가 있는가? 

 v1<v2

문자열 비교처럼 v2가 v1보다 큰가? 

 v1>v2

문자열 비교처럼 v1이 v2보다 큰가? 

 v[i]

v의 i번째 원소를 참조한다. 



멤버 형식 

 allocator_type

 메모리 관리자 형식 

 const_iterator

 const 반복자 형식 

 const_pointer

 const value_type* 형식 

 const_reference

 const value_type& 형식 

 const_reverse_iterator

 const 역 반복자 형식 

 difference_type

 두 반복자 차이의 형식 

 iterator

 반복자 형식 

 pointer

 value_type* 형식 

 reference

 value_type& 형식 

 reverse_iterator

 역 반복자 형식 

 size_type 첨자(index)나 원소의 개수 등의 형식 

 value_type

 원소의 형식 


시퀀스 컨테이너는 차례차례 원소를 추가하고 제거하는 push_back()과 pop_back()을 가지며, 첫 원소와 마짐가 원소를 참조하는 front()와 back()을 가진다. 또한, 지정한 위치에 원소를 삽입할 수 있는 insert()를 가진다.


vector는 앞쪽이 막혀 있는 형태로 앞쪽에는 원소를 추가/제거할 수 없으며 뒤쪽에만 추가/제거할 수 있다.


* vector 사용 예제 1


 Colored By Color Scripter

#include <iostream>
#include <vector>
using namespace std;

int main(){

    vector<int> v;
    v.reserve(8);        // 벡터 메모리 공간 8 예약 할당

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);

    for (vector<int>::size_type i = 0; i < v.size(); ++i)
        cout << v[i] << endl;
    cout << endl;

    cout << "size : " << v.size()                // 벡터 원소 개수
        << " capacity : " << v.capacity()            // 벡터의 할당된 메모리의 크기
        << "  max_size : " << v.max_size() << endl;    // 최대 저장 가능한 원소 개수


    cout << endl << "-- resize(10) -- " << endl;
    
    v.resize(10);            // 벡터의 원소 갯수를 10개로 확장, 추가된 공간은 디폴트 0으로 채워진다.
    
    for (vector<int>::size_type i = 0; i < v.size(); ++i)   // 벡터의 size 타입으로 i를 지정한다 (unsigned int) 
        cout << v[i] << endl;
    cout << endl;

    cout << "size : " << v.size()
        << " capacity : " << v.capacity()
        << "  max_size : " << v.max_size() << endl;


    cout << endl << "-- resize(3) -- " << endl;

    v.resize(3);            // 벡터의 원소 갯수를 3개로 축소, capacity는 변화 없다.

    for (vector<int>::size_type i = 0; i < v.size(); ++i)
        cout << v[i] << endl;
    cout << endl;

    cout << "size : " << v.size()                
        << " capacity : " << v.capacity()            
        << "  max_size : " << v.max_size() << endl;


    cout << endl << "-- vector clear() -- " << endl;

    v.clear();    // 벡터 비운다    capacity(메모리) 는 그대로 남아있다.

    if (v.empty()){    // 벡터에 원소가 없는지 확인한다.
        cout << "벡터에 원소가 없다." << endl;
    }

    cout << "size : " << v.size()
        << " capacity : " << v.capacity()
        << "  max_size : " << v.max_size() << endl;

    return 0;
}


결과 :

10

20

30

40

50


size : 5 capacity : 8 max_size : 1073741823


-- resize<10> --

10

20

30

40

50

0

0

0

0

0


size : 10 capacity : 12 max_size : 1073741823


-- resize<3> --

10

20

30


size : 3 capacity : 12 max_size : 1073741823

벡터에 원소가 없다.

size : 0 capacity : 12 max_size : 1073741823


- v.reserve(8) : 벡터의 메모리 공간(capacity) 을 미리 할당한다. * 추가할당이 아님

- vector<int>::size_type : 벡터의 size 의 반환 타입을 가져온다 (unsigned int)

- v.resize(10) : 벡터의 원소 갯수를 수정한다. (size 를 줄여도 capacity는 그대로다)

- v.clear() : 벡터를 비운다 (capacity 크기는 그대로다)

- v.empty() : 벡터가 비워져 있는지 확인한다.


* for문으로 vector를 탐색할 때, v.size() 만큼 i를 돌리려면, v.size()의 타입과 i 가 같아야 한다.


* v.capacity()는 벡터에 할당된 메모리 공간이다.

새로운 원소가 벡터에 추가되면 메모리 공간이 추가적으로 할당된다.

매번 새로운 원소가 들어올 때마다 새로운 메모리가 할당되는 것은 비효율적이다.

capacity가 모자랄 경우 capacity/2 만큼의 capacity를 늘려간다.

만약 입력될 원소의 갯수를 알 수 있다면 reserve 를 사용하여 미리 capapcity 메모리를 할당해 놓으면 효율적이다.


* v.clear()를 사용하면 벡터의 원소를 비운다.

하지만 capacity는 그대로 남아 있다. 비어있는 벡터인데 메모리를 할당하고 있는 것은 아깝다.

이럴경우 clear()를 사용하기 보다 . 임시 벡터와 swap 을 통해 교환하면 메모리까지 해제할 수 있다.




 Colored By Color Scripter

#include <iostream>
#include <vector>
using namespace std;

int main(){

    vector<int> v(5);    // 0으로 초기화된 5개의 원소
    cout << "size : " << v.size() << " capacity : " << v.capacity() << endl;

    vector<int>().swap(v);        // 임의 벡터와 교환한다.
    cout << "size : " << v.size() << " capacity : " << v.capacity() << endl;

    vector<int> v1;
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(40);
    v1.push_back(50);

    cout << v1[0] << ", " << v1.at(0) << ", " << v1.front() << endl; // 첫번째 원소
    cout << v1[4] << ", " << v1.at(4) << ", " << v1.back() << endl; //  마지막 원소

    v1.front() = 100;
    v1.back() = 500;

    cout << v1[0] << ", " << v1.at(0) << ", "<< v1.front() << endl; // 첫번째 원소
    cout << v1[4] << ", " << v1.at(4) << ", " << v1.back() << endl; //  마지막 원소

    try{

        cout << v.at(10) << endl;        // 범위를 벋어난 호출 throw out_of_range 예외
    
    } catch (out_of_range &e){
        cout << e.what() << endl;
    }

    return 0;
}




결과 :

size : 5 capacity : 5

size : 0 capacity : 0

10, 10, 10

50, 50, 50

100, 100, 100

500, 500, 500

invalid vector<T> subscript 



* vector<int>().swap(v); : 임의 벡터와 swap을 하면서 벡터를 비우고 할당된 메모리(capacity)까지 해제한다.


* v.front()는 벡터의 첫번째 요소를 반환하고 v.back()는 마지막 요소를 반환한다.


* 벡터의 임의 요소에 접근하는 방법으로는 [] 연산자와 at 멤버함수가 있다.

[] 연산자를 사용하면 접근이 빠르지만 범위 점검을 하지 않는다.

at() 멤버 함수를 사용하여 접근하면 범위 점검을 수행하며, 범위에 벗어난 요소에 접근하면 out_of_range 예외를 throw 하여 예외를 처리할 수 있다.

출처:http://hyeonstorage.tistory.com/325




deque 컨테이너는 vector 컨테이너와 기능과 동작이 비슷한 컨테이너로 vector의 단점을 보완하는 몇가지 특징을 갖는다.

deque도 vector 컨테이너와 같이 시퀀스 컨테이너이며 배열 기반 컨테이너이다.


[C++/STL] - [STL] vector 벡터 정리 및 예제



템플릿 형식 

 template<typename T, typename Allocator=allocator<T>>

class deque

 T는 deque 컨테이너 원소의 형식



 생성자

 deque dq

dq는 빈 컨테이너이다. 

 deque dq(n)

dq는 기본값으로 초기화된 n개의 원소를 갖는다. 

 deque dq(n,x)

dq는 x 값으로 초기화된 n 개의 원소를 갖는다. 

 deque dq(dq2)

dq는 dq2 컨테이너의 복사본이다. 

 deque dq(b,e)

dq는 반복자 구간 [b,e)로 초기화된 원소를 갖는다. 



멤버 함수 

 dq.assign(n,x)

dq에 x 값으로 n 개의 원소를 할당한다 

 dq.assign(b,e)

dq를 반복자 구간 [b,e)로 할당한다. 

 dq.at(i) 

dq의 i번째 원소를 참조한다. 

 dq.back()

dq의 마지막 원소를 참조한다. 

 p=dq.begin()

p는 dq의 첫 원소를 가리키는 반복자다 

 dq.clear()

dq의 모든 원소를 제거한다. 

 dq.empty()

dq가 비었는지 조사한다. 

 p=dq.end()

p는 dq의 끝을 표식하는 반복자다 

 q=dq.erase(p)

p가 가리키는 원소를 제거한다. q는 다음 원소를 가리킨다. 

 q=dq.erase(b,e)반복자 구간 [b,e)의 모든 원소를 제거한다. q는 다음 원소다 

 dq.front()

dq의 첫 번째 원소를 참조한다. 
 q=dq.insert(p,x)

 p가 가리키는 위치에 x 값을 삽입한다. q는 삽입한 원소를 가리킨다. 

 dq.insert(p, n, x)

p가 가리키는 위치에 n 개의 x 값을 삽입한다. 

 dq.insert(p, b, e)

p가 가리키는 위치에 반복자 구간 [b,e)의 원소를 삽입한다. 

 x=dq.max_size()

x는 dq가 담을 수 있는 최대 원소의 개수이다. 

 dq.pop_back()

 dq의 마지막 원소를 제거한다. 

 dq.pop_front()

dq의 첫 원소를 제거한다. 
 dq.push_back()dq의 끝에 x를 추가한다. 
 dq.push_front()

dq의 앞쪽에 x를 추가한다. 

 p=dq.rbegin()

p는 dq의 역 순차열의 첫 원소를 가리키는 반복자이다. 
 p=dq.rend()p는 dq의 역 순차의 끝을 표식하는 반복자 

 dq.resize(n)

dq의 크기를 n으로 변경하고 확장되는 공간의 값을 기본값으로 초기화한다. 
 dq.resize(n,x)dq의 크기를 n으로 변경하고 확장되는 공간의 값을 x 값으로 초기화한다. 

 dq.size()

dq 원소의 개수다 
 dq.swap(dq2)

dq와 dq2를 swap 한다. 



연산자 

 dq1 == dq2

dq1과 dq2의 모든 원소가 같은가? (bool) 

 dq1!=dq2

dq1과 dq2의 모든 원소 중 하나라도 다른 원소가 있는가? 

 dq1 < dq2

문자열 비교처럼 dq2가 dq1보다 큰가? 

 dq1 > dq2

문자열 비교처럼 dq1이 dq2보다 큰가? 

 dq[i]

dq의 i번째 원소를 참조한다. 


멤버 형식 

 allocator_type

 메모리 관리자 형식 

 const_iterator

 const 반복자 형식

 const_pointer

 const value_type* 형식 

 const_reference

 const value_type& 형식 

 const_reverse_iterator

 const 역 반복자 형식 

 difference_type

 두 반복자 차이의 형식 

 iterator

 반복자 형식 

 pointer

 value_type* 형식 

 reference

 value_type& 형식 

 reverse_iterator

 역 반복자 형식 
 size_type 첨자(index)나 원소의 개수 등의 형식 
 value_type 원소의 형식 


deque 는 vector의 메모리 할당 단점을 해결하기 위해 여러 개의 메모리 블록을 할당하고 사용자에게는 하나의 블록처럼 보이게 하는 정책을 사용한다.


vector는 새로운 원소를 삽입할 때 할당된 메모리가 부족하면 이전 메모리 블록을 삭제하고 새로운 메모리 블록을 재할당하며 이전 원소를 모두 복사하지만, deque는 새로운 단위의 메모리 블록을 할당하고 원소를 삽입한다.

또한, 새로운 원소를 순차열 중간에 삽입 , 제거 하더라도 원소의 개수가 작은 쪽 으로 밀어낸다.


따라서 deque는 vector 보다 효율적으로 동작한다.



 Colored By Color Scripter

#include <iostream>
#include <deque>
using namespace std;

int main(){

    deque<int> dq;

    dq.push_back(10);
    dq.push_back(20);
    dq.push_back(30);
    dq.push_back(40); 
    dq.push_back(50);

    for (deque<int>::size_type i = 0; i < dq.size(); ++i){
        cout << dq[i] << ' ';
    }
    cout << endl;

    dq.push_front(100);
    dq.push_front(200);    // 앞에 추가한다.

    for (deque<int>::size_type i = 0; i < dq.size(); ++i){
        cout << dq[i] << ' ';
    }
    cout << endl;


    deque<int>::iterator iter;
    deque<int>::iterator iter2;

    for (iter = dq.begin(); iter != dq.end(); ++iter){
        cout << *iter << ' ';
    }
    cout << endl;

    iter = dq.begin() + 2;            // dq의 3번째 원소에 접근
    iter2 = dq.insert(iter, 500);    // 3번째 원소 자리에 500을 삽입한다.
    cout << *iter2 << endl;

    for (iter = dq.begin(); iter != dq.end(); ++iter){
        cout << *iter << ' ';
    }

    return 0;
}


출처:http://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Backtracking-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9


백트래킹

정의 : 여러 해들 중에 조건에 맞는 모든 해를 찾는 알고리즘.


알고리즘

1. 후보 해를 선택한다.

2. 조건에 따라 후보 해에 적절성 검사를 시행한다. 통과하지 못하면 지금 현재 선택한 후보 해를 버리고 1로 돌아가 후보 해를 다시 선택한다.

3. 적설성 검사가 통과한 경우 이 후보 해가 문제의 해가 되는지 검사한다. 검사를 통과하면 이것이 문제의 해이고, 검사를 통과하지 못하면 1로 돌아가 후보 해를 계속해서 선택한다.


백트래킹의 활용

1. 미로 탈출로 찾기

재귀함수를 통해 백트래킹으로 미로 탈출로를 찾아보자. 


알고리즘

1. 시작점을 현재 위치로 지정하고, 이동방향을 북으로 설정한다.

2. 현재 위치에서 가고자 하는 이동 방향으로 이동이 가능한지 확인한다. 벽과 이미 지나온 길은 이동가능한 길이 아니다.

3. 현재 가고자 하는 이동 방향으로 이동이 가능하면 그곳으로 이동한다. 이동이 불가능하면 방향을 바꾸어 다시 2번을 수행한다. 모든 방향으로 이동이 불가능하면 이전 위치로 되돌아간다.

4. 출구에 다다르거나 미로 내의 모든 길을 방문할때까지 2, 3단계를 반복한다.


3번 과정에서 이동하는 부분을 재귀함수로 구현하면 될 것이다. 이동이 가능하면 재귀함수를 통해 그곳으로 이동하면 모든 방향으로 이동이 불가능하면 반환을 통해 재귀함수를 탈출하여 이전 상태로 돌아가면 될 것이다.


2. N개의 퀸

체스에서 퀸은 모든 방향으로 거리 제한없이 움직일 수 있는 말이다. N개의 퀸 문제는 N × N 크기의 체스판에서 N개의 말들이 서로 공격이 불가능하게 배치하는 모든 경우를 구하는 문제이다. 


알고리즘

1. 첫 행, 첫 열을 시작점으로 지정한다.

2. 현재 지점에서 퀸을 놓으면 다른 퀸에게 위협을 받는지 검사한다. 이전 단계에서 놓은 퀸들 중에 현재 지점에서의 퀸의 행 값이 같으면 수평방향으로 위협을 받는 것이고, 열 값이 같으면 수직방향으로 위협을 받는 것이다. 행의 차와 열의 차가 같으면 대각선 방향으로 위협을 받고 있는 것이다.

3. 위협을 받고 있지 않다면 행의 값을 증가시키고 열의 첫번째 값으로 가서 2를 수행한다. 위협을 받고 있다면 열의 값을 증가시켜서 2를 수행한다. 열의 마지막 값에서도 위협을 받고 있다면 이전 단계의 퀸의 위치로 되돌아간다.

4. 마지막 행, 마지막 열에 다다르면 종료한다.


과정 3을 재귀함수로 구현하면 될 것이다.

+ Recent posts