| [ Guru ] in KIDS 글 쓴 이(By): chilly (김규동) 날 짜 (Date): 1996년01월23일(화) 21시05분14초 KST 제 목(Title): 메아리: 수학 잘하시는 분께 질문 하나! 저는 수학은 못하지만, 질문하신 문제가 integer linear programming 인 것같은데, 알고리듬의 복잡도가 2의 지수승이라는 판단은 옳은 것으로 알고 있습니다. 그런 종류의 문제가 문제 크기의 다항함수로 주어지는 시간에 풀 수 없는 종류로, NP complete인 것으로 배웠습니다. 아마 왕도가 없을 듯. 주어진 오차 내에서 정수 해라는 것을 무시하고 문제를 해결한 다음 그 근처의 정수해를 택하지 않고서는 그 문제(쉽게 해결하려는)의 답은 그할 수 없는 것으로 알려져 있습니다. (제가 알기로는). 이런 종류(NP complete) 의 문제는 서로 다른 형태의 문제로 변환이 가능하여, 한가지만 푸는 방법을 찾아내더라도 다른 문제도 해결이 가능하다고들 합니다. 그런데, 아직도 쉽게 푸는 방법은 없다고 하지요. 인간이 직관으로 풀어나가는 것만이 빨리 해결하는 비결이라고 합니다. 안녕. -- Gyudong Kim % Dept. of Electronics, Seoul Nat'l Univ., Seoul 151-742, Korea chilly % Phone +82 2 880 7280; Fax +82 2 885 6993; Pager +82 12 845 3420 Fabiano % http://www.iclab.snu.ac.kr/~chilly, chilly@iclab.snu.ac.kr |