col*_*son 5 algorithm optimization performance search magic-square
我一直在编写解决各种数字难题的程序,但我一直在设计无法合理的复杂搜索算法.
例如,在一个谜题中,您将获得一个3x3网格,数字1到9如下:
123
456
789
您可以在任何方向上循环任何行或列中的数字.下面是将顶行数字向右移动的示例.如果它们位于网格的边缘,则数字将循环.
123 -> 312
456 456
789 789
您必须以这种方式移动数字,直到创建一个魔术方块,其中每列,行和对角线中的数字总和为15.
我编写了一个DFS强力算法来测试所有可能的移动序列,尽管每个回合的可用移动次数呈指数增长(大约12 ^ [当前转弯]),使其无用.
看起来BFS最适合找到正确的动作,但这需要我存储数百甚至数千个网格副本才能回溯!
我一直遇到这些问题.BFS和DFS算法分别使用太多的内存和时间.我需要帮助优化这些算法,以便它们更快更有效地运行.也许识别数字的模式和关系或者让算法逻辑朝着目标努力会有所帮助吗？(我不知道会带来什么).
编辑:
我的固定算法就像一个魅力.学习如何对我的排列进行编号是至关重要的.谢谢你们!
我建议查找memoization(根据输入缓存函数调用的结果,以便不会为相同的后续调用重新计算函数).理解了memoization后,我会查找动态编程(仍然保存函数的结果,但也重新排序计算以消除不必要的调用).动态编程的一些解释使用斐波纳契的递归定义,然后使用斐波纳契+ memoization,并使用计算重新排序完成.
对于一般的DFS和BFS问题,称为分支和束缚的技术可能是有意义的.边界部分可以在一些问题上给你带来实质性的收益.修剪比使用不太复杂的边界高一代的子树消除了搜索树中的许多新分支(替代措辞:因为树随着深度呈指数级增长,所以提前修剪搜索很重要).
对于您的特定问题,我认为可以进行优化.
首先,让我们考虑一下DFS.我相信您的电路板的所有排列都可以从电路板的任何配置中获得.作为结果.DFS可以在没有回溯的情况下实现(尽管我猜你知道这一点).深度只搜索？(编辑:根据丹尼尔菲舍尔,这是错误的.一半的州是可以达到的,虽然它不影响无回溯声明,因为回溯不会帮助你达到无法到达的状态)
但是,您可能会发现您不想仅仅为了发现您尚未解决问题而通过许多排列.回溯可能实际上有所帮助.要么...
考虑一下你的最终目标.魔术方块具有一些特定的属性,您可以利用这些属性来更仔细地选择操作.例如,由于行和列必须总和为15,因此您知道9,8和7不能相互共享行或列.9和6都不能与8和1或7和2一起使用.6不能与5和4共用一列/行,即使它们总和为15,因为鸽子洞原则(每行/每列包含9个) ,8或7).实际上,您可能会发现您的问题有一个独特的解决方案,在所有行,全列,反射和转置中模拟某种循环置换.对角线要求进一步限制了有效的解决方案.
旁白:前一段中使用的逻辑与基于约束的编程没有什么不同.它实际上并不是一种优化技术(尽管如果不是运行时间,它可能被认为是对实现时间的优化),但也可能对您感兴趣(还要注意魔术方块和数独库经常用于说明基于约束的编程) .
现在你有一个目标:
这是一种根本不同的方法,而不是搜索各种排列直到问题得到解决.我试着找到一个动态的编程解决方案.对于使用增量操作从开始状态移动到目标状态的稍微容易的动态编程问题,请查看Levenshtein编辑距离问题.