组织毡尖笔：通过相邻项目的相似性优化 2D 网格中项目的排列，使用 JS [更新]

Question

组织毡尖笔：通过相邻项目的相似性优化 2D 网格中项目的排列，使用 JS [更新]

And*_*aus 36 javascript arrays algorithm matrix mathematical-optimization

UPD：问题已经更新了细节和代码，见下文。

警告：这个问题是关于优化矩阵中项目的排列。这不是比较颜色。最初，我决定提供有关我的问题的上下文会有所帮助。我现在后悔这个决定，因为结果恰恰相反：关于颜色的无关紧要的谈论太多，而对实际算法几乎没有。

我为我的孩子准备了一盒 80 支毡尖笔，这让我很恼火，以至于它们没有分类。

我曾经在 Android 上玩过一个叫做 Blendoku 的游戏，你需要这样做：以形成渐变的方式排列颜色，附近的颜色最相似：

像填字游戏一样在交叉线上组织颜色既简单又有趣。但是有了这些草图标记，我就有了一个完整的 2D 网格。更糟糕的是，颜色不是从均匀渐变中提取的。

这让我无法凭直觉对毡尖笔进行分类。我需要用算法来做！

这是我所拥有的：

扎实的 JavaScript 知识
所有笔的颜色值的平面数组
甲功能 distance(color1, color2)，显示一个颜色对是如何相似。它返回一个浮点数0和100where0表示颜色相同。

我所缺少的只是一个算法。

阶乘80是一个 118 位的数字，它排除了暴力破解。

可能有一些方法可以使暴力破解可行：

固定几支笔的位置（例如在角落）以减少可能的组合数量；
删除包含至少一对非常不同的邻居的分支；
找到第一个满意的安排后停止。

但我仍然缺乏一个实际的算法，更不用说一个非暴力的算法了。

PS作业：

按相似度对矩阵进行排序- 没有答案。
最佳 2D 调色板排列算法——非常相似的问题，没有答案。
如何在二维中对颜色进行排序？-- 超过 50% 的单元格已经包含正确组织的颜色；不熟悉的编程语言；没有解释实际的排序解决方案。
排序颜色/颜色值——单个平面阵列。

更新

目标

在 8×10 网格中排列一组预定义的 80 种颜色，使颜色形成漂亮的渐变而不会撕裂。

由于以下原因，这个问题没有明确的解决方案，可能的解决方案容易产生不完美的结果和主观性。这是预期的。

请注意，我已经有一个函数可以比较两种颜色并说明它们的相似程度。

色彩空间是 3D

人眼具有三种类型的感受器来区分颜色。人类色彩空间是三维的（三色）。

描述颜色有不同的模型，它们都是三维的：RGB、HSL、HSV、XYZ、LAB、CMY（请注意，CMYK 中的“K”只是必需的，因为彩色墨水并非完全不透明且价格昂贵）。

例如，这个调色板：

...使用极坐标，角度为色调，半径为饱和度。没有第三维（亮度），这个调色板缺少所有明亮和黑暗的颜色：白色、黑色、所有灰色（除了中心的 50% 灰色）和有色灰色。

这个调色板只是 HSL/HSV 色彩空间的一小部分：

不可能在不撕裂渐变的情况下以渐变的方式在 2D 网格上布置所有颜色。

例如，这里是所有 32 位 RGB 颜色，按字典顺序枚举到 2D 网格中。可以看到渐变有很多撕裂：

因此，我的目标是找到一个任意的、“足够好”的安排，其中邻居或多或少相似。我宁愿牺牲一点相似性，也不愿有几个非常相似的集群，它们之间存在撕裂。

这个问题是关于在 JavaScript 中优化网格，而不是关于比较颜色！

我已经选择了一个函数来确定颜色的相似性：Delta E 2000。此功能专门用于反映人类对颜色相似性的主观感知。这是一份白皮书，描述了它是如何工作的。

这个问题是关于优化 2D 网格中项目的排列方式，使得每对相邻项目（垂直和水平）的相似度尽可能低。

使用“优化”一词并不是为了让算法运行得更快。它在某种意义上是数学优化：

