算法分析入门系列(三) 动态规划算法

作业排程问题

问题描述

Automobile factory with two assembly lines(汽车厂两条装配线)

– Each line has n stations: S1,1, . . . , S1,n and S2,1, . . . , S2,n(每条装

配线有n个工序站台)

– Corresponding stations S1, j and S2, j perform the same function

but can take different amounts of time a1, j and a2, j (每条装配线的

第j个站台的功能相同,但是效率不一致)

– Entry times e1 and e2 and exit times x1 and x2(上线和下线时间)

描述并实现动态规划的作业排程算法，并显示下图的排程结果。

源代码

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

/**
 * OperationSequencing
 * 作业排程算法实现
 */
/**
 * int arrayA[2][5] = { 7,9,3,4,8,8,5,6,4,5 }; int arrayT[2][4] = {
 * 2,3,1,3,2,1,2,2 };
 */
public class OperationSequencing {

    public static List<Route> routes = new ArrayList<>();

    public void addToRoutes(Node node, Integer costTime) {
        boolean flag = false;
        
        for (Route route : routes) {
            if (route.getWorkIndex() == node.getWorkIndex() && costTime < route.getCostTime()) {
                route.setLineIndex(node.getLineIndex());
                route.setCostTime(costTime);
                flag = true;
            } else if (route.getWorkIndex() == node.getWorkIndex()) {
                flag = true;
            }
        }
        if (!flag) {
            routes.add(new Route(node.getLineIndex(), node.getWorkIndex(), costTime));
        }
    }

    public void printRoutes() {
        Collections.sort(routes, new Comparator<Route>() {
            @Override
            public int compare(Route r1, Route r2) {
                return r1.getWorkIndex() - r2.getWorkIndex();
            }
        });
        System.out.print("enter-->");
        for (Route route : routes) {
            System.out.print("(" + route.getLineIndex() + "," + route.getWorkIndex() + ")-->");
        }
        System.out.print("exit");
    }

    public Integer getShortestTime(WorkingGraph workingGraph, Node endNode) {
        WorkingGraph _workingGraph = new WorkingGraph(workingGraph);
        if (endNode.getParents().size() == 1) {
            return Edge.getEdgeWeight(_workingGraph.getEnterNode(), endNode, _workingGraph.getEdges())
                    + endNode.getWorkTime();
        }
        Integer leftParentTime = Edge.getEdgeWeight(endNode.getParents().get(0), endNode, _workingGraph.getEdges());
        Integer rightParentTime = Edge.getEdgeWeight(endNode.getParents().get(1), endNode, _workingGraph.getEdges());
        // 去掉与末尾节点相关的边
        Edge.removeEdgeWithNode(endNode, _workingGraph.getEdges());
        _workingGraph.getNodes().remove(endNode);

        Integer leftTime = getShortestTime(_workingGraph, endNode.getParents().get(0)) + leftParentTime;
        Integer rightTime = getShortestTime(_workingGraph, endNode.getParents().get(1)) + rightParentTime;
        addToRoutes(endNode.getParents().get(leftTime > rightTime ? 1 : 0),
                leftTime > rightTime ? rightTime : leftTime);
        return Math.min(leftTime, rightTime) + endNode.getWorkTime();
    }

