我目前正在研究一种算法来安排 pub-crawling(尽管它可以更通用)。这是众所周知的:
- 有一定数量的团队和酒吧,团队的数量永远不会超过酒吧的数量
- 团队必须参观所有酒吧
- 团队不能同时在同一个酒吧
- 整个过程是暂时的;团队在酒吧爬行的开始和结束时间之间的相同离散时间间隔内位于酒吧。
我认为这是旅行推销员问题和一些名册计划之间的混合,但现在我尝试使用蛮力来实施它,因为我不知道如何实施上述混合。我期望的结果可能如下所示:
蛮力正在起作用,但它太慢了。当所有行和列都是唯一的时,就会找到一个解决方案——就像数独一样。然后可以将这些数字映射到特定酒吧的时间间隔/到达和离开时间。我正在寻找想法和建议,但也非常欢迎实现(C#)。
目前我正在强制执行以下操作:
- 初始化一个二维数组,其行数与团队数相同,列数与条数相同。这些值也被初始化,范围为 1 列。
- 检查数组是否是一个解决方案,如果不是:随机排列数组并再次检查。
最后,我需要提到的是,当这可以足够快地完成时,将引入一层复杂性。为特定团队选择的路线必须是最佳路线,这意味着所有团队都必须在旅行时间方面采取最佳路线 - 为此,我将使用 Google Maps API。我想如果算法的第一部分相对较快,那么距离优化可能是蛮力的。
期待创造性的解决方案!