四色图定理递归回溯算法
Four Color Map Theorem Recursive Backtracking Algorithm
我已经编写了以下程序来递归地实现四色地图定理(简而言之,任何地图只能用 4 种颜色着色,没有任何相邻区域是相同的颜色)。一切都编译,但我的输出给我错误的数据(-1 代表每个区域的颜色,而不是现在的值 0-3)。我最大的问题是为什么输出不正确。
对于那些想知道的人,输入文件是一个邻接矩阵,如下所示:
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
这是我的代码:
public class FourColorMapThm
{
public static boolean acceptable(int[] map, int[][] matrix, int r, int c)
{
for(int i = 0; i < map.length; i++)
{
if(matrix[r][i] == 1)
{
if(map[i] == c) return false;
}
}
return true;
}
public static boolean colorTheMap(int[] map, int[][] matrix, int r, int c)
{
boolean q = false;
int i = 0;
if(!acceptable(map, matrix, r, i)) return false;
map[r] = i;
boolean done = true;
for(int j = 0; j < map.length; j++)
{
if(map[j] == -1)
{
done = false;
}
}
if(done) return true;
do
{
i++;
q = colorTheMap(map, matrix, r+1, i);
if(q) return true;
}
while(i <= 3);
map[r] = -1;
return false;
}
public static void main(String[] args) throws IOException
{
Scanner in = new Scanner(System.in);
String snumRegions, fileName;
int numRegions;
System.out.print("Enter the number of regions: ");
snumRegions = in.nextLine();
numRegions = Integer.parseInt(snumRegions);
System.out.print("\nEnter filename for adjacency matrix: ");
fileName = in.nextLine();
in.close();
Scanner inFile = new Scanner(new FileReader(fileName));
PrintWriter outFile = new PrintWriter("coloredMap.txt");
int[][] matrix = new int[numRegions][numRegions];
int[] map = new int[numRegions];
//initializing matrix from file
for(int row = 0; row < matrix.length; row++)
{
for(int col = 0; col < matrix.length; col++)
{
matrix[row][col] = inFile.nextInt();
}
}
inFile.close();
//initialize map vals to -1
for(int i = 0; i < map.length; i++)
{
map[i] = -1;
}
colorTheMap(map, matrix, 0, 0);
outFile.println("Region\t\tColor");
for(int i = 0; i < map.length; i++)
{
outFile.println(i+1 + "\t\t" + map[i]);
}
outFile.close();
}
}
您没有在 colorTheMap
中使用 c
,您可能想要使用。
您获得包含所有条目 -1
的 map
的原因是:
int i = 0;
if(!acceptable(map, matrix, r, i)) return false;
map[r] = i;
.
.
.
do
{
i++;
q = colorTheMap(map, matrix, r+1, i);
if(q) return true;
}
while(i <= 3);
map[r] = -1;
colorTheMap(map, matrix, r+1, i)
returns false
的每个调用在它命中的那一刻
int i = 0;
if(!acceptable(map, matrix, r, i)) return false;
如果它的任何邻居已经用 0
着色(因为你从不使用 c
,你将始终在 [=23] 中将 0
分配给 map[r]
=] 如果你到达那条线),所以在 return 之后,我们会立即 return false
,然后再将任何颜色分配给 r
。我假设你的输入图是连接的,所以 colorTheMap(map, matrix, r, c)
的任何调用要么找到 r
的邻居,用 0
着色,甚至没有将 map[r]
设置为其他任何东西,因为if(!acceptable(map, matrix, r, i)) return false;
将立即 return,或者它只接收
中的 q = false
的赋值
do
{
i++;
q = colorTheMap(map, matrix, r+1, i);
if(q) return true;
}
while(i <= 3);
并撤消循环后 map[r] = -1;
行中的着色。
另一个注意事项:我假设您正在尝试实现贪婪着色,但这不是最佳选择,即您可能会以这种方式结束无色区域。四色问题比简单的“只要用邻居的颜色none给所有东西上色就可以了”要复杂得多,否则它不会花一个多世纪的时间来证明四种颜色足以显示。 Here is what looks like an outline of a correct algorithm that takes quadratic time (citation in case the link gets lost: Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas. 1996. Efficiently four-coloring planar graphs. In Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing (STOC '96). Association for Computing Machinery, New York, NY, USA, 571–575. DOI:https://doi.org/10.1145/237814.238005)。又过了 20 年才出现了平面图四色总是可能的证明。
我已经编写了以下程序来递归地实现四色地图定理(简而言之,任何地图只能用 4 种颜色着色,没有任何相邻区域是相同的颜色)。一切都编译,但我的输出给我错误的数据(-1 代表每个区域的颜色,而不是现在的值 0-3)。我最大的问题是为什么输出不正确。
对于那些想知道的人,输入文件是一个邻接矩阵,如下所示:
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
这是我的代码:
public class FourColorMapThm
{
public static boolean acceptable(int[] map, int[][] matrix, int r, int c)
{
for(int i = 0; i < map.length; i++)
{
if(matrix[r][i] == 1)
{
if(map[i] == c) return false;
}
}
return true;
}
public static boolean colorTheMap(int[] map, int[][] matrix, int r, int c)
{
boolean q = false;
int i = 0;
if(!acceptable(map, matrix, r, i)) return false;
map[r] = i;
boolean done = true;
for(int j = 0; j < map.length; j++)
{
if(map[j] == -1)
{
done = false;
}
}
if(done) return true;
do
{
i++;
q = colorTheMap(map, matrix, r+1, i);
if(q) return true;
}
while(i <= 3);
map[r] = -1;
return false;
}
public static void main(String[] args) throws IOException
{
Scanner in = new Scanner(System.in);
String snumRegions, fileName;
int numRegions;
System.out.print("Enter the number of regions: ");
snumRegions = in.nextLine();
numRegions = Integer.parseInt(snumRegions);
System.out.print("\nEnter filename for adjacency matrix: ");
fileName = in.nextLine();
in.close();
Scanner inFile = new Scanner(new FileReader(fileName));
PrintWriter outFile = new PrintWriter("coloredMap.txt");
int[][] matrix = new int[numRegions][numRegions];
int[] map = new int[numRegions];
//initializing matrix from file
for(int row = 0; row < matrix.length; row++)
{
for(int col = 0; col < matrix.length; col++)
{
matrix[row][col] = inFile.nextInt();
}
}
inFile.close();
//initialize map vals to -1
for(int i = 0; i < map.length; i++)
{
map[i] = -1;
}
colorTheMap(map, matrix, 0, 0);
outFile.println("Region\t\tColor");
for(int i = 0; i < map.length; i++)
{
outFile.println(i+1 + "\t\t" + map[i]);
}
outFile.close();
}
}
您没有在 colorTheMap
中使用 c
,您可能想要使用。
您获得包含所有条目 -1
的 map
的原因是:
int i = 0;
if(!acceptable(map, matrix, r, i)) return false;
map[r] = i;
.
.
.
do
{
i++;
q = colorTheMap(map, matrix, r+1, i);
if(q) return true;
}
while(i <= 3);
map[r] = -1;
colorTheMap(map, matrix, r+1, i)
returns false
的每个调用在它命中的那一刻
int i = 0;
if(!acceptable(map, matrix, r, i)) return false;
如果它的任何邻居已经用 0
着色(因为你从不使用 c
,你将始终在 [=23] 中将 0
分配给 map[r]
=] 如果你到达那条线),所以在 return 之后,我们会立即 return false
,然后再将任何颜色分配给 r
。我假设你的输入图是连接的,所以 colorTheMap(map, matrix, r, c)
的任何调用要么找到 r
的邻居,用 0
着色,甚至没有将 map[r]
设置为其他任何东西,因为if(!acceptable(map, matrix, r, i)) return false;
将立即 return,或者它只接收
q = false
的赋值
do
{
i++;
q = colorTheMap(map, matrix, r+1, i);
if(q) return true;
}
while(i <= 3);
并撤消循环后 map[r] = -1;
行中的着色。
另一个注意事项:我假设您正在尝试实现贪婪着色,但这不是最佳选择,即您可能会以这种方式结束无色区域。四色问题比简单的“只要用邻居的颜色none给所有东西上色就可以了”要复杂得多,否则它不会花一个多世纪的时间来证明四种颜色足以显示。 Here is what looks like an outline of a correct algorithm that takes quadratic time (citation in case the link gets lost: Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas. 1996. Efficiently four-coloring planar graphs. In Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing (STOC '96). Association for Computing Machinery, New York, NY, USA, 571–575. DOI:https://doi.org/10.1145/237814.238005)。又过了 20 年才出现了平面图四色总是可能的证明。