8

在模拟中，工作人员必须在地图上移动来执行任务。

每次模拟'tick'，他们可以移动一格。

一旦他们与它相邻执行任务需要 10 个滴答声。

任务方块不能通过。有工人的广场不能通过。一个以上的工人可以在一个广场上工作。

工人不相互竞争；目标是尽快完成所有任务。

补充：理想情况下，算法应该易于概念化并且易于实现。这不是每个人都想要的吗？如果它高效，例如模型可以更新和重用，而不是经常从头开始重新计算，这是一个很大的优势。理想情况下，它将能够使用局部最优，因此它不会试图暴力破解 NP 问题，而是避免过于贪婪并提前思考，而不是基本上随机游荡，工人很少注意其他人的计划。

这是一个例子：

在此处输入图像描述

工人 1 和 2 必须完成方格 A、B、C 和 D 上的任务。

你如何决定哪个工人做哪个任务？

1 应该做 A 而 2 应该做 C 似乎是不言而喻的。

1 距离 A 4 个方格，因此将在 14 个刻度内完成。1接下来应该去哪里，为什么？

如果有另一个任务 - E - 直接放在 B 上方怎么办？

工人用来决定下一步从哪里进行的逻辑是什么？

我试过的：

这是一个爱好 RTS 游戏，我尝试让它让空闲的工作人员继续执行最近的任务，或者继续执行其他工作人员没有做的最近的任务。

这种贪婪的方法已被证明是非常低效的，玩家测试表明它是站不住脚的。因为战略性的采矿/建筑/耕作是游戏的关键，并且因为我不希望玩家对所有工人进行微观管理和路由，所以我正在寻找一种相当公平且合理的优化算法，工人可以使用它。

4

8 回答 8

11

即使只有一个工人，这也是一个 NP 完全优化问题（然后它变成了旅行商问题），所以让我们忘记“最优”。

如果您知道工人 1 将处理任务 A1、A2、...，工人 2 将处理任务 B1、B2...等等，那么您可以在做出决定后尝试解决独立旅行推销员一个一个的问题，你得到所有工人的时间表和路径。

但是，问题在于，在解决该集合的旅行推销员问题之前，您无法知道为工人完成一组任务 A1、A2、... 需要多长时间，因为步行时间会影响完成任务的总时间。执行任务。

因为这只是一个游戏，并且可以假设工人不是最佳思想家，所以我会使用随机过程：

  1. 将所有任务随机分配给所有工人
  2. 使用贪心算法计算工人任务组中每个工人的步行时间上限
  3. 尝试随机移动，或者将一项任务从一名工人转移到另一名工人，或者在两名工人之间交换任务
  4. 接受基于禁忌搜索或模拟退火原则的移动，取决于移动是否降低最大执行时间的上限（步行时间+任务执行时间），以便目标是尽可能早地完成最后一个任务
  5. 在 N 次迭代之后，停止并计算旅行商子问题的更好解决方案，例如使用随机搜索，或者如果问题很小（例如每个工人少于 10 个任务），则明确
于 2013-09-05T11:23:08.877 回答
7

与其贪婪地将工人分配给最近的任务，不如尝试贪婪地将最远的任务分配给它的“最近”工人——即路径很近并且有足够的松弛时间来处理它的工人。这样，您就有了完成所有任务所需的最短时间的（贪心）概念。

例如：

D 是“最遥远的任务”，即使尚未定义该术语，所以将 D 分配为 1。距离 15+10 个单位，因此设置t= 25，2 到 25 的松弛。

现在这里是分配下一个任务的距离成本，考虑到最短路线。

    A   B   C   D  
1  10  22  24   -
2  29  19  18   -

但这里是根据贪心想法的真实成本；增加到最大时间t。

    A   B   C   D  
1  10  22  24   -
2   4  0    0   -

由于 C 的成本最高（从贪婪的角度来看这是最危险的任务），因此将 C 分配为 2。

接下来的费用如下

    A   B   slack    A  B
1  10  22     0     10 22
2  21  11  (-)7     14  4

分配 B，因为 22 是最大时间的最大增加t。将其分配给工人 2。

...

背包问题有很多方法，但如果需要简单，这可能是接下来要尝试的方法。也许存储任务之间的最短路径。这是一种公然贪婪的方式，确实有点超前思考！

