我有问题。我的工作需要一些组件的所有可能的构建订单。作为一个简单的例子,您可以想象一个简单的乐高金字塔:
http://i.stack.imgur.com/Y7Lcr.jpg
我尝试了某种 DFS,但没有成功。最后缺少一些可能性。
有人可以帮我吗?语言应该是 C++,但我只需要一个提示而不是一个完整的算法。
一些信息:模型以 XML 文件的形式提供。您可以在其中找到所有 3 个方向(x、y、z)上的所有邻域关系。所有作品都有一个唯一的名称/ID。开头没有定义。构建顺序没有限制。因此,您不必完成金字塔的一层即可开始另一层。我知道有很多可能的构建顺序。即使是 3x3-base 本身也有很多可能性(九阶乘)。不过暂时没关系。
拜托,我需要帮助。
您好, 埃里克
最佳答案
首先,将每一层(或“类(class)”)视为一个独立的问题。考虑底部的九 block 砖;忽略所有其他,有 9 个!可能的订单,因此生成这些订单,称它们为 P。同样是4!中间积木的可能顺序是Q。我们现在可以忽略顶部的单 block 砖。
遍历 P 和 Q。给定底部砖 block p 和中间砖 block q 的顺序,可能是 q 的第一步(即铺设第一 block 中层砖)在底部完成之前是可能的,因此我们可以在 p 的移动中穿插该移动;对于 q 的第一个允许的时间,迭代 q 的第二个允许的时间,并为每个允许的时间迭代第三个的允许时间,和等等。
请注意,顶层积木必须始终放在最后。也是好事。
这还不够吗?
关于c++ - 从给定模型获取所有构建订单。,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30983572/