算法学习——回溯

回溯算法的经典算法，如素数环问题、哈密顿回路、N皇后问题等。

回溯

经典算法

素数环问题

将正整数1~n填入环中，满足如下条件：

• 每个数字只能用一次
• 相邻两个数字之和是素数，最后一个元素与第一个元素之和也为素数

public static void PrimeCircle(int n) {
    int i, k;
    int[] circle = new int[n];// 素数环
    for (i = 0; i < n; i++) {// 初始化为0
        circle[i] = 0;
    }
    circle[0] = 1;// 第0个位置填1
    k = 1;
    while (k >= 1) {
        circle[k]++;
        while (circle[k] <= n) {
            if (Check(circle, k))// 若位置k可以填写整数circle[k]则跳出内层循环
                break;
            else// 否则试探下一个数
                circle[k]++;
        }
        if (circle[k] <= n && k == n - 1) {// 若求解完毕则输出解，结束算法
            for (int item : circle) {
                System.out.println(item);
            }
            return;
        } else if (circle[k] <= n && k < n - 1)// 若未结束则填写下一个位置
            k++;
        else{// 若每个数字都不能填入，则回溯
            circle[k--] = 0;
        }
    }
}

public static boolean Check(int[] circle, int k) {// 判断第k个位置填写是否满足约束条件
    boolean flag;
    for (int i = 0; i < k; i++) {
        if (circle[i] == circle[k])// 判断是否重复
            return false;
    }
    flag = Prime(circle[k] + circle[k - 1]);// 判断相邻数之和是否为素数
    if (flag && k == circle.length - 1) {// 判断第一个和最后一个数之和是否为素数
        flag = Prime(circle[k] + circle[0]);
    }

    return flag;
}

public static boolean Prime(int x) {// 判断x是否为素数
    int i, n;
    n = (int) Math.sqrt(x);
    for (i = 2; i <= n; i++) {
        if (x % i == 0)
            return false;
    }
    return true;
}

图着色问题

public static void GraphColor(int[][] arc, int m) {// m种颜色
    int i, k = 0;
    int n = arc.length;
    int[] color = new int[n];
    for (i = 0; i < n; i++) {// 初始化
        color[i] = 0;
    }
    while (k >= 0) {
        color[k]++;// 取下一种颜色
        while (color[k] <= m) {
            if (Ok(arc, color, k))// 若顶点k可以填入颜色color[k]则跳出内层循环
                break;
            else// 否则试探下一种颜色
                color[k]++;
        }
        if (color[k] <= m && k == n - 1) {// 若求解完毕，输出解
            for (int item : color) {
                System.out.println(item);
            }
            return;
        } else if (color[k] <= m && k < n - 1)// 若未结束，则填充下一个顶点
            k++;
        else// 若每个颜色都不能填入，则回溯
            color[k--] = 0;
    }
}

public static boolean Ok(int[][] arc, int[] color, int k) {// 判断顶点k的着色是否发生冲突
    for (int i = 0; i < k; i++)
        if (arc[k][i] == 1 && color[i] == color[k])
            return false;
    return true;
}

哈密顿回路

public static void Hamiton(int[][] arc) {
    int i, k;
    int n = arc.length;
    int[] visited = new int[n];
    int[] x = new int[n];// 存储哈密顿回路经过的顶点
    for (i = 0; i < n; i++) {
        x[i] = 0;
        visited[i] = 0;
    }
    x[0] = 0;
    visited[0] = 1;// 从顶点0出发
    k = 1;
    while (k >= 1) {
        x[k]++;
        while (x[k] < n) {
            if (visited[x[k]] == 0 && arc[x[k - 1]][x[k]] == 1)// 顶点x[k]不在哈密顿回路上,且边(x[k-1],x[k])存在
                break;// 则跳出内层循环
            else// 否则试探下一个顶点
                x[k]++;
        }
        if (x[k] < n && k == n - 1 && arc[x[k]][0] == 1) {// 若已经形成哈密顿回路则输出结果
            for (k = 0; k < n; k++)
                System.out.println(x[k] + 1);
            return;
        } else if (x[k] < n && k < n - 1) {// 若还未形成哈密顿回路则继续算法
            visited[x[k]] = 1;
            k++;
        } else {// 否则取消x[k]顶点的访问标识，回溯
            visited[x[k]] = 0;
            x[k] = 0;
            k--;
            visited[x[k]] = 0;// 此处是为了将回溯后的顶点，即x[k-1]恢复为未访问状态
        }
    }
}

N皇后问题

public static void Queen(int n) {
    int k = 0;
    int[] x = new int[n];// x[i]表示第i个皇后放在第i行的第x[i]列
    for (int i = 0; i < n; i++)// 初始化为-1
        x[i] = -1;
    while (k >= 0) {// 摆放皇后k
        x[k]++;// 在下一列摆放皇后k
        while (x[k] < n && Place(x, k)) {// 发生冲突
            x[k]++;
        }
        if (x[k] < n && k == n - 1) {// 求解完成，输出
            for (int i = 0; i < n; i++) {
                System.out.println(x[i] + 1);
            }
            return;
        } else if (x[k] < n && k < n - 1) {// 求解未完成，摆放下一个皇后
            k++;
        } else {// 重置x[k]，回溯
            x[k--] = -1;
        }
    }
    System.out.println("无解");
}

public static boolean Place(int[] x, int k) {// 判断放置是否冲突
    for (int i = 0; i < k; i++) {
        if (x[i] == x[k] || Math.abs(i - k) == Math.abs(x[i] - x[k])) {// 若在同一列或同一斜线
            return true;// 返回冲突
        }
    }
    return false;
}

批处理作业调度问题

public static int BatchJob(int[] a, int[] b) {// a记录n个作业在机器1上所需时间，b记录n个作业在机器2上所需时间
    int i, k;
    int n = a.length;
    int[] x = new int[n + 1];// 存储具体的作业调度，x[k]表示第k个作业的编号
    int[] sum1 = new int[n + 1];// 存储机器1的完成时间
    int[] sum2 = new int[n + 1];// 存储机器2的完成时间
    int bestTime = 10000;// 假设时间不超过10000

    for (i = 1; i <= n; i++) {
        x[i] = -1;
        sum1[i] = 0;
        sum2[i] = 0;
    }
    sum1[0] = 0;
    sum2[0] = 0;
    k = 1;
    while (k >= 1) {
        x[k]++;// 安排第k个作业，作业编号为x[k]
        while (x[k] < n) {
            for (i = 1; i < k; i++) {// 检测作业x[k]是否重复处理
                if (x[i] == x[k]) {
                    break;
                }
            }
            if (i == k) {// 作业x[k]还未处理
                sum1[k] = sum1[k - 1] + a[x[k]];
                sum2[k] = Math.max(sum1[k], sum2[k - 1]) + b[x[k]];
                if (sum2[k] <= bestTime)// 未超过目前最短时间则跳出内层循环
                    break;
                else// 否则剪枝
                    x[k]++;
            } else // 作业x[k]已经处理，则处理下一个作业
                x[k]++;
        }
        if (x[k] < n && k < n) {
            k++;// 安排下一个作业
        } else {
            if (x[k] < n && k == n) {
                if (bestTime >= sum2[k]) {
                    bestTime = sum2[k];
                    System.out.println("目前最短作业安排是：");
                    for (int j = 1; j <= n; j++)
                        System.out.println(x[j] + 1);
                    System.out.println("最短时间是：" + bestTime);
                }
            }else
                x[k--] = -1;// 重置x[k]，回溯
        }
    }
    return bestTime;
}