하노이탑 문제에서 기둥의 개수..

  • Chevalier
    Chevalier

    하노이탑 문제를 공부하고 있는데요,
    기둥 4개..를 넘어 5개를 풀어야 하는데..
    쉽지 않네요.
    어떤 식으로 풀어야 할까요?
    점화식을 아시는 분 있으신가요?

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]


    13년 전
7개의 댓글이 있습니다.
  • Kyungryeol
    Kyungryeol

    a[n][k] = "n개의 disc와 k개의 pole을 이용해서 문제를 풀 때의 최소 이동 수"
    로 가정하고 동적계획법을 사용하여 풀 수 있습니다.
    http://acm.zju.edu.cn/show_problem.php?pid=2338


    13년 전 link
  • helloneo
    helloneo

    KLDP에서 본글이 여기도 있군요.. 음.. 숙제인가.. -_-?


    13년 전 link
  • Yongrok
    Yongrok

    저도 KLDP에서 글 봤는데 여기도 올라왔었군요 ㅋㅋ


    13년 전 link
  • JongMan
    JongMan

    ㅎㅎㅎㅎㅎ 숙제맞는듯? ^^
    그나저나 경렬님, 점화식 좀 더 설명해 주세요 ~ 잘 모르겠다능..


    13년 전 link
  • Chevalier
    Chevalier

    저도 검색하다가 KLDP에서 봤었는데요,
    '숙제'는 아닙니다.ㅋㅋ
    재귀로 돌렸더니, 디스크 10000개 일 때 25분쯤 걸려서요..ㄷㄷ
    좋은 점화식을 찾아볼랬죠.ㅋ


    13년 전 link
  • Kyungryeol
    Kyungryeol

    a[n][k] = "n개의 disc와 k개의 pole을 이용해서 문제를 풀 때의 최소 이동 수" 로 가정하겠습니다.
    먼저 일반적인 하노이 탑 문제를 살펴보겠습니다.
    문제는 어느 한 pole (pole A) 에서 다른 pole (pole B) 로 n개의 disc를 옮겨야 하는 것입니다.
    그 과정으로 다른 하나의 pole (pole C) 에 n-1개의 disc를 임시로 옮겨놓고
    가장 큰 disc를 pole A 에서 pole B로 옮긴 다음
    다시 n-1개의 disc를 pole C 에서 pole B로 옮기는 것입니다.
    즉, 옮기는 횟수의 점화식은 a[n][3] = a[n-1][3] + 1 + a[n-1][3] = 2*a[n-1][3]+1 이 됩니다.
    여기서 1은 엄밀히 말하면 a[1][2] 가 되겠습니다.
    a[1][3] = 1 이기 때문에 점화식을 풀면 a[n][3] = 2^n-1 이 되는 것이죠.
    자 그럼 과연 k가 3 이상일 때는 점화식이 어떻게 될까요?
    a[n][k] = min (a[j][k] + a[n-j][k-1] + a[j][k]), (1 <= j < n)
    이런 형식이 되겠습니다.
    먼저 j개의 disc를 어느 빈 pole에 옮기고 (a[j][k])
    나머지 n-j개의 disc를 목표 pole에 옮깁니다 (a[n-j][k-1])
    이 때, j개의 disc가 있는 pole을 이용할 수 없기 때문에 이용할 수 있는 pole의 수는 k-1 입니다.
    그리고 다시 j개의 disc를 목표 pole에 옮기는 것이죠 (a[j][k])
    이상 n개의 disc와 k개의 pole을 이용한 하노이 탑 점화식 설명이었습니다.


    13년 전 link
  • Being
    Being

    제가 알기로, 구경렬님이 제시하신 점화식은 '가설'입니다. 즉, 최적해인지 증명은 되지 않았습니다. 그러나 알려진 최적해이므로 아마도 최적해가 아닐까 하고 생각되고 있습니다.
    기본적인 아이디어는 과연 몇 개의 디스크를 덜어서 옮길 것인가 하는 것입니다. 기둥 3개짜리 하노이 탑에서는 항상 N-1개의 디스크를 덜어서 다른 곳에 임시로 옮겨 두고, 가장 큰 디스크를 타겟 기둥에 옮겼어야 하죠. 기둥이 여러 개인 경우, 임시로 작은 j개의 디스크를 옮겨 둔 뒤 큰 N-j개의 디스크를 타겟 기둥에 옮기고 옮겨둔 디스크들을 가져오는 거죠.


    13년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.