/* 課題1 */
list *appendList(stid state, SL *hpt, list *pt){
   /* 再帰バージョン */
  list *tmpst;

  if(pt == NULL){ /* ptそのものがNULLのとき 最後の要素 停止条件 */
    tmpst = newList(); /* tmpst -> next は、NULLで初期化されている */
    tmpst->state = state;
    tmpst->history = hpt; /* hptは、この頂点までの経路情報　SL型 */
    return tmpst; /* 新要素のアドレス */
  } else { /* 再帰条件。returnされるアドレスを繋ぎなおしていることに注意 */
    pt->next = appendList(state, hpt, pt->next); /* pt -> next == NULLのとき、つまり最後の要素だけ、変 更になる */
    return pt; /* 自分自身のアドレスをreturn */
  }

/************************************************************
 * 探索アルゴリズム
 ************************************************************/

/**************************************************
 深さ優先探索 (Depth First Search)
 **************************************************/
SL *dfs(stid start, stid goal){
  int i;
  stid curstate;
  SL *nextstateset;
  SL *curhpt;

// 探索管理用リスト Lを初期状態だけのリストにする
  ol = NULL;
  ol = pushList(start, NULL, ol);

// while Lが空リストでない
  while(ol != NULL){
    PRINTLIST(ol);  // 探索管理用リストをプリント

    /* Lの先頭要素を取り出して、curstateに代入 */
    curstate = ol->state;
    curhpt = pushSL(curstate, ol->history);
    ol = popList(ol);
    if(curstate == goal) return(curhpt);

    nextstateset = generateChildren(curstate);
    while(nextstateset != NULL){
      if(memberSL(nextstateset->state, curhpt)==false){
        ol = pushList(nextstateset->state, curhpt, ol);
      }
      nextstateset=popSL(nextstateset);
    }
  }
  return(NULL);
}


/**************************************************
課題2  幅優先探索 (Breadth First Search)
   dlsをまるごとコピーして、接続ノードをリスト処理をキューに
 **************************************************/
SL *bfs(stid start, stid goal){
  int i;
  stid curstate;
  SL *nextstateset;
  SL *curhpt;

// 探索管理用リスト Lを初期状態だけのリストにする
  ol = NULL;
  ol = pushList(start, NULL, ol);

// while Lが空リストでない
  while(ol != NULL){
    PRINTLIST(ol);  // 探索管理用リストをプリント

    /* Lの先頭要素を取り出して、curstateに代入 */
    curstate = ol->state;
    curhpt = pushSL(curstate, ol->history); /* 本来ここは、enqueue */
    ol = popList(ol)            ;/* 本来ここは、dequeue */
    if(curstate == goal) return(curhpt);

    nextstateset = generateChildren(curstate);
    while(nextstateset != NULL){
      if(memberSL(nextstateset->state, curhpt)==false){
/*      ol = pushList(nextstateset->state, curhpt, ol); */ /* 変更 */
        ol = appendList(nextstateset->state, curhpt, ol);
      }
      nextstateset=popSL(nextstateset);
    }
  }
  return(NULL);
}

/**************************************************
 課題3 深さ制限探索 (Depth-limited Search)
dfsをコピーして、条件を付け加える
 **************************************************/

SL *dls(stid start, stid goal, int limit){
  int i;
  stid curstate;
  SL *nextstateset;
  SL *curhpt;

// 探索管理用リスト Lを初期状態だけのリストにする
  ol = NULL;
  ol = pushList(start, NULL, ol);

//  while Lが空リストでない
   while(ol != NULL){
       PRINTLIST(ol);  // 探索管理用リストをプリント

  /* Lの先頭要素を取り出して、curstateに代入 */
    curstate = ol->state;
    curhpt = pushSL(curstate, ol->history);
    ol = popList(ol);
    if(curstate == goal) return(curhpt);

    if(lengthSL(curhpt) < limit){  /*  limit以下の深さなら、追加 */
      nextstateset = generateChildren(curstate);
      while(nextstateset != NULL){
        if(memberSL(nextstateset->state, curhpt)==false){
          ol = pushList(nextstateset->state, curhpt, ol);
        }
        nextstateset=popSL(nextstateset);
      }
    }
  }
  return(NULL);
}

/**************************************************
 反復深化探索 (Iterative Deepening Search)
 このまま、手をいれないこと
 **************************************************/
SL *ids(stid start, stid goal){
  int cutdepth;
  SL *result;

  cutdepth = 1;
  printf("==================== cut depth = %2d ====================\n",
         cutdepth);

  while((result = dls(start, goal, cutdepth++)) == NULL){
    printf("==================== cut depth = %2d ====================\n",
           cutdepth);
  }
  return(result);
}

/**********************************************************************
 Main
mt-search Bの値 Dの値 Goalノード 探索タイプ
B: 分岐数  D: 木の深さ Goalノード：ノードの番号
探索タイプ： 0 深さ優先 1 幅優先 2 反復深化
 ******************************************：１****************************/

typedef struct _searchfunc {
  char *comment;
  SL *(*func)(stid, stid);
} searchfunc;

searchfunc searchtable[] = {
  {"Depth First Search", dfs},
  {"Breadth First Search", bfs},
  {"Iterative Deepening Search", ids},
  {NULL, NULL}
};

void help(char *cmdname){
  int i;

  fprintf(stderr, "Usage: %s BranchingFactor MaxDepth Goal [search_algorithm]\n", cmdname);
  for(i = 0; searchtable[i].comment!=NULL; i++){
    fprintf(stderr, "  %d : %s\n", i, searchtable[i].comment);
  }
}

int main(int argc, char *argv[]){
  stid start, goal;
  SL *sp;
  int maxalg, curalg;

  for(maxalg = 0; searchtable[maxalg].comment!=NULL; maxalg++);

  // 引数の個数のチェックと探索方法(第5引数,デフォールトは 0)の設定
  if( (argc != 4 && argc != 5) ||
      (curalg= argc == 5 ? atoi(argv[4]) : 0) < 0 ||
      maxalg <= curalg) {
    help(argv[0]);
    exit(0);
  }

  // 初期状態(0), 木のサイズ(分岐数,深さ)と目標状態の設定
  start = 0;
  BF = atoi(argv[1]);
  MD = atoi(argv[2]);
  goal = atoi(argv[3]);

  // 探索の実施
  sp = (searchtable[curalg].func)(start, goal);
  printf("Path %d : ", lengthSL(sp));
  printSL(sp);
}
STEP 1.3 課題プログラム 2016

STEP 1.3　課題プログラム 2016
