algorithm - Travelling Salesman 的最大化版本，您不必前往某些节点并且可以通过多条路径？

Question

具体来说，我想最大化我的利润。我从一个前缀节点(总部)开始，每次去到不同的节点都会获得一些利润(对于一个特定的节点，我只能获得一次这个利润，但我可以去那里多次)。但是要到达任何节点，我都要付出一些代价(沿着每条路径行进)。我想最大化我的收入并返回总部。如果这会导致我的收入最大化(因为到达那里的成本)，我可以不去某些节点。我也可以在路线上多次遍历路径。有这样的TSP版本吗？可以解决吗？ (我在想 Warshall 的可能适用)。

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], [])

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