목차
1) 프로그램 개요
「문제 풀이」
2) 함수설명
3) 소스 코드
4) 출력화면
5) 고찰
「문제 풀이」
2) 함수설명
3) 소스 코드
4) 출력화면
5) 고찰
본문내용
1) 프로그램 개요
W의 행렬에서 각 행과 열을 vertex라고 보고 0이면 자기 자신 weight가 있으면 그 weight로 연결되어 있다고 생각하자. 이 연결된 vertex에서 한 지점을 선택해 다른 vertex들을 거쳐 다시 돌아오는 프로그램이다. (단, 각 vertex는 한번만 거친다.) 그때 거친 vertex들의 weight을 합친 값이 최소가 되는 것이 프로그램의 결과값이다.
간단히 예를 보이겠다. 출발점을 v1이라고 하고 v2~v5개의 vertex가 있다. v1 -> {v2, v3, v4, v5} ->v1으로 되는 형태이다. 이제 중간에 들어가는 {v2, v3, v4, v5}에서 무엇이 먼저 오느냐에 따라 최종 결과값이 달라진다. 즉, {v2, v3, v4, v5}에서 하나씩 순서를 나열하는 것이다. 문제는 이것을 하나씩 나열하는 경우 모두를 생각했을땐 어마어마하게 많은 계산 과정을 거쳐야 한다는것이다. 그것을 줄이기 위해 Dynamic programming을 사용한다. 즉, 처음부터 {v2, v3, v4, v5} 의 원소들이 다 있다고 생각하는것이 아니라. {v2}만 있다고 생각하고 v1->v2->v1을 계산해보고 {v3]을 넣어보고, 이번엔 {v2,v3} 두 개의 경우를 생각해 보는 식으로 하나씩 늘려가서 이전 결과값들을 사용해 최종 결과값을 도출해 내는 것이다.
W의 행렬에서 각 행과 열을 vertex라고 보고 0이면 자기 자신 weight가 있으면 그 weight로 연결되어 있다고 생각하자. 이 연결된 vertex에서 한 지점을 선택해 다른 vertex들을 거쳐 다시 돌아오는 프로그램이다. (단, 각 vertex는 한번만 거친다.) 그때 거친 vertex들의 weight을 합친 값이 최소가 되는 것이 프로그램의 결과값이다.
간단히 예를 보이겠다. 출발점을 v1이라고 하고 v2~v5개의 vertex가 있다. v1 -> {v2, v3, v4, v5} ->v1으로 되는 형태이다. 이제 중간에 들어가는 {v2, v3, v4, v5}에서 무엇이 먼저 오느냐에 따라 최종 결과값이 달라진다. 즉, {v2, v3, v4, v5}에서 하나씩 순서를 나열하는 것이다. 문제는 이것을 하나씩 나열하는 경우 모두를 생각했을땐 어마어마하게 많은 계산 과정을 거쳐야 한다는것이다. 그것을 줄이기 위해 Dynamic programming을 사용한다. 즉, 처음부터 {v2, v3, v4, v5} 의 원소들이 다 있다고 생각하는것이 아니라. {v2}만 있다고 생각하고 v1->v2->v1을 계산해보고 {v3]을 넣어보고, 이번엔 {v2,v3} 두 개의 경우를 생각해 보는 식으로 하나씩 늘려가서 이전 결과값들을 사용해 최종 결과값을 도출해 내는 것이다.
추천자료
sort에 관한 프로그램을 짜오거나 조사하기 : C언어로
DFT / FFT C언어 소스 및 소스 분석 및 결과분석
신호와 시스템 (그래프 그리기- C언어를 이용한 맥놀이 현상의 해석)
최단거리의 비용과 그 경로를 출력(C언어로)
Binomial random variable X의 distribution C언어 구현
[castlenine]C언어 요점정리
명함관리 프로그램 발표(c언어)
전기요금계산 프로그램 발표(c언어)
6족 로봇 보행 발표(c언어)
동적 메모리 할당 + 파일 입출력을 이용한 행렬 곱 소스코드 (c언어)
Rip,Ospf,C언어로 구현 및 소스,주석 포함
최대한 간단한 함수를 이용한 C언어 야구게임
2013 장애인 기능경기 대회 1과제 C언어 답안 (프랜차이즈 커피전문점에서 상품별 판매실적 ...
MAZE 확장[자료구조/자료구조및실험/c언어/c#/ Maze problem/Maze/Maze problem/미로/미로찾기]