活动相容问题——树搜索、动态规划、贪心实现

文章目录

• 活动相容问题——树搜索、动态规划、贪心
• • 动态规划
  • 贪心算法
  • 树搜索
  • 代码实现
  • • 数据结构的定义
    • 动态规划
    • 贪心算法
    • 树搜索
    • 测试类

活动相容问题——树搜索、动态规划、贪心

输入：$$S=1,2,\dots ,n，F=\{[s_i，f_i]\},1\le i\le n$$

输出：S 中的最大相容活动集合。

下面先给出三种算法的思路和描述，最后给出三种算法的实现

动态规划

首先需要按开始时间对这些活动进行排序。

dp[i] 表示以第 i 个活动结尾的最大相容活动的个数。

递归方程如下

$$dp[i]=\{\begin{array}{ll}1& 活动i之前没有与之相容的活动\\ \underset{0\le k<i}{\max }\{dp[k]+1\}& i\ge 1,活动k与活动i相容\end{array}$$

初始化 dp[i] = 1 。

优化子结构

以第 i 个活动结尾的最大相容活动集合 A 中，第 k 个活动为第 0 个和第 i 个活动之间且与活动 i 相容的活动。如果 i 和 k 不相等，以第 i 个活动结尾的最大相容活动数 (即dp[i]) 就等于以第 k 个活动结尾的最大相容活动数 + 1 中的最大值 (即 max{dp[k] + 1)}。假设以 i 结尾的最大相容活动集为 A，显然这样的活动 k 就是倒数第二个元素。集合 A - { 活动 i } 中，这些元素就是以活动 k 结尾的最大相容活动集了，如若不然，我们就可以找到一个更大的以 k 结尾的相容活动 B 集代替它 ，这样一来 |B + {活动 i }| 反而比 |A| 还大了，这与 A 是以 i 结尾的最大相容活动集这个假设矛盾，因此整体的优化解的一部分包含了也是子问题的优化解。

子问题重叠性

没有重叠。计算以第i个元素结尾的最大相容活动数，需要往前看找到其合适的前驱，并更新最大值，但是前面的都已经求出来了，直接把数组里的值拿出来用即可，因此并没有重复解决某个子问题。

贪心算法

每次从剩余子问题中找最晚结束的，请看后面代码实现部分。

树搜索

如果转换为树搜索，需要转化为代价问题，很容易发现，每次选完一个活动之后剩余的节点当中都有不能选的，因此以此作为代价，选完一个后，从剩余节点后中的和这个节点相容的活动作为子节点，最终累计下来，到了叶子的时候，代价就是整个过程一共淘汰的活动个数，因此淘汰掉的个数越少，剩下的就越多，得到的集合就越大。于是我们可以用爬山法取深度搜索找出一个上界，后面找的时候，如果比这个上界还要大就直接剪掉，否则继续扩展。找到叶子的时候，就判定代价是否小于这个界，如果小于这界，就以此作为新的界。直到没有可扩展的节点为止，然后根据叶子反向追溯路径即可得到选了哪些活动。

大概的思路是这样，具体的实现有些区别，为了方便实现，有些地方使用了点小技巧，但是整体的思路就是爬山加分支界限。详细请见后面的代码实现部分。

代码实现

数据结构的定义

Activity.java

public class Activity {
    double start;
    double finish;

    public Activity(double start, double finish) {
        this.start  = start;
        this.finish = finish;
    }

    boolean isCompatible(Activity o) {
        return !this.equals(o) && (this.start >= o.finish || o.start >= this.finish);
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Activity)) {
            return false;
        }

        Activity o = (Activity) obj;
        return this.start == o.start && this.finish == o.finish;
    }
}

TSNode.java

import java.util.ArrayList;
import java.util.List;

// 解空间树的节点
public class TSNode implements Comparable<TSNode> {
    final Activity activity;
    TSNode         parent  = null;
    int            price   = 0xfff;
    List<TSNode>   childs  = new ArrayList<>();
    boolean        flag    = false;
    int            counter = 0;           // 计数器，用于记录当前正在访问哪个儿子

    public TSNode(Activity activity, TSNode parent, int price) {
        this.activity = activity;
        this.parent   = parent;
        this.price    = price;
    }

    boolean isCompatible(TSNode o) {
        return this.activity.isCompatible(o.activity);
    }

    @Override
    public boolean equals(Object obj) {
        return (obj instanceof TSNode) ? this.activity.equals(((TSNode) obj).activity) : false;
    }

    @Override
    public int compareTo(TSNode o) {
        return this.price == o.price ? 0 : (this.price > o.price ? 1 : -1);
    }
}

动态规划

DynamicProgramming.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class DynamicProgramming {
    List<Activity> getMaxCompatibles(List<Activity> activities) {
        int[]      dp          = new int[activities.size()];
        int[]      pre         = new int[activities.size()];
        int        n           = activities.size();

        Activity[] activityArr = activities.toArray(new Activity[0]);

        // 按开始时间排序
        Arrays.sort(activityArr, (o1, o2) -> o1.start < o2.start ? -1 : (o1.start == o2.start ? 0 : 1));

        for (int i = 0; i < activities.size(); ++i) {
            dp[i]  = 1;
            pre[i] = i;
        }

        for (int i = 1; i < n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (activityArr[i].isCompatible(activityArr[j])) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i]  = dp[j] + 1;
                        pre[i] = j;
                    }
                }
            }
        }

        int maxPos = 0;

        for (int i = 0; i < n; ++i) {
            if (dp[i] > dp[maxPos]) {
                maxPos = i;
            }
        }

        List<Activity> maxCompitableActivities = new ArrayList<>();

        for (int i = dp[maxPos] - 1, j = maxPos; i >= 0; --i) {
            maxCompitableActivities.add(activityArr[j]);
            j = pre[j];
        }
        
        Collections.reverse(maxCompitableActivities);

        return maxCompitableActivities;
    }
}