    public static void main(String[] args) {
        WorkingGraph workingGraph = new WorkingGraph();
        // -1-1代表起始节点，-2-2代表离开节点
        Node enter = new Node(-1, -1, 0);
        Node exit = new Node(-2, -2, 0);

        Node a11 = new Node(1, 1, 7);
        Node a12 = new Node(1, 2, 9);
        Node a13 = new Node(1, 3, 3);
        Node a14 = new Node(1, 4, 4);
        Node a15 = new Node(1, 5, 8);

        Node a21 = new Node(2, 1, 8);
        Node a22 = new Node(2, 2, 5);
        Node a23 = new Node(2, 3, 6);
        Node a24 = new Node(2, 4, 4);
        Node a25 = new Node(2, 5, 5);

        enter.addToChildren(a11);
        enter.addToChildren(a21);

        a11.addToParents(enter);
        a11.addToChildren(a12);
        a11.addToChildren(a22);

        a21.addToParents(enter);
        a21.addToChildren(a12);
        a21.addToChildren(a22);

        a12.addToParents(a11);
        a12.addToParents(a21);
        a12.addToChildren(a13);
        a12.addToChildren(a23);

        a22.addToParents(a11);
        a22.addToParents(a21);
        a22.addToChildren(a13);
        a22.addToChildren(a23);

        a13.addToParents(a12);
        a13.addToParents(a22);
        a13.addToChildren(a14);
        a13.addToChildren(a24);

        a23.addToParents(a12);
        a23.addToParents(a22);
        a23.addToChildren(a14);
        a23.addToChildren(a24);

        a14.addToParents(a13);
        a14.addToParents(a23);
        a14.addToChildren(a15);
        a14.addToChildren(a25);

        a24.addToParents(a13);
        a24.addToParents(a23);
        a24.addToChildren(a15);
        a24.addToChildren(a25);

        a15.addToParents(a14);
        a15.addToParents(a24);
        a15.addToChildren(exit);

        a25.addToParents(a14);
        a25.addToParents(a24);
        a25.addToChildren(exit);

        exit.addToParents(a15);
        exit.addToParents(a25);

        List<Node> nodes = new ArrayList<>();

        nodes.add(enter);

        nodes.add(a11);
        nodes.add(a12);
        nodes.add(a13);
        nodes.add(a14);
        nodes.add(a15);

        nodes.add(a21);
        nodes.add(a22);
        nodes.add(a23);
        nodes.add(a24);
        nodes.add(a25);

        nodes.add(exit);
        List<Edge> edges = new ArrayList<>();

        edges.add(new Edge(enter, a11, 2));
        edges.add(new Edge(a11, a12, 0));
        edges.add(new Edge(a12, a13, 0));
        edges.add(new Edge(a13, a14, 0));
        edges.add(new Edge(a14, a15, 0));
        edges.add(new Edge(a15, exit, 3));

        edges.add(new Edge(enter, a21, 4));
        edges.add(new Edge(a21, a22, 0));
        edges.add(new Edge(a22, a23, 0));
        edges.add(new Edge(a23, a24, 0));
        edges.add(new Edge(a24, a25, 0));
        edges.add(new Edge(a25, exit, 6));

        edges.add(new Edge(a11, a22, 2));
        edges.add(new Edge(a21, a12, 2));
        edges.add(new Edge(a12, a23, 3));
        edges.add(new Edge(a22, a13, 1));
        edges.add(new Edge(a13, a24, 1));
        edges.add(new Edge(a23, a14, 2));
        edges.add(new Edge(a14, a25, 3));
        edges.add(new Edge(a24, a15, 2));

        workingGraph.setNodes(nodes);
        workingGraph.setEdges(edges);
        workingGraph.setEnterNode(enter);
        workingGraph.setExitNode(exit);

        OperationSequencing operationSequencing = new OperationSequencing();
        System.out.println(operationSequencing.getShortestTime(workingGraph, exit));
        operationSequencing.printRoutes();
    }

}

/**
 * 图上的节点类
 */
class Node {
    // 父节点
    private List<Node> parents;
    // 子节点
    private List<Node> children;
    // 流水线编号
    private Integer lineIndex;
    // 工作顺序编号
    private Integer workIndex;
    // 加工时间
    private Integer workTime;

    public Node() {

    }

    public Node(Integer lineIndex, Integer workIndex, Integer workTime) {
        this.children = new ArrayList<>();
        this.parents = new ArrayList<>();

        this.lineIndex = lineIndex;
        this.workIndex = workIndex;
        this.workTime = workTime;
    }

    public List<Node> getParents() {
        return parents;
    }

    public void setParents(List<Node> parents) {
        this.parents = parents;
    }

    public void addToParents(Node parent) {
        this.parents.add(parent);
    }

    public List<Node> getChildren() {
        return children;
    }

    public void setChildren(List<Node> children) {
        this.children = children;
    }

    public void addToChildren(Node child) {
        this.children.add(child);
    }

    public Integer getLineIndex() {
        return lineIndex;
    }

    public void setLineIndex(Integer lineIndex) {
        this.lineIndex = lineIndex;
    }

    public Integer getWorkIndex() {
        return workIndex;
    }

    public void setWorkIndex(Integer workIndex) {
        this.workIndex = workIndex;
    }

