赞
踩
在当前节点(扩展节点)处,先生成其所有的儿子节点(分支),然后再从当前的活节点(当前节点的子节点)表中选择下一个扩展节点。为了有效地选择下一个扩展节点,加速搜索的进程,在每一个活节点处,计算一个函数值(限界),并根据函数值,从当前活节点表中选择一个最有利的节点作为扩展节点,使搜索朝着解空间上有最优解的分支推进,以便尽快地找出一个最优解。分支限界法解决了大量离散最优化的问题。
1.队列式(FIFO)分支限界法
队列式分支限界法将活节点表组织成一个队列,并将队列的先进先出原则选取下一个节点为当前扩展节点。
2.优先队列式分支限界法
优先队列式分支限界法将活节点表组织成一个优先队列,并将优先队列中规定的节点优先级选取优先级最高的下一个节点成为当前扩展节点。如果选择这种选择方式,往往将数据排成最大堆或者最小堆来实现。
- import static org.junit.Assert.*;
-
- import java.util.LinkedList;
- import java.util.Queue;
- import java.util.Scanner;
-
- import javax.management.Query;
-
- import org.junit.Test;
-
- class Node{
- private int curw, curv;
- private int units_i;
- private int[] route;
- Node(){
- route = new int[110];
- }
- public Node(int curw, int curv, int units_i, int[] route) {
- super();
- this.curw = curw;
- this.curv = curv;
- this.units_i = units_i;
- this.route = route;
- }
- public int getCurw() {
- return curw;
- }
- public void setCurw(int curw) {
- this.curw = curw;
- }
- public int getCurv() {
- return curv;
- }
- public void setCurv(int curv) {
- this.curv = curv;
- }
- public int getUnits_i() {
- return units_i;
- }
- public void setUnits_i(int units_i) {
- this.units_i = units_i;
- }
- public int[] getRoute() {
- return route;
- }
- public void setRoute(int[] route) {
- this.route = route;
- }
-
- }
-
- public class 最小重量设计_分支限界法 {
-
- /*
- * 3 3
- * 3 2 1 4 5 6
- * 1 4 3 2 5 6
- * 5 6 3 2 1 4
- * 10
- *
- * 答案是5
- */
- private static int w[][];
- private static int c[][];
- private static int n, m, cc;
- private static Scanner cin;
- private static Queue<Node>q;
- static{
- cin = new Scanner(System.in);
- q = new LinkedList<Node>();
- }
-
-
- public static void main(String[] args) {
- System.out.println("请输入部件数目以及供货商数量n和m:");
- n = cin.nextInt();
- m = cin.nextInt();
- w = new int[n][m];
- c = new int[n][m];
-
- System.out.println("n行代表n个部件,每行输入每个供货商供应此部件的重量以及价格:");
- for(int i = 0; i < n; i++){
- for(int j = 0; j < m; j++){
- w[i][j] = cin.nextInt();
- c[i][j] = cin.nextInt();
- }
- }
- System.out.println("请输入不超过的价格p:");
- cc = cin.nextInt();
- q.clear();
- int[] route = new int[110];
- Node e = new Node(0, 0, -1, route);
- q.add(e);
- int ans = Integer.MAX_VALUE;
- while(!q.isEmpty()){
- e = q.poll();
-
- for(int j = 0; j < m; j++){
- int i = e.getUnits_i() + 1;
- if(i >= n){
-
- if(e.getCurv() <= cc){
- if(ans > e.getCurw()){
- ans = Math.min(ans, e.getCurw());
- route = e.getRoute();
- }
- }
- continue;
- }
- int curv = e.getCurv() + c[i][j];
- int curw = e.getCurw() + w[i][j];
-
- int[] lastroute = e.getRoute();
- int[] curroute = new int[110];
- for(int k = 0; k <= e.getUnits_i(); k++){
- curroute[k] = lastroute[k];
- }
- curroute[i] = j;
-
- q.add(new Node(curw, curv, i, curroute));
- }
- }
- if(ans == Integer.MAX_VALUE){
- System.out.println("不能找出总价格不超过 c的最小重量机器的方案");
- }else{
- System.out.println("满足方案的最小重量是:" + ans);
- System.out.println("方案是:");
- for(int j = 0; j < n; j++){
- System.out.print(route[j] + " ");
- }
-
- }
- }
-
-
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。