검색 게임

Search game

검색 게임은 검색 공간이라고 불리는 세트에서 일어나는 2인용 제로섬 게임이다.검색자는 최대 속도 구속조건을 따르는 모든 연속 궤적을 선택할 수 있다.탐색자나 히더 모두 그들의 거리가 발견 반지름보다 작거나 같을 때까지 상대 선수의 움직임에 대한 지식을 가지고 있지 않고 바로 이 순간에 포획이 일어난다고 항상 가정한다.수학적 모델로서, 검색 게임은 아이들이 하는 숨바꼭질 게임이나 일부 전술적 군사 상황을 나타내는 것과 같은 분야에 적용될 수 있다.검색 게임의 영역은 루푸스 아이작스의 고전인 "차등 게임"[1]의 마지막 장에 소개되었고 슈무엘 갈과[2][3] 스티브 알펜에 의해 더 발전되었다.[3]공주와 괴물 게임은 움직이는 표적을 다룬다.

, 전략

그래프에서 정지해 있는 표적을 검색하는 자연스러운 전략은 그래프의 모든 호를 덮는 최소한의 닫힌 곡선 L을 찾는 것이다.(L을 중국 우체부 투어라고 한다.)그런 다음 각 방향에 대해 확률 1/2로 L을 통과시킨다.이 전략은 그래프가 오일러식이라면 효과가 좋은 것 같다.일반적으로 이 무작위 중국 우체부 투어는 그래프가 나무와 같은 구조로 연결된 오일러 그래프 세트로 구성된 경우에만 최적의 검색 전략이다.[4]이 패밀리에 포함되지 않은 그래프의 오해의 소지가 있을 정도로 간단한 예는 세 개의 호로 연결된 두 개의 노드로 구성된다.무작위 중국 우체부 투어(임의 순서에 따라 3개의 호를 가로지르는 것과 동일)는 최적이 아니며, 이 3개의 호를 검색하는 최적의 방법은 복잡하다.[2]

바인딩되지 않은 도메인

일반적으로 온라인 알고리즘의 경우와 같이 무한 영역을 검색하기 위한 합리적인 프레임워크는 표준화된 비용 함수(컴퓨터 과학 문헌의 경쟁률이라고 함)를 사용하는 것이다.이러한 유형의 문제에 대한 미니맥스 궤적은 항상 기하학적 시퀀스(또는 연속적인 문제에 대한 지수 함수)이다.이 결과는 전체 궤적 공간을 탐색하는 대신 단일 매개변수(이 시퀀스의 생성기)를 최소화함으로써 미니맥스 궤적을 쉽게 찾을 수 있는 방법을 산출한다.이 도구는 선형 검색 문제, 즉 무한선에서 대상을 찾는 데 사용되어 왔으며, 이는 수십 년 동안 많은 관심을 끌었고 검색 게임으로 분석되어 왔다.[5]그것은 또한 동시 광선 세트를 검색하기 위한 미니맥스 궤적을 찾는 데 사용되었다.평면에서 최적의 검색은 지수 나선형을 사용하여 수행된다.[2][3][6]동시 광선 세트를 검색하는 것은 나중에 컴퓨터 과학 문헌에서 '소경로 문제'로 재발견되었다.[7]

참조

  1. ^ 루퍼스 아이작스, 차등 게임스, 존 와일리 앤 선스, (1965)
  2. ^ a b c S. Gal, Search Games, Academic Press, New York (1980)
  3. ^ a b c S. Alpern과 S. Gal, Theory of Search Games and Rendevous, Springer(2003).
  4. ^ Gal, Shmuel (2001). "On the optimality of a simple strategy for searching graphs". International Journal of Game Theory. 29: 533–542. doi:10.1007/s001820000056.
  5. ^ Beck, Anatole; Newman, D.J. (1970). "Yet More on the linear search problem". Israel Journal of Mathematics. 8: 419–429. doi:10.1007/BF02798690.
  6. ^ M. Chrobak, 괴물 소를 찾아 안개 속을 헤엄치는 공주 ACM Sigact 뉴스, 35(2), 74–78(2004).
  7. ^ MY Kao, JH Reif 및 SR Tate, 알 수 없는 환경에서 검색: 젖소 경로 문제에 대한 최적의 무작위 알고리즘, SODA 1993.