贪心算法

Greedy.java

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Greedy {
    List<Activity> getMaxCompatibles(List<Activity> activities) {
        List<Activity>  maxCompitableActivities = new ArrayList<>();
        Queue<Activity> minHeap                 = new PriorityQueue<>(
                (o1, o2) -> o1.finish < o2.finish ? -1 : (o1.finish == o2.finish ? 0 : 1));
        minHeap.addAll(activities);

        maxCompitableActivities.add(minHeap.remove());

        while (!minHeap.isEmpty()) {
            Activity heapTop = minHeap.remove();
            Activity tmp     = maxCompitableActivities.get(maxCompitableActivities.size() - 1);

            if (heapTop.isCompatible(tmp)) {
                maxCompitableActivities.add(heapTop);
            }
        }

        return maxCompitableActivities;
    }
}

树搜索

TreeSearch.java

public class TreeSearch {
    List<Activity> getMaxCompatibles(List<Activity> activities) {
        Activity      sentry   = new Activity(-0xfff, -0xfff);
        TSNode        root     = new TSNode(sentry, null, 0);
        Stack<TSNode> stack    = new Stack<>();
        int           upLimit  = 0xfff;
        TSNode        bestTail = null;

        stack.push(root);
        while (!stack.empty()) {
            TSNode stackTop = stack.peek();

            // 判断该节点是否已经被访问过了
            if (stackTop.flag) {
                if (stackTop.counter >= stackTop.childs.size()) {
                    stack.pop();
                } else {
                    stack.push(stackTop.childs.get(stackTop.counter++));
                }

                continue;
            }

            // 标记为已访问
            stackTop.flag = true;

            // 如果比上界大就没必要扩展了
            if (stackTop.price >= upLimit) {
                stack.pop();
                continue;
            }

            // 求出其子节点以及子节点的代价
            makeChilds(stackTop, activities);

            // 判断是否到了叶子节点
            if (stackTop.childs.isEmpty()) {
                // 判定是否需要更新上界
                if (stackTop.price < upLimit) {
                    // 更新上界
                    upLimit  = stackTop.price;
                    bestTail = stackTop;
                }

                stack.pop();

                continue;
            }

            ++stackTop.counter;
            stack.push(stackTop.childs.get(0));
        }

        Stack<TSNode>  bestStack               = new Stack<>();
        List<Activity> maxCompitableActivities = new ArrayList<>();

        while (bestTail.parent != null) {
            bestStack.push(bestTail);
            bestTail = bestTail.parent;
        }

        while (!bestStack.empty()) {
            maxCompitableActivities.add(bestStack.pop().activity);
        }

        return maxCompitableActivities;
    }

    void makeChilds(TSNode tsNode, List<Activity> activities) {
        if (tsNode.parent == null) {
            for (Activity a : activities) {
                int price = 0;
                for (Activity b : activities) {
                    if (b.equals(a)) {
                        continue;
                    }

                    if (!a.isCompatible(b)) {
                        ++price;
                    }
                }
                tsNode.childs.add(new TSNode(a, tsNode, price));
            }
            return;
        }

        for (TSNode a : tsNode.parent.childs) {
            // 子节点不能是自己，也不能是和自己不相容的
            if (!a.isCompatible(tsNode)) {
                continue;
            }

            // 计算这个子节点的代价
            int price = 0;
            for (TSNode b : tsNode.parent.childs) {
                // 求这个子节点的代价时参考的集合是除了自己之外和它父亲相容的活动集合
                if (b.equals(a) || !b.isCompatible(tsNode)) {
                    continue;
                }

                if (!a.isCompatible(b)) {
                    ++price;
                }
            }

            tsNode.childs.add(new TSNode(a.activity, tsNode, tsNode.price + price));
        }

        if (!tsNode.childs.isEmpty()) {
            Collections.sort(tsNode.childs);
        }
    }
}

测试类

Main.java

package exp4;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner        scanner    = new Scanner(System.in);
        List<Activity> activities = new ArrayList<>();
        double         start, finish;

        while (scanner.hasNext()) {
            start  = scanner.nextDouble();
            finish = scanner.nextDouble();
            activities.add(new Activity(start, finish));
        }
        
        DynamicProgramming dp = new DynamicProgramming();
        Greedy gd = new Greedy();
        TreeSearch ts = new TreeSearch();
        
        List<Activity> maxCompitableActivities;
        
        System.out.println("\n======== DP ========");
        maxCompitableActivities = dp.getMaxCompatibles(activities);
        for (Activity a : maxCompitableActivities) {
            System.out.printf("[%f, %f]\n", a.start, a.finish);
        }
        
        System.out.println("\n======== Greedy ========");
        maxCompitableActivities = gd.getMaxCompatibles(activities);
        for (Activity a : maxCompitableActivities) {
            System.out.printf("[%f, %f]\n", a.start, a.finish);
        }
        
        
        System.out.println("\n======== Tree Search ========");
        maxCompitableActivities = ts.getMaxCompatibles(activities);
        for (Activity a : maxCompitableActivities) {
            System.out.printf("[%f, %f]\n", a.start, a.finish);
        }

        scanner.close();
    }
}

本文地址：https://blog.csdn.net/Zero__White/article/details/109632035