英文:
Weighted Graph with arbitrary start/end points
问题
我有几百个节点。
每个节点都有一个表示访问它有多大益处的值。
每个节点之间都有一些其他节点的距离。可以沿着这些边双向旅行（带权重的双向边）。
我可以从任何节点开始。
我可以重访现有节点，但只能在经过11步之后才能这样做。
换句话说，我正在寻找至少包含11个节点的循环，以提供最高的价值/距离比率。
我对图论了解甚微，只足够知道如何描述这个问题，但完全不足够了解如何以半有效的方式解决它。老实说，我甚至不确定将这些数据视为图是否有用，或者是否应该将其重新表述为其他类型的问题（组合学？）。
如果存在用于解决这种问题的算法，或者只是类似问题的文献，我会很乐意得到指引。
英文:
I have a few hundred nodes.
Each node has a value for how beneficial it is to visit it.
Each node has a set distance between some number of other nodes. Travel is permitted in both ways along these edges. (Weighted bi-directional edges)
I can start at any node I desire.
I CAN revisit existing nodes, but only after 11 steps.
So in other words, I am looking for the cycle of at least 11 nodes which provides the highest Value/Distance ratio.
I am barely familiar enough with graph theory to know how to describe this problem, and not at all familiar enough to know how to solve it in any semi-efficient manner. I'm honestly not even sure thinking about this data as a graph is useful at all, or if I should be rephrasing this as a some other kind of problem (Combinatorics?)
If there exists algorithms to solve this kind of problem, or even just literature on similar problems I could study, I would love to be pointed in that direction.
答案1
得分: 3
这是旅行商问题的一种变体。
TSP问题很难解决，即使没有您所提及的额外约束。有各种方法可以获得近似解，而且在合理的时间内相对接近最优解。通常这涉及到某种形式的“找到最近或最有价值的下一个点”。具体的方法取决于输入数据的细节。您是希望获得近似解，还是坚持要求最优解呢？
以下是一种近似算法的示例，您可以使用它来快速获得一个可行但价值相对不错的解决方案。该算法假定您的输入图是“度量的”——意味着在所有A、B、C的情况下，没有快捷方式A到B总是比A到C到B短。您的输入数据是这样的吗？
- 选择最有价值的11个节点
- 使用Dijkstra算法找到这11个节点之间的最短路径。
- 创建一个新图，其中只包含这11个节点，它们之间的链接由Dijkstra路径的成本确定。
- 对这11个选定的节点应用TSP算法的度量近似。
- 将TSP路径映射回原始图。
也许如果您将您的输入发布在某个地方并提供一个链接会更容易处理。有许多合理的格式化输入的方法。我更喜欢使用空格分隔的文本文件——就像这样：https://github.com/JamesBremner/PathFinder3/wiki/Sales
英文:
This is a variation on the travelling salesman problem.
The TSP is a very hard problem to solve, even without the extra constraints you have here. There are various ways to get an approximate solution, fairly close to the optimum, in a reasonable amount of time. Generally this is some kind of 'find nearest or most valuable next point'. The details depend on the details of your input data. Would you be interested in approximate solutions, or do you insist on getting the optimum?
Here is an example of the kind of approximation algorithm you can use to get a quick and dirty feasible solution with a worthwhile value. It assumes that your input graph is "metric" - meaning there are no shortcuts A to B is always shorter than A to C to B for all A,B,C. Is your input like that?
- Select the 11 most valuable nodes
- Use the Dijkstra algorithm to find the shortest path between every pair of the 11 nodes.
- Create a new graph with just the 11 nodes and links between them costed with the Dijsktra path costs.
- Apply the metric approximation of the TSP algorithm to the 11 selected nodes.
- Map the the TSP path back on to the original graph.
Perhaps it would be easiest if you just posted your input somewhere and provide a link. There are numerous sensible ways to format the input. I prefer a space delimited text file - like this: https://github.com/JamesBremner/PathFinder3/wiki/Sales
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论