最优的三重城镇算法
我一直在努力为游戏"三重城镇"激发的问题找到最佳算法.游戏如下:
将对象放置在网格中,每次创建一组三个对象时,它们会在放置的最后一个对象的位置压缩为一个更高级别的对象.
此外,如果将这些b对象中的三个放在一起,它们会再次压缩以形成更高级别的对象.
注意:在这些图中,对象的级别表示为i,b i和c i,下标表示三个集合中的对象编号.
为了简化事情,我只考虑你必须放置的每个对象何时是最低级别.
现在我的问题是:
1:给定x,是否有算法确定制作x级对象所需的最小网格区域数量？
例如,对于等级a,您需要1x1,对于等级b,您需要1x3,对于等级c,您需要1x5.
2:鉴于网格的尺寸,我们能找到最高水平和可实现的物体数量吗？
例如,对于2x2,您可以获得2级'a'和2级'b'
3:在给定固定网格的情况下,是否有算法可以找到对象的最佳顺序和位置以获得最高级别？
例如,对于2x2,您可以得到(1,1),(1,2),(2,2)
4:给定一个预期级别x对象的位置,哪组移动最小化了制作此对象所需的空间量？
5:这些算法的最佳复杂性是什么？
更新:
我认为在找到解决方案时突出的一点是,获取x级项目不能在任何任意位置完成.
例如:[ _ _ _ _ c]在固定的1乘5格中是不可能实现的,因为你需要你的最后一个b在第5位,因此你的最后一个在第5位.所以放置第一个b:[a _ _ _ _]->[a a _ _ _]->[_ _ b _ _]或[_ a _ _ _]->[_ a a _ _]->[_ _ _ b _].在这两种情况下,没有足够的空间放置3'a来制作c的最后一个b.
另一件事,我们不能假设任何东西都可以展开到一维网格.我的下一点很明显.
我找到了一些有趣的东西:
边界的最小接近度是c级对象可以在1维网格中.[_ _ a a a]->[_ _ _ b]->[_ a a a b]->[_ _ _ b b]->[a a a b b]->[_ _ c _ _].因此,1乘5(最佳)网格中的c级对象只能在第3个位置进行.
因此,这是任何数字网格可以在1中进行的最高级别.采用无限网格1:
..._ a a a _ ... -> ... _ a a a b _ ... -> ... _ a a a b b _ ... -> ... _ c _ ...
现在我们尝试直接在它旁边获得另一个c:
..._ c a a a _ ... = ... _ c b _ ... or ... _ c _ b _ ... or ... _ c _ _ b _ ...
唯一的选择是..._ c b _ ...因为其他选项使得无法在c和b之间形成另一个b.我们唯一的选择阻止了我们在第一个c旁边直接创建c的唯一方法,因为它阻止了去往那里的最后一个c.因此,在一个维度上,c是我们可以做出的最高水平.换句话说,必须在两个方面考虑问题.
编辑：下面的内容实际上是错误的，原因如下：按照它所描述的操作来获得“c”，具体过程如下：_ _ aaa -> _ _ _ _ b -> (..) _ _ _ bb -> _ _ bbb -> _ _ c _ _
所以“c”现在位于行的中间，并且前置不能以这种方式工作。我把它留在这里，这样如果有人读到它，至少有一个解释为什么它是错误的。也许这会节省你思考同样错误的时间。
[此处错误] 1：您始终可以在 3+2*(x-1) 中执行此操作，因为您只需为字母的每个“级别”“添加”所需的元素。归纳证明：
要得到“b”，您需要 3+2*(1-1) = 3 个空格。
如果你能在 3+2*(x-1) 空间内获得 x 级，那么 x+1 级需要你 3+2*(x-1) 空间来构建 x 级角色和 2 个存储空间，花费你 3+ 2*(x-1)+2 = 3+2*((x+1)-1) 个空格。
这样，您实际上可以在高度为 1、宽度为 5 的矩形中得到一个“c”。您可以使用 13 个空格得到“f”，依此类推。想想这意味着什么：如果您想将信件打包到一个小区域中，请找到一个包含 3+2*(x-1) 空格的小区域，并在需要时转动前缀。这意味着您始终可以从您想要的螺旋位置向外移动。但这里有一个转折：你可能需要每个级别的最后一块石头来自交替的方向，这样你就不会离开你开始的地方。实际完成所有步骤的复杂度是 O(3^x)，因为下一个步骤需要前一级别的 3 个字母，而且都是乘法。