回溯法/活动安排 最大兼容活动

• 活动安排问题
• n个活动需要使用1个互斥资源，每个活动都有1个开始时间和1个介绍时间因此会产生冲突，求最大兼容活动数量
• 什么是兼容/不兼容活动：
• 活动编号 1 2 3 4
• 开始时间 1 2 4 6
• 结束时间 3 5 8 9
• 活动最终结束时间为latest=0 兼容活动总量compatibleSum=0
• 0_{1，无活动，1}3，latest=3，活动1；活动2要求从2开始，不兼容，剔除它；3_{4，无活动；4}8，latest=8，活动3；活动4要求从6开始，不兼容，剔除它
• 活动安排问题本身是1个排列问题，求出1个排列之后需要判断排列树代表的活动是否兼容，求兼容活动最多的排列即兼容活动最多的活动安排
• 1. 使用排列树的递归算法先获取活动的排列
• 回溯法：有回就有去-结点扩展规则，深度优先搜索的解空间树的过程中剪枝，剪枝函数有约束函数，限界函数，解空间树有子集树和排列树两种
• 解空间树/子集数：达到要求的子集，元素子集；分支代表选择或不选择
• 解空间树/排列树：达到要求的排列，所有元素都在；把那个元素放到第1位，把那个元素放到第2位，依次类推
• 剪枝函数/约束函数：决定是否访问下一个结点，子树不满足约束条件，
• 剪枝函数/限界函数：决定是否访问下面的子树，子树得不到需要的解，求最大值使用上界函数，求最小值使用下界函数

package xcrj.kchalgorithm.backtracking;

import java.util.Arrays;

/** * 活动安排问题 * n个活动需要使用1个互斥资源，每个活动都有1个开始时间和1个介绍时间因此会产生冲突，求最大兼容活动数量 * <p> * 什么是兼容/不兼容活动： * 活动编号 1 2 3 4 * 开始时间 1 2 4 6 * 结束时间 3 5 8 9 * 活动最终结束时间为latest=0 兼容活动总量compatibleSum=0 * 0~1，无活动，1~3，latest=3，活动1；活动2要求从2开始，不兼容，剔除它；3~4，无活动；4~8，latest=8，活动3；活动4要求从6开始，不兼容，剔除它 * <p> * <p> * 活动安排问题本身是1个排列问题，求出1个排列之后需要判断排列树代表的活动是否兼容，求兼容活动最多的排列即兼容活动最多的活动安排 * 排列树形成过程：选择第i个元素之后形成的父节点，父节点的孩子结点，通过父结点的第i和第j元素交换，轮流把第j个元素放到第i位，形成子结点 * <p> * 回溯法：有回就有去-结点扩展规则，深度优先搜索的解空间树的过程中剪枝，剪枝函数有约束函数，限界函数，解空间树有子集树和排列树两种 * 解空间树/子集数：达到要求的子集，元素子集；分支代表选择或不选择 * 解空间树/排列树：达到要求的排列，所有元素都在；把那个元素放到第1位，把那个元素放到第2位，依次类推 * 剪枝函数/约束函数：决定是否访问下一个结点，子树不满足约束条件， * 剪枝函数/限界函数：决定是否访问下面的子树，子树得不到需要的解，求最大值使用上界函数，求最小值使用下界函数 */
public class ActivityArrange {
    
    static class Activity {
    
        private int start;
        private int end;

        public Activity() {
    
        }

        public Activity(int start, int end) {
    
            this.start = start;
            this.end = end;
        }

        public int getStart() {
    
            return start;
        }

        public void setStart(int start) {
    
            this.start = start;
        }

        public int getEnd() {
    
            return end;
        }

        public void setEnd(int end) {
    
            this.end = end;
        }
    }

    // 不使用下标0，下标是活动的唯一编号
    static Activity[] activities = {
    new Activity(0, 0), new Activity(1, 3), new Activity(2, 5), new Activity(4, 8), new Activity(6, 9)};

    /*求解过程*/
    // 活动数量
    static int n = 3;
    // 活动安排，+1下标0不使用
    static int[] xs = {
    0, 1, 2, 3};
    // 活动最终结束时间
    static int latest;
    // 兼容活动数量
    static int compatibleSum;

    /*结果展示*/
    // 最优活动安排，+1下标0不使用
    static int[] optimalXs = new int[n + 1];
    // 最大兼容活动数量
    static int maxCompatibleSum;

    /** * */
    public static void deepFirstSearch(int i) {
    
        // 到达叶子结点，因为根结点为(0,0)，所以到达叶子结点是i>n
        if (i > n) {
    
            // 结果更好则保留
            if (compatibleSum > maxCompatibleSum) {
    
                maxCompatibleSum = compatibleSum;
                // 下标0不使用
                for (int j = 1; j <= n; j++) {
    
                    optimalXs[j] = xs[j];
                }
            }
        }
        // 到达非叶子结点，生成i结点的所有孩子结点活动xs[j]（j从i开始）
        else {
    
            // 下标0不使用
            for (int j = i; j <= n; j++) {
    
                // 为了便于回溯，保存
                int compatibleSumTemp = compatibleSum;
                int latestTemp = latest;
                // xs[j]为活动的编号，判断活动是否兼容
                if (activities[xs[j]].start >= latest) {
    
                    compatibleSum++;
                    latest = activities[xs[j]].end;
                }
                // ！交换，选择第i个元素之后形成的父节点，父节点的孩子结点，通过父结点的第i和第j元素交换，轮流把第j个元素放到第i位，形成子结点
                int temp = xs[i];
                xs[i] = xs[j];
                xs[j] = temp;
                // 第i+1层选择活动xs[j]（从i+1开始）作为结点，深度优先遍历操作孩子结点
                deepFirstSearch(i + 1);
                // 交换
                int temp2 = xs[i];
                xs[i] = xs[j];
                xs[j] = temp2;
                // 回溯，取消第i层对活动的选取
                compatibleSum = compatibleSumTemp;
                latest = latestTemp;
            }
        }
    }

    public static void main(String[] args) {
    
        // 1，从活动1开始
        deepFirstSearch(1);

        System.out.println("最大兼容活动数量:" + maxCompatibleSum);
    }
}