创建公交路线

什么是可用于创建公交路线的好算法或一类算法？创建公交路线

我在考虑用来解决旅行推销员或哈密尔顿路径问题的算法，但事实上，这两个问题都没有解决如何在两站之间移动的问题。

我想算法至少有以下特点：

产生一个相对优化的路径（我的理解，这个问题可能是NP完全，所以一个好的启发式是罚款）
能处理具有不同权重的路径部分（例如，在该路径的该部分上行进的时间）
可以被迫使用给定的起点和终点（我认为这不会是这样的问题）

可以做到这一点的代码，或类似的东西，将不胜感激（尤其是在C＃中），但一个好的算法本身就没有问题。

注意：虽然有很多算法可以找到两点之间的最短路径，但我不知道我希望停止的顺序。因此，除非我应该使用两种算法的组合（我怀疑是这种情况），那些算法不会做我想做的事情（如果您认为他们这样做，请解释）。

编辑：假设我知道所有需要做的停靠点。

来源

2012-01-01 soandos

看来，这样做的方法涉及使用Floyd-Warshall算法，然后使用一种算法来解决旅行商问题。

这解决了所有“可选”顶点（交叉点）的问题，并使用旅行推销员算法来确定停靠点的命中顺序。

来源

2012-01-01 04:08:47 soandos

我用Djikstra的算法：http://en.wikipedia.org/wiki/Dijkstras_algorithm

沿着边缘行进的成本不只是距离，但直到“下一个”总线从给定节点出发，也与时间有关。注意：当它停在一个节点时，你可能已经在总线上了。

来源

2012-01-01 00:22:49

我想你误会了。我不想搭公车，我想创建公交路线。不知道Djisksra如何在这种情况下工作... – soandos 2012-01-01 00:24:19

请参阅编辑。我不认为你的答案适用。 – soandos 2012-01-01 00:29:32

我仍然不明白，我仍然认为Dijkstra的算法适用，因为它告诉你要制造的停止。所有的道路通向罗马，迪杰斯特拉的算法告诉你最好的。虽然维基百科指的是最短路径，但算法实际上适用于最低成本。所以应用与您的标准相关的成本。如果您想知道每个节点中有多少人，请将其作为您的标准添加，并且这应该告诉您从A到B的最佳路径，以便您可以捡到最多的人。 – 2012-01-01 09:17:55

您可以在这里稍微修改/假设使用旅行推销员算法来解决点＃2（具有不同权重的路径的一部分）。

比方说，从点路径“A”至“B”点有2个权重（比如说，交通在某个时间点）

即使它的单一路径，我们可以假设一个简化的问题“虚拟顶点“，在”A“和”B“之间的点”C“，其在每个边中将具有固定的权重。

A -------重量= 10 ------ ------ c ^重量= 15 ------乙

在这个新的曲线图中，运行该旅行推销员算法。

来源

2012-01-01 00:28:59

我想你明白了。这个问题使得这个问题与旅行商不同（正如我理解的那样，如果我错了，请纠正我）是有很多顶点我不需要命中（即每个未使用的交点）。有旅行推销员算法可以做到这一点吗？ – soandos 2012-01-01 00:31:37

那么，如果你绝对不需要顶点命中，那么你可以将通向该顶点的所有边的权重增加到“无穷大”，并且推销员问题机制将“自然地”避开那些边。你的想法？ – 2012-01-01 00:37:05

图上的所有交点都应该是虚拟顶点。他们应该有选择地被击中，而不是从未被击中，或总是被击中。 – soandos 2012-01-01 00:39:21

公交路线是由人而不是电脑创建的。只有人知道谁需要去哪里以及经常出差。您至少需要这样的数据来思考如何找到最适合人们需求的路线。关于这一点，我认为你的问题是不明确的。

来源

2012-01-01 00:32:53

请参阅编辑以获得澄清，但我认为您不正确。我不希望一个计划告诉我停车位应该在哪里，但是按照什么顺序，以及在每一站停车的路径。这似乎是一个非常明确的问题对我来说...... – soandos 2012-01-01 00:35:10

关键是你需要*定义约束* - 并且有**几十个** - 然后只是应用Dijkstra的算法。 – 2012-01-01 00:39:19

Dijkstra算法适用于两点之间的最短路径。对于这个问题（正如我看到的那样，如果我错了，请纠正）我首先需要确定点的命中顺序。迪克斯特拉不会这样做。 – soandos 2012-01-01 00:40:52

创建公交路线

回答

相关问题