最小化矩阵中总线变化的数量

Question

[ 42,  45,  47,  x,  x] -> stop1 to stop2
[ 45,  47,  42,  88,  x] -> stop2 to stop3
[ 21,  77,  42,  x,  x] -> stop3 to stop4
[ 22,  47,  42,  88,  x] -> stop4 to stop5
[ 23,  47,  42,  x,  x] -> stop5 to stop6
[ 24,  47,  42,  8,  91] -> stop6 to stop7
[ 25,  13,  42,  3,  84] -> stop7 to stop8
[ 26,  10,  11,  4,  54] -> stop8 to stop9
[ 27,  9,  8,  88,   71] -> stop9 to stop10

x is there just for formatting. The first row means that there are only three buses from stop1 to stop2(42, 45, 47).

我有这个类似矩阵的结构，其中每一行代表从一站到另一站的公共汽车。我需要尽量减少一个人从 stop1 到 stop10 的公交车换乘次数。

例如，其中一个输出应该是 42, 42, 42, 42, 42, 42, 42, 26, 27 另一个可以是 42, 42, 42, 42, 42, 42, 42, 10, 9 .如果变化的次数超过三个我可以丢弃结果

实现此目标的最佳方法是什么，因为现在强制通过它非常低效？

Answer 1

您可以通过将其建模为图形搜索来解决此问题。

假设您是一个人，您正试图从 A 点到达 B 点。与您最相关的信息是

您目前所在的位置，以及
您目前乘坐的是哪条公交线路。

因此，您可以将一个人的状态建模为一对位置（公交车站）和一条公交线路（开始或结束时可能 "not on a line"）。因此，为位置和公交线路的每个组合创建一个具有一个节点的图表。

此图中的边将对应于状态的变化。您可以通过

更改状态

留在您当前的公交线路上去某个地方，或者
切换公交线路。

如果您当前在公交线路上，并且线路从第一个位置到第二个位置，您可以留在该线路上从一个位置移动到下一个位置。所以创建边((location1, line), (location2, line)) if bus line line从位置 1 到位置 2。这不涉及转移，所以给这条边的成本为0。

或者，您可以随时下车或从下车到上车。因此，为每条线和每个位置添加一条边 ((location, line), (location, free)) （您始终可以选择下车）并给它成本 0，因为这不涉及换线。同样，为每条公交线路line[=46]添加边((location,free),(location,line)) =] 在给定位置可用。给它cost 1表示这需要你上车。

现在，假设您在此图中找到一条从（点 A，自由）到（点 B，自由）的路径。这对应于您在 A 点开始并在 B 点结束的一系列公共汽车的上下车，成本将是您最终上车的不同公共汽车的数量。如果您运行在此图中使用最短路径算法（例如 Dijkstra 算法），您将找到从起点到终点的路径，使总线传输次数最少！

Answer 2

您可以遍历数组一次，并保留一组对所访问的站点公共的公共汽车。一旦找到 none 辆这样的公交车，就拿上一组，从中选择一辆公交车，然后用那辆公交车填充结果。

然后将当前停靠的所有公交车放入集合中，并对后续停靠站重复操作，...等

这里是用 ES6 JavaScript 编码的算法。它使用 Set 允许恒定时间访问它存储的项目（总线）。

// Helper function: given a reduced set of buses, and a count,
//   add one of those buses as the bus to take during that many stops
function addToResult(common, count, result) {
    let bus = common.values().next().value; // pick any available bus
    while (count > 0) {
        result.push(bus);
        count--;
    }
}

// Main algorithm
function getBusRide(stops) {
    if (stops.length === 0) return [];

    let result = [],
        count = 0,
        common;
    for (let buses of stops) {
        if (count == 0) { // First iteration only
            common = new Set(buses); // all buses are candidate
            count = 1;
        } else {
            let keep = new Set();
            for (let bus of buses) {
                // Only keep buses as candidate when they 
                //     are still served here
                if (common.has(bus)) keep.add(bus);
            }
            if (keep.size == 0) { // Need to change bus
                addToResult(common, count, result);
                count = 0;
                keep = new Set(buses); // all buses are candidate
            }
            common = keep;
            count++;
        }
    }
    addToResult(common, count, result);
    return result;
}

// Sample input
const stops = [
    [ 42,  45,  47],
    [ 45,  47,  42,  88],
    [ 21,  77,  42],
    [ 22,  47,  42,  88],
    [ 23,  47,  42],
    [ 24,  47,  42,  8,  91],
    [ 25,  13,  42,  3,  84],
    [ 26,  10,  11,  4,  54],
    [ 27,  9,  8,  88,   71]
];

// Apply the algorithm
console.log(getBusRide(stops));

.as-console-wrapper { max-height: 100% !important; top: 0; }

此算法在 O(n) 中运行，其中 n 是输入中值的总数，因此在示例中 n = 37.

最小化矩阵中总线变化的数量

Minimising the number of bus changes in a matrix

algorithm

path-finding

backtracking