時間計算コストの評価について

[雷電]

こんにちは。前に8パズルについて質問させていただいたものです。
そのときに、時間計算コスト評価について質問させていただきました。

ユーザーの方から参考URLを提示していただき、その後調べてみたのですがよくわからず、
先生に尋ねてみたところ、解に到達するまでに行った操作回数のことだそうです。

しかし、これをどう求めればよいのかわかりません。
「オーダー」を使うらしいのですが、これを求めるプログラムってあるのでしょうか？

わかる方いましたら教えていただけると嬉しいです。
たびたびですが、すいません。

[たいちう]

> 先生に尋ねてみたところ、解に到達するまでに行った操作回数のことだそうです。
>
> しかし、これをどう求めればよいのかわかりません。
> 「オーダー」を使うらしいのですが、これを求めるプログラムってあるのでしょうか？

操作回数そのものならば、操作するたびにカウンタをインクリメントすればOK。
オーダーについては、普通はプログラムでは求めません。
「計算量 オーダー」というキーワードでググると良いでしょう。

3×3の8パズルを1ミリ秒で解くプログラムについて、
同じ方法で3000×3000の8,999,999パズルを解くのにどの位の時間がかかるか？
というようなことを概算で計算する時など、オーダーと言う考え方が便利です。

[雷電]

回答ありがとうございます。

インクリメントというと、for文を使うんでしょうか？
初期状態からゴールにたどり着くまで、何回か寄り道をする（操作回数）。
ゴールについたら、通ってきた道(操作回数)を出力する(おそらく実行するごとに回数に誤差がある)。
のようなプログラムって書けるでしょうか？
90行目に書いてみたのですが、あいまいでよく分かりません･･･
どうすればいいか分かりますでしょうか？
いろいろ考えているのですが、うまくできずに聞いてばかりで申し訳ありません･･･

コード:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
//#include<time.h>

#define D 3    /*D×D-1 パズル。　このマクロを変えればどんな大きさのパズルでも探索できる*/


struct node{

  int block[D][D];        /*各ノードのブロック状態*/
  char ei;                /*空白の場所*/
  char ej;
  unsigned int nextnum: 3;    /*直属の子ノードの数*/
  int depth;                 /*このノードの深さ*/
  int heuristic;             /*ヒューリスティック値*/
  int exp;                   /*ヒューリスティック値 ＋ 深さ*/
  struct node **next;        /*子ノードへのポインタ*/
  struct node *reverse;      /*親ノードへのポインタ*/
  struct node *nextleaf;     /*リーフだった場合、次のリーフへのポインタ*/
  struct node *reverseleaf;  /*前のリーフへのポインタ*/
};


void init(struct node *root, struct node *goal);         /*ルート初期化、ゴール状態定義*/
void heuristic(struct node *cur, struct node *goal);     /*ヒューリスティック関数*/
int allocate(struct node *cur, struct node *endleaf);   /*メモリを確保してリストにつなげる*/
int rootdev(struct node *cur, struct node *endleaf);   /*allocateのルート版*/
int operate(struct node *cur, char direction);          /*状態遷移関数*/
struct node *search(struct node *leaf);                /*次に展開するノードを探す*/
void output(struct node *cur);                         /*解法を表示*/
	int goal_state[9]={1,2,3,8,0,4,7,6,5};


void output(struct node *cur)
{
	int i, j, k=0;
	FILE *fp;
	//clock_t start,end;
	//start = clock();
	int count;
	//count = count + 1;
	
  if((fp=fopen("解法.txt","w"))==NULL){
	printf("ファイルを生成できません\n");
    exit(1);
  }


  do{
	cur->reverse->nextleaf = cur;
    cur = cur->reverse;
  }while(cur->reverse);    /*ポインタ再利用*/


  do{
    printf("%d 手目\n", k);//最後以外、常に出てくる手数
    fprintf(fp, " %d 手目\n", k++);//メモ帳に書き写す
    
	for(i=0;i<D;i++){  //iを増やすと、行が上から減る
      for(j=0;j<D;j++){//jを増やすと、列が左から減る。完成だけ普通
        printf("%3d", cur->block[i][j]);       /*解法を表示*/
      											//cur->block[i][j]が数値？1～8+0を全て受け持つ?
      											//%d=数値、%とdの間に数字でスペース
        fprintf(fp, "%3d", cur->block[i][j]);//解法txtに
      }
	  printf("\n");
      fprintf(fp, "\n");//解法txtに(fprintfが、メモ帳に書きこむ役割？)
    }
    fprintf(fp, "\n\n");
    printf("\n\n");

    cur = cur->nextleaf;
  }while(cur->heuristic);

  printf(" %d 手目\n", k);//最後の手数
  fprintf(fp, " %d 手目\n", k);//最後の手数を、解法.txtに写す

  for(i=0;i<D;i++){
    for(j=0;j<D;j++){
      fprintf(fp, "%3d", cur->block[i][j]);
	  printf("%3d", cur->block[i][j]);//完成形をあらわす。
    }
    printf("\n");
    fprintf(fp, "\n");
  }
  printf("\n\n結果：%d手で完成します。");
  fprintf(fp, "\n\n");

	for(count = 1; "%d"  ;count = count + 1){
		//fclose(fp);
		//count = count + 1;
		//end = clock();
		printf("\n\n%d回です。",count/*(double)(end-start) / CLOCKS_PER_SEC*/);

	}
}


