我有这个图表问题，我有许多节点（公交车站）和一些特殊节点（公交车站），我必须覆盖所有节点 - 分配覆盖所有节点的公交路线 - 在车站开始和结束时我对可以使用的总线数量有一些限制，我应该如何开始？
问问题
1199 次
2 回答
1
寻找连接所有节点的最短路径（有公共汽车站限制）的问题可以从旅行推销员问题减少：给定一个 TSP 问题，用 1/2 个车站/“特殊节点创建这个问题的实例"（取决于你是否可以回到同一个车站）。
使用这种减少 - 如果这个问题是多项式可解决的 - TSP 也是如此。
因此 - 问题是NP-Hard，并且没有已知的多项式解决方案（假设是 - 一个不存在，尽管尚未证明）
一些替代方法是启发式算法，例如遗传算法和爬山算法，近似算法或指数算法（如果数据相对较小，可用于找到最佳解决方案），例如动态规划或分支定界。
编辑：（回复已编辑的问题）
即使您可以使用多条总线 - 但数量有限- 问题仍然是 NP-Hard，因为（假设总线的数量是恒定的/在一元编码中给出）：您可以将图形“复制”到k不同的组件（有限数量的公共汽车在哪里k） - 每个组件都有一个新的 TSP 问题。
于 2012-11-25T15:20:38.360 回答
0
这是一个简单的想法：
- 从图中删除开始和结束节点。
- 搜索最小生成树
- 将起始节点连接到生成树。
有了它，您可以获得最小的封面解决方案。
当然，如果您需要访问每个节点一次，那么如上所述，这是一个 NP-Hard 问题。
于 2012-11-25T15:23:54.293 回答