基于hash表的华容道算法研究  

Research on Huarongdao algorithm based on hash table

作　　者：周扬[1] 陈伊琳 韦妮君 周一诺 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)

机构地区：[1]中山大学附属第七医院信息管理处大数据应用中心,广东深圳518000

出　　处：《计算机应用文摘》2023年第1期102-104,109,共4页Chinese Journal of Computer Application

摘　　要：目前,华容道算法是基于广度优先或深度优先搜索策略的改进,时间复杂为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.

关 键 词：华容道 时间复杂度 HASH表 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]