摘要
目前,华容道算法是基于广度优先或深度优先搜索策略的改进,时间复杂为O(V+E)。为了提高效率,文章利用排列组合算法找到所有开局,再用广度优先算法找到开局的最优解,将所有开局及对应最优解保存在文件中。执行算法时最快可以以O(1)的时间复杂度找到最优解。理论分析和实验结果都表明,基于h as h表的求解华容道的算法能明显提高算法效率。
One popular algorithm for solving the H uarongdao puzzle is based on breadth-first search for which the time complexity is 0(V+E).To improve its efficiency,all the start states were found using permutations and com binations algorithm and saved with corresponding optimal solutions into a file.Given any particular start state,the optimal solution can be found with time complexity 0(1)by looking up a hash table preloaded from the compressed file.Both theoretical analysis and experiments have shown that the algorithm based on hash table can significantly improve the efficiency in solving Huarongdao puzzles.
作者
周扬
陈伊琳
韦妮君
周一诺
ZHOU Yang;CHEN Yiin;WEI Nijun;ZHOU Yinuo(Big Data Application Center of Information Management Office of the Seventh Affiliated Hospital of Sun Yat-sen University,Shenzhen,Guangdong 518000,China)
出处
《计算机应用文摘》
2023年第1期102-104,109,共4页
Chinese Journal of Computer Application
