algorithm - 图中最有值(value)的路径

Question

我遇到了以下问题:

给定

• 一个无向图，其中每条边 E 具有:
  • Et - 遍历E所需的时间
  • Er - 遍历 E 的奖励

目标:

• 问题 1:给定时间段 T，找到图中最有值(value)的路径
• 问题 2:给定时间段 T，找到图中最有值(value)的循环(在时间段 T 之后，智能体必须再次处于起点)。

注意事项:

• 如果一条边被部分遍历，则奖励与遍历的部分成正比
• 每遍历(或部分)边只能领取一次奖励
• 路径/循环可以从任何给定点开始(在顶点或沿边)

我的问题:

• 这是一个已知问题吗(它有名字吗？以前研究过吗？)。
• 它是 NP 难的吗？
• 对如何处理它有任何想法吗？

已知相关问题:

• The orienteering problem - 奖励是基于顶点的 ()。就我而言，奖励是基于边缘的。
• Profitable Arc Tour Problem - 目标是在图中找到一组循环，使利润减去旅行成本的集合最大化。
• 编辑: The Undirected Capacitated Arc Routing Problem with Profits - 与我的问题非常相似，但给出了一个仓库顶点(每个循环的开始、结束)，三角不等式得到满足，问题被推广到一组代理，所有代理都在同一个仓库开始和结束。

Answer 1

这个让我想起了这个众所周知的 NP-hard 问题 http://en.wikipedia.org/wiki/Longest_path_problem

你指出的问题也必须是 NP-hard。