允许一种颜色相邻的索引着色问题的优化

Question

我遇到了这个索引着色问题（不完全是典型的图形 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;
    }
}

Answer 1

是的，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)

无论如何。

允许一种颜色相邻的索引着色问题的优化

Optimization of Index coloring problem with one color adjacent allowed

algorithm

backtracking

data-structures

graph-coloring

recursive-backtracking