The $n$-vehicle exploration problem (NVEP) is a combinatorial optimization problem, which tries to find an optimal permutation of a fleet to maximize the length traveled by the last vehicle. NVEP has a fractional form of objective function, and its computational complexity of general case remains open. We show that Hamiltonian Path $\leq_P$ NVEP, and prove that NVEP is NP-complete.


翻译:$n$-车辆探索问题(NVEP)是一个组合优化问题,其目标是找到一种最佳的车队排列方式,使得最后的车辆行驶长度最大化。NVEP的目标函数具有分数形式,它的一般情况的计算复杂度仍然未知。我们证明了哈密尔顿路径$\leq _P$ NVEP,并证明了NVEP是NP完备的。

0
下载
关闭预览

相关内容

战术先验知识启发的多智能体双层强化学习
专知会员服务
106+阅读 · 2023年5月9日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
NP完备破解羊了个羊?
新智元
0+阅读 · 2022年10月10日
灾难性遗忘问题新视角:迁移-干扰平衡
CreateAMind
17+阅读 · 2019年7月6日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
vae 相关论文 表示学习 1
CreateAMind
12+阅读 · 2018年9月6日
【推荐】深度学习目标检测概览
机器学习研究会
10+阅读 · 2017年9月1日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
5+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2023年5月24日
VIP会员
相关资讯
NP完备破解羊了个羊?
新智元
0+阅读 · 2022年10月10日
灾难性遗忘问题新视角:迁移-干扰平衡
CreateAMind
17+阅读 · 2019年7月6日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
vae 相关论文 表示学习 1
CreateAMind
12+阅读 · 2018年9月6日
【推荐】深度学习目标检测概览
机器学习研究会
10+阅读 · 2017年9月1日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
5+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员