5

什么是一个很好的启发式来解决以下挑战？

Quality Blimps Inc. 正在寻求将他们的销售扩展到其他城市 (N)，因此他们聘请您作为推销员飞往其他城市销售飞艇。飞艇旅行可能很昂贵，因此您需要确定每次旅行要带多少飞艇，以及何时返回总部以获得更多飞艇。Quality Blimps 提供无限量的飞艇。

您将只能在您访问的每个城市出售一个飞艇，但您不需要访问每个城市，因为有些城市的旅行费用很高。每个城市都有飞艇出售的初始价格，但随着出售更多飞艇（并且新奇感消失），价格会下降一定比例。找到一条利润最大化的好路线。

https://www.hackerrank.com/codesprint4/challenges/tbsp

这个挑战类似于标准的旅行推销员问题，但有一些额外的曲折：推销员需要跟踪他自己的旅行费用和飞艇的费用。每个城市都有不同的飞艇售价，但这些价格会随着他的旅程而下降。什么是用于最大化利润的快速算法（即 n log n ）？

以某种方式运输物品的价格使 TSP 更简单。如果业务员在A市，想去B市，他可以比较直接去B市的成本和先回总部接更多飞艇的成本。即，通过 A 乘坐额外的飞艇到 B 或在两者之间返回是否更便宜。此检查将创建一系列循环旅行，然后销售人员可以按照收入最高的顺序进行循环。但是首先确定这些循环的好方法是什么？

4

4 回答 4

3

这是一个搜索问题。假设网络比蛮力解决的要大，最好的算法是蒙特卡洛树搜索。

于 2013-02-06T18:43:22.917 回答
3

此类问题的算法通常是“多次运行解决方案，选择最好的”类型。此外，要选择下一步尝试的解决方案，请使用先前迭代的结果。

至于特定算法，请尝试使用修剪、模拟退火、禁忌搜索、遗传算法、神经网络进行回溯（按照我认为相关的顺序）。此外，Tyler Durden 提出的蒙特卡罗树搜索想法看起来很酷。

于 2013-02-12T11:32:22.610 回答
0

这看起来像是一个经典的优化问题，我知道可以使用模拟退火算法来处理（我认为这是模拟退火的第一个商业用途，即早在 1980 年代的 Wintek 电子 CAD 自动放置程序）。大多数优化算法可以处理像您这样的许多变量的问题——问题是正确设置适应度算法，以便获得最佳解决方案（在您的情况下，成本最低）。

其他优化算法可能值得一看——我只是有实现模拟退火算法的经验。

（如果您走模拟退火路线，您可能想要获得 PJ van Laarhoven 和 EH Aarts 的“模拟退火：理论与应用（数学及其应用）”，但您必须寻找它，因为它已绝版（它甚至可能是我在 1980 年代使用的书）。）

于 2013-02-13T12:03:55.670 回答
0

我已阅读原始问题。由于城市数量众多，因此不可能得到确切的答案。逼近算法是唯一的选择。正如@maniek 提到的，AA 有很多选择。如果你以前有过 AA 的经验，那最好，你可以选择一个你熟悉的，然后得到一个大概的答案。但是，如果您之前没有进行 AA，也许您可​​以从带有修剪的回溯开始。

至于这个问题，你可以很容易地得到这些剪枝规则：

  1. 带上尽可能少的飞艇。也就是说，当你从总部出发，访问城市A，B，C......，然后返回总部（你可以将其视为一个回合），你带来的飞艇数量与你将访问的城市相同.
  2. 随着销售价格越来越低，当它低于旅行费用时，这个城市将永远不会被访问。这给出了回溯方法的结束。

您甚至可以先应用 KNN 来聚类附近的几个城市。然后从总部出发，参观各个小组。

总而言之，这确实是一个悬而未决的问题。没有最佳答案。也许在情况 1 中，使用回溯给出了最好的答案，而在情况 2 中，模拟退火是最好的。只需计算近似答案就足够了，实现这一目标的方法有很多。总而言之，真正最好的方法是尽可能多地编写 AA，然后比较这些结果并输出最好的结果。

于 2013-02-13T02:31:24.907 回答