algorithm - 给定表示单个出租车预订的数据序列(开始位置、结束位置)，找到最佳的不间断序列

Question

我一直在尝试解决一个优化问题，但无法想出任何有效的解决方案。问题来了

We are given data representing a sequence of bookings on a single car. Each booking data consist of two points (start location, end location). Now given two adjacent bookings b1,b2, we say a relocation is required between those bookings if the end location of b1 not equal to the start location of b2

We have to design an algorithm that takes a sequence of bookings as input and outputs a single permutation of the input that minimizes the total number of relocations within the sequence.

这是我的方法对我来说，它看起来像是一个贪婪的调度问题，但我无法从任何现有的调度问题中得出任何好的启发式来解决这个问题。最后想到用插入排序的方法，根据相邻两个序列开始时间和结束时间的最小差值对给定序列进行排序。

所以，对于我们给定的问题[(23, 42),(77, 45),(42, 77)] 将被排序为 [(23, 42),(42, 77),(77, 45)] 从而最小化终点我的起点。

再举个例子

[(3,1),(1,3),(3,1),(2,2),(3,1),(2,3),(1,3),( 1,1),(3,3),(3,2),(3,3)]

现在使用插入排序排序到索引 7 后，我们的数组看起来像

[(3,1),(1,3),(3,1),(2,2),(2,3),(3,3),(3,1),(1,3),(3,3),(3,2),(3,3)]

现在为了将点 (3,3) 放在未排序数组中的索引 8 处，我们将执行以下操作

The idea is to put each point in its correct location. For the point (3,3) at index 8 I will search in the already sorted array the first entry whose endpoint matches 3 i.e. starting point of this new point, given the condition that adding this point after that first found entry does not violate the variant that start of next entry should match the end of this point. So, we inserted (3,3) in between (2,3) and (3,1) at index. It looks like this

[(3,1),(1,3),(3,1),(2,2),(2,3),(3,3),(3,1),(1,3),(3,3),(3,2),(1,1)]

但是，我不确定如何证明这是最优解或不是最优解。任何指针都受到高度赞赏。有没有更好的方法，我相信可以帮助我们解决这个问题。

Answer 1

您可以轻松地将其转换为图形问题。

[a, b] -> 顶点 a 和 b，边在 a 和 b 之间。使用 DFS 在这个无向图中找到所有连接的组件并进行一些后处理。

它在输入大小上是线性的。