图中最有意义的路径 [英] Most rewarding path in a graph

问题描述

我遇到了以下问题：

鉴于

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

$ b

• 问题1：给定时间段T，找到图中最有回报的路径
  
• 问题2：给定时间段T，找到图中最有回报的周期（在时间段T之后，代理人必须再次在起点）。
  
  
  

  注意：

  
  
  
  
  
  • 如果边缘部分穿过，奖励与所遍历的部分
    
  • 对于每个遍历的边（或部分），奖励只能声明一次。
    
  • 路径/循环可以在任何给定点开始（无论是在顶点还是沿着边缘）
  
  
  
  
  

  我的问题：

  
  
  
  
  
  • 这是一个已知的问题（它是否有名字？ ）
    
  • 它是NP-hard吗？
  
  
  • 任何想法如何处理它？<​​/ li>
    
  
  
  

  已知的相关问题： 定向问题 - 奖励是基于顶点的（）。在我的情况下，奖励是基于边缘的。 盈利的Arc Tour问题 - 目标是在图表中找到一组循环，以最大限度地收集利润减去差旅费用。
  

• 编辑： 带利润的无向带电弧路由问题 - 非常类似于我的问题，但是给出了一个仓库顶点（每个周期的开始和结束），三角形不等式得到满足，问题被推广到一组代理，所有代理都在同一个仓库开始和结束）。
  

解决方案

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

问题你表示必须是NP-hard也是。

I'm faced with the following problem:

Given

• An undirected graph, where each edge E has:
  • Et - the time it takes to traverse E
  • Er - the reward for traversing E

Goal:

• Problem 1: Given time period T, find the most rewarding path in the graph
• Problem 2: Given time period T, find the most rewarding cycle in the graph (after period T, the agent must be at the start-point again).

Notes:

• If an edge is partially traversed, the reward is proportional the the portion traversed
• Reward can be claimed only once for each edge traversed (or portion of)
• A path/cycle may start at any given point (either on a vertex, or along an edge)

My questions:

• Is this a known problem (Does it has a name? Has it been studied before?).
• Is it NP-hard?
• Any ideas how to approach it?

Known Related Problems:

• The orienteering problem - Rewards are vertex-based (). In my case, the rewards are edge-based.
• Profitable Arc Tour Problem - The objective is to find a set of cycles in the graph that maximizes the collection of profit minus travel costs.
• Edit: The Undirected Capacitated Arc Routing Problem with Profits - Quite similar to my problem, but a depot vertex (start,end of each cycle) is given, the triangle inequality is satisfied, and the problem is generalized to a set of agents, all starting and ending at the same depot).

解决方案

This one reminded me this well known NP-hard problem http://en.wikipedia.org/wiki/Longest_path_problem

The problem you denoted must be NP-hard too.

这篇关于图中最有意义的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！