算法设计与分析: 6-18 一般解空间的优先队列式分支限界法_采用优先队列式分支限界法计算该 tsp 问题的最优解，画出解空间树的构造过程。

6-18 一般解空间的优先队列式分支限界法

---

问题描述

试设计一个用优先队列式分支限界法搜索一般解空间的函数。该函数的参数包括结点可 行性判定函数和上界函数等必要的函数，并将此函数用于解布线问题。
印刷电路板将布线区域划分成 n×m 个方格阵列如图(a)所示。精确的电路布线问题要求 确定连接方格 a 的中点到方格 b 的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，如图(b)所示。为了避免线路相交，已布了线的方格做了封锁标记，其它线路不允许穿过被封锁的方格。

对于给定的布线区域，编程计算最短布线方案。

数据输入：
第一行有 3 个正整数 n，m，k，分别表示布线区域方格阵列的行数，列数和封闭的方格数。接下来的 k 行中，每行 2 个正整数，表示被封闭的方格所在的行号和列号。最后的 2 行，每行也有 2 个正整数，分别表示开始布线的方格(p，q)和 结束布线的方格(r，s)。

---

Java

package Chapter6FenZhiXianJieFa;

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class YiBanJieKongJianYouXianDuiLie {

    private static class HeapNode implements Comparable{
        int row,col,len;

        public int compareTo(Object o){
            HeapNode heapNode = (HeapNode) o;
            int result = Integer.compare(len, heapNode.len);

            return result;
        }
    }

    private static class Maze{
        int n,m;
        boolean found;
        int[][] grid;
        int pathLen;
        HeapNode start,finish;
        HeapNode[] offset = new HeapNode[4];
        HeapNode[] path;

        private void newHeap(){
            H = new PriorityQueue<>(100000);
        }

        private void init(){
            //设置方格阵列围墙
            for(int i=0; i<=m+1; i++)
                grid[0][i]=grid[n+1][i]=1;//顶部和底部
            for(int i=0; i<=n+1; i++)
                grid[i][0]=grid[i][m+1]=1;//左翼和右翼

            //初始化相对位移
            for(int i=0; i<4; i++)
                offset[i] = new HeapNode();
            offset[0].row=0; offset[0].col=1;//右
            offset[1].row=1; offset[1].col=0;//下
            offset[2].row=0; offset[2].col=-1;//左
            offset[3].row=-1; offset[3].col=0;//上

            E = new HeapNode();
            E.row = start.row;
            E.col = start.col;
            E.len = 0;
            grid[start.row][start.col] = 2;
        }

        //叶结点判定
        private boolean answer(HeapNode E){
            return false;
        }

        //保存最优解
        private void save(HeapNode E){
        }

        private int f(int n, HeapNode E){
            return 1;
        }

        private int g(int n, HeapNode E){
            return 4;
        }

        //产生新结点
        private void newNode(HeapNode E, int i){
            N = new HeapNode();
            N.row = E.row+offset[i-1].row;
            N.col = E.col+offset[i-1].col;
        }

        //可行性约束
        private boolean constrain(HeapNode E){
            return grid[E.row][E.col]==0;
        }

        //边界约束
        private boolean bound(HeapNode E){
            if(!found) found=(E.row==finish.row && E.col==finish.col);

            return true;
        }

        private void addLiveNode(HeapNode N, HeapNode E, int i){
            grid[N.row][N.col] = grid[E.row][E.col]+1;
            N.len = grid[N.row][N.col];
            if(!found) H.add(N);
        }

        private boolean getNext(){
//            if(found || H.isEmpty()) return false;
            if(found) return false;
            E = H.poll();

            return true;
        }

        private void output(){
            if(!found) {System.out.println("No path!"); return;}
            //构造最优解
            pathLen = grid[finish.row][finish.col]-2;
            path = new HeapNode[pathLen];
            for(int i=0; i<pathLen; i++)
                path[i] = new HeapNode();
            //从目标位置finish开始向起始位置回溯
            HeapNode N = new HeapNode();
            HeapNode E = finish;
            for(int j=pathLen-1; j>=0; j--){
                path[j].row = E.row;
                path[j].col = E.col;
                //找前驱位置
                for(int i=0; i<4; i++){
                    N.row = E.row+offset[i].row;
                    N.col = E.col+offset[i].col;
                    if(grid[N.row][N.col] == j+2) break;
                }
                E.row = N.row;//向前移动
                E.col = N.col;//向前移动
            }
            System.out.println(pathLen);
            System.out.println(start.row+" "+start.col);
            for(int j=0; j<pathLen; j++)
                System.out.println(path[j].row+" "+path[j].col);
        }

        private void pqbb(){
            newHeap();
            E = new HeapNode();
            init();
            //搜索一般解空间树
            while (true){
                if(answer(E)) save(E);
                else
                    for(int i=f(n,E); i<=g(n,E); i++){
                        newNode(E,i);
                        if(constrain(N) && bound(N)) addLiveNode(N,E,i);
                    }
                //取下一扩展结点
                if(!getNext()) break;
            }
            output();
        }
    }

    private static HeapNode E,N;
    private static Queue<HeapNode> H;

    public static void main(String[] args){
        int n,m,k,a,b;
        Scanner input = new Scanner(System.in);

        while (true){
            n = input.nextInt();
            m = input.nextInt();
            k = input.nextInt();

            Maze X = new Maze();
            X.n=n; X.m=m; X.found=false;
            X.grid = new int[n+2][m+2];
            for(a=0; a<n+2; a++)
                for(b=0; b<m+2; b++)
                    X.grid[a][b] = 0;

            for(int i=k; i>=1; i--){
                a = input.nextInt();
                b = input.nextInt();
                X.grid[a][b] = 1;
            }

            X.start = new HeapNode();
            X.finish = new HeapNode();
            X.start.row = input.nextInt();
            X.start.col = input.nextInt();
            X.finish.row = input.nextInt();
            X.finish.col = input.nextInt();

            X.pqbb();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188

---

Input & Output

8 8 3
3 3
4 5
6 6
2 1
7 7
11
2 1
3 1
4 1
5 1
6 1
7 1
7 2
7 3
7 4
7 5
7 6
7 7


17 17 77
1 1
1 2
1 3
1 5
1 8
1 15
1 17
2 1
2 6
2 7
3 1
4 4
4 13
4 14
4 15
5 2
5 3
5 7
5 9
5 16
6 5
6 8
6 11
7 4
7 14
7 17
8 7
8 12
8 17
9 6
9 9
9 11
9 12
9 13
9 16
10 7
10 9
10 13
10 15
11 3
11 5
11 7
11 13
11 15
12 4
12 5
12 6
12 12
12 14
12 15
12 17
13 7
13 10
13 11
14 2
14 3
14 8
15 3
15 8
15 10
15 11
15 12
15 13
15 14
15 15
15 17
16 4
16 6
16 12
16 17
17 1
17 8
17 11
17 12
17 13
17 16
17 17
5 14
15 9
15
5 14
6 14
6 13
7 13
7 12
7 11
8 11
8 10
9 10
10 10
11 10
12 10
12 9
13 9
14 9
15 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

---

Reference

王晓东《计算机算法设计与分析》