在最简单的情况下，优化问题包括通过系统地从允许的集合中选择输入值并计算函数值来最大化或最小化实际函数。

就我而言：

这里的“函数”意味着DeltaE.getDeltaE00(color1, color2)为所有相邻项目运行该函数，输出是一堆数字（其中 142 个......我认为）反映了所有相邻对的不同程度。
“最大化或最小化”——目标是最小化“函数”的输出。
“一个输入值”——是 8×10 网格中 80 个预定义项目的特定排列。共有80!输入值，这使得该任务无法在家用计算机上进行暴力破解。

请注意，我对“函数”的最小化标准没有明确的定义。如果我们简单地使用所有数字的最小总和，那么获胜的结果可能是总和最小的情况，但几个相邻的项目对非常不同。

因此，“函数”可能不仅应该考虑所有比较的总和，而且还应该确保没有任何比较。

解决问题的可能途径

从我之前对这个问题的赏金尝试中，我学到了以下途径：

遗传算法
优化器/求解器库
使用一些算法帮助手动排序
还有什么？

优化器/求解器库解决方案正是我最初所希望的。但是 CPLEX 和 Gurobi 等成熟的库不在 JS 中。有一些 JS 库，但它们没有很好的文档记录，也没有新手教程。

遗传算法方法非常令人兴奋。但它需要考虑变异和交配样本（网格排列）的算法。变异似乎微不足道：只需交换相邻的项目。但我不知道交配。总的来说，我对整个事情知之甚少。

手动排序建议乍一看似乎很有希望，但在深入研究它们时却不尽如人意。他们还假设在不提供实际算法的情况下使用算法来解决某些步骤。

代码样板和颜色样本

我在 JS 中准备了一个代码样板：https ://codepen.io/lolmaus/pen/oNxGmqz?editors =0010

注意：代码需要一段时间才能运行。要更轻松地使用它，请执行以下操作：

登录/注册 CodePen 以便能够分叉样板。
分叉样板。
转到设置/行为并确保禁用自动更新。
调整窗格大小以最大化 JS 窗格并最小化其他窗格。
转到更改视图/调试模式以在单独的选项卡中打开结果。这使console.log(). 此外，如果代码执行冻结，您可以终止渲染选项卡而不会失去对编码选项卡的访问权限。
更改代码后，在代码选项卡中点击保存，然后刷新渲染选项卡并等待。
要包含 JS 库，请转到 Settings/JS。我使用此 CDN 链接到来自 GitHub 的代码：https : //www.jsdelivr.com/? docs =gh

源数据：

const data = [
  {index: 1, id: "1", name: "Wine Red", rgb: "#A35A6E"},
  {index: 2, id: "3", name: "Rose Red", rgb: "#F3595F"},
  {index: 3, id: "4", name: "Vivid Red", rgb: "#F4565F"},
  // ...
];

Run Code Online (Sandbox Code Playgroud)

索引是颜色的基于 1 的编号，按照它们在框中出现的顺序，按 id 排序。它在代码中未使用。

Id 是钢笔制造商的颜色编号。由于某些数字的形式为WG3，因此 id 是字符串。

颜色类。

这个类提供了一些抽象来处理单独的颜色。它可以轻松地将给定颜色与另一种颜色进行比较。

  index;
  id;
  name;
  rgbStr;
  collection;
  
  constructor({index, id, name, rgb}, collection) {
    this.index = index;
    this.id = id;
    this.name = name;
    this.rgbStr = rgb;
    this.collection = collection;
  }
  
  // Representation of RGB color stirng in a format consumable by the `rgb2lab` function
  @memoized
  get rgbArr() {
    return [
      parseInt(this.rgbStr.slice(1,3), 16),
      parseInt(this.rgbStr.slice(3,5), 16),
      parseInt(this.rgbStr.slice(5,7), 16)
    ];
  }
  
  // LAB value of the color in a format consumable by the DeltaE function
  @memoized
  get labObj() {
    const [L, A, B] = rgb2lab(this.rgbArr);
    return {L, A, B};
  }

  // object where distances from current color to all other colors are calculated
  // {id: {distance, color}}
  @memoized
  get distancesObj() {
    return this.collection.colors.reduce((result, color) => {
      if (color !== this) {      
        result[color.id] = {
          distance: this.compare(color),
          color,
        };
      }
      
      return result;
    }, {});
  }
    
  // array of distances from current color to all other colors
  // [{distance, color}]
  @memoized
  get distancesArr() {
    return Object.values(this.distancesObj);
  }
  
  // Number reprtesenting sum of distances from this color to all other colors
  @memoized
  get totalDistance() {
    return this.distancesArr.reduce((result, {distance}) => {      
      return result + distance;
    }, 0); 
  }

  // Accepts another color instance. Returns a number indicating distance between two numbers.
  // Lower number means more similarity.
  compare(color) {
    return DeltaE.getDeltaE00(this.labObj, color.labObj);
  }
}

