-2

我目前正在研究一种算法来安排 pub-crawling(尽管它可以更通用)。这是众所周知的:

  • 有一定数量的团队和酒吧,团队的数量永远不会超过酒吧的数量
  • 团队必须参观所有酒吧
  • 团队不能同时在同一个酒吧
  • 整个过程是暂时的;团队在酒吧爬行的开始和结束时间之间的相同离散时间间隔内位于酒吧。

我认为这是旅行推销员问题和一些名册计划之间的混合,但现在我尝试使用蛮力来实施它,因为我不知道如何实施上述混合。我期望的结果可能如下所示:

预期结果

蛮力正在起作用,但它太慢了。当所有行和列都是唯一的时,就会找到一个解决方案——就像数独一样。然后可以将这些数字映射到特定酒吧的时间间隔/到达和离开时间。我正在寻找想法和建议,但也非常欢迎实现(C#)。

目前我正在强制执行以下操作:

  • 初始化一个二维数组,其行数与团队数相同,列数与条数相同。这些值也被初始化,范围为 1 列。
  • 检查数组是否是一个解决方案,如果不是:随机排列数组并再次检查。

最后,我需要提到的是,当这可以足够快地完成时,将引入一层复杂性。为特定团队选择的路线必须是最佳路线,这意味着所有团队都必须在旅行时间方面采取最佳路线 - 为此,我将使用 Google Maps API。我想如果算法的第一部分相对较快,那么距离优化可能是蛮力的。

期待创造性的解决方案!

4

1 回答 1

0

看来您应该首先解决最佳路线问题。如果您这样做,那么您可以在解决方案的第一个小节开始第一个团队,在第二个小节开始第二个团队,等等,就像您在示例中所做的那样。

因此,如果您确定通过条形的最佳(或几乎最佳)路径是 B4、B3、B1、B2、B6、B5,那么您只需重新排列表格标题中条形的顺序以匹配。所以在第一个时间段,团队 1 会访问酒吧 4,等等。

于 2017-06-29T14:28:09.893 回答