| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2000년 12월 4일 월요일 오후 03시 41분 12초 제 목(Title): Re: 꼬마들 줄을 어떻게 세워야 하나? 어떤 아이 x의 친구들의 집합을 F(x)라 하고, x가 대열의 pi(x) 번째 선다고 해 봅시다. 그러면 이 문제는 MIN SUM SUM | pi(x) - pi(y) | 쯤으로 모델링할 수 x y in F(x) 있을 듯 싶습니다. (친구들끼리의 거리의 합이 최소화!) 이렇게 하면 회로 배선 문제의 고전이 됩니다. Minimum Linear Arrangement 문제죠. NP optimization 문제입니다. http://www.nada.kth.se/~viggo/wwwcompendium/node55.html -- 박.. |