Electronic Joint Business

Solution for E-Business

用图着色来解决数独问题

在本文中,我将简单介绍图着色(graph coloring) 的概念,并演示如何用这一概念来解决 9×9 的数独(Sudoku Puzzle)。本文假设读者已对图(graph)的概念和表现形式相当熟悉。1 揭秘图着色 图是一组彼此之间互相链接的对象的数学表示。对象表示为顶点(节点),链接则称为边。 图着色则是为图的顶点指定”颜色”,让相邻的两个顶点不能共享相同的颜色。比如在上图中顶点 1 和 2 不能用相同的颜色因为有一条边连接着它们。然而顶点 2 和 3 可以用相同的颜色,因为它们彼此并未连接。下面可能的着色图之一。 很显然,图可以有多种可能的着色。我们的目标是力求使用最少的颜色。图1-3是另外两个可能的着色图。着色图(1)使用了3种颜色,而着色图(2)使用5种颜色,因此 着色图(1)比着色图(2)更好。 对于给定的图,着色是是为了使图可以正常着色的最少颜色数。使用至多 k 种颜色的着色被称为 K-着色(比如上面的例子中,着色图(1)为3-着色,而着色图(2)是5-着色)。 如果你想试试用两种颜色能不能对上图正常着色,你会发现这根本做不到,不信可以试试。因此,使图可以正常着色的最少颜色数被称为“色数”。 收缩和贪婪着色算法— Contraction and Greedy Coloring Algorithms 着色问题已经作为一个课题被研究了许多年。目前的大部分算法可以大致被归类为两个标题之一:“收缩 — Contraction ”与“贪婪着色 — Greedy Coloring ”。 贪婪着色关注于仔细挑选下一个要着色的顶点。顶点一旦着色后,其颜色就不会改变。该类别的算法之间的差异主要在于挑选下一个顶点的方法。 其中一个著名的算法是威尔士-鲍威尔算法(Welsh–Powell)。具体步骤如下: 1. 找出每个顶点的度数。(度数:与顶点相连接的边数) 2. 根据顶点的度数进行降序排序。 3. 遍历该列表,对未和已着色顶点相连的顶点,使用相同的颜色进行着色。 4. 将已着色的顶点的移除,对剩下的顶点反复进行着色直到所有顶点都被着色为止。 我们用图1-1作为例子来详细了解这一过程。 第一步:找到所有顶点的度数 顶点      度 1 […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.