algorithm - 优化 2D 调色板排列的算法

Question

给定一组256种颜色，我希望从这些颜色中创建一个16 x 16 的调色板，其中颜色之间所有 4 连接差异的总和最小。当然有256个！不同的安排，因此不考虑蛮力。

我尝试使用贪心算法，从最接近黑色的颜色开始，然后以 zig-zig 对角线方式通过 16x16 网格将最接近的未使用颜色插入已插入的一两个邻居。结果是以下（糟糕的）调色板：

我使用 RGB的低成本近似值来使用感知差异。当然，无论差异度量如何，算法都应该是相同的。

我假设最佳解决方案是（至少）NP-hard（我不确定 NP 验证器将如何工作，所以这个问题甚至可能不在 NP 中）。如果没有，请告诉我。否则，好的启发式解决方案是可以接受的。

标签： algorithmoptimizationcolors