☰

Excel 公式用于优化路线，其中每一行代表一个可以做不同事情的不同“站点”

tag-icon • tag-icon microsoft-excel algorithm
Excel 公式用于优化路线，其中每一行代表一个可以做不同事情的不同“站点”

我不确定该如何提出这个问题。

这是一个最小可行示例：

  • 简可以做 A、B、D。她距离 1 公里。
  • 杰克可以做 B、D、F。他距离 1.5 公里。
  • 元帅可以做 E、F、A。他距离 20 公里。
  • 波莉 (Polly) 可以做 E、D、C。她距离这里有 10 公里。
  • 詹姆斯可以做 C、F、B。他​​距离这里有 15 公里。

表格中为每个人设置了行，为每项操作设置了列，AF。

我想找到要完成 A、C、F 的人员组合，且访问人数最少。如果两个组合有效，我想要距离最小的组合。

（所以上面的解决方案是 Jane 和 James）

在我的第一行，我为每项都设置了复选框：A、B、C、D、E、F。我已选择 A、C、F。

我应该使用什么公式来突出显示或用颜色标记我应该拜访的人？如果这在 excel 中无法完成，那么解决这个问题的算法应该叫什么，以便我可以使用编程语言来实现它？

答案1

完成！

在此处输入图片描述

概念

强力搜索。计算每个要拜访的人员组合的路线距离。忽略未提供所有必需任务的组合（AF）。选择路线距离最短的路线。

执行

这个想法是使用二进制表示来减少所需的数学运算。假设每个人在整数中分配 1 位，例如 1001 表示访问第 1 个人和第 4 个人。因此，如果我们有 8 个人，则我们有 2^8-1 = 255 种要访问的人的组合。我们将在编号为 1..255 的行中进行组合。

现在我们对每个人分配的任务执行相同的操作。任务 A 是位 1，任务 B 是位 2... 等等。因此，如果人员 010 提供的任务掩码 (TM) 为 0101，则人员 2 提供 A 和 C，而 TM 为 1000 的人员 001 仅提供 D。

如果我们计划拜访人员 011（001 和 010），那么提供的组合任务是

=BITOR("TM for 001", "TM for 010") which will result in TM 1101 (tasks A, C, D)

为每个人提供的组合任务是

=BITOR("TM for 001", BITOR("TM for 010", BITOR("TM for 100",... "TM for 10000000"))))))))

因此，为了分辨某个随机人员 x 组合提供的任务，我们只需要将相关的 TM 组合在一起：

=BITOR("TM for 001" * x0, BITOR("TM for 010" * x1, BITOR("TM for 100" * x2,... "TM for 10000000" * x7))))))))

其中 xi 是 x 中的第 i 位

=BITAND(1,BITRSHIFT(x,i))

同样地，确定人员组合/路线 x 的总距离

"Person 1 distance" * x0 + "Person 2 distance" * x1 +... "Person 8 distance" * x7

现在确定对于具有 TM y 的人 x 来说，是否可以完成所有必需的任务 z（即有效路线）：

=IF(BITAND(y,z) = z, "All tasks offered by x", "All tasks cannot be done")

And the distance for valid routes only

=IF(BITAND(y,z) = z, *distance calc above*,"") so invalid routes are blank ""

现在计算每个可能的组合，例如（1..255），并寻找最小有效路线距离分钟(...)，然后使用 MATCH(MIN(...) 找到最佳路线 x路线距离栏, 0) 与该最小路线距离相匹配。将 x 拆分为 x0.. x7 位，并使用条件格式突出显示最佳路线中的每个人。

相关内容