    public Integer getWorkTime() {
        return workTime;
    }

    public void setWorkTime(Integer workTime) {
        this.workTime = workTime;
    }

}

/**
 * 边类
 */
class Edge {
    // 起始节点
    private Node startNode;
    // 结束节点
    private Node endNode;
    // 边的权重
    private Integer weight;

    public Edge() {

    }

    public Edge(Node startNode, Node endNode, Integer weight) {
        this.startNode = startNode;
        this.endNode = endNode;
        this.weight = weight;
    }

    /**
     * 获取两个顶点之间的直线距离
     * 
     * @param n1    起始节点
     * @param n2    结束节点
     * @param edges
     * @return
     */
    public static Integer getEdgeWeight(Node n1, Node n2, List<Edge> edges) {
        for (Edge edge : edges) {
            if (edge.getStartNode().equals(n1) && edge.getEndNode().equals(n2))
                return edge.weight;
        }
        return 0;
    }

    /**
     * 移除与指定节点相关的边
     * 
     * @param Node
     * @param edges
     */
    public static void removeEdgeWithNode(Node Node, List<Edge> edges) {
        List<Edge> _removeEdges = new ArrayList<>();
        for (Edge edge : edges) {
            if (edge.getStartNode().equals(Node) || edge.getEndNode().equals(Node)) {
                _removeEdges.add(edge);
            }
        }
        for (Edge edge : _removeEdges) {
            edges.remove(edge);
        }
    }

    public Node getStartNode() {
        return startNode;
    }

    public void setStartNode(Node startNode) {
        this.startNode = startNode;
    }

    public Node getEndNode() {
        return endNode;
    }

    public void setEndNode(Node endNode) {
        this.endNode = endNode;
    }

    public Integer getWeight() {
        return weight;
    }

    public void setWeight(Integer weight) {
        this.weight = weight;
    }

}

class Route {
    private Integer lineIndex;
    private Integer workIndex;
    private Integer costTime;

    public Integer getLineIndex() {
        return lineIndex;
    }

    public void setLineIndex(Integer lineIndex) {
        this.lineIndex = lineIndex;
    }

    public Integer getWorkIndex() {
        return workIndex;
    }

    public void setWorkIndex(Integer workIndex) {
        this.workIndex = workIndex;
    }

    public Integer getCostTime() {
        return costTime;
    }

    public void setCostTime(Integer costTime) {
        this.costTime = costTime;
    }

    public Route(Integer lineIndex, Integer workIndex, Integer costTime) {
        this.lineIndex = lineIndex;
        this.workIndex = workIndex;
        this.costTime = costTime;
    }

}

/**
 * 工作图类
 */
class WorkingGraph implements Cloneable {

    private List<Node> nodes;

    private List<Edge> edges;

    private Node enterNode;

    private Node exitNode;

    public WorkingGraph() {

    }

    public WorkingGraph(WorkingGraph workingGraph) {
        this.nodes = new ArrayList<>(workingGraph.getNodes());
        this.edges = new ArrayList<>(workingGraph.getEdges());
        this.enterNode = workingGraph.getEnterNode();
        this.exitNode = workingGraph.getExitNode();
    }

    @Override
    public WorkingGraph clone() {
        WorkingGraph o = null;
        try {
            o = (WorkingGraph) super.clone();
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return o;
    }

    public List<Node> getNodes() {
        return nodes;
    }

    public void setNodes(List<Node> nodes) {
        this.nodes = nodes;
    }

    public List<Edge> getEdges() {
        return edges;
    }

    public void setEdges(List<Edge> edges) {
        this.edges = edges;
    }

    public Node getEnterNode() {
        return enterNode;
    }

    public void setEnterNode(Node enterNode) {
        this.enterNode = enterNode;
    }

    public Node getExitNode() {
        return exitNode;
    }

    public void setExitNode(Node exitNode) {
        this.exitNode = exitNode;
    }
}

实验分析

使用动态规划的思想，从上至下，从出口到入口。我这里还用了贪婪的策略，只需要保证每一次都是最短的工作耗时即可。

最长子序列问题

问题描述

描述并实现最长共同子序列动态规 划 算 法 ， 并 显 示 S1= ACCGGTCGAGATGCAG，S2 = GTCGTTCGGAATGCAT *的最长共同子序列。 *

共同子序列可以是不连续的，且每个元素在母串中的位置也是可以不相同，但是顺序必须一致

源代码

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

/**
 * MaxSubsequence
 */
/**
 * 描述并实现最长共同子序列动态规 划 算 法 ， 并 显 示 S1= ACCGGTCGAGATGCAG，S2 = GTCGTTCGGAATGCAT
 * 的最长共同子序列。 共同子序列可以是不连续的，且每个元素在母串中的位置也是可以不相同，但是顺序必须一致
 */
public class MaxSubsequence {

