#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define B 13 //ブロック数
#define N (B*2-1) //ノード数
#define X_MAX 10 //横の最大値
#define Y_MAX 10 //縦の最大値
#define Z_MAX 10 //高さの最大値
typedef struct _node {
int info1,info2,info3,info4, info5,info6,info7;
struct _node *left, *right,*oya;
}Node;
//info1が「1のとき横に配列」「2のとき縦に配列」「3のとき上に配列」「4のときはブロック」
//info2は荷台につめる順番
//info3,info4,info5はブロックの横、縦、高さ（info1!=4のときは全て0）
//info6は根を含む右端のノードのinfo1が1,2,3の時1、それ以外は0
static Node
Z={ 0,0,0,0,0,0,0,&Z,&Z,NULL},
y={ 4,11,5,5,3,0,25,&Z,&Z},
x={ 4,12,4,6,6,0,24,&Z,&Z},
w={ 4,10,8,5,3,0,23,&Z,&Z},
v={ 4,1,5,5,2,0,22,&Z,&Z},
u={ 4,9,6,4,5,0,21,&Z,&Z},
t={ 2,0,0,0,0,0,20,&x,&y},
s={ 4,5,3,5,9,1,19,&Z,&Z},
r={ 2,1,0,0,0,0,18,&v,&w},
q={ 4,6,2,6,3,0,17,&Z,&Z},
p={ 4,3,6,4,8,0,16,&Z,&Z},
o={ 1,10,0,0,0,0,15,&t,&u},
n={ 4,8,9,2,5,0,14,&Z,&Z},
m={ 1,9,0,0,0,1,13,&r,&s},
l={ 3,8,0,0,0,0,12,&p,&q},
k={ 4,4,6,7,2,0,11,&Z,&Z},
j={ 1,7,0,0,0,0,10,&n,&o},
i={ 4,2,1,2,1,0,9,&Z,&Z},
h={ 4,7,7,5,6,0,8,&Z,&Z},
g={ 3,6,0,0,0,1,7,&l,&m},
f={ 4,13,9,3,4,0,6,&Z,&Z},
e={ 3,5,0,0,0,0,5,&j,&k},
d={ 3,4,0,0,0,0,4,&h,&i},
c={ 2,3,0,0,0,1,3,&f,&g},
b={ 2,2,0,0,0,0,2,&d,&e},
a={ 3,1,0,0,0,1,1,&b,&c,&Z};
Node *Clone(Node *t1){
Node *node = malloc(sizeof(Node));
Copy(node, t1);
return node;
}
Copy(Node *node,Node *t1){
node->info1 = t1->info1;
node->info2 = t1->info2;
node->info3 = t1->info3;
node->info4 = t1->info4;
node->info5 = t1->info5;
node->info6 = t1->info6;
node->info7 = t1->info7;
if(!node->info1==0){
node->left=malloc(sizeof(Node));
Copy(node->left,t1->left);
node->right=malloc(sizeof(Node));
Copy(node->right,t1->right);
node->left->oya=node;
node->right->oya=node;
}
}
/*後順走査のよって全体の体積を算出*/
static Node taisekikeisan(Node *t1){
if((t1->info1>0)&&(t1->info1<4)){
Node *a1,*b1;
taisekikeisan(a1=t1->left);
taisekikeisan(b1=t1->right);
/*横に配置 info3は足し算、info4,info5は大きいほうを選択*/
if(t1->info1==1){
t1->info3=a1->info3+b1->info3;
if(a1->info4>b1->info4){
t1->info4=a1->info4;
}
else t1->info4=b1->info4;
if(a1->info5>b1->info5){
t1->info5=a1->info5;
}
else t1->info5=b1->info5;
}
/*縦に配置 info4は足し算、info3,info5は大きいほうを選択*/
else if(t1->info1==2){
if(a1->info3>b1->info3){
t1->info3=a1->info3;
}
else t1->info3=b1->info3;
t1->info4=a1->info4+b1->info4;
if(a1->info5>b1->info5){
t1->info5=a1->info5;
}
else t1->info5=b1->info5;
}
/*上下に配置 info5は足し算、info3,info4は大きいほうを選択*/
else if(t1->info1==3){
if(a1->info3>b1->info3){
t1->info3=a1->info3;
}
else t1->info3=b1->info3;
if(a1->info4>b1->info4){
t1->info4=a1->info4;
}
else t1->info4=b1->info4;
t1->info5=a1->info5+b1->info5;
}
// printf("info1=%2d, info2=%2d, x=%2d, y=%2d, z=%2d \n", t1->info1,t1->info2, t1->info3,t1->info4,t1->info5);
return *t1;
}
else{
// printf("info1=%2d, info2=%2d, x=%2d, y=%2d, z=%2d \n", t1->info1,t1->info2, t1->info3,t1->info4,t1->info5);
return *t1;
}
}
//ノードの数字より小さい数字をカウント
static int countChildNodeYoritiisai(Node *target, int value)
{
int sum=0;
if(target->info1==0)return 0;
if((target->info1==4)&&(target->info2<value)){
sum=1;
}
sum+=countChildNodeYoritiisai(target->left,value);
sum+=countChildNodeYoritiisai(target->right,value);
return sum;
}
static int mudaNode(Node *target, int value)
{
int count=0;
while(target->info6!=1){
if((target->oya->info1!=2)&&(target->oya->right!=target)){
count+=countChildNodeYoritiisai(target->oya->right,value);
}
target=target->oya;
}
return count;
}
//先順走査によって無駄の合計値を算出
int goukei=0;
static Node preorder(Node *t1){
if((t1->info1>0)&&(t1->info1<4)){
Node *a1,*b1;
t1->left->oya = t1;
t1->right->oya = t1;
preorder(a1=t1->left);
preorder(b1=t1->right);
return *t1;
}
else{
goukei+=mudaNode(t1,t1->info2);
return *t1;
}
}
//親子関係にあれば１を返す、なければ０
static int isOyakokankei(Node *t1,Node *t2){
Node *n;
n = t1;
while(n!=&Z){
n=n->oya;
if(n==t2)return 1;
}
n = t2;
while(n!=&Z){
n=n->oya;
if(n==t1)return 1;
}
return 0;
}
//ランダムでノードを探索
static Node *findNode(int ransu, Node *t1){
Node *a1,*b1;
if(t1!=&Z){
if(t1->info7==ransu)return t1;
a1 = findNode(ransu,t1->left);
b1 = findNode(ransu,t1->right);
if(a1!=&Z) return a1;
else if(b1!=&Z)return b1;
}
return &Z;
}
//部分木の交換
static void ChangeSubTree(Node *t1,Node *t2){
Node a1,b1,*c1,*n;
if(t1->oya == t2->oya){
c1 = t1->oya->left;
t1->oya->left = t1->oya->right;
t1->oya->right = c1;
}
else{
if(t1->oya->left==t1)t1->oya->left=t2;
else t1->oya->right=t2;
if(t2->oya->left==t2)t2->oya->left=t1;
else t2->oya->right=t1;
}
a1.info6=t1->info6;
a1.oya=t1->oya;
b1.info6=t2->info6;
b1.oya=t2->oya;
t1->info6=b1.info6;
t1->oya=b1.oya;
t2->info6=a1.info6;
t2->oya=a1.oya;
if(t1->info6){
n = t1;
while(n->info1!=4){
n->right->info6=1;
n=n->right;
}
n = t2;
while(n->info1!=4){
n->right->info6=0;
n=n->right;
}
}
else if(t2->info6){
n = t2;
while(n->info1!=4){
n->right->info6=1;
n=n->right;
}
n = t1;
while(n->info1!=4){
n->right->info6=0;
n=n->right;
}
}
return;
}
//ランダムで部分木を交換
int ransu1,ransu2;
static Node RandomChangeSubTree(){
Node *targetNode1, *targetNode2;
ransu1 = rand()%N;
ransu2 = (ransu1+1+(rand()%(N-1)))%N;
targetNode1 = findNode(ransu1,&a);
targetNode2 = findNode(ransu2,&a);
if(!isOyakokankei(targetNode1,targetNode2))
ChangeSubTree(targetNode1,targetNode2);
return *targetNode1, *targetNode2;
}
//ランダムで選択したブロックを９０度回転
static Node Kaiten(Node *t1){
int a1,b1;
do{
ransu1 = rand()%N;
t1 = findNode(ransu1,&a);
}while(t1->info1!=4);
a1=t1->info3;
b1=t1->info4;
t1->info3=b1;
t1->info4=a1;
return *t1;
}
//ランダムで選択したノードの配置変換
static Node HaitiTenkan(Node *t1){
do{
ransu1 = rand()%N;
t1 = findNode(ransu1,&a);
}while((t1->info1== 0)||(t1->info1==4));
ransu2 = rand()%2;
if(ransu2){
if(t1->info1==1)
t1->info1=2;
else if(t1->info2==2)
t1->info1=3;
else t1->info1=1;
}
else {
if(t1->info1==1)
t1->info1=3;
else if(t1->info2==2)
t1->info1=1;
else t1->info1=2;
}
return *t1;
}
/*----------------------------------------------------------------------------*/
int main()
{
int i1,ransu_R,kai_x,kai_y,kai_z;
double pena_x,pena_y,pena_z,kai_muda=10000,kai_muda_ima;
Node *temp = &a;
Node *copy1 = Clone(a);
srand((unsigned) time(NULL));
//初期解生成
preorder(temp);
printf("初期の無駄合計は%d\n",goukei);
taisekikeisan(temp);
printf("初期のx＝%2d,y=%2d,z=%2d\n\n",temp->info3,temp->info4,temp->info5);
goukei = 0;
//３分の１の確率で３パターンから選んで近傍解生成
for(i1=0;i1<10;i1++){
//ransu_Rは０か１か２
ransu_R = rand()%3;
//部分木入れ替え
if(ransu_R == 0){
RandomChangeSubTree();
preorder(temp);
printf("無駄合計は%d\n",goukei);
taisekikeisan(temp);
printf("x＝%2d,y=%2d,z=%2d\n",temp->info3,temp->info4,temp->info5);
}
//ブロック回転
else if(ransu_R == 1){
Kaiten(temp);
preorder(temp);
printf("無駄合計は%d\n",goukei);
taisekikeisan(temp);
printf("x＝%2d,y=%2d,z=%2d\n",temp->info3,temp->info4,temp->info5);
}
//配置転換
else {
HaitiTenkan(temp);
preorder(temp);
printf("無駄合計は%d\n",goukei);
taisekikeisan(temp);
printf("x＝%2d,y=%2d,z=%2d\n",temp->info3,temp->info4,temp->info5);
}
kai_x=temp->info3;
kai_y=temp->info4;
kai_z=temp->info5;
//x軸でのはみ出しのペナルティ
if(kai_x>X_MAX)
pena_x=(double)(kai_x-X_MAX)*0.01*(i1+1);
else
pena_x=0;
//y軸でのはみ出しのペナルティ
if(kai_y>Y_MAX)
pena_y=(double)(kai_y-Y_MAX)*0.01*(i1+1);
else
pena_y=0;
//z軸でのはみ出しのペナルティ
if(kai_z>Z_MAX)
pena_z=(double)(kai_z-Z_MAX)*0.01*(i1+1);
else
pena_z=0;
//ペナルティの合計値を表示
printf("ペナ合計は %f\n",pena_x+pena_y+pena_z);
//解無駄が小さければ更新、大きかったらそのまま
kai_muda_ima=goukei+pena_x+pena_y+pena_z;
printf("無駄合計とペナをあわせた途中の評価値 %f\n\n",kai_muda_ima);
//前回より解がよかったら（評価値が小さかったら）
if(kai_muda_ima<kai_muda){
kai_muda=kai_muda_ima;
Node *copy1 = Clone(a);
}
//前回より解が悪かったら（評価値が大きかったら）
else
Node *a= Clone(copy1);
//数値の初期化
goukei=0;
pena_x=0;
pena_y=0;
pena_z=0;
printf("評価値は %f\n\n",kai_muda);
}
return 0;
}