于 2013-09-10T23:10:20.257 回答
5

这听起来确实很像（已经提到的）旅行推销员问题（TSP，http ://en.wikipedia.org/wiki/Travelling_salesman_problem ）。这实际上是一个类似于多重背包（MKP，http ://en.wikipedia.org/wiki/Knapsack_problem#Multiple_knapsack_problem ）甚至装箱（http://en.wikipedia.org/wiki/Bin_packing_problem）的问题。

有一组算法可能适合这种情况，称为“蚁群优化”（ACO，http ://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms ）。

为了将两者结合起来，有一些实现使用 ACO 来解决 MKP 问题；在这种情况下，这似乎是一个好方法，例如：

http://www.researchgate.net/publication/221246039_Probabilistic_Model_of_Ant_Colony_Optimization_for_Multiple_Knapsack_Problem

于 2013-09-10T08:32:51.633 回答
3

我猜“实时”的贪婪结果是不好的，因为工人们最终会疯狂地追逐在他们到达时将完成或几乎完成的任务。因此，我将提出一种规划算法：一种智能地将每个工人分配给一系列任务的方法，其中序列的联合是一个掩护。

正如其他人所说，TSP 嵌入在此规划要求中，因此这是一个 NP Hard 问题。

但是对于 TSP，有一个简单的多项式时间逼近算法，它产生的路径长度不超过 2 倍最优。只需计算一个最小生成树，包括所有工作地点和一名工人。然后在每个方向上遍历每个边一次的明显路径触及每个节点。

当然，在回溯时，您可以“直线”通过已经访问过的节点。这意味着只需通过预先遍历 MST 来发出任务序列。由于三角不等式，这条路径通常比 2x 最优路径好很多。（我假设这里允许对角线步骤。否则这是不正确的，但算法仍然可以正常工作。）

所以规划的方法是这样的：

  1. 计算每个工人和所有工作地点的 MST。
  2. 使用与每个工人 W 关联的 MST 来计算前序路径：S_W, T_Wi, i = 1, 2.... 这里，S_W 是工人 W 的起始位置。 T_Wi 是顺序 W 中的任务位置会拜访他们。
  3. 现在做一个简单的事件驱动模拟来构建一个计划，如下所示。（这是游戏模拟中的“内部”模拟，只是为了制定计划。）

在下面的算法中，事件包括预计的发生时钟时间，并以该时间作为键放置在事件队列中。

Let Arrive(W, T, L) be an arrival event of worker W 
  at task T starting from previous location L, traveling the shortest path
Let Complete(W, T) be a completion event for worker W of task T

For each worker W, place Arrive(W, T_W1, S_W) on the queue
While events are left on the queue
  Remove an event E
  If E is an arrival Arrive(W, TW_i, L) 
    If TW_i has no worker yet, 
      Assign TW_i to W
      Schedule a future event Complete(W, TW_i) 10 time units in the future.
    Else // T has a worker
      Schedule Arrive(W, TW_{i+1}, L), if TW_{i+1} exists
  Else E is a completion Complete(W, TW_i)
    Schedule Arrive(W, TW_{i+1}, TW_i), if TW_{i+1} exists

现在按照在这个（内部）模拟中发现的顺序为每个工人执行分配。

使用先前的位置和目的地计算到达时间以获得最直接的路线。

这个算法相当贪心，但它是“提前”贪心的。因为您是在模拟提前分配任务，所以您永远不会派一个工人去执行一项任务，该任务将在另一个工人到达之前完成或很好地开始。

此外，没有任何工作人员会覆盖超过最佳 TSP 路线 2 倍的距离。

于 2013-09-17T03:19:58.447 回答
3

因为它是一款 RTS 游戏，所以我会尝试选择一种简单、快速且易于理解的方法。

  1. 它必须很快，因为性能很重要
  2. 必须很容易理解为什么工人会到处乱跑，因为在游戏中您希望奴才按预期行事。不要试图为球员考虑。

首先，当然，我会尝试贪婪的方法。但是你已经提到它只是行不通。

接下来我会尝试类似二阶贪心算法。每个工人选择最接近的任务 A，然后选择最接近 A 的任务 B。他们尝试（！）选择迄今为止没有人选择的任务。类似的东西。

