완도군청

[공학][인공지능 프로젝트] PC 기반 지하철 최소비용 알고리즘 연구 - 지하철 노선 찾기 (첨부#1)

첨부파일 : 공학 인공지능 프로젝트 PC 기반 지하철 최소비용 알고리즘 연구 - 지하철 노선 찾기.hwp
다운경로 : http://www.jisik114.net/search/detail.asp?pk=11077788&sid=korea072




[공학][인공지능 프로젝트] PC 기반 지하철 최소비용 알고리즘 연구 - 지하철 노선 찾기

인공지능 프로젝트 결과보고서

0. 프로젝트명 - PC 기반 지하철 최소비용 알고리즘 연구

1. 서론

1.1 프로젝트 개요

부산지하철 최소환승과 최단거리경로를 구하는 인공지능 프로젝트

1.2 프로젝트 목적

프로그램을 통해 최소환승과 최단거리경로를 구함으로써 사용자가 원하는 경로를 쉽고 빠르게

구할 수 있도록 하는 것 입니다.


1.3 프로젝트 내용

부산지하철 노선을 데이터베이스를 구성하고 백트래킹 알고리즘 원리를 이용해서 C#을 기반

으로 하는 최소환승과 최단거리경로를 구하는 프로그램

2. 백트래킹 알고리즘 연구

2.1 백트래킹 알고리즘 이란

백트래킹(backtracking)은 한정 조건을 가진 문제를 풀려는 전략이다.

`백트랙(backtrack)`이란 용어는 1950년대의 미국 수학자
D. H. 레머에 의해 지어졌다.

문제가 한정 조건을 가진 경우 원소의 순서는 해결 방법과 무관하다.
이런 문제는 변수 집합으로 이뤄지는데, 한정 조건을 구성하려면 각각의 변수들은 값이 있어야 한다.
백트래킹은 모든 조합을 시도해서 문제의 해를 찾는다.
이것이 장점이 될 수 있는 이유는 백트래킹 구현 방법들이 많은 부분 조합들을 배제하기 때문이다.
결국 풀이 시간이 단축된다.

백트래킹의 주요 개념은 해를 얻을 때까지 모든 가능성을 시도한다는 점이다.
모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지 중에 해결책이 있다.
트리를 검사하기 위해 깊이 우선 탐색을 사용한다.
탐색 중에 오답을 만나면 이전 분기점으로 돌아간다.
시도해보지 않은 다른 해결 방법이 있으면 시도한다.
해결 방법이 더 없으면 더 이전의 분기점으로 돌아간다.
모든 트리의 노드를 검사해도 답을 못 찾을 경우, 이 문제의 해결책은 없는 것이다.

백트래킹은 보통 재귀 함수로 구현된다.
재귀로 파생된 해결 방법은 하나 이상의 변수가 필요한데 , 이것은 현재 시점에서 적용할 수 있는 변수 값들을 알고 있다.
백트래킹은 깊이 우선 탐색과 대략 같으나 기억 공간은 덜 차지한다.
현재의 상태를 보관하고 바꾸는 동안만 차지한다.

탐색 속도를 높이기 위해, 재귀 호출을 하기 전에 시도할 값을 정하고 조건(전진 탐색의 경우)을 벗어난 값을 지우는 알고리즘을 적용할 수 있다.
아니면 그 값을 제외한 다른 값들을 탐색할 수도 있다.

2.2 백트래킹 예

4-Queens Problem

4개의 Queen을 서로 상대방을 위협하지 않도록 4X4 체스 판에 위치시키는 문제이다.

서로 상대방을 위협하지 않기 위해서는 같은 행이나, 같은 열이나, 같은 대각선상에 위치하지 않아야 한다.



무작정 알고리즘

각 Queen을 각각 다른 행에 할당한 후에, 어떤 열에 위치하면 해답은 얻을 수 있는지를 차례대로 점검해 보면 된다.

이때, 각 Queen은 4개의 열중에서 한 열에 위치할 수 있기 때문에, 해답을 얻기 위해서 점검해 보아야 하는 모든 경우의 수는 4X4X4X4 = 256가지가 된다.

4-Queens Problem의 상태 공간 트리와 백트래킹



4-Queens Problem의 상태 공간 트리 Backtracking on 4-queens

Backtracking의 문제점

위 그림에서, 깊이 우선 탐색을 수행하면 노드의 방문 순서는 1 4 7 8 5 9 10 6 11 12 2 … 3…이 된다.

1번 노드를 선택해서 자손 노드로 내려갈 때, 마지막 노드들(7 8 9 10 11 12)이 어떠한 경우라도 옳지 않은 경우가 발생할 때가 있다.
(즉, 애초에 1번 노드의 선택이 잘못 되었다.)

이 경우, 잘못된 1번 노드를 선택함으로써, 불필요한 탐색(4 7 8 5 9 10 6 11 12)이 발생하는 것이다.

(the same failure can be rediscovered an exponential number of times)

Backtracking의 문제점 해결 방안

check not completely assigned constraints: propagation

(전파. 여기서는 다루지 않는다.)

non-chronological backtracking: backjumping

Non-chronological Backtracking

위의 그림은 8X8 체스 판에 퀸을 8개 놓는 문제이다.

X1, X2, X3, … , X8 순으로 퀸을 순차적으로 놓는다.

X4를 (2,4)에 놓음으로써 X5는 놓을 수 있으나, 더 이상 X6을 놓을 자리가 없게 된다.

또한 X5의 위치를 바꾼다고 해서, X6을 놓을 자리가 생기는 것도 아니다.

X4를 놓는 위치가 잘못 되었다고 할 수 있다.

따라서 위의 트리에서 보는 것처럼 X6에서 X4의 다른 대안(노드)으로 backjump를 하게 된다.

Conflict Set

노드의 탐색에 있어서 각 주기에서 수행 가능한 규칙이 하나 이상인 경우가 많다.
이들 수행 가능한 규칙들의 집합을 충돌집합 (conflict set) 이라고 하며, 시스템은 이들 중 하나를 선택하여야 한다.

Conflict-Directed Backjumping

conflict set에 있는 마지막 변수(variable)로 점프한다.

conflict set은 back up된다.

중간 결정은 제거된다.

3. 데이터 베이스 구현

3.1 부산지하철 데이터 베이스

3.1.1. 앞의 빨간 박스에 있는 숫자들은 노드의 번호와 노드이름을 설정했다.
1번 노드는 신평 2번노드는 하단순으로 설정했다.

3.1.2. 노란색 박스도 노드의 번호와 노드의 이름이다.
지하철은 한 방향으로만 운행하지 않고 양방향 운행이기 때문에 2번 노드부터 순서대로 다시 설정해준다.

3.1.3. 출발역과 도착역의 가중치이다.
1번 노드에서 2번노드로 이동할때의 가중치 여기에서 가중치는 역에서 역까지 이동할 때 걸리는 시간이다.

3.2 데이터 베이스의 그래프 구현

3호선에서 2호선으로 환승하는 구간이다.
배산 → 망미 → 수영에서 광안과 민락으로 나뉜다.
수영은 환승역이기 때문에 가중치(소요시간)을 5분으로 주었고 수영에서 환승할 수 있는 2호선이 광안과 민락으로 나뉘기 때문에 그래프가 갈라졌다.

ex)

