랑데부 문제

Rendezvous problem

랑데부 딜레마는 논리적인 딜레마이며, 일반적으로 다음과 같이 표현됩니다.

두 사람은 한번도 가본 적이 없는 공원에서 데이트를 한다.따로따로 공원에 도착한 두 사람 모두 이곳이 넓은 지역이어서 서로를 찾을 수 없다는 것을 알고 놀란다.이 상황에서 각자는 상대방이 자신을 찾을 수 있기를 바라며 정해진 장소에서 기다리거나 아니면 어딘가에서 기다리기로 선택했다는 희망으로 상대방을 찾기 시작해야 한다.

둘 다 기다리기로 하면 절대 만나지 않을 거야.두 사람 모두 걷기를 선택한다면 만날 확률과 그렇지 않을 확률이 있습니다.만약 한 사람이 기다리기로 하고 다른 한 사람이 걷기를 선택한다면, 그들이 결국 만나게 될 것이라는 이론적인 확실성이 있다. 하지만, 실제로는, 그것이 보장되기까지 너무 오래 걸릴 수도 있다.그렇다면, 제기되는 질문은, 그들이 만날 확률을 최대화하기 위해 어떤 전략을 선택해야 하는가이다.

이러한 종류의 문제의 예로는 랑데부 문제가 있습니다.이 문제들은 1976년 [1]Steve Alpern에 의해 비공식적으로 처음 소개되었고,[2] 그는 1995년에 문제의 연속 버전을 공식화하였다.이것은 랑데부 검색에 [3]대한 많은 최근의 연구로 이어졌다.심지어 n개의 개별적인 장소에서 연주되는 대칭적인 랑데부 문제([4]모차르트 카페 랑데부 문제라고도 불린다)도 해결하기 매우 어려운 것으로 밝혀졌고, 1990년에 리차드 웨버와 에디 앤더슨은 최적의 [5]전략을 추측했다.2012년 리처드 [6]웨버에 의해 n = 3에 대한 추측이 입증되었다.이것은 완전히 해결된 최초의 사소한 대칭 랑데부 검색 문제였다.대응하는 비대칭 랑데부 문제에는, 최적인 간단한 해결책이 있습니다.즉, 한쪽 플레이어는 그대로 있고 다른 한쪽 플레이어는 로케이션의 랜덤 순열을 방문합니다.

랑데부 문제에는 이론적으로 중요한 문제일 뿐만 아니라 동기화, 운영 체제 설계, 운영 연구, 심지어 탐색 및 구조 운영 계획 분야의 애플리케이션에 대한 실제 문제가 포함됩니다.

결정론적 랑데부 문제

주요 기사:결정론적 랑데부 문제

결정론적 랑데부 문제는 플레이어 또는 로봇이 결정론적 명령 시퀀스를 따라 서로를 찾아야 하는 랑데부 문제의 변형이다.각 로봇은 동일한 지침 시퀀스를 따르지만 대칭 [7]깨짐에는 각 로봇에 할당된 고유한 라벨이 사용됩니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ 를 클릭합니다Alpern, Steve (1976), Hide and Seek Games, Seminar, Institut fur Hohere Studien, Wien, 26 July.
  2. ^ Alpern, Steve (1995), "The rendezvous search problem", SIAM Journal on Control and Optimization, 33 (3): 673–683, doi:10.1137/S0363012993249195, MR 1327232
  3. ^ 를 클릭합니다Alpern, Steve; Gal, Shmuel (2003), The Theory of Search Games and Rendezvous, International Series in Operations Research & Management Science, vol. 55, Boston, MA: Kluwer Academic Publishers, ISBN 0-7923-7468-1, MR 2005053.
  4. ^ 를 클릭합니다Alpern, Steve (2011), "Rendezvous search games", in Cochran, James J. (ed.), Wiley Encyclopedia of Operations Research and Management Science, Wiley, doi:10.1002/9780470400531.eorms0720.
  5. ^ 를 클릭합니다Anderson, E. J.; Weber, R. R. (1990), "The rendezvous problem on discrete locations", Journal of Applied Probability, 27 (4): 839–851, doi:10.2307/3214827, JSTOR 3214827, MR 1077533.
  6. ^ 를 클릭합니다Weber, Richard (2012), "Optimal symmetric Rendezvous search on three locations" (PDF), Mathematics of Operations Research, 37 (1): 111–122, doi:10.1287/moor.1110.0528, MR 2891149.
  7. ^ Ta-Shma, Amnon; Zwick, Uri (April 2014). "Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences". ACM Transactions on Algorithms. 10 (3). 12. doi:10.1145/2601068. S2CID 10718957.