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 回答