서울 지하철의 일부를 그래프로 만들고 그래프의 가중치를 입력한 모습니다.

4. 프로젝트 실험 및 고찰

출발역과 도착역을 입력하여 Root와 최적의 해를 설정해준다.

Root Node부터 검색을 시작하는데 가중치의 합은 다음 노드부터 연산해준다.
그런 후 다음 노드를 탐색하고 끝 역인지 판별 후 끝 역이 아니라면 … (첨부#1)



..... (중략)






제목 : [공학][인공지능 프로젝트] PC 기반 지하철 최소비용 알고리즘 연구 - 지하철 노선 찾기 (첨부#1)
출처 : 지식114 자료실



[문서정보]

문서분량 : 16 Page
파일종류 : HWP 파일
자료제목 : [공학][인공지능 프로젝트] PC 기반 지하철 최소비용 알고리즘 연구 - 지하철 노선 찾기
파일이름 : 공학 인공지능 프로젝트 PC 기반 지하철 최소비용 알고리즘 연구 - 지하철 노선 찾기.hwp
키워드 : 공학,인공지능,프로젝트,PC,기반,지하철,최소비용,알고리즘,노선,찾기



문서종류 : HWP 파일
다운받기 : http://www.jisik114.net/search/detail.asp?pk=11077788&sid=korea072