引用jnazario · 2014-03
“see this research:”
引这项研究作为洪水填充游戏是 NP-hard 的依据
证明 Flood-It 在三色及以上时 NP 难,并给出近似算法与步数界
论文研究单人益智游戏 Flood-It:求把整块棋盘变成同一种颜色所需的最少填充次数。作者证明当颜色数 c≥3 时该问题 NP 难,c=2 的“自由”变体属于 P,并给出 c-1 近似和随机化的 2c/3 近似算法,同时证明除非 P=NP 否则不存在与 c 无关的常数因子多项式近似。他们还分析了最难棋盘所需的步数增长,以及随机棋盘需要的步数下界为 Ω(n)。
评论者把它当作洪水填充类游戏是 NP 难问题的依据,推荐给对 Flood-It 感兴趣的人。
“see this research:”
“Bonus, a paper on flood-it: The Complexity of Flood Filling Games”