yg2356   6달 전

문제를 품에 있어서 제3자가 필요한 상황이라고 생각을 못했는데 

왜 제3자를 도입해야만 하는건가요?

이 부분이 이해가 잘 가지 않습니다.

byeongkeunahn   6달 전

이 문제를 풀어보지는 않았지만 최적해를 분류해보면 다음과 같습니다.

  • 두 죄수가 서로 독립된 경로로 빠져나가는 경우
  • 두 죄수 중 한 죄수가 다른 죄수 위치로 이동하고, 둘이 같이 빠져나가는 경우
  • 두 죄수가 이동하다가 중간에서 만나서 같이 빠져나가는 경우

첫 번째와 두 번째 경우는 죄수가 한 명만 있는 경우처럼 풀 수 있습니다.

따라서 세 번째 경우가 중요합니다.

그런데 세 번째 경우는 결국 그 중간에서 만나는 위치가 중요하게 됩니다.

중간에서 만나는 위치를 P로 고정했다고 하면, 최적해는 결국 두 죄수를 P로 끌고 오는 최소비용에 P와 밖을 연결하는 최소비용으로 주어지게 됩니다.

아마도 이 P를 제3자라고 말씀하신 것 같네요.

도움이 되셨기를 바랍니다!

yg2356   6달 전

네 너무 감사드립니다. 

댓글을 작성하려면 로그인해야 합니다.