DataStructure-Queueアプリケーション

3.迷宮探索問題

3.1深さ優先ナビゲーションと幅優先ナビゲーション

[スタックを使用して迷路をナビゲート]

深度優先ナビゲーション(DFS、Depth Frest Serach)

なるべく歩けるところまで歩いて、渋滞していたら、もう一つの道を探し直して、

隣人のナビゲーション順序:上、下、左、右(この順序は重要ではありません)

次のスタックから取り出されるのは、常に最近保存されている

である.

[キューを使用して迷路をナビゲート]

幅優先ナビゲーション(BFS、Breadth First Search)

ナビゲーションシーケンスでは、幅は深さ

よりも優先する.

現在位置、上、下、左、右の順に隣接位置

を検査する.

の隣接する到達可能な位置が見つかった場合、その位置を保存する必要があります.この場合、キューを使用するのは

です.

の位置の処理が完了すると、キューから再び1つの位置を現在位置(スタックとは異なり、この場合が最初に保存する位置)

として取り出す.

3.2 STLキューを使用した迷宮ナビゲーションプログラム（幅優先ナビゲーション）

コード

#include "Location2D.h" // 위치 클래스 포함
#include <cstdio>
#include <queue> // STL의 queue 탬플릿 파일 포함

using namespace std;
const int MAZE_SIZE = 6; // 미로 맵 크기 고정
char map[MAZE_SIZE][MAZE_SIZE] = {
  {'1','1','1','1','1','1'},
  {'e','0','1','0','0','1'},
  {'1','0','0','0','1','1'},
  {'1','0','1','0','1','1'},
  {'1','0','1','0','0','x'},
  {'1','1','1','1','1','1'}
};

// (r,c)가 갈 수 있는 위치인지를 검사하는 함수
// (r,c)가 배열 안에 있고, 값이 갈 수 있는 위치 '0'이거나 출구 'x'이어야 함
bool isValidLoc(int r, int c){
  if(r<0 || c<0 || r>=MAZE_SIZE || c>=MAZE_SIZE) return false;
  else return map[r][c] =='0' || map[r][c] == 'x';
}

// 미로 탐색 프로그램 함수
int main(){
  queue<Location2D> locQueue; // 위치 큐 객체 생성
  Location2D entry(1,0); // 입구 객체
  locQueue.push(entry); // 큐에 입구 위치 삽입

  while(locQueue.empty() == false){ // 큐가 비어 있지 않는 동안
    Location2D here = locQueue.front(); // 큐의 front 상단 객체 복사
    locQueue.pop(); // 큐 상단 객체 삭제

    int r = here.row;
    int c = here.col;

    printf("(%d, %d)\n",r,c); // 현재 위치를 화면에 출력
    if(map[r][c] == 'x'){ // 출구이면 -> 탐색 성공
      printf("Maze Search Success\n");
      return 0;
    }else{ // 출구가 아니면 현재 위치를
      map[r][c]='.'; // 현재 위치를 지나옴으로 처리
      if(isValidLoc(r-1,c)) locQueue.push(Location2D(r-1,c)); // 먼저 들어간 값을 뺌
      if(isValidLoc(r+1,c)) locQueue.push(Location2D(r+1,c));
      if(isValidLoc(r,c-1)) locQueue.push(Location2D(r,c-1));
      if(isValidLoc(r,c+1)) locQueue.push(Location2D(r,c+1));
    }
  }
  printf("Maze Search Fail\n"); // 스택이 공백 상태가 되면 출구 탐색이 실패함
  return 0;
}

運転結果

3.3 STLのDequeによる迷宮航法（深度優先航法）

コード

#include "Location2D.h" // 위치 클래스 포함
#include <cstdio>
#include <deque> // STL의 deque 탬플릿 파일 포함

using namespace std;
const int MAZE_SIZE = 6; // 미로 맵 크기 고정
char map[MAZE_SIZE][MAZE_SIZE] ={
  {'1','1','1','1','1','1'},
  {'e','0','1','0','0','1'},
  {'1','0','0','0','1','1'},
  {'1','0','1','0','1','1'},
  {'1','0','1','0','0','x'},
  {'1','1','1','1','1','1'}
};

