允许一种颜色相邻的索引着色问题的优化
Optimization of Index coloring problem with one color adjacent allowed
我遇到了这个索引着色问题(不完全是典型的图形 m 着色问题),我试图使用回溯来解决这个问题,但该解决方案仅适用于低值测试用例,而对于较大的测试用例则由于指数而失败时间复杂度。
如何优化它,使其在指数时间内不会 运行。有没有DP方法可以解决这个问题?
Problem statement:
You are given 3 variables: n, k, x
n -> Number of indices to be colored
k -> Number of colors available -> 1,2,3,...K
x -> Color ID which can be used to color two adjacent indices.
You have to color n indices
placed on the x-axis with k colors such that no two adjacent
indices have the same color.
However, you are also given x which is
a colorID which is an exception to the above rule such that it
is allowed to have two adjacent nodes with color = colorID.
You have to find out total number of ways all indices can be colored while following the above rules.
Example. For, n = 3 k = 2 x = 1 : All possible solutions are: (1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,1,2)
以下是我的解决方案。
public class ColoringIndices {
public static void main(String[] args) {
int n = 17;
int k = 4;
int x = 3;
placeColors(n, k, x);
}
static int count = 0;
private static void placeColors(int n, int k, int x) {
int currpos = 0;
int[] arr = new int[n];
placeColorsUtil(n, k, x, currpos, arr);
System.out.println(count % 1000000007);
count = 0;
}
private static void placeColorsUtil(int n, int k, int x, int currpos, int[] arr) {
if(currpos == n){
int mod = 1000000007;
count = count % mod;
count++;
return;
}
for (int colorId = 1; colorId <= k; colorId++) {
if (isSafe(colorId, currpos, arr, x)) {
arr[currpos] = colorId;
placeColorsUtil(n, k, x, currpos + 1, arr);
}
}
}
private static boolean isSafe(int colorId, int currpos, int[] arr, int x) {
if (currpos < arr.length && currpos > 0) {
if (colorId != x && arr[currpos - 1] == colorId) {
return false;
}
}
return true;
}
}
是的,DP 是最后一个彩色索引是否是 x
。我们得到两次重复
X(n) = number of valid sequences of length n ending in x
Y(n) = number of valid sequences of length n not ending in x
X(1) = 1
Y(1) = k-1
X(n+1) = X(n) + Y(n)
| | \__/
\/ continue sequence not ending in x with x
continue sequence ending in x with another x
Y(n+1) = (k-1) X(n) + (k-2) Y(n)
| | \________/
| | continue sequence not ending in x in k-2 possible ways
\______/ (excluding the last color (not x in this case) and x)
continue sequence ending in x in k-1 possible ways (excl. x)
可以及时评价O(n)
。答案是 X(n) + Y(n)
(如果 n
为零,则为 0
)。
为了后代,我会尝试得到一个解析解。 嗯,k
的存在让这变得无趣。实际上,您只是在评估矩阵的适当幂
( 1 1 )
(k-1 k-2)
无论如何。
我遇到了这个索引着色问题(不完全是典型的图形 m 着色问题),我试图使用回溯来解决这个问题,但该解决方案仅适用于低值测试用例,而对于较大的测试用例则由于指数而失败时间复杂度。
如何优化它,使其在指数时间内不会 运行。有没有DP方法可以解决这个问题?
Problem statement:
You are given 3 variables: n, k, x
n -> Number of indices to be colored
k -> Number of colors available -> 1,2,3,...K
x -> Color ID which can be used to color two adjacent indices.
You have to color n indices placed on the x-axis with k colors such that no two adjacent indices have the same color. However, you are also given x which is a colorID which is an exception to the above rule such that it is allowed to have two adjacent nodes with color = colorID.
You have to find out total number of ways all indices can be colored while following the above rules.
Example. For, n = 3 k = 2 x = 1 : All possible solutions are: (1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,1,2)
以下是我的解决方案。
public class ColoringIndices {
public static void main(String[] args) {
int n = 17;
int k = 4;
int x = 3;
placeColors(n, k, x);
}
static int count = 0;
private static void placeColors(int n, int k, int x) {
int currpos = 0;
int[] arr = new int[n];
placeColorsUtil(n, k, x, currpos, arr);
System.out.println(count % 1000000007);
count = 0;
}
private static void placeColorsUtil(int n, int k, int x, int currpos, int[] arr) {
if(currpos == n){
int mod = 1000000007;
count = count % mod;
count++;
return;
}
for (int colorId = 1; colorId <= k; colorId++) {
if (isSafe(colorId, currpos, arr, x)) {
arr[currpos] = colorId;
placeColorsUtil(n, k, x, currpos + 1, arr);
}
}
}
private static boolean isSafe(int colorId, int currpos, int[] arr, int x) {
if (currpos < arr.length && currpos > 0) {
if (colorId != x && arr[currpos - 1] == colorId) {
return false;
}
}
return true;
}
}
是的,DP 是最后一个彩色索引是否是 x
。我们得到两次重复
X(n) = number of valid sequences of length n ending in x
Y(n) = number of valid sequences of length n not ending in x
X(1) = 1
Y(1) = k-1
X(n+1) = X(n) + Y(n)
| | \__/
\/ continue sequence not ending in x with x
continue sequence ending in x with another x
Y(n+1) = (k-1) X(n) + (k-2) Y(n)
| | \________/
| | continue sequence not ending in x in k-2 possible ways
\______/ (excluding the last color (not x in this case) and x)
continue sequence ending in x in k-1 possible ways (excl. x)
可以及时评价O(n)
。答案是 X(n) + Y(n)
(如果 n
为零,则为 0
)。
为了后代,我会尝试得到一个解析解。 嗯,k
的存在让这变得无趣。实际上,您只是在评估矩阵的适当幂
( 1 1 )
(k-1 k-2)
无论如何。