Run Code Online (Sandbox Code Playgroud)

集合：一个用于存储所有颜色并对其进行排序的类。

  index;
  id;
  name;
  rgbStr;
  collection;
  
  constructor({index, id, name, rgb}, collection) {
    this.index = index;
    this.id = id;
    this.name = name;
    this.rgbStr = rgb;
    this.collection = collection;
  }
  
  // Representation of RGB color stirng in a format consumable by the `rgb2lab` function
  @memoized
  get rgbArr() {
    return [
      parseInt(this.rgbStr.slice(1,3), 16),
      parseInt(this.rgbStr.slice(3,5), 16),
      parseInt(this.rgbStr.slice(5,7), 16)
    ];
  }
  
  // LAB value of the color in a format consumable by the DeltaE function
  @memoized
  get labObj() {
    const [L, A, B] = rgb2lab(this.rgbArr);
    return {L, A, B};
  }

  // object where distances from current color to all other colors are calculated
  // {id: {distance, color}}
  @memoized
  get distancesObj() {
    return this.collection.colors.reduce((result, color) => {
      if (color !== this) {      
        result[color.id] = {
          distance: this.compare(color),
          color,
        };
      }
      
      return result;
    }, {});
  }
    
  // array of distances from current color to all other colors
  // [{distance, color}]
  @memoized
  get distancesArr() {
    return Object.values(this.distancesObj);
  }
  
  // Number reprtesenting sum of distances from this color to all other colors
  @memoized
  get totalDistance() {
    return this.distancesArr.reduce((result, {distance}) => {      
      return result + distance;
    }, 0); 
  }

  // Accepts another color instance. Returns a number indicating distance between two numbers.
  // Lower number means more similarity.
  compare(color) {
    return DeltaE.getDeltaE00(this.labObj, color.labObj);
  }
}

Run Code Online (Sandbox Code Playgroud)

用法：

class Collection {
  // Source data goes here. Do not mutate after setting in the constructor!
  data;
  
  constructor(data) {
    this.data = data;
  }
  
  // Instantiates all colors
  @memoized
  get colors() {
    const colors = [];

    data.forEach((datum) => {
      const color = new Color(datum, this);
      colors.push(color);
    });
  
    return colors;    
  }

  // Copy of the colors array, sorted by total distance
  @memoized
  get colorsSortedByTotalDistance() {
    return this.colors.slice().sort((a, b) => a.totalDistance - b.totalDistance);
  }

  // Copy of the colors array, arranged by similarity of adjacent items
  @memoized
  get colorsLinear() {
    // Create copy of colors array to manipualte with
    const colors = this.colors.slice();
    
    // Pick starting color
    const startingColor = colors.find((color) => color.id === "138");
    
    // Remove starting color
    const startingColorIndex = colors.indexOf(startingColor);
    colors.splice(startingColorIndex, 1);
    
    // Start populating ordered array
    const result = [startingColor];
    
    let i = 0;
    
    while (colors.length) {
      
      if (i >= 81) throw new Error('Too many iterations');

      const color = result[result.length - 1];
      colors.sort((a, b) => a.distancesObj[color.id].distance - b.distancesObj[color.id].distance);
      
      const nextColor = colors.shift();
      result.push(nextColor);
    }
    
    return result;
  }

