외판원 문제 C++ - oepan-won munje C++

• 상세정보
• 자료후기 (1)
• 자료문의 (0)
• 판매자정보

소개글

정말 보기 힘든 자료 일거라고 생각합니다.
말그대로 외판원 경로 구하기 프로그램이구요.
C로 구현하였습니다.
경로는 파일로 읽어와서 데이터를 처리하였구요..
많은 도움이 되시길 바랍니다.

본문내용

//=================================================//
// 파일명 : Sale_Report.cpp(소스), sales.txt(배열) //
//=================================================//

#include "stdafx.h"
#include <stdlib.h>
#include <math.h>
#include <string>

#define N 10 //정점의 수..
#define M 1024 //부분집합의 수
#define VS 1 //시작경로
#define VSP (int)pow(2,VS-1)

int W[N][N]; //인접행렬 입력값
int D[N][M]; //최단경로 저장배열
int P[N][M]; //P[Vi][A] = D[Vi][A]의 최단경로로 갈때 처음가는 원소
int set[M]; //각 부분집합이며, 원소갯수를 저장한다.

void setCount();
int travel();
void path(int,int);
void mininum(int,int);

int main(int argc, char* argv[])
{
static char *inFile = "sales.txt";//읽을 화일명
char buffer[1024];
char bb[1024];

FILE *fp;
fp = fopen(inFile, "r");
if(!fp){
printf("읽을 파일이 없습니다.\n");
fclose(fp);
return-1;
}
else{
for(int i=0; i<10; i++){
for(int j=0; j<10; j++){
fread( buffer, sizeof( char ), 4, fp); //처음 4자리 불러오기
fread( bb, sizeof( char ), 1, fp); //"," 불러오기
W[i][j] = atoi(buffer); //정수로 변환하여 배열에 넣기
}fread( bb, sizeof( char ), 1, fp); //"\n" 불러오기
}
}
fclose(fp); //파일 닫기

if(travel()>=1000)
printf("불가능한 경로입니다.");
else
{
printf("파일에서 불러온 배열은 다음과 같습니다.\n\n");
for(int i=0; i<10; i++){
for(int j=0; j<10; j++){
printf("%d ",W[i][j]); //배열값 출력
}printf("\n");
}
printf("\n-------------------------------------------------\n");
printf("외판원 경로의 최소비용은 %d 입니다.\n\n",travel()); //최소비용 출력
printf("외판원의 최소비용 경로는 -----♥\n"); //경로출력
path(VS-1,M-1-VSP);
}
return 0;
}

int travel() //외판원 경로구하기
{

압축파일 내 파일목록

ReadMe.txt
result.JPG
sales.txt
Sale_Report.cpp
Sale_Report.dsp
Sale_Report.dsw
Sale_Report.ncb
Sale_Report.opt
Sale_Report.plg
StdAfx.cpp
StdAfx.h
Debug/sales.txt
Debug/Sale_Report.exe
Debug/Sale_Report.ilk
Debug/Sale_Report.obj
Debug/Sale_Report.pch
Debug/Sale_Report.pdb
Debug/StdAfx.obj
Debug/vc60.idb
Debug/vc60.pdb

태그

이 자료와 함께 구매한 자료

백준 2098번: 외판원 순회 [Gold 1]
//www.acmicpc.net/problem/2098

2098번: 외판원 순회

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j

www.acmicpc.net

문제 풀이

• 이 문제는 TSP (Traveling Salesperson Problem) 알고리즘 문제로 그래프의 모든 노드를 한 바퀴 순회하는 최적의 경로를 찾아내는 알고리즘입니다.
• 모든 노드를 순회하는 최적의 경로는 완전 탐색으로도 해결이 가능하지만 노드의 개수가 10개가 넘어간다면 시간 초과에 걸리게 됩니다. 이 문제는 노드의 최대 개수가 16개이기 때문에 Memoization을 적용해야 합니다.

int memo[16][1<<16]; // 현재 노드, 노드 방문 상태

• 문제에는 "어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로"라고 적혀있기 때문에 각 마을에서 모두 출발해 보면서 경로를 찾아야 할 것 같지만 실제로는 한 마을에서만 순회 경로를 찾게 되면 모두 같은 경로이기 때문에 모든 마을에서 출발할 필요가 없습니다!

코드 (c++)

#include <cstdio> #include <algorithm> using namespace std; const int INF = 1e9; int N, END; int arr[16][16]; int memo[16][1<<16]; int tsp(int city, int visited) { // 마지막 노드에서 출발 지점으로 이동 if(visited == END) return arr[city][0]; // 현재 상태를 이미 계산한 값이 있다면 사용 if(memo[city][visited] != INF) return memo[city][visited]; // 값이 없다면 계산 for(int i=0; i<N; ++i) { if(visited & (1 << i)) continue; if(arr[city][i]) { int res = tsp(i, visited | (1 << i)); if(res) memo[city][visited] = min(memo[city][visited], res + arr[city][i]); } } return memo[city][visited]; } int main() { scanf("%d", &N); END = (1 << N) - 1; for(int i=0; i<N; ++i) { for(int j=0; j<N; ++j) { scanf("%d", &arr[i][j]); } for(int j=0; j<(1<<N); ++j) { memo[i][j] = INF; } } int ans = tsp(0, 1); printf("%d\n", ans); return 0; }

실행 결과

코드 (Java)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; // 백준 2098: 외판원순회 // TSP 알고리즘 public class 외판원순회 { static final int INF = (int) 1e9; static int[][] arr = new int[16][16]; static int[][] memo = new int[16][1<<16]; static int N, END; public static int tsp(int city, int visited) { if(visited == END) return arr[city][0]; if(memo[city][visited] != INF) return memo[city][visited]; for(int i=0; i<N; ++i) { if(arr[city][i] != 0 && (visited & (1 << i)) == 0) { int res = tsp(i, visited | (1 << i)); if(res > 0) memo[city][visited] = Math.min(memo[city][visited], res + arr[city][i]); } } return memo[city][visited]; } public static void solution() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); END = (1 << N) - 1; StringTokenizer st; for(int i=0; i<N; ++i) { st = new StringTokenizer(br.readLine()); for(int j=0; j<N; ++j) { arr[i][j] = Integer.parseInt(st.nextToken()); } Arrays.fill(memo[i], INF); } System.out.println(tsp(0, 1)); } }

실행 결과