Online searching
成果类型：
Article
署名作者：
Jaillet, P; Stafford, M
署名单位：
University of Texas System; University of Texas Austin; University of Texas System; University of Texas Austin
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.49.4.501.11227
发表日期：
2001
页码：
501-515
关键词：
摘要：
We consider the problem of searching m branches which, with the exception of a common source s, are disjoint (hereafter called concurrent branches). A searcher, starting at s, must find a given exit t whose location, unknown to the searcher, is on one of the m branches. The problem is to find a strategy that minimizes the worst-case ratio between the total distance traveled and the length of the shortest path from s to t. Additional information may be available to the searcher before he begins his search, In addition to finding optimal or near optimal deterministic online algorithms for these problems, this paper addresses the value of getting additional information before starting the search.