TSP 외판원 C언어 프로그래밍 문제
누림
질문 제목 :TSP 외판원 C언어 프로그래밍 문제질문 요약 :C언어를 사용하여 TSP 외판원 문제를 해결
알고리즘은 한 점에서 모든 연결가능한 점의 가중치를 계산하여 그중 가장 작은 가중치가 있는 점으로 이동
그후 다시 그 점에서 가중치를 비교후 한번도 가지않은 점으로 이동
질문 내용 :
입력 파일 input.txtba b 5a c 6a d 8b c 7b d 10c d 3입니다 실행파일 이름이 TSP일때 tsp input.txt ouput.txt 라고 cmd에 쳤을때출력 파일 output.txt가b a c d b 24 로 나오도록 하고싶은데지금26x26배열에 다음과 같이 넣어놨습니다.(0은 보기편하기위해 0으로 해놓은것이며 다른 충분히 큰 수로 변경가능합니다)이제 경로 탐색과 가중치 계산이 남았는데 이 부분을 하나도 모르겠습니다 ㅜㅜ... 이부분 도움좀 주셨으면합니다.*추가정보입니다.*입력파일과 출력파일
입력 파일의 첫 줄에는 외판원이 여행을 처음 시작하는 지점을 입력한다.예를들어 그림1의 그래프에서b정점부터 외판원이 여행을 시작한다면 아래의 예제 입력파일과 같이 첫 줄에b가 나타나야 한다.입력파일의 두 번째 줄부터는 한 줄마다 하나의 간선(아크)을 나타낸다.간선은2개의 정점 그리고 비중 순으로 나타낸다.두 점은 문자열로 나타내고 비중은 숫자로 나타낸다.두 점 사이는 빈 칸으로 구분한다.그리고 끝점과 비중 사이도 빈칸으로 구분한다.예를 들어 그림1의 그래프에서a—5—b와 같은 간선은 아래의input.txt파일의 두 번째 줄에서a b 5로 나타낸다.이와 같은 방식으로 그래프의 간선들을 나타낸다.
출력 파일의 첫 번째 줄에는 외판원이 여행한 경로를 시작 정점부터 끝 정점까지 순서대로 출력한다.예를 들어 그림1의 그래프에서 외판원의 경로는b, a, c, d, b순이므로output.txt파일에는b a c d b가 출력된다.그 다음에 비중의 합을 출력한다.예를 들어 생성된 해밀턴회로에서 비중의 합은24이므로output.txt파일의b a c d b다음에24가 출력된다.
