2

通用目标

假设我们有一个“小”10x10 网格，其中一些固定节点 @ 放置在随机位置

. . . . . . . . . . 
. . . . . . . . . . 
. . . @ . . . . . . 
. . . @ . . . . . . 
. . . . . . . . . . 
. . . . . @ . . . . 
. . . . . . . . . . 
. . . . . . . @ . . 
. . . . . . . . . . 
. . . . . . . . . .

假设我们有大约 30 个节点，其值是它相邻的节点的函数（邻接被定义为围绕一个点的 8 个点中的任何一个）。也就是说，如果我们考虑放置在地图上的节点 A 和 B

. . . . . . . . . .     . . . . . . . . . . 
. . . . . . . . . .     . . . . . . . . . . 
. . A @ . . B . . .     . . A @ . . . . . . 
. . . @ . . . . . .     . B . @ . . . . . . 
. . . . . . . . . .     . . . . . . . . . . 
. . . . . @ . . . .     . . . . . @ . . . . 
. . . . . . . . . .     . . . . . . . . . . 
. . . . . . . @ . .     . . . . . . . @ . . 
. . . . . . . . . .     . . . . . . . . . . 
. . . . . . . . . .     . . . . . . . . . .

在这两个映射中 A 和 B 的输出可能不同，因为 A 和 B 在第二个映射中相邻但在第一个映射中不相邻。

我们的目标是将所有节点放置在地图上，以使所有节点的总和最大（或至少相当不错）。

针对我的特定问题的其他限制

  1. 大约有 8 个“类”节点。每个类中的所有节点的行为都相同，因此可以用来减少搜索空间。
  2. 某些节点在整体价值中占主导地位，因此知道这一点可以让我围绕这些核心节点进行优化。
  3. 每个节点通常只有两个或三个其他类的节点，当它与这些类的节点相邻时会增加它的值。
  4. 所有值均≥ 0。
  5. 我想在几秒钟内找到合适的拟合......所以有一些计算空间，但 5 秒内的一个很好的解决方案比 2 天内的完美解决方案要好。

天真的贪婪方法

我现在正在做的是采用简单的贪婪方法，然后微调结果。

我查看网格上的所有位置并考虑所有尚未放置的节点，然后选择我找到的最佳位置。如果有多个“最佳”位置，我会随机选择一个。我这样做，直到所有节点都已放置。

在这个初始过程之后，我会随机选择一个节点，并通过查看所有开放点来尝试为它找到一个更好的位置。我考虑移动节点对节点本身以及它的相邻邻居的影响，所以如果它已经在整体上处于最佳位置，我不会移动它。我这样做几千次以“微调”我的布局。

由于随机因素，给定相同的输入，我可以获得非常不同的输出，因此我多次执行此过程并获得最佳结果。

问题

我怎样才能比这种天真的贪婪方法做得更好？

我觉得应该有一个更好的解决方案来考虑先验邻接信息，但它让我望而却步。任何想法、链接或提示将不胜感激！

4

1 回答 1

0

我最近研究了一种类似的算法。

想法：

我们想限制我们的选项以获得计算时间（这是我的问题，因为我已经在 3D 中完成了它）

在您的情况下，您希望将节点放置在已放置的节点旁边似乎是合乎逻辑的。让我们标记 p 的可能性。

. p . . . . .
p @ p p . . .
. p p @ p . .
. p @ p . . .
. p p . . . .
p @ @ p . p .
p p p . p @ p

初始化：

让我们称“Cluster”为一个包含可能位置的数组。这是所有 p 的数组

对于您需要放置的每个节点，您可以在这些 p 中找到最佳选项；因此，对于每个新节点，您都会得到类似 Node::(place & value)

迭代：

您放置最好的节点，这将删除集群中的 1 种可能性并添加一些（取决于已经周围的节点）

现在您要更新每个节点的最佳位置和价值。但是您可以在少数修改的节点上工作，因为已经计算了所有其他可能性：

. p . . . . .  A : recently placed
p @ p p . . .  C : new possibilities / possible changes
. p p @ p . .
. p @ p . . .
. C A C . . .
p @ @ p . p .
p p p . p @ p

例如，这里对于每个剩下的节点只需要 2 次计算。如果新值更大 => 更改（值和位置）

迭代。

错误的可能性：

我不知道这是否能完美地解决您的问题，因为我无法知道是否需要先放置“更大”的值，但我想是的。

如果您的值与周围毛孔的数量呈线性或几乎呈线性关系，则此解决方案将不是完美的解决方案，但应该是正确的解决方案。

我找不到用英语说的方法，但在法语中，我称这种算法为“Algorithme de progress de front”，类似于“Front-Progress Algorithm”。也许你能找到一些基于此的东西，但我在快速搜索后没有找到。

我希望它对你有所帮助。

于 2013-05-22T14:56:35.030 回答