0033算法筆記——分支限界法與單源最短路徑問題

      1、分支限界法

    (1)描述：采用廣度優先産生狀态空間樹的結點，并使用剪枝函數的方法稱為分枝限界法。

     所謂“分支”是采用廣度優先的政策，依次生成擴充結點的所有分支（即：兒子結點）。

     所謂“限界”是在結點擴充過程中，計算結點的上界（或下界），邊搜尋邊減掉搜尋樹的某些分支，進而提高搜尋效率。

    (2)原理：按照廣度優先的原則，一個活結點一旦成為擴充結點（E-結點）R後，算法将依次生成它的全部孩子結點，将那些導緻不可行解或導緻非最優解的兒子舍棄，其餘兒子加入活結點表中。然後，從活結點表中取出一個結點作為目前擴充結點。重複上述結點擴充過程，直至找到問題的解或判定無解為止。

    (3)分支限界法與回溯法

     1)求解目标：回溯法的求解目标是找出解空間樹中滿足限制條件的所有解，而分支限界法的求解目标則是找出滿足限制條件的一個解，或是在滿足限制條件的解中找出在某種意義下的最優解。 

     2)搜尋方式的不同：回溯法以深度優先的方式搜尋解空間樹，而分支限界法則以廣度優先或以最小耗費優先的方式搜尋解空間樹。

    (4)常見的分支限界法

     1)FIFO分支限界法(隊列式分支限界法)

     基本思想：按照隊列先進先出(FIFO)原則選取下一個活結點為擴充結點。

     搜尋政策：一開始，根結點是唯一的活結點，根結點入隊。從活結點隊中取出根結點後，作為目前擴充結點。對目前擴充結點，先從左到右地産生它的所有兒子，用限制條件檢查，把所有滿足限制函數的兒子加入活結點隊列中。再從活結點表中取出隊首結點（隊中最先進來的結點）為目前擴充結點，……，直到找到一個解或活結點隊列為空為止。

    2)LC(least cost)分支限界法(優先隊列式分支限界法)

    基本思想：為了加速搜尋的程序，應采用有效地方式選擇活結點進行擴充。按照優先隊列中規定的優先級選取優先級最高的結點成為目前擴充結點。

    搜尋政策：對每一活結點計算一個優先級（某些資訊的函數值），并根據這些優先級；從目前活結點表中優先選擇一個優先級最高（最有利）的結點作為擴充結點，使搜尋朝着解空間樹上有最優解的分支推進，以便盡快地找出一個最優解。再從活結點表中下一個優先級别最高的結點為目前擴充結點，……，直到找到一個解或活結點隊列為空為止。

     (5)分支限界法搜尋應用舉例

      1)0-1背包問題，當n=3時，w={16,15,15}, p={45,25,25}, c=30

     隊列式分支限界法(處理法則:先進先出)：{}—>{A}—>{B,C}—>{C,D,E}(D是不可行解，舍棄)—>{C,E}—>{E,F,G}—>{F,G,J,K}(J是不可行解，舍棄)—>{F,G,K}—>{G,K,L,M}—>{K,L,M,N,O}—>{}

     優先隊列式分支限界法(處理法則:價值大者優先)：{}—>{A}—>{B,C}—>{C，D，E}—>{C，E}—>{C，J，K}—>{C}—>{F，G}—>{G，L，M}—>{G，M}—>{G}—>{N，O}—>{O}—>{}

     2)旅行員售貨問題

     隊列式分支限界法(節點B開始)：{ }—{B}—{C，D，E}—{D，E，F，G}—{E，F，G，H，I}—{F，G，H，I，J，K}—{G，H，I，J，K，L}—{H，I，J，K，L，M}—{I，J，K，L，M，N}—{J，K，L，M，N，O}—{K，L，M，N，O，P}—{L，M，N，O，P，Q}—{M，N，O，P，Q}—{N，O，P，Q}—{O，P，Q}—{P，Q}—{Q}—{ }

     優先隊列式分支限界法：優先級是結點的目前費用：{ }—{B}—{C，D，E}—{C，D，J，K}—{C，J，K，H，I}—{C，J，K，I，N}—{C，K，I，N，P}—{C，I，N，P，Q}—{C，N，P，Q，O}—{C，P，Q，O}—{C，Q，O}—{Q，O，F，G}—{Q，O，G，L}—{Q，O，L，M}—{O，L，M}—{O，M}—{M}—{ }

     2、單源最短路徑問題

    問題描述

     在下圖所給的有向圖G中，每一邊都有一個非負邊權。要求圖G的從源頂點s到目标頂點t之間的最短路徑。

     下圖是用優先隊列式分支限界法解有向圖G的單源最短路徑問題産生的解空間樹。其中，每一個結點旁邊的數字表示該結點所對應的目前路長。

    算法設計

     算法從圖G的源頂點s和空優先隊列開始。結點s被擴充後，它的兒子結點被依次插入堆中。此後，算法從堆中取出具有最小目前路長的結點作為目前擴充結點，并依次檢查與目前擴充結點相鄰的所有頂點。如果從目前擴充結點i到頂點j有邊可達，且從源出發，途經頂點i再到頂點j的所相應的路徑的長度小于目前最優路徑長度，則将該頂點作為活結點插入到活結點優先隊列中。這個結點的擴充過程一直繼續到活結點優先隊列為空時為止。

    在算法擴充結點的過程中，一旦發現一個結點的下界不小于目前找到的最短路長，則算法剪去以該結點為根的子樹。

    在算法中，利用結點間的控制關系進行剪枝。從源頂點s出發，2條不同路徑到達圖G的同一頂點。由于兩條路徑的路長不同，是以可以将路長長的路徑所對應的樹中的結點為根的子樹剪去。 

     算法具體代碼如下：

     1、MinHeap2.h

