本文為大家帶來用C語言實現的回溯法電路板排列程序。

C語言程序

//電路板排列問題 回溯法求解

//#include “stdafx.h” #include < P>

#include < P>

int bestx［8］;

int m=5，n=8;

int *x;

int bestd=0;

int *total，*now;

int B［8］［5］;

/*

void Swap（int &a， int &b）

{

int temp;

temp=a;

a=b;

b=temp;

}

*/

void Backtrack（int i，int cd）//回溯法搜索排列樹

{

int j，k，temp，temp1，ld;

// printf（“diaoyong 2 ”）;

if（i == n-1） {

for（j=0; j

{

bestx［j］ = x［j］;

}

bestd = cd;

}

else

{

for（j=i; j

{ //選擇x［j］為下一塊電路板

ld = 0;

for（k=0; k

{

now［k］ += B［x［j］］［k］;

if（now［k］>0 && total［k］！=now［k］）

{

ld ++;

}

}

//更新ld

if（cd>ld）

{

ld = cd;

}

if（ld

{

//Swap（x［i］，x［j］）;

temp=x［i］; x［i］=x［j］;

x［j］=temp; Backtrack（i+1，ld）;

//Swap（x［i］，x［j］）;

temp1=x［i］;

x［i］=x［j］;

x［j］=temp1;

//恢復狀態

for（k=0; k

}

}

}

}

}

int Arrangement（int B［8］［5］， int n， int m， int bestx［8］）

{

//初始化X

int i，j;

// int *x，*total，*now;

x = （int *）malloc（（n+1）*sizeof（int））;

total= （int *）malloc（（m+1）*sizeof（int））;

now= （int *）malloc（（m+1）*sizeof（int））;

//

bestx = bestx;

bestd = m+1;

// printf（“diaoyong 1”）;

//初始化total和now

for（i=0; i

{

total［i］ = 0;

now［i］ = 0;

}

//初始化x為單位排列并計算total

for（i=0; i

{

x［i］ = i;

for（j=0; j

{

total［j］ += B［i］［j］;

}

}

//回溯搜索

Backtrack（0，0）;

return bestd;

}

void main（） {

int i，j，m = 5，n = 8;

int

A［］［5］={0，0，1，0，0，0，1，0，0，0，0，1，1，1，0，1，0，0，0，0，1，0，0，0，0，1，0，0，1，0，0，0，0，0，1，0，0，0，0，1};

//B={1，2，3，4，5，6，7，8}

//N1={4，5，6}，N2={2，3}，N3={1，3}，N4={3，6}，N5={7，8}

printf（“m=%d，n=%d”，m，n）;

printf（“\n”）;

printf（“N1={4，5，6}，N2={2，3}，N3={1，3}，N4={3，6}，N5={7，8}”）;

printf（“\n”）;

printf（“二維數組A如下：”）;

printf（“\n”）;

//構造A

for（i=0; i

{

for（j=0; j

{

B［i］［j］=A［i］［j］;

}

}

for（i=0; i

{

for（j=0; j

{

printf（“%d ”，B［i］［j］）;

}

printf（“\n”）;

}

for（i=0;i

{

bestx［i］=0;

}

bestd=Arrangement（B，n，m，bestx）;

printf（“最優密度：%d”，bestd）;

printf（“\n”）;

printf（“最優密度排列”）;

for（i=0; i

{

printf（“%d ”，bestx［i］+1）;

}

}