使用树的TipOver Solver最快的算法 [英] The fastest algorithm for TipOver Solver using tree

问题描述

我正在C中制作翻转解算器。

我试图通过创建一个包含所有可能路径的树来解决它，然后使用级别搜索算法处理所有树，寻找最短路径。这种实现很容易实现，但需要的处理时间比我预期的要长。所以现在我正在考虑使用A *算法的变体做到这一点。你认为它会跑得更快吗？或问题在于寻找所有可能的路径？

I am making a tipover solver in C.
I''m trying to solve it by creating a tree with all the possible paths and then process all the tree with a level search algorithm, looking for the shortest path. This implementation is pretty easy to do but takes more processing time than I was expecting. So now I''m thinking about do it with a variation of the A* algorithm. Do you think it will run faster? Or the problem is in looking to all the possible paths?

推荐答案

假设有一个解决方案，它应该运行得更快。

我的问题是：你如何确定哪个提示是最优的？


我认为向后工作会更容易，并且只允许连接的提示结束箱子结构。

Assuming there is a solution, it should run faster.
My question is: How are you determining which tip is optimal?

I think it would be easier to work backwards, and only allow tips which joined up with the end crate structure.

让我想起二进制堆（可以用来找到最短路径）

that reminds me of the binary heap (which can be used to find a shortest path)

@Tsuk


如果我要攻击它，我会使用广度优先搜索来生成路径。当你找到解决方案时就停止了。


如果长度很重要，我会使用上述技术应用Djikstra。

@Tsuk
If I were to attack it, I would use a breadth first search to generate the paths. You stop when you reach a solution.

If the lengths matter, I would apply Djikstra using the above technique.

这篇关于使用树的TipOver Solver最快的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！