#include <iostream>

template<class Type>
class Graph;

template<class T> 
class MinHeap 
{ 
	template<class Type>
	friend class Graph;
	public: 
		MinHeap(int maxheapsize = 10); 
		~MinHeap(){delete []heap;} 

		int Size() const{return currentsize;} 
		T Max(){if(currentsize) return heap[1];} 

		MinHeap<T>& Insert(const T& x); 
		MinHeap<T>& DeleteMin(T &x); 

		void Initialize(T x[], int size, int ArraySize); 
		void Deactivate(); 
		void output(T a[],int n);
	private: 
		int currentsize, maxsize; 
		T *heap; 
}; 

template <class T> 
void MinHeap<T>::output(T a[],int n) 
{ 
	for(int i = 1; i <= n; i++) 
	cout << a[i] << " "; 
	cout << endl; 
} 

template <class T> 
MinHeap<T>::MinHeap(int maxheapsize) 
{ 
	maxsize = maxheapsize; 
	heap = new T[maxsize + 1]; 
	currentsize = 0; 
} 

template<class T> 
MinHeap<T>& MinHeap<T>::Insert(const T& x) 
{ 
	if(currentsize == maxsize) 
	{ 
		return *this; 
	} 
	int i = ++currentsize; 
	while(i != 1 && x < heap[i/2]) 
	{ 
		heap[i] = heap[i/2]; 
		i /= 2; 
	} 

	heap[i] = x; 
	return *this; 
} 

template<class T> 
MinHeap<T>& MinHeap<T>::DeleteMin(T& x) 
{ 
	if(currentsize == 0) 
	{ 
		cout<<"Empty heap!"<<endl; 
		return *this; 
	} 

	x = heap[1]; 

	T y = heap[currentsize--]; 
	int i = 1, ci = 2; 
	while(ci <= currentsize) 
	{ 
		if(ci < currentsize && heap[ci] > heap[ci + 1]) 
		{ 
			ci++; 
		} 

		if(y <= heap[ci]) 
		{ 
			break; 
		} 
		heap[i] = heap[ci]; 
		i = ci; 
		ci *= 2; 
	} 

	heap[i] = y; 
	return *this; 
} 

