[한겨레] 현상금 100만달러가 걸린 세계 7대 수학난제 중 첫번째 문제를 김양곤(55·수학통계정보과학부) 전북대 교수가 이끄는 국내 연구팀이 3년 만에 풀어냈다.
김 교수는 5일 “미국 클레이 수학재단(CMI)이 지난 2000년 상금 700만달러를 걸고 발표했던 세계 7대 난제 중 1번 문제를 풀어 독일의 논문평가기관인 첸트랄블라트에서 발간하는 논문집에 수록했다”고 밝혔다.
김 교수는 미국 위스콘신 대학 남기봉 교수와 함께 1번 문제인 ‘P 대 NP’를 공동으로 해결했다. 이번 논문은 지난 3월에 인도의 한 저널에도 발표됐다. 김 교수가 푼 ‘P 대 NP’는 컴퓨터 알고리즘과 관련된 분야로 수학의 귀납법 풀이는 가능하나 연역적 풀이도 가능한가라는 문제로 물리학자들도 향후 10~20년 이후 해답이 나올 것으로 예측했다. 김 교수의 논문은 게재 후 2년 동안 수학계의 반응을 본 뒤 클레이 수학재단의 심사를 거쳐 100만달러를 수상하게 된다.
전주/박임근 기자 pik007@hani.co.kr ⓒ 한겨레(http://www.hani.co.kr), 무단전재 및 재배포 금지
int main() { fin.open("test.in"); float* x = new float[3]; float* y = new float[3]; int cur_y, count, tx1, tx2; float a1, a2, cur_x1, cur_x2; bool turn;
while ( read_input(x, y) ) { if ( y[1] < y[0] && y[1] <= y[2] ) { swap( x[0], x[1] ); swap( y[0], y[1] ); } else if ( y[2] < y[0] && y[2] < y[1] ) { swap( x[0], x[2] ); swap( y[0], y[2] ); } // for largest y
bool read_input(char* filename) { ifstream fin; int buf;
fin.open( filename );
fin >> array_size; // take the array size N if ( array_size <= 0 ) { cout << "Error : array size!" << endl; return false; }
num_array = new char*[array_size]; for (int i=0; i<array_size; i++) num_array[i] = new char[array_size]; // 2-dim array M-allocate
for (int i=0; i<array_size; i++) for (int j=0; j<array_size; j++) { fin >> buf; num_array[i][j] = (char) buf; // take the values }
fin.close();
return true; }
int main() { char* input_filename; int** sum; int max = 1 << 31; int local_max, local_max_candi, temp;
input_filename = "test.in";
if ( !read_input(input_filename) ) return -1;
sum = new int*[array_size+1]; // 2-dim array for SUM from [0,0] to [x,y] for (int i=0; i<array_size+1; i++) { sum[i] = new int[array_size+1]; sum[i]++; // move the pointer to use the -1 index } sum++; // move higher pointer too, so we can use sum[-1 ~ array_size][-1 ~ array_size]
a1, a2, ..., ax, ..., ay, ay+1, ..., ak-1, ak, ...
이런 행렬이 있다고 치고,
a1~ak-1 중에 maxsum substring을 ax...ay 라고 하자.
그렇다면 위의 조건을 이용하여 a1~ak의 maxsum substring을 O(1) 안에 구할 수 있으면
귀납법으로 전체의 maxsum substring을 O(N) 안에 구할 수 있게된다.
a1~ak의 maxsum substring이 될 수 있는 후보는,
1. a1~ak-1의 최대값인 ax...ay : max
2. 새로운 원소 하나 ak
3. 또 다른 스트링 az...ak (단, x<=z<k) : candi
위에서 1번과 3번을 편의상 max랑 candi라고 부르자.
여기서 candi 값을 잘 유지하는게 중요한데
임의의 점부터 현재원소까지의 합 중 maximum 값을 유지해야 한다.
(즉, ak를 끝점으로 하는 substring 중에 max를 말한다.)
위의 과정을 하는 코드를 짜보면..
max = -inf; candi=0;
for k=1 to k=N
{
candi += ak
if ( ak > max && ak > candi )
max = candi = ak; // 위에서 2번 후보에 해당
else if ( candi > max )
max = candi; // 위에서 3번 후보에 해당
else if ( ak > candi )
candi = ak; // candi를 최신으로 유지하기 위한 코드
} // 위에서 1번 후보의 경우는 max값을 갱신할 필요 없음
print max;
이래서 1차원 행렬의 max를 O(N) 만에 구할 수 있다.
이것을 2차원에 적용하는 방법은
사각형의 네 좌표를 [,]-[,] 식으로 나타낸다면
[0,a]-[0,b] (a,b는 임의의 수) 같은 사각형은 총 O(N^2)개 존재한다.
이 각 사각형들 내부의 합은 우리가 N^4할때 썼던 방법으로 쉽게 구하고
이 사각형 중 maximum은 위에서 언급한 1차원 알고리즘으로 구할 수 있다.
즉, O(N) 시간안에 최대값을 구할 수 있다는 얘기다.
이런 방법으로 [0,a]-[1,b] 의 최대값, [2,a]-[5,b] 의 최대값
식으로 구하면
총 O(N^2)개의 최대값을 O(N^3) 시간 안에 구할 수 있고
그 모든 최대값 중에 최대값이 바로 우리가 원하는 값이다.
bool read_input(char* filename) { ifstream fin; int buf;
fin.open( filename );
fin >> array_size; // take the array size N if ( array_size <=> return false; }
num_array = new char*[array_size]; for (int i=0; i<array_size; i++) num_array[i] = new char[array_size]; // 2-dim array M-allocate
for (int i=0; i<array_size; i++) for (int j=0; j<array_size; j++) { fin >> buf; num_array[i][j] = (char) buf; // take the values }
fin.close();
return true; }
int main() { char* input_filename; int** sum; int max = 1 << 31; int temp;
input_filename = "test.in";
if ( !read_input(input_filename) ) return -1;
sum = new int*[array_size+1]; // 2-dim array for SUM from [0,0] to [x,y] for (int i=0; i<array_size+1; i++) { sum[i] = new int[array_size+1]; sum[i]++; // move the pointer to use the -1 index } sum++; // move higher pointer too, so we can use sum[-1 ~ array_size][-1 ~ array_size]
short CELL[WIDTH][WIDTH][WIDTH]; short* CELL_S = &(CELL[0][0][0]); // the 1-dimension alias of the 3-dimension array CELL short MD[WIDTH*WIDTH*WIDTH][WIDTH*WIDTH*WIDTH]; // save All possible MD values. short ANS[1000] = {0}; // the optimal solution of minimum moving sequence int bound;
bool read_input(char* filename) // at first, load input file (ex. from puzzle.in) { ifstream in (filename);
char buf; int current_cell = 0; int counter = 0;
while (in.get(buf)) { if (buf>='0' && buf<='9') { current_cell = current_cell*10 + (buf - '0'); } else if (buf == '$') current_cell = 64; else { if (current_cell > 64) { cout << "ERROR : Wrong input file." << endl; return false; } else if (current_cell > 0) { CELL_S[counter] = current_cell; // save it in to the array counter++; current_cell = 0; } } }
in.close();
int inv_count = 0; // Check whether this problem can be solved or not
for (int i=1; i<WIDTH*WIDTH*WIDTH; i++) { if (CELL_S[i-1]>CELL_S[i]) inv_count++; }
if (inv_count%2 == 0) { cout << "Impossible to solve!" << endl; return false; }
return true; }
void set_md() // compute Manhattan Distance of all possible pair of cells { int i_x, i_y, i_z, j_x, j_y, j_z;
for (int i=0; i<WIDTH*WIDTH*WIDTH; i++) { i_x = i % WIDTH; i_z = i / (WIDTH*WIDTH); i_y = (i - i_z*WIDTH*WIDTH) / WIDTH; for (int j=0; j<WIDTH*WIDTH*WIDTH; j++) { j_x = j % WIDTH; j_z = j / (WIDTH*WIDTH); j_y = (j - j_z*WIDTH*WIDTH) / WIDTH;
int cur_MD() // return current sum of MDs { int md = 0;
for (int i=0; i<WIDTH*WIDTH*WIDTH; i++) { if (CELL_S[i] == 64) continue; md += MD[i][CELL_S[i]-1]; }
return md; }
bool move_to(int dir) // move to dir { int x, y, z, idx; // find the empty cell for (idx=0; idx<WIDTH*WIDTH*WIDTH; idx++) if (CELL_S[idx]==64) break; x = idx % WIDTH; z = idx / (WIDTH*WIDTH); y = (idx - z*WIDTH*WIDTH) / WIDTH;
switch (dir) { case 1 : // move up if (y != 0) { CELL[z][y][x] = CELL[z][y-1][x]; CELL[z][y-1][x] = 64; } else return false; // impossible to move break;
case 2 : // move down if (y != 3) { CELL[z][y][x] = CELL[z][y+1][x]; CELL[z][y+1][x] = 64; } else return false; break;
case 3 : // move left if (x != 0) { CELL[z][y][x] = CELL[z][y][x-1]; CELL[z][y][x-1] = 64; } else return false; break;
case 4 : // move right if (x != 3) { CELL[z][y][x] = CELL[z][y][x+1]; CELL[z][y][x+1] = 64; } else return false; break;
case 5 : // move forward if (z != 0) { CELL[z][y][x] = CELL[z-1][y][x]; CELL[z-1][y][x] = 64; } else return false; break;
case 6 : // move backward if (z != 3) { CELL[z][y][x] = CELL[z+1][y][x]; CELL[z+1][y][x] = 64; } else return false; break;
default : return false; }
return true; // success to move }
bool IDA(int depth, short prev) // searching algorithm { depth++; short opp;
for (int i=1; i<=6; i++) { opp = (i%2 == 0) ? i-1 : i+1; // the opposite side of moving direction. if (prev != opp && move_to(i)) { if (cur_MD()+depth<=bound) { if (depth == bound || IDA(depth, i)) // recursive call { move_to(opp); // move back ANS[depth] = i; // save the answer return true; } } move_to(opp); // move back } }
return false; }
void print_cur() // print out the current status { for (int i=0; i<WIDTH; i++) { for (int j=0; j<WIDTH; j++) { for (int k=0; k<WIDTH; k++) { if (CELL[j][i][k] == 64) printf(" $"); else printf("%3d", CELL[j][i][k]); } printf(" | "); } printf("\n"); } return; }
void search() // find the optimal solution { bound = cur_MD(); // lower bound of moves in optimal solution
슬라이딩 퍼즐은 기본적으로 state들로 볼 수 있다.
15-puzzle의 경우엔 총 16!개의 state가 존재하고
그 state들이 서로 얽히고 섥히도록 transition이 존재한다.
초기의 생각은 그런 state들을 그룹지어서..
각 transition에게 특성을 부여하는거였는데..
워낙 광범위하고, 정의하기가 어려워서 포기했다.
그러던 중 IDA* 알고리즘을 발견하게 됐고,
트리 형태로 구현하는 방법을 생각하게 됐다.
16!개의 state로 생각하지 말고...
현재의 state를 root로 두고...
모든 state는 child를 4개(4방향으로 움직일 수 있음, 실제론 3개-왔던방향으로 돌아가는건 의미없으므로)씩 갖고 있는 node라고 생각하면...
무한히 뻗어나갈 수 있는 트리를 생각할 수 있다.
이렇게 되면 transition은 아주 일반적인 것이 되므로..
각 node를 특성화 시키는게 필요한데
가장 간단한것이 node마다 어떤 숫자를 부여하는 것이다.
GOAL state로 부터 얼마나 떨어져있나 하는 숫자.
이때 쓴것은 Manhattan Distance 라고...
간단히 말해 |x1-x2| + |y1-y2| 를 구하는 것이다.
현재 15개의 cell에 대해 MD들을 다 합하면(empty cell 제외)
일정한 값이 되고 이 값이 각 state를 구분짓는 기준이 된다.
또한, 현재 state의 MD의 합은 곧 optimal solution의 move수의 lower bound가 된다.
(한번의 move에 반드시 하나의 cell이 empty cell과 바뀌므로)
이제 tree를 타고 내려가면서 검색을 시작한다.
tree라고 해서 직접 구현하는것이 아니라
recursive function을 통해 간단히 구현한다.
empty cell이 이동 가능한 지점들을 차례로 방문하면서
만약 그 지점으로 이동했을경우 MD+depth가 구해놓은 lower bound보다 작거나 같다면 제대로 찾아온 것이므로 검색을 계속한다(recursive call).
크다면 잘못 온것이므로 false를 return하면서 이동한것을 원래대로 복귀시킨다.
이렇게 검색을 하다가 MD = 0 이 되고 현재 node의 tree depth가 lower bound랑 같다면 해를 구한 것이 된다. 이 때는 true를 return하면서 구했던 solution을 저장한다.
만약 lower bound에 해당하는 모든 solution을 검색했으나 딱 떨어지는 solution이 없을 경우엔 lower bound를 2만큼 증가시켜 다시 검색을 시도한다.
(bound를 1 증가시키는건 의미가 없다.)
이번 숙제는 3차원 63-puzzle 이였는데
간단한 확장으로 어렵지 않게 구현이 가능하다.
댓글을 달아 주세요
알고리즘 시간에 많이 들은 얘기지만..
P=NP 가 연역적으로 풀이 가능하다면 정말
알고리즘 학계에 역사상 최대의 사건이 되는건데 -_-
그동안 수많은 시도가 있었고 다들 '풀었다!'라고 했지만
다른 수학자 혹은 공학자들이 항상 오류를 발견해내었다 ㅡㅡ;;
왠지 이번에도 그럴것 같은 느낌...
문병로 교수님이 수엽시간에 한이야기 생각난다
그 수업들을 당시 약 몇초간...생각한건데..
'함 풀어보까?'
ㅋㅋㅋ
허허..전에 assignment problem 풀 때, 잠시 본 문제였는데..
문제 자체를 이해하기도 힘들던데.. 허허..
뵨//나도 그때 몇초간 생각했었어 ㅋㅋ
엽//알고리즘 수업 들으면 문교수님이 친절히 설명해주신다 -_-;