  // Accepts name of a property containing a flat array of colors.
  // Renders those colors into HTML. CSS makes color wrap into 8 rows, with 10 colors in every row.
  render(propertyName) {
    const html =
      this[propertyName]
        .map((color) => {
          return `
          <div
            class="color"
            style="--color: ${color.rgbStr};"
            title="${color.name}\n${color.rgbStr}"
          >
            <span class="color-name">
              ${color.id}
            </span>
          </div>
          `;
        })
        .join("\n\n");
    
    document.querySelector('#box').innerHTML = html;
    document.querySelector('#title').innerHTML = propertyName;
  }
}

Run Code Online (Sandbox Code Playgroud)

示例输出：

Answer 1

Dav*_*tat 9

通过将几个想法装订在一起，我设法找到了一个目标值为 1861.54 的解决方案。

通过找到最小成本匹配并连接匹配的子簇，形成大小为 8 的无序颜色簇，重复 3 次。我们使用 d(C1, C2) = ? _{C1 中的 C1} ? _{C2 中的 c2} d(c1, c2) 作为子簇 C1 和 C2 的距离函数。
根据上述距离函数找到最佳的 2 × 5 簇排列。这涉及到暴力破解 10！排列（如果利用对称性，真的是 10！/4，我没有打扰）。
分别考虑每个集群，通过强制 8! 找到最佳的 4 × 2 排列！排列。（更多的对称破坏可能，我没有打扰。）
蛮力翻转集群的 4 ^{10 种}可能方法。（甚至可能破坏更多的对称性，我没有打扰。）
通过本地搜索改进这种安排。我交错了两种轮次：一个 2-opt 轮次，其中每对位置都被考虑进行交换，以及一个大邻域轮次，我们选择一个随机的最大独立集并使用匈牙利方法进行最佳重新分配（这个问题很容易当我们试图移动的任何东西都不能彼此相邻）。

输出如下所示：

Python 实现在https://github.com/eisenstatdavid/felt-tip-pens

Answer 2

id0*_*d01 8

The trick for this is to stop thinking about it as an array for a moment and anchor yourself to the corners.

First, you need to define what problem you are trying to solve. Normal colors have three dimensions: hue, saturation, and value (darkness), so you're not going to be able to consider all three dimensions on a two dimensional grid. However, you can get close.

If you want to arrange from white->black and red->purple, you can define your distance function to treat differences in darkness as distance, as well as differences in hue value (no warping!). This will give you a set, four-corner-compatible sorting for your colors.

