哈希表打包问题

主要观点:项目旨在为基于位棋盘的棋类及类似游戏的移动生成建立理论极限并尽可能接近;哈希表打包问题是优化象棋中魔法位棋盘时遇到的问题,其为强(\mathcal{NP})-完全问题,无法寻找最优解,应使用启发式算法;介绍了哈希表及哈希表打包的定义,通过归约证明了哈希表打包问题是强(\mathcal{NP})-完全的;对于魔法位棋盘的最优打包,即使已知前两步的解决方案,剩余问题仍是困难的哈希表打包问题,不能通过分解问题来高效获得最优解,应使用启发式算法。
关键信息

  • 哈希表打包问题定义及相关概念,如多个哈希表在内存中的排列及有效打包的条件。
  • 通过归约将(3)-划分问题与哈希表打包问题联系起来,证明哈希表打包问题是强(\mathcal{NP})-完全的。
  • 魔法位棋盘优化的复杂问题及与哈希表打包问题的关系,即使已知前两步解决方案,剩余问题仍困难。
    重要细节
  • 给出了哈希表打包问题的实例及决策问题,如给定哈希表列表和整数(K),判断是否存在大小不大于(K)的有效哈希表打包。
  • 证明哈希表打包问题属于(\mathcal{NP})类及(\mathcal{NP})-难类的过程,包括从(3)-划分问题进行归约的构造。
  • 关于魔法位棋盘优化中不同步骤的相互关系及与哈希表打包问题的联系,如不能通过分解问题来高效获得最优解等。
阅读 9
0 条评论