单源最短路径问题——分支限界法（Java）

1、 前置芝士

1.1 分支限界法求解目标

分支限界法与回溯法的不同求解目标：

• 回溯法的求解目标：找出解空间树中满足约束条件的所有解；

• 分支限界法的求解目标：找出满足约束条件的一个解，或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

1.2 分支限界法引言

分支限界法与回溯法的不同搜索方式：

• 回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

• 分支限界法的搜索策略：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

1.3 分支限界法基本思想

• 分支限界法通常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

• 问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。

1.4 两种典型的解空间树

子集树（Subset Trees）：

当所给问题是从n个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集树。在子集树中，|S0|=|S1|=…=|Sn-1|=c，即每个结点有相同数目的子树，通常情况下c=2，所以，子集树中共有2ⁿ个叶子结点，因此，遍历子集树需要O(2ⁿ)时间。

排列树（Permutation Trees）：

当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。在排列树中，通常情况下，|S0|=n，|S1|=n-1，…，|Sn-1|=1，所以，排列树中共有n!个叶子结点，因此，遍历排列树需要O(n!)时间。

2、分支限界法解题过程

2.1 算法要点

• 在分支限界法中，每一个活结点只有一次机会成为扩展结点。

• 活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

• 从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程

• 这个过程一直持续到找到所求的解或活结点表为空时为止。

活结点表：具有先进先出的性质，是队列

2.2 两个重要机制

• 产生分支（解空间树）
• 产生一个界限，能够终止许多分支（剪枝）

2.3 适用范围

• 分支限界法类似于回溯法，有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决，但是另外一些则不然。

• 下表列出了回溯法和分支限界法的一些区别：

2.4 两种方式

从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。

最常见的有以下两种方式：

• 队列式（FIFO）分支限界法：队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。

• 优先队列式分支限界法：优先队列式分支限界法将活结点表组织成一个优先队列，按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。

常用堆来实现优先队列

3、单源最短路径问题

3.1 问题描述

给定带权有向图G =(V,E),其中每条边的权是非负实数.另外,还给定V中的一个顶点,称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点内数字表示该结点所对应的当前路长

3.2 图解题目

4、程序代码

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


/**
 * TODO
 *   11 19
 *   SA 2 SB 3 SC 4 AF 7 AB 3 AE 2 BE 9 BD 2 CD 2 FG 9 FH 1 EH 3 ED 1 DI 1 DH 5 GT 7 HT 8 IH 2 IT 2
 */
public class t1 {
    static int N;   // 节点个数
    static int EDGES;   // 边的数量
    static float[][] adj;     // 邻接矩阵

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        System.out.print("input the number of vertix and edge:");
        N = scanner.nextInt();
        EDGES = scanner.nextInt();
        adj = new float[N + 1][N + 1];

        for (int i = 0; i < adj.length; i++) {
            for (int j = 0; j < adj.length; j++) {
                adj[i][j] = Float.MAX_VALUE;
            }
        }

        System.out.println("please input vertix and weight:");
        for (int i = 0; i < EDGES; i++) {
            String vertix = scanner.next();
            int startPos = vertix.charAt(0) - 'A' + 1, targetPos = vertix.charAt(1) - 'A' + 1;
            if (vertix.charAt(0) == 'S') {
                startPos = 0;
            }
            if (vertix.charAt(1) == 'T') {
                targetPos = N - 1;
            }
            float weight = scanner.nextFloat();
            adj[startPos][targetPos] = weight;
        }


        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (adj[i][j] != Float.MAX_VALUE && adj[i][j] != 0 && i != j) {
                    char start = (char) ('A' + i - 1), end = (char) ('A' + j - 1);
                    if (i == 0) {
                        start = 'S';
                    }
                    if (j == N - 1) {
                        end = 'T';
                    }
                    System.out.println("(" +  start + ", " + end  + ") = " + adj[i][j]);
//                    System.out.println("(" +  i + ", " + j  + ") = " + adj[i][j]);
                }
            }
        }

        int[] path = new int[N + 1];        // path[i]:记录最佳路径中，i的上一个顶点是path[i]
        float[] dist = new float[N + 1];    // dist[i]:从源点到当前顶点i的距离
        int vertix = 0;

        for (int j = 1; j <= N; j++) {
            dist[j] = Float.MAX_VALUE;
        }
        shortest(vertix, adj, dist, path);


        System.out.print("最小堆求解的路径为：");
//        for (int i = 1; i < path.length; i++) {
//            System.out.println(path[i]);
//        }
//        System.out.println("------------------------");

        // TODO 10 9 4 2 0
        List<Integer> list = new ArrayList<>();
        list.add(N - 1);
        list.add(path[N - 1]);
        while (true) {
            if (path[list.get(list.size() - 1)] == 0) {
                list.add(0);
                break;
            }
            list.add(path[list.get(list.size() - 1)]);
        }

//        for (int i = 0; i < list.size(); i++) {
//            System.out.println(list.get(i));
//        }
//        System.out.println("-------------------------");
        for (int j = list.size() - 1; j >= 0; j--) {
            if (list.get(j) == 0) {
                System.out.print("S-->");
            } else {
                char c = (char) (list.get(j) + 'A' - 1);
                if (j != 0) {
                    System.out.print(c + "-->");
                } else {
                    System.out.println('T');
                }
            }
        }


        System.out.println("从顶点S到各顶点最短距离：");
        for (int i = 1; i < dist.length - 1; i++) {
            char end = (char) ('A' + i - 1);
            System.out.print("dist[" + end + "] = " + dist[i] + " ");
        }
        System.out.println("dist[" + 'T' + "] = " +dist[10]);
    }

    public static void shortest(int v, float[][] adj, float[] dist, int[] path) {
        int n = path.length - 1;
        HeapNode enode = new HeapNode(v, 0);
        PriorityQueue<HeapNode> pq = new PriorityQueue<>();
        pq.offer(enode);

        while (!pq.isEmpty()) {
            HeapNode pollNode = pq.poll();
            int start = pollNode.vIdx;
            float currStep = pollNode.step;
            // 搜索问题的解空间
            for (int i = 1; i <= n; i++) {
                if (adj[start][i] <= Float.MAX_VALUE && pollNode.step + adj[start][i] < dist[i]) {
                    dist[i] = currStep + adj[start][i];
                    path[i] = start;
                    HeapNode node = new HeapNode(i, dist[i]);
                    pq.offer(node);
//                    System.out.println(start + "-->" + i);
                }
            }
        }
    }

    static class HeapNode implements Comparable {
        int vIdx;  // 顶点编号
        float step;   // 当前路长

        public HeapNode(int vIdx, float step) {
            this.vIdx = vIdx;
            this.step = step;
        }

        @Override
        public int compareTo(Object o) {
            float oLen = ((HeapNode) o).step;
            if (step < oLen) {
                return -1;
            }
            if (step == oLen) {
                return 0;
            }
            return 1;
        }
    }
}

其中，shorest方法的while()代码块可以用以下代码替换

while (true) {
        // 搜索问题的解空间
        for (int i = 1; i <= n; i++) {
            if (adj[enode.vIdx][i] < Float.MAX_VALUE && enode.step + adj[enode.vIdx][i] < dist[i]) {
                dist[i] = enode.step + adj[enode.vIdx][i];
                path[i] = enode.vIdx;
                HeapNode node = new HeapNode(i, dist[i]);
                pq.offer(node);
            }
        }
        if (pq.isEmpty()) {
            break;
        } else {
            // 移除
            enode = (HeapNode) pq.poll();
        }
    }

运行结果

5、参考资料

• 算法设计与分析（第四版）

结束！