우리는 그래프를 탐색하기 위한 다양한 자연스러운 노드 기반 및 간선 기반 국소 전략에 대한 하한을 제시한다. 본 연구는 이 문제를 임의의 그래프의 맥락에서뿐 아니라 로봇에 의한 공간의 기하학적 탐색이라는 추상화에서도 다룬다. 두 경우 모두 이전에 광범위하게 연구되어 왔다. 우리는 탐색 경로에서 다음 단계를 선택하기 위해 마지막 방문 시각(time-of-last-visit) 또는 대안적으로 가장 덜 빈번하게 방문된(least-frequently-visited) 지역적 탐욕 전략을 사용하는 국소 탐색 정책을 고려한다. 이 두 전략은 이전에 Cooper et al. (2011)이 간선에 마지막 방문 또는 방문 빈도에 대한 카운터가 부착된 시나리오에 대해 고려한 바 있다. 본 연구에서는 카운터가 노드에 연관되는 경우를 다루며, 이는 기하학적 공간의 이중 그래프(dual graphs)에서는 직관적으로 더 자연스럽고 또한 더 효율적일 가능성이 있다고 주장할 수 있다. 그런데도 놀랍게도, 이러한 대안적 전략들은 탐색에 대해 최악의 경우 초다항/지수 시간의 성능을 보이는 반면, 간선에 대한 가장 덜 빈번하게 방문된 전략은 Cooper et al. (2011)이 제시한 바와 같이 다항식으로 상계되는 탐색 시간을 갖는다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.