保持小而简单。请注意：无论您选择哪种算法，都会出现惨败的情况。毕竟没有免费的午餐。

于 2013-09-10T08:25:00.270 回答
3

我会建议类似于TobiMcNamobi的方法，但更精致：

  • 为每个工作人员初始化一个空工作队列以及z完成此队列所需的时间。
  • 给每个任务一个属性d，设置为 0。它表示根据当前计划，这个任务“已经处理”了多少。
  • 重复直到所有工人至少有一份工作并且（z>某个固定值或给定的时间已经过去）：
    • w以最小的工人之一z。
      • 设置为' 队列p中最新条目的位置，如果队列为空，则设置为 ' 位置。ww
      • 按距离顺序循环遍历不在此工作队列中的任务p
        • 计算distance/d
        • 如果您找到此值的最小值，请将此任务添加到工作人员的队列中，将距离添加到任务 + 7 到z并添加1/z到d. 打破循环。

在运行此之前，您应该根据与最近任务的距离对工作人员进行排序。否则，第一个任务是相当随机的，第一个任务是最重要的。

每当添加工作或工作人员时，您都可以更新它。重用之前的一些值（可能存储中间结果，比如将匹配添加z到工作队列中的任务），这个更新应该是相当快的。

无论如何，这也可能需要不时更新一次，因为一旦你走得足够远，这个算法就会变得非常不准确。

该distance/d公式可能还需要一些调整，但我想测试在这里会有很大帮助。

“最低”的定义取决于您。我会建议采取本地最低限度，也许最多检查 5 个以上的任务。找到全局最小值似乎不必要地昂贵。

于 2013-09-10T20:04:24.157 回答
2

（注意：做完这一切之后，我意识到你说的是 14 个滴答声，因为“相邻”你在想“在上面”，而我把它解释为“旁边”……所以请记住，我的计算是基于此的，但是它不应该改变太多的结果。）

我的第一直觉是首先根据最佳完成时间为每个工作人员建立一个独立的队列，假设不存在其他工作人员并稍后处理冲突（请注意，根据我的解释，当 A 完成 1 时，B 是比 D 更接近，但我们要防止的关键是 1 取 B)：

1 [A, B, C, D]
2 [C, B, A, D]

然后我会计算每个人的移动+工作时间：

1 [A=3+10, B=8+10, C=1+10, D=20+10]
2 [C=7+10, B=1+10, A=10+10, D=11+10]

作为参考，这里只是总刻度：

1 [A=13, B=18, C=11, D=30]
2 [C=17, B=11, A=20, D=21]

这里是累积的：

1 [A=13, B=31, C=42, D=72]
2 [C=17, B=28, A=48, D=69]

那么，如果您只是遍历每个任务以查看谁的时间最短并将其从其他工作人员的队列中删除，会发生什么？显然，一旦您更改某些内容，就必须重新计算所有累积时间（我将手动进行，呃）

开始（同上）：

1 [A=13, B=31, C=42, D=72]
2 [C=17, B=28, A=48, D=69]

1的A时间最短，所以2输了，重新计算2的D时间：

1 [A=13, B=31, C=42, D=72]
2 [C=17, B=28, D=59]

2 胜 B，所以 C 和 D 再次改变 1 的时间：

1 [A=13, C=32, D=62]
2 [C=17, B=28, D=59]

2胜C，再次改变1的D时间：

1 [A=13, D=24]
2 [C=17, B=28, D=59]

1胜 D：

1 [A=13, D=24]
2 [C=17, B=28]

如果在 B 的正上方有另一个任务 E 怎么办？对不起，我没有时间计算这个。

于 2013-09-13T07:40:35.287 回答
1

我假设工人的外观需要类似于人类会做的事情（算法需要像人类一样分配每项工作）。如果算法没有，玩家会想知道 AI 在做什么，并且可能会尝试手动路由（即使它不是最优的）。我认为任何“全局最优”的解决方案都可能不会像人类会做的那样......

因此，我认为您的（Will）初始算法可能只需要稍微改进即可工作。让每个工人前往最近的空缺工作，但模拟它去那里并在工人到达工作或另一个工人空闲时停止模拟（然后该工人将抓住该工作）。如果无法找到空缺职位，请选择最近的已占用职位并在那里提供帮助。

于 2013-09-17T07:59:06.763 回答