| [ QuizWit ] in KIDS 글 쓴 이(By): fox (혼 돈) 날 짜 (Date): 1998년 6월 29일 월요일 오후 02시 45분 39초 제 목(Title): Re: [문제] 땅파기? 일단 네개를 잇는 최소의 방법인 다음 그림을 그린다. A B \ / \ / E------F / \ / \ C D 여기서 B-F를 떼어내고 AF를 잇는 선에 대한 수선을 B에서 그리고 (AF와 만날때까지만) C-E도 마찬가지로 떼어내고 ED에 대한 수선을 내리면 (참고:각 BFA와 CED는 직각이 아니고 그보다 약간 작습니다.) 원래의 것보다 약간 (아주아주아주 약간) 짧게 되죠 그리고 모든 전선을 알아낼 수 있습니다. 멋진 문제군요! 일단 이건 문제에 합당하긴 한데... 최소인지의 증명은 잘 못하겠네요. 꼭 알레프 쓰는거 같다. 대략 저 방법으로는 최소일거 같은데... 참고로 네점을 잇는 방법의 확장은, 결과로 나타난 선분들에 대해 만나는 두선분의 각은 최소 120도 이다. 이거하고 약간 렘마 수준을 덧붙이면 exponential time algorithm은 쉽게 구했던 것 같고 임의의 n개의 점에 대해 최소 연결 방법은 np-hard라고 합니다. (기억이 맞나???) 고럼. |