//?分支限界.cpp?:?定義控制臺應用程序的入口點。
//
#include?“StdAfx.h“
#include
#include
#include

using?namespace?std;

struct?Node
{
	int?parent[10];??//存放父節點
	int?me;????????//記錄自己的位置
	int?value;???//記錄到目前為止的費用
	Node?*next;???//下一個節點
	Node?*last;???//上一節點
};

int?a[10][10];???//????距離矩陣
int?n;????//????城市點個數
Node?*point=NULL;???//當前最小費用的結點
Node?*L;

void?Initialize（）//初始化
{
	Node?*p0?=?new?Node;
	p0->parent[0]=0;
	p0->parent[1]=1;
	for（int?ti=2;ti<10;ti++）
	{
		p0->parent[ti]=0;
	}
	p0->value=a[1][2];
	p0->me=2;
	p0->last=NULL;
	p0->next=NULL;
	L=p0;
	for（int?i=3;i	{
		//Node?*q0=（Node?*）malloc（sizeof（Node））;
		Node?*q0?=?new?Node;
		q0->parent[0]=0;
		q0->parent[1]=1;
		for（int?tj=2;tj<10;tj++）
		{
			q0->parent[tj]=0;
		}
		q0->value=a[1][i];
		q0->me=i;
		q0->last=p0;
		q0->next=NULL;
		
		p0->next=q0;
		p0=q0;
	}
	
}
int?Branch（）?????//???分支限界發查找
{
	Node?*p=L;
	Node?*q;
	Node?*s;
	int?temp?=453231;
	while（NULL?!=?p）
	{
		
		if（temp?>?p->value）
		{
			temp?=?p->value;
			q=p;
		}
		p?=?p->next;
	}
	{??//記錄最優值
		point?=?new?Node;
		for（int?tt=0;tt<10;tt++）
		{
			point->parent[tt]=q->parent[tt];
		}
		point->me?=q->me;
		point->value?=?q->value;
		point->last=NULL;
		point->next?=NULL;
		
	}
	int?i=1;
	while（0!=q->parent[i]）
		i++;
	
	int?st[10]={0};??//存放兄弟結點
	int?Li?=?0;??????//???兄弟結點的個數
	bool?TF=FALSE;???//????結點控制
	for（int?j=0;j<（（n-i）-1）;j++）???//????需要添加的結點數
	{
		Node?*q0?=?new?Node;
		
		//??為新結點的父節點賦值
		q0->parent[0]=0;
		for（int?k=1;k		{
			q0->parent[k]=point->parent[k];
		}
		q0->parent[i]=point->me;
		
		for（int?tj=i+1;tj<10;tj++）
		{
			q0->parent[tj]=0;
		}
		for（int?R=2;R		{
			TF?=?FALSE;
			for（int?t=0;t				if（st[t]?==?R）
					TF=TRUE;
					
			if（FALSE?==TF）
				for（int?ti=1;ti					if（q0->parent[ti]==R）
						TF?=?TRUE;
							
			if（FALSE?==TF）
			{
				q0->me=R;
				st[Li]=R;
				Li++;
				break;
			}
		}
		L;
		q0->value=point->value+a[q0->me][point->me];
		if（NULL?==q）??????//插入結點
		{
			q0->last=s;
			q0->next=s->next;
			if（NULL?==?s->next）
			{
			}
			else
				s->next->last=q0;
			s->next=q0;
			s=q0;
		}
		else????????//????替換結點
		{
			if（NULL?==?q->last）
			{
			}
			else
				q->last->next=q0;
			q0->last=q->last;
			q0-