通用目标
假设我们有一个“小”10x10 网格,其中一些固定节点 @ 放置在随机位置
. . . . . . . . . .
. . . . . . . . . .
. . . @ . . . . . .
. . . @ . . . . . .
. . . . . . . . . .
. . . . . @ . . . .
. . . . . . . . . .
. . . . . . . @ . .
. . . . . . . . . .
. . . . . . . . . .
假设我们有大约 30 个节点,其值是它相邻的节点的函数(邻接被定义为围绕一个点的 8 个点中的任何一个)。也就是说,如果我们考虑放置在地图上的节点 A 和 B
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . A @ . . B . . . . . A @ . . . . . .
. . . @ . . . . . . . B . @ . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . @ . . . . . . . . . @ . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . @ . . . . . . . . . @ . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
在这两个映射中 A 和 B 的输出可能不同,因为 A 和 B 在第二个映射中相邻但在第一个映射中不相邻。
我们的目标是将所有节点放置在地图上,以使所有节点的总和最大(或至少相当不错)。
针对我的特定问题的其他限制
- 大约有 8 个“类”节点。每个类中的所有节点的行为都相同,因此可以用来减少搜索空间。
- 某些节点在整体价值中占主导地位,因此知道这一点可以让我围绕这些核心节点进行优化。
- 每个节点通常只有两个或三个其他类的节点,当它与这些类的节点相邻时会增加它的值。
- 所有值均≥ 0。
- 我想在几秒钟内找到合适的拟合......所以有一些计算空间,但 5 秒内的一个很好的解决方案比 2 天内的完美解决方案要好。
天真的贪婪方法
我现在正在做的是采用简单的贪婪方法,然后微调结果。
我查看网格上的所有位置并考虑所有尚未放置的节点,然后选择我找到的最佳位置。如果有多个“最佳”位置,我会随机选择一个。我这样做,直到所有节点都已放置。
在这个初始过程之后,我会随机选择一个节点,并通过查看所有开放点来尝试为它找到一个更好的位置。我考虑移动节点对节点本身以及它的相邻邻居的影响,所以如果它已经在整体上处于最佳位置,我不会移动它。我这样做几千次以“微调”我的布局。
由于随机因素,给定相同的输入,我可以获得非常不同的输出,因此我多次执行此过程并获得最佳结果。
问题
我怎样才能比这种天真的贪婪方法做得更好?
我觉得应该有一个更好的解决方案来考虑先验邻接信息,但它让我望而却步。任何想法、链接或提示将不胜感激!