계명대 컴퓨터 알고리즘 과제 입니다.

소개글

계명대 컴퓨터 알고리즘 과제 입니다.에 대한 보고서 자료입니다.

본문내용

문제 설명 >

Traveling Salesperson Problem

어떤 vertex에서 Graph상의 모든 vertex를 최소한의 길이로 순회하여 다시 돌아오는 문제를 Traveling Salesperson Problem이라고 한다. 외판원 문제를 통해 동적계획 알 고리즘과 Branch and Bound 알고리즘 설계법으로 구현해서 알고리즘의 비교/평가해보고 이 과제물을 통해 알게 된 사실을 요약 정리한다.

알고리즘의 설명 >

-Branch and Bound 알고리즘을 이용한 Traveling Salesman Problem
각 노드를 검색할 때 마다, 그 노드가 유망한지 여부를 결정하기 위해서 한계값을 계산하여 노드의 한계값이 지금까지 찾은 최적의 해답보다 나쁜 경우, 더 이상 그 가지를 뻗어서 검색을 계속할 필요가 없음을 이용
Depth-frist-search, Best-first-search 두개의 알고리즘으로 구해야함

-동적계획 알고리즘을 이용한 Traveling Salesman Problem
제일 먼저 노드(정점)가 하나만 있다고 가정하고서 문제를 풀고, 그 결과를 가지고 노드(정점)의 개수를 하나 더 늘렸을 때의 문제를 풀고, 이렇게 부분 답을 가지 고서 노드(정점)의 개수를 점점 늘여가면서 결국에 원하는 답을 찾는 방식임

comment가 포함된 소스 리스트 >

동적 알고리즘과 Best - first - search 알고리즘 두 개만 구현 했습니다.

해당자료는 한글2002나 워디안 자료로 한글97에서는 확인하실 수 없으십니다.

키워드

컴퓨터알고리즘,   알고리즘,   외판원