基于行驶公交车段判断午夜时间的算法

Question

我正在编写一个从公交公司获取信息并以下列格式提供的导入器:1. 站点用索引从 0 到 n (0,1,2,3,4,5... etc) 进行编号

1. 提供商发送一个分段列表:0->1,0->3,4->5 等，代表站点之间的行程。每个站点至少提供一个段。

2. 每个段都有一个整数，表示时间经过午夜的次数。

所以这里有几个例子:示例 1:

0->2: 1

0->3: 1

1->2: 0

1->3: 0

这实际上意味着午夜只在站点 0 和站点 1 之间出现一次。

示例 2:

0->2: 1

1->3: 1

2->3: 0

这意味着午夜在车站 1 和车站 2 之间只出现一次

在某些情况下，信息可能不足以找到所有午夜过境点，在这种情况下应跳过目的地。

是否有算法可以发现这些东西？

到目前为止我的尝试:我发现如果我为第二个示例布置所有站点，例如:

0--------1--------2--------3

然后我对 0-2 和 1-3 应用最大交叉点，这意味着:

0->1 has between 0 and 1 crossings

1->2 has between 0 and 1 crossings

2->3 has between 0 and 1 crossings

之后我应用第三条规则 - 2->3 有 0 个交叉点，这让我得到:

0->1: 0,1

1->2: 0,1

2->3: 0

这给了我以下组合:

0,0,0

0,1,1

1,1,0

1,0,0

然后我再次应用规则(位置 1 + 位置 2 应为 1，位置 2 + 位置 3 应为 1)，我只剩下:

0,1,0

这意味着午夜在车站 1 和车站 2 之间出现一次

但是，这种方法需要生成数字之间所有可能的组合，这不适用于编程算法。每个路段有可能有 0、1、2、3 和 20 个站点，即 4 的 20 次方组合。

是否有人对如何执行此操作有其他想法？

Answer 1

您可以使用 Guaussian elimination 将其作为联立方程组求解.

相邻车站之间午夜交叉点的数量是您的变量，您的系数对于路段中包含的每对车站仅为 1，否则为 0。

以第二个例子为例:

0->2: 1

1->3: 1

2->3: 0

将 0->1 视为变量 a，将 1->2 视为变量 b，将 2->3 视为变量 c，则可以重写为:

a + b = 1

b + c = 1

c = 0

或者矩阵形式为

[ 1 1 0 ] [ a ]   [ 1 ]
[ 0 1 1 ] [ b ] = [ 1 ]
[ 0 0 1 ] [ c ]   [ 0 ]

(矩阵中的列数应等于相邻站点对的数量，行数是您拥有的方程式的数量)。求解 a、b、c 以找出每对车站之间的午夜交叉点数。

你有一个额外的约束，即值是非负的，所以例如如果 a + b = 0 你知道 a 和 b 都为零，因为不可能一个为正而另一个为负。因此，您可以将 a = 0 和 b = 0 作为另外两个方程添加到您的系统中。