algorithm - 成本最小化算法(限时)

Question

假设我有一群 N 人要乘火车旅行。我需要以最小化总门票成本的方式组织他们到售票处。如果一家人买家庭票，去同一目的地的人买团体票，成本可以降到最低。

我不知道这些人中谁是家人，他们要去哪里旅行。

我能做的就是把其中任意一个M(1 <= M <= N)送到售票处然后得到答案，这些M要花多少钱人。

我也有一个有限的时间，因为几分钟后火车就要离开了，所以接近最佳的解决方案对我来说已经足够了。

蛮力解决方案是 O(N!)，因此显然是 Not Acceptable 。

编辑

售票处的答案总是M人的总金额，没有细节。

团体和/或家庭可以从 2 人开始，也可以包括所有 N 人。

售票处的服务员总是知道谁是一家人，谁不是。

编辑

如果我派一个家庭和更多人去售票处，这个家庭将不会得到家庭票，他们都会得到他们的普通票。

Answer 1

既然你提到你可以满足于“足够好”，而且你的时间有限 - 这是一个贪婪的 any-time approach :

1. p <- 创建一个随机排列
2. 估计这种排列的成本。 (让它成为 cost )
3. 找到一个新的排列 p'这样 cost(p') < cost(p)这是从 p 实现的使用两个人的单次交换(有 n(n-1)/2 种可能的交换)¹
4. 如果存在这样的 p':p <- p'并返回到 2。
5. 否则，存储 p作为局部最小值，并返回到 1。
6. 时间到了 - 选择找到的最佳局部最小值。

这基本上是 steepest ascent hill climbing 的变体随机重启。

请注意，如果您的 time->infinity ，你会找到最优解， 因为检查任何可能排列的概率是 随着时间的推移越来越接近 1。

---

(1) 获取价格可以通过首先检查谁是家庭成员/前往同一目的地并且在 O(n) 的排列中彼此相邻来完成使用 d(passenger1,passenger2) < d(passenger1) + d(passenger2) 的事实, 然后分别检查每个组。