四色定理 [英] Four Color Theorem

问题描述

我一直想写一个code，将使用四色定理由邻接矩阵定义的颜色区域。邻接矩阵如下所示：

I have been trying to write a code that would use the four color theorem to color regions defined by an adjacency matrix. An adjacency matrix would look like:

    A B C D

A   0 1 0 1
B   1 0 1 0
C   0 1 0 1
D   1 0 1 0

因此​​，对于这个例子，A是不相邻本身或C，但它是相邻B和D

So for this example A is not adjacent to itself or C, but it is adjacent to B and D.

我写的程序必须使用递归和回追踪指定4种颜色（或更少）来定义的地区。

The program I am writing has to use recursion and back-tracing to assign 4 colors (or less) to the defined regions.

到目前为止，我的算法如下：

So far my algorithm is as follows:

global int[] colors = <region one color,region two, region three, region four >
public static int color(row,column)
  if out of bounds ??
    loop(!colored)
    {
      case 1: are any adjacent regions this color? assign
      case 2: are any adjacent regions this color? assign.
      case 3: are any adjacent regions this color? assign.
      case 4: are any adjacent regions this color? assign.
      case 5: if nothing found, steal closest (in #) region's color and call method from there
  }

不过，我有几个问题：

But I have a few questions:

1. 会是什么这个方法的返回？
2. 将这项工作，并有递归/回溯像它应注意什么？
3. 我会怎么输出，如果给定的行/列出界？

感谢您！

推荐答案

您伪code看起来更像的比递归/回溯本地搜索。合乎逻辑的回报将是无效，因为本地搜索不能证明没有一个解决方案，所以失败是由运行下去表示。 （着色本身，如果找到，通过全局变量返回。）

Your pseudocode looks more like local search than recursion/backtracking. The logical return would be void, since local search cannot prove the absence of a solution, so failure is indicated by running forever. (The coloring itself, if found, is returned via the global variables.)

递归/回溯会更喜欢这样。

Recursion/backtracking would be more like this.

boolean extend-coloring(partial-coloring):
    if every vertex has a color, then return true
    let v be a vertex without a color
    for each color c,
        if v has no neighbors of color c,
            apply color c to v in partial-coloring
            if extend-coloring(partial-coloring), then return true
            remove color c from v
    return false

根调用是扩展着色（空着色），其中空着色分配没有顶点颜色。返回值指示尝试延长部分着色是否成功。

The root invocation is extend-coloring(empty-coloring), where empty-coloring assigns no vertex a color. The return value indicates whether the attempt to extend the partial coloring succeeded.

这篇关于四色定理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！