击败贪婪算法

对于课堂，我们有一个网格和我们需要检测并前往的网格上的一串正方形。我们从（0,0）开始。我们每次扫描网格的微小区域（出于与我们的数据结构有关的原因，这是强制性的），以及当我们检测到需要移动的正方形，然后我们移动时。网格上有32个位置，但我们只需要移动其中的16个位置，并且尽可能快（我们正在与其他人竞争）。击败贪婪算法

迪杰斯特拉的算法会找到从我们当前位置到下一个位置的最短路径。然而，这是次优的，因为我们的下一个位置可能离那之后的位置非常远。如果我们能够以某种方式计算我们扫描的位置密度，然后选择去一个非常密集的地方并在该地区内的所有位置行驶，那将会更加有益。

是否有最适合这种情况的算法？我知道贪婪的启发式不是最优的。 A *和Dijkstra是我们最初想到的，但我们希望有一个完全不同的解决方案。

不幸的是，这是在汇编中完成的。

来源

2010-10-28 Sam

对于Dijkstra方法为什么不是最优的，您是否有确切的反例？我似乎无法找到任何东西。 – IVlad 2010-10-28 21:34:32

您需要去哪些地方连接到对方？从一个位置到另一个位置的距离是否等于欧几里德距离sqrt（dx^2 + dy^2）？或者是否有指定位置之间的道路（边缘）和距离（重量）？ – LarsH 2010-10-28 21:45:35

装配？可怜的你。 :( – st0le 2010-10-29 06:01:25

找到密集的点（例如，您必须访问的位置）称为cluster analysis。查看几类算法的链接。

汇编语言是一个非常痛苦的实验高级算法的方法。你的教授是个虐待狂吗？

来源

2010-10-28 21:42:16 LarsH

击败贪婪算法

回答

相关问题