文章基本信息
- 标题：Applications of a special polynomial class of TSP
- 本地全文：下载
- 作者：Brimberg Jack ; Korach Ephraim ; Amami Mokhtar 等
- 期刊名称：Yugoslav Journal of Operations Research
- 印刷版ISSN：0354-0243
- 电子版ISSN：1820-743X
- 出版年度：2005
- 卷号：15
- 期号：1
- 页码：5-14
- DOI：10.2298/YJOR0501005B
- 出版社：Faculty of Organizational Sciences, Belgrade, Mihajlo Pupin Institute, Belgrade, Economics Institute, Belgrade, Faculty of Transport and Traffic Engineering, Belgrade, Faculty of Mechanical Engineering, Belgrade
- 摘要：
A hypothetical problem which we call a "buried treasure problem" is presented where the objective is to locate m objects among N fixed equi-spaced caches in order to minimize a measure of the risk of loss. The general problem is shown to be NP-hard. However, a sub problem may be solved as a special class of TSP in O (N log N) time. Several applications are noted.
- 关键词：partition problem; traveling salesman problem; pyramidal tours
