基于软边缘匹配的26块六边形瓷砖最优排布方案技术问询

现有26块六边形瓷砖，每块瓷砖的6条边均不相同，可在无界六边形网格中任意放置且允许旋转。相邻瓷砖边缘匹配时可获得0、1、2或3分（已构建尺寸为(26×6)×(26×6)的匹配得分数组），目标是最大化所有边缘匹配的总得分，对排布形状无要求。

已尝试的求解方向 #

• 构建MIP求解完整问题：但开放求解器下，仅16块无旋转正方形瓷砖的4×4网格问题就需要15分钟，因此26块带旋转的六边形瓷砖方案不可行；
• 考虑动态规划：经评估同样不可行；
• 贪心算法：逐个放置瓷砖，每次选择能使当前得分最大的瓷砖、位置及旋转方式，平局时随机选择。目前最佳得分为116，约每10000次运行出现一次；
• 毁弃重建（ruin-and-recreate）变体：先通过贪心算法生成初始解，随机移除若干瓷砖后用相同贪心逻辑重新放置，若新解得分更高则替换原解。已用该方法得到3种得分117的配置；
• 编写MIP用于最优重插移除的瓷砖：仅支持最多重插5块瓷砖，无法实现得分进一步提升。

需求 #

寻求未尝试过的可行求解方法或相关参考文献。

内容的提问来源于stack exchange，提问作者yaron