Now, anchor each of your colors to the four corners, like so, defining (0:0) as black, (1:1) as white, (0,1) as red (0 hue), and (1:0) as purple-red (350+ hue). Like so (let's say purple-red is purple for simplicity):

Now, you have two metrics of extremes: darkness and hue. But wait... if we rotate the box by 45 degrees...

Do you see it? No? The X and Y axes have aligned with our two metrics! Now all we need to do is divide each color's distance from white with the distance of black from white, and each color's distance from purple with the distance of red from purple, and we get our Y and X coordinates, respectively!

Let's add us a few more pens:

Now iterate over all the pens with O(n)^2, finding the closest distance between any pen and a final pen position, distributed uniformly through the rotated grid. We can keep a mapping of these distances, replacing any distances if the respective pen position has been taken. This will allow us to stick pens into their closest positions in polynomial time O(n)^3.

However, we're not done yet. HSV is 3 dimensional, and we can and should weigh the third dimension into our model too! To do this, we extend the previous algorithm by introducing a third dimension into our model before calculating closest distances. We put our 2d plane into a 3d space by intersecting it with the two color extremes and the horizontal line between white and black. This can be done simply by finding the midpoint of the two color extremes and nudging darkness slightly. Then, generate our pen slots fitted uniformly onto this plane. We can place our pens directly in this 3D space based off their HSV values - H being X, V being Y, and S being Z.

Now that we have the 3d representation of the pens with saturation included, we can once again iterate over the position of pens, finding the closest one for each in polynomial time.

我们走了！好分类的钢笔。如果你想要数组中的结果，只需再次统一为每个数组索引生成坐标并按顺序使用它们！

现在停止整理笔并开始编写代码！

Answer 3

Ber*_*ach 5

正如在某些评论中向您指出的那样，您似乎对找到离散优化问题的全局最小值之一感兴趣。如果您对此知之甚少，则可能需要仔细阅读。

想象一下，您有一个误差（目标）函数，它只是所有 (c1, c2) 对相邻笔的距离 (c1, c2) 之和。最佳解决方案（笔的布置）是误差函数最小的解决方案。可能有多个最优解。请注意，不同的误差函数可能会给出不同的解决方案，您可能对我刚刚介绍的简单化误差函数提供的结果不满意。

您可以使用现成的优化器（例如 CPLEX 或 Gurobi），然后将问题的有效公式提供给它。它可能会找到最佳解决方案。但是，即使没有，它仍然可能提供对您的眼睛非常有益的次优解决方案。

您还可以编写自己的启发式算法（例如专门的遗传算法）并获得比求解器在其时间和空间限制内为您找到的更好的解决方案。鉴于您的武器似乎是输入数据、测量颜色差异的函数和 JavaScript，实现启发式算法可能是您最熟悉的路径。

我的答案最初没有代码，因为与大多数实际问题一样，这个问题没有简单的复制粘贴解决方案。

使用 JavaScript 进行这种计算很奇怪，而在浏览器上进行计算则更奇怪。但是，由于作者明确要求，这里是托管在 CodePen 上的简单进化算法的 JavaScript 实现。

由于输入大小比我最初演示此算法时使用的 5x5 大，因此该算法进行了多少代，以及代码执行速度有多慢，所以需要一段时间才能完成。我更新了突变代码以防止突变导致重新计算解决方案成本，但迭代仍然需要相当长的时间。以下解决方案通过 CodePen 的调试模式在我的浏览器中运行大约需要 45 分钟。

其目标函数略小于 2060，并使用以下参数生成。

const SelectionSize = 100;
const MutationsFromSolution = 50;
const MutationCount = 5;
const MaximumGenerationsWithoutImprovement = 5;

Run Code Online (Sandbox Code Playgroud)

值得指出的是，对参数的微小调整会对算法的结果产生重大影响。增加突变数量或选择大小都会显着增加程序的运行时间，但也可能会带来更好的结果。您可以（并且应该）试验这些参数以找到更好的解决方案，但它们可能需要更多的计算时间。

在许多情况下，最好的改进来自算法的改变，而不仅仅是更多的计算能力，因此关于如何执行突变和重组的聪明想法通常是在仍然使用遗传算法的同时获得更好解决方案的方法。

使用明确播种和可重现的 PRNG（而不是 Math.random()）非常棒，因为它允许您根据调试和重现性证明的需要多次重播程序。

您可能还想为算法设置一个可视化（而不是像您暗示的那样只是 console.log()），以便您可以看到它的进度，而不仅仅是它的最终结果。

此外，允许人工交互（以便您可以对算法提出突变并根据您自己对颜色相似性的感知来指导搜索）也可以帮助您获得想要的结果。这将引导您使用交互式遗传算法 (IGA)。文章JC Quiroz、SJ Louis、A. Shankar 和 SM Dascalu，“用户界面设计的交互式遗传算法”，2007 年 IEEE 进化计算大会，新加坡，2007 年，第 1366-1373 页，doi：10.1109/CEC.2046304.4。是这种方法的一个很好的例子。

Answer 4

vvg*_*vvg 4

如果您可以在两种颜色之间定义一个总排序函数来告诉您哪一种颜色是“较深”的颜色，则可以使用此总排序函数对颜色数组进行从暗到亮（或从亮到暗）的排序。

从左上角开始，使用排序数组中的第一种颜色，继续沿对角线穿过网格，并用后续元素填充网格。您将得到一个渐变填充的矩形网格，其中相邻颜色相似。

您认为这会实现您的目标吗？

您可以通过更改总排序函数的行为来更改外观。例如，如果使用如下所示的颜色图按相似性排列颜色，则可以将总排序定义为从一个单元格到下一个单元格的图遍历。通过更改遍历中接下来选择的单元格，您可以获得不同颜色的渐变网格填充。

归档时间：	5 年，4 月前
查看次数：	750 次
最近记录：	5 年，3 月前