struct node *search(struct node *leaf)
{
  struct node *nextdev;
  int min=50000;

  leaf = leaf->nextleaf;

  while(leaf->nextleaf){   /*リーフリストをたどってexpが最小のリーフを探す*/
	if(min > leaf->exp){
      nextdev = leaf;
      min = leaf->exp;
    }
    leaf = leaf->nextleaf;
  }

//  printf("\nあと%d 手以下で完成\n\n", nextdev->heuristic);

  return  nextdev;
}


int operate(struct node *cur, char direction)
{
  char i, j;


  for(i=0;i<D;i++)
    for(j=0;j<D;j++)
	  cur->block[i][j] = cur->reverse->block[i][j];

  cur->ei = cur->reverse->ei;
  cur->ej = cur->reverse->ej;

  if(direction == 'u'){
    cur->block[cur->ei][cur->ej] = cur->block[cur->ei-1][cur->ej];   /*状態遷移を実行*/
    cur->block[--cur->ei][cur->ej] = 0;
  }

  else if(direction == 'd'){
    cur->block[cur->ei][cur->ej] = cur->block[cur->ei+1][cur->ej];
    cur->block[++cur->ei][cur->ej] = 0;
  }

  else if(direction == 'r'){
    cur->block[cur->ei][cur->ej] = cur->block[cur->ei][cur->ej+1];
    cur->block[cur->ei][++cur->ej] = 0;
  }

  else if(direction == 'l'){
    cur->block[cur->ei][cur->ej] = cur->block[cur->ei][cur->ej-1];
    cur->block[cur->ei][--cur->ej] = 0;
  }

  else{
    printf("ありえない\n");    /*万が一の例外処理*/
    exit(1);
  }

  return (cur->depth = cur->reverse->depth + 1);
}



int allocate(struct node *cur, struct node *endleaf)
{
  char k = 0, i, direction[3];
  int depth=0, buf;


  if(cur->ei != 0 && cur->reverse->ei+1 != cur->ei)   /*遷移できる状態とその数を調べる*/
    direction[k++] = 'u';

  if(cur->ei != D-1 && cur->reverse->ei != cur->ei+1)
	direction[k++] = 'd';

  if(cur->ej != 0 && cur->reverse->ej+1 != cur->ej)
    direction[k++] = 'l';

  if(cur->ej != D-1 && cur->reverse->ej != cur->ej+1)
    direction[k++] = 'r';

  if(k<1 || 3<k){
    printf("ありえない\n");
	exit(1);
  }

  cur->next = (struct node **)malloc(sizeof(struct node *)*(int)k); 
  cur->nextnum = (unsigned int)k;

  for(i=0;i<k;i++){
    cur->next[i] = (struct node *)malloc(sizeof(struct node));
    if(!cur->next[i]){
      printf("メモリ割り当てエラー");
	  exit(1);
    }

    cur->next[i]->reverse = cur;

    cur->next[i]->reverseleaf = endleaf->reverseleaf;   /*リストにつなげる*/
	endleaf->reverseleaf->nextleaf = cur->next[i];
    cur->next[i]->nextleaf = endleaf;
    endleaf->reverseleaf = cur->next[i];

    if(depth < (buf=operate(cur->next[i], direction[i])))
      depth = buf;
  }

  cur->reverseleaf->nextleaf = cur->nextleaf;
  cur->nextleaf->reverseleaf = cur->reverseleaf;

  return depth;
}



int rootdev(struct node *cur, struct node *endleaf)
{
  char k = 0, i, direction[4];
  int buf, depth=0;

  if(cur->ei != 0)
    direction[k++] = 'u';

  if(cur->ei != D-1)
    direction[k++] = 'd';

  if(cur->ej != 0)
    direction[k++] = 'l';

  if(cur->ej != D-1)
    direction[k++] = 'r';

  if(k<2 || 4<k){
    printf("ありえない\n");
    exit(1);
  }


  cur->next = (struct node **)malloc(sizeof(struct node *)*(int)k); 
  cur->nextnum = (unsigned int)k;

  for(i=0;i<k;i++){
    cur->next[i] = (struct node *)malloc(sizeof(struct node));
    if(!cur->next[i]){
	  printf("メモリ割り当てエラー");
      exit(1);
    }

	cur->next[i]->reverse = cur;

    cur->next[i]->reverseleaf = endleaf->reverseleaf;
	endleaf->reverseleaf->nextleaf = cur->next[i];
    cur->next[i]->nextleaf = endleaf;
    endleaf->reverseleaf = cur->next[i];

    if(depth < (buf = operate(cur->next[i], direction[i])))
      depth = buf;
  }

  cur->reverseleaf->nextleaf = cur->nextleaf;
  cur->nextleaf->reverseleaf = cur->reverseleaf;

  return depth;
}



