旅行推销员的最大化版本，您不必去某些节点并且可以通过多个路径？

Question

具体地说，我想使我的利润最大化。我从一个固定的节点(总部)开始，每次我去一个不同的节点，我都能获得一些利润(对于一个特定的节点，我只能获得一次利润，但我可以随心所欲地去那里旅行)。但是要到达任何一个节点，我都要付出一些代价(沿着每条路径旅行)。我想让我的收入最大化，然后回到总部。我可以不去一些节点，如果这会导致我的收入达到最大值(因为到达那里的成本)。我也可以在我的路线上多次经过路径。TSP有这样的版本吗?是可解的吗?(我在想Warshall’s可能适用)

Answer 1

下面是一些试图解决这个问题的未经测试的伪代码。你只需要不断尝试节点，直到达到利润限制。

Home = StartNode
Result = [Home]
MaxProfit = 0
Sub Solve(last, currentProfit, path, visitedSet)
  If currentProfit + graph.Nodes.Except(visitedSet).Sum(n => n.Profit) <= MaxProfit Then
    Return
  End If
  If node == Home AndAlso currentProfit > MaxProfit Then
    Result = path
    MaxProfit = currentProfit
  End If
  For Each node In graph.Nodes
    edge = graph.Edges.FirstOrDefault(e => e.Has(last) && e.Has(node))
    If edge Then
      profit = -edge.Cost
      If Not visitedSet.Contains(node) Then
        profit += node.Profit
      End If
      Solve(node, currentProfit + profit, path.Copy().Add(node), visitedSet.Copy().Add(node))
    End If
  Next
End Sub
Call Solve(Home, 0, [Home], [])

EDIT一个改进可能是预先计算从每个节点回家的最便宜路线，并使用它来细化利润约束。