template<class T> 
void MinHeap<T>::Initialize(T x[], int size, int ArraySize) 
{ 
	delete []heap; 
	heap = x; 
	currentsize = size; 
	maxsize = ArraySize; 

	for(int i = currentsize / 2; i >= 1; i--) 
	{ 
		T y = heap[i]; 
		int c = 2 * i; 
		while(c <= currentsize) 
		{ 
			if(c < currentsize && heap[c] > heap[c + 1]) 
				c++; 
			if(y <= heap[c]) 
				break; 
			heap[c / 2] = heap[c]; 
			c *= 2; 
		} 
		heap[c / 2] = y; 
	} 
} 

template<class T> 
void MinHeap<T>::Deactivate() 
{ 
	heap = 0; 
}       

     2、6d2.cpp

//單源最短路徑問題 分支 限界法求解
#include "stdafx.h"
#include "MinHeap2.h"
#include <iostream>
#include <fstream> 
using namespace std;

ifstream fin("6d2.txt"); 

template<class Type>
class Graph
{
	friend int main();
    public:
		void ShortesPaths(int);
	private:
        int		n,		   //圖G的頂點數
				*prev;     //前驅頂點數組
 	    Type	**c,       //圖G的領接矩陣
				*dist;     //最短距離數組
}; 

template<class Type>
class MinHeapNode
{
   friend Graph<Type>;
   public:
	   operator int ()const{return length;}
   private:
       int       i;		  //頂點編号
       Type  length;	  //目前路長
}; 

template<class Type>
void Graph<Type>::ShortesPaths(int v)//單源最短路徑問題的優先隊列式分支限界法
{ 
	MinHeap<MinHeapNode<Type>> H(1000);
	MinHeapNode<Type> E;

	//定義源為初始擴充節點
	E.i=v;
	E.length=0;
	dist[v]=0;

	while (true)//搜尋問題的解空間
	{
		for (int j = 1; j <= n; j++)
			if ((c[E.i][j]!=0)&&(E.length+c[E.i][j]<dist[j])) {

				 // 頂點i到頂點j可達，且滿足控制限制
				 dist[j]=E.length+c[E.i][j];
				 prev[j]=E.i;

				 // 加入活結點優先隊列
				 MinHeapNode<Type> N;
				 N.i=j;
				 N.length=dist[j];
				 H.Insert(N);
			}`
		try 
		{
			H.DeleteMin(E); // 取下一擴充結點
		}        
		catch (int) 
		{
			break;
		}  
		if (H.currentsize==0)// 優先隊列空
		{
			break;
		}
	}
}

int main()
{  
	int n=11;
	int prev[12] = {0,0,0,0,0,0,0,0,0,0,0,0};  

	int dist[12]={1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000};

	cout<<"單源圖的鄰接矩陣如下："<<endl;
	int **c = new int*[n+1];

	for(int i=1;i<=n;i++)
	{
		c[i]=new int[n+1];
		for(int j=1; j<=n; j++)
		{
			fin>>c[i][j];
			cout<<c[i][j]<<" ";
		}
		cout<<endl;
	}

	int v=1;
    Graph<int> G;
    G.n=n;

    G.c=c;
    G.dist=dist;
    G.prev=prev;
    G.ShortesPaths(v);

    cout<<"從S到T的最短路長是："<<dist[11]<<endl;
    for (int i = 2; i <= n; i++)
	{
		cout<<"prev("<<i<<")="<<prev[i]<<"   "<<endl;
	}

    for (int i = 2; i <= n; i++)
	{
		cout<<"從1到"<<i<<"的最短路長是："<<dist[i]<<endl;
	}

	for(int i=1;i<=n;i++)
	{
		delete []c[i];
	}

	delete []c;
	c=0;	
	return 0;
}      

     程式運作結果如圖：