// (r,c)가 갈 수 있는 위치인지를 검사하는 함수
// (r,c)가 배열 안에 있고, 값이 갈 수 있는 위치 '0'이거나 출구 'x'이어야 함
bool isValidLoc(int r, int c){
  if(r<0 || c<0 || r>=MAZE_SIZE || c>=MAZE_SIZE) return false;
  else return map[r][c] =='0' || map[r][c] == 'x';
}

// 미로 탐색 프로그램 함수
int main(){
  deque<Location2D> locDeque; // 위치 덱 객체 생성
  Location2D entry(1,0); // 입구 객체
  locDeque.push_front(entry); // 덱 입구 위치 삽입

  while(locDeque.empty() == false){ // 덱이 비어 있지 않는 동안
    Location2D here = locDeque.front(); // 덱의 front 상단 객체 복사
    locDeque.pop_front(); // 덱 상단 객체 삭제

    int r = here.row;
    int c = here.col;

    printf("(%d, %d)\n",r,c); // 현재 위치를 화면에 출력
    if(map[r][c] == 'x'){ // 출구이면 -> 탐색 성공
      printf("Maze Search Success\n");
      return 0;
    }else{ // 출구가 아니면 현재 위치를
      map[r][c]='.'; // 현재 위치를 지나옴으로 처리
      if(isValidLoc(r-1,c)) locDeque.push_front(Location2D(r-1,c));
      if(isValidLoc(r+1,c)) locDeque.push_front(Location2D(r+1,c));
      if(isValidLoc(r,c-1)) locDeque.push_front(Location2D(r,c-1));
      if(isValidLoc(r,c+1)) locDeque.push_front(Location2D(r,c+1));
    }
  }
  printf("Maze Search Fail\n"); // 스택이 공백 상태가 되면 출구 탐색이 실패함
  return 0;
}

運転結果

3.4 STLのDequeによるラビリンスナビゲーション（幅優先ナビゲーション）

コード

#include "Location2D.h" // 위치 클래스 포함
#include <cstdio>
#include <deque> // STL의 deque 탬플릿 파일 포함

using namespace std;
const int MAZE_SIZE = 6; // 미로 맵 크기 고정
char map[MAZE_SIZE][MAZE_SIZE] ={
  {'1','1','1','1','1','1'},
  {'e','0','1','0','0','1'},
  {'1','0','0','0','1','1'},
  {'1','0','1','0','1','1'},
  {'1','0','1','0','0','x'},
  {'1','1','1','1','1','1'}
};

// (r,c)가 갈 수 있는 위치인지를 검사하는 함수
// (r,c)가 배열 안에 있고, 값이 갈 수 있는 위치 '0'이거나 출구 'x'이어야 함
bool isValidLoc(int r, int c){
  if(r<0 || c<0 || r>=MAZE_SIZE || c>=MAZE_SIZE) return false;
  else return map[r][c] =='0' || map[r][c] == 'x';
}

// 미로 탐색 프로그램 함수
int main(){
  deque<Location2D> locDeque; // 위치 덱 객체 생성
  Location2D entry(1,0); // 입구 객체
  locDeque.push_front(entry); // 덱에 입구 위치 삽입

  while(locDeque.empty() == false){ // 덱가 비어 있지 않는 동안
    Location2D here = locDeque.front(); // 덱의 front 상단 객체 복사
    locDeque.pop_front(); // 덱 상단 객체 삭제

    int r = here.row;
    int c = here.col;

    printf("(%d, %d)\n",r,c); // 현재 위치를 화면에 출력
    if(map[r][c] == 'x'){ // 출구이면 -> 탐색 성공
      printf("Maze Search Success\n");
      return 0;
    }else{ // 출구가 아니면 현재 위치를
      map[r][c]='.'; // 현재 위치를 지나옴으로 처리
      if(isValidLoc(r-1,c)) locDeque.push_back(Location2D(r-1,c)); // 먼저 들어간 값을 뺌
      if(isValidLoc(r+1,c)) locDeque.push_back(Location2D(r+1,c));
      if(isValidLoc(r,c-1)) locDeque.push_back(Location2D(r,c-1));
      if(isValidLoc(r,c+1)) locDeque.push_back(Location2D(r,c+1));
    }
  }
  printf("Maze Search Fail\n"); // 스택이 공백 상태가 되면 출구 탐색이 실패함
  return 0;
}

運転結果

参考文献

千人国·崔英圭知音,『c++楽に书いた资料构造』,生能出版(2016),p.161~