Algorithm with C/BackTracking
-
미로 탐색Algorithm with C/BackTracking 2020. 8. 26. 19:26
0. 참고 문헌 1. 개념 미로의 한 지점에서 탈출구로 향하는 경로 속에는 여러 길목이 있는데, 이들 각 길목에서 왼쪽으로 갈지, 오른쪽으로 갈지, 또 계속 가던 방향으로 계속 갈지의 물음(부분 문제)에 답(부분해)을 구하는 과정을 반복하면서 완성한 것이 탈출로(해) 이다. 여기에서 부분 문제의 답은 어느 것이라도 될 수 있다. 선택한 방향으로 끝까지 가봐야 '해를 이루는 부분해'가 될지 안될지를 알 수 있는 것이므로. 게다가 선택한 방향으로 가다 보면 새로운 갈래길목을 만나게 될 것이고, 그 곳에서도 또 여러 가능성을 두고 선택을 해야 하는 상황이 온다. 이렇게 해가 될 수 있는 가능성을 가진 부분해의 조합을 두고 후보해라고 한다. 백트래킹이 다루는 문제들은 대개 후보해의 수가 굉장히 많다는 특징이 있..
-
N - QueenAlgorithm with C/BackTracking 2020. 8. 24. 18:19
0. 참고 문헌 1. 문제 2. 문제 분석 퀸은 8가지 방향으로 움직이며 공격을 할 수 있고, 이동 범위도 체스판 전체이다. 8개의 퀸 문제는 8 X 8 크기의 체스판을 염두에 두고 제안됐지만 다른 크기의 체스 판으로도 문제의 확장과 축소가 가능하다. 4 X 4 이상의 크기라면 이 문제를 적용할 수 있는데, 그래서 8개의 퀸 문제를 N 개의 퀸 문제라 부르기도 한다. 퀸을 체스판에 배치할 때, 행을 기준으로 배치하는 것으로 약속을 하도록 하자. 그리고 체스판은 4 X 4로 고정하고 문제 풀이에 접근한다. 당연히 퀸은 하나의 행에 하나만 배치가 가능하다. (퀸의 공격 범위가 가능하므로) 아래의 [그림 1 ~ 4]는 체스판의 크기가 4 X 4일 때의 퀸을 놓는 방법을 나타낸 것이다. 별 모양이 퀸이다. [그..
-
연구활동 가는 길( 그래프 방식 )Algorithm with C/BackTracking 2020. 8. 21. 08:49
1. 그래프 방식의 풀이 과정 문제는 앞에 있으니 생략하도록 한다. 우선 자료 구조에서 작업한 그래프를 가지고 와서 구현을 할 것이다. (비용을 포함한 그래프를 그대로 가지고 와서 구현) 첫 작업은 파일에 있는 내용을 그래프에 저장해야 한다. 이는 LoadDataFromFile함수가 한다. 이 작업이 끝나면 아래와 같은 구조가 된다. 정점의 개수는 7개로 고정을 했다. 정점의 개수만큼 pVertexList배열이 동적할당이 된다. 탐색을 할 시작 정점은 앞의 인접 행렬 풀이에서와 마찬가지로 0번 정점이다. 아래는 탐색 함수이다. 2. 구현 프로그램 실행결과 3. 소스 & 헤더 파일
-
연구활동 가는 길( 인접 행렬 풀이 )Algorithm with C/BackTracking 2020. 8. 19. 19:08
1. 문제 2. 문제 분석 위는 SetDataLoadDataFromFile함수가 호출이 되면, 이차원배열g_Path에 cost가 저장이 된다. cost값이 0이라는 의미를 2가지를 포함하고 있다. 1. 자기 자신에서 자기 자신으로 갈 때의 cost값은 0이다. 2. '길'을 갈 수가 없는 경우에 cost값은 0이다. (현재의 정점과의 연결이 안된 경우) 예를 들어서, g_Path[0][0] = 0 의 의미는 자기 자신에서 자기 자신으로 갈 때의 경우이다. g_Path[1][2] = 0 의 의미는 1번 정점과 2번 정점은 서로 연결되지 않았다는 의미이다, 여기서, 탐색을 할 때 이차원 배열의 행과 열은 다음과 같다. 행 요소 = 현재의 정점 열 요소 = 현재의 정점과 연결된 다음 정점 이를 토대로 다시 설..