void heuristic(struct node *cur, struct node *goal)
{
  char i, j, gi, gj, k, d = D*D;


  cur->heuristic = 0;
  
  for(k=1;k<d;k++){

    for(i=0;i<D;i++)
      for(j=0;j<D;j++)
		if(cur->block[i][j] == k)
          goto breakpoint;              /*オペレータの制限を緩めてゴールまでの手数を見積もる*/
    breakpoint:

    for(gi=0;gi<D;gi++)
      for(gj=0;gj<D;gj++)
		if(goal->block[gi][gj] == k)
          goto breakpoint2;
	breakpoint2:


    cur->heuristic += (int)(fabs((double)(i-gi)) + fabs((double)(j-gj)));
  }
  cur->exp = cur->heuristic + cur->depth;

}



void init(struct node *root, struct node *goal)
{
  FILE *fp;
  char i, j;

  if((fp=fopen("初期状態.txt","r"))==NULL){
    printf("初期状態ファイルを開けませんでした。\n");
	exit(1);
  }

	printf("--初期状態--\n");
  for(i=0;i<D;i++){
	for(j=0;j<D;j++){
      fscanf(fp, "%d", &root->block[i][j]);
      printf(" %2d", (int)root->block[i][j]);
	  goal->block[i][j]=goal_state[i*3+j];
		//goal->block[i][j] = k++;
      if(!root->block[i][j]){
        root->ei = i;
        root->ej = j;
	  }
    }
    printf("\n");
  }

  root->depth = 0;
  root->reverse = NULL;
//  goal->block[D-1][D-1] = 0;

  printf("\nルートの初期化、ゴール状態の定義完了\n\n");

/*
  for(i=0;i<D;i++){
    for(j=0;j<D;j++)
      printf("%3d", goal->block[i][j]);
    printf("\n");
  }
*/

}



int main(void)
{
  struct node root, *cur, goal, startleaf, endleaf, *next;
  int i, depth=0, buf;


  startleaf.nextleaf = &root;
  root.nextleaf = &endleaf;
  endleaf.reverseleaf = &root;
  root.reverseleaf = &startleaf;
  endleaf.nextleaf = NULL;
 
  init(&root, &goal);

  heuristic(&root, &goal);
  if(!(root.heuristic)){
    printf("すでにゴール状態です\n");
	return 0;
  }

  if(depth < (buf = rootdev(&root, &endleaf)))
    depth = buf;
  printf("\n深さ 1 まで展開");

  for(i=0;i<(int)(root.nextnum);i++)
    heuristic(root.next[i], &goal);


  while((next = search(&startleaf))->heuristic){
    if(depth < (buf = allocate(next, &endleaf))){
        depth = buf;
	  for(buf=0;buf<30;buf++)
        printf("\b");
      printf("深さ %d まで展開", depth);
	}

    for(i=0;i<(int)(next->nextnum);i++)
	  heuristic(next->next[i], &goal);
  }

  printf("\n\n%d 手で完成\n\n", next->depth);
  output(next);

  return 0;
}

[non]

90行から96行を見ると、何をやりたいのか、わかりません。
って、いうより、このプログラムを全く理解していません。
学校の課題とのことですが、通常のC言語の授業課題にしては難しすぎますね。
あなたは、別の人が作ったプログラムを参考にしているようですが、他の人たちは
一から全部作るのでしょうか？だとしたら、結構レベルの高い授業ですね。
いずれにしても、少し、プログラムの勉強をした方がいいでしょう。

[たいちう]

もう見てないようだけど一応回答。

> インクリメントというと、for文を使うんでしょうか？

プログラムによります。
for文でインクリメントを使う事は多いですが、
for文とインクリメントは関係ありません。

時間計算コストの評価に取り組む前に、
自分が添付しているプログラムを理解してください。
本や授業や回答者のサンプルをコピペしているだけみたいですが、
それでは理解はできませんよ。


nonさん

> 学校の課題とのことですが、通常のC言語の授業課題にしては難しすぎますね。
> あなたは、別の人が作ったプログラムを参考にしているようですが、他の人たちは
> 一から全部作るのでしょうか？だとしたら、結構レベルの高い授業ですね。

もし大学のC言語の授業だとして、4月から週一で講義があったとすると、
この程度の課題は高レベルとは思えません。
私は大学でプログラミングを履修したことはないので、
他の講義の難易度と比較しての話ですが。

[non]

たいちうさん
>もし大学のC言語の授業だとして、4月から週一で講義があったとすると、
>この程度の課題は高レベルとは思えません。
>私は大学でプログラミングを履修したことはないので、
>他の講義の難易度と比較しての話ですが。

私が、習ったのはもう数十年も前ですからねぇ。
一般の教養として学ぶプログラミング言語としては難しいと思いますが、今は、どれくらい
習っているのでしょうか。別のスレッドを立てて、みなさんに聞いてみますね。