    /**
     * 求解最长子序列
     * 
     * @param str1 字符串1
     * @param str2 字符串2
     * @return
     */
    public static String lcs(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        StringBuffer sb = new StringBuffer();
        int c[][] = new int[len1 + 1][len2 + 1];
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                if (i == 0 || j == 0) {
                    c[i][j] = 0;
                } else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                } else {
                    c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
                }
            }
        }
        for (int m = 0; m < Math.max(len1, len2); m++) {
            for (int n = 0; n < Math.max(len1, len2); n++) {
                System.out.print(c[m][n] + "\t");
            }
            System.out.println();
        }
        int m = len1;
        int n = len2;
        while (c[m][n] > 0) {
            if (str1.charAt(m - 1) == str2.charAt(n - 1)) {
                sb.append(str1.charAt(m - 1));
                m--;
                n--;
            } else if (c[m][n] == c[m][n - 1]) {
                n--;
            } else if (c[m][n] == c[m - 1][n]) {
                m--;
            }
        }
        return sb.reverse().toString();
    }

    /**
     * 生成最长子序列的字符串
     * 
     * @param arr  比较矩阵
     * @param str1 字符串1
     * @param str2 字符串2
     */
    public void generateLcs(int[][] arr, String str1, String str2) {
        int m = arr.length - 1;
        int n = arr[0].length - 1;
        StringBuffer sb = new StringBuffer();
        while (arr[m][n] > 0) {
            if (str1.charAt(m) == str2.charAt(n)) {
                sb.append(str1.charAt(m));
                m--;
                n--;
            } else if (arr[m][n] == arr[m][n - 1]) {
                n--;
            } else if (arr[m][n] == arr[m - 1][n]) {
                m--;
            }
        }
        System.out.println(sb.reverse().toString());
    }

    public static void main(String[] args) {
        MaxSubsequence maxSubsequence = new MaxSubsequence();
        String ms = maxSubsequence.lcs("ACCGGTCGAGATGCAG", "GTCGTTCGGAATGCAT");
        System.out.println(ms);
    }
}

实验结果

生成的子序列矩阵

查找到的最长子序列

实验分析

实现最长子序列的关键在于创建最长子序列矩阵，这里是使用二维数组来实现的，每一个点都与其上方，左边，左上方这三个点相关，是在判断对应字符相等于否的基础上，根据这几个点来确定当前点的值。当到达最右下角的点时，也就是点dist[dist.length-1][dist.lenght-1]时，也就得到了最长共同子序列的长度，然后再使用逆向思维获取最终的序列。

并且最长子序列并不是唯一的，可能有多个值，这取决于你选择的打印方式。

思考题

1. 动态规划算法范式是什么？

动态规划与分治法相似，但是动态规划所划分的子问题并不是完全相互独立的，是有可能相互关联的，如果使用分治法来实现就有可能重复处理子问题，造成资源浪费。

动态规划需要将问题分为子问题，前一个子问题为后一个子问题提供信息，并且每一次求解时需要存储之前的结果，以期得到最佳答案。

2. 利用动态规划算法设计方法解决矩阵链相乘问题？

矩阵链相乘问题在于寻找最好的括号加法，对于$A_{i~j}(使用该符号来代表矩阵A_iA_{i+1}..*A_j的最佳值)$可以选取一个数k,其中$i≤k≤j$成立,并且k是i到j中的最佳分割点，即括号的所在处，那么我们的乘法矩阵m[][]就可以表示为：

if(i==j){
	m[i][i] = 0;
}else{
	m[i][j]=min{m[i][k] + m[k+1][j] + Pi-1PkPj}
}

然后使用自底向上的思想就可以计算出最佳括号加法获得问题的解