最优多联骨牌围栏
Optimal Polyomino Fences
Alexis Langlois-Rémillard, Mia N. Müßig, Helmut Podhaisky, Erika Roldan, Günter Rote, Maximilian Brömme, Matthes Norden, Maximilian Prietzel 等 10 位作者
AI 速读 基于摘要
该论文用动态规划方法研究多联骨牌围栏问题，证明了五联骨牌和六联骨牌围栏的最优性，并给出了高达15联骨牌的启发式解和上界，还将问题推广到三维。
math.CO · cs.CG · cs.DM
查看原文摘要
The $n$-omino fence problem asks how many cells can be surrounded by placing every $n$-omino exactly once in the grid. We present a new dynamic programming approach for this problem, allowing us to prove optimality for the pentomino and hexomino fence and to classify all possible pentomino orders by optimal area. For the first time we also provide strong heuristic solutions and upper bounds for all fences up to $n = 15$, after which we even approximate the $500$-omino fence with computational experiments. Finally, we generalize the problem to 3D, where we prove optimality for pentacubes and derive heuristic solutions for hexacubes and heptacubes.