分支限界法求旅行商问题

// 分支限界.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-