순회판매원 문제 자바로 구현하기

순회판매원 문제 알고리즘은 헤밀턴 순회의 응용문제입니다. 

 

* 헤밀턴 순회란? 

출발점으로부터 모든 정점을 한번씩만 지나서 출발점으로 돌아오는 순회를 의미합니다.

 

순회판매원 문제는 판매원이 각 도시를 한 번만 방문하여 출발점으로 되돌아오는 최소 경로를 구해야합니다.

이 최소의 경로가 "최적"의 경로라고 할 수 있는데 일반적인 해결 알고리즘이 존재하지 않습니다. 

이 때, "최근접 이웃 방법"을 통하여 최소값은 아니더라도 근사값을 구할 수 있습니다. 

 

본 코드는 최근접 이웃 방법 알고리즘을 이용하여 모든 정점에서 최소값의 근사값을 구한 후 그 중 최소값을 출력합니다. 

위의 그림의 최소경로는 2->3->1->4->2이며 그값은 75입니다.

 

필요한 변수

- 정점의 개수를 나타내는 n

- 정점사이의 경로값을 나타내는 이차원 배열 c

- 모든 정점들의 집합인 all, v <List>

- 최소경로를 나타내는 minW <int>

- 최소경로를 가지는 정점을 담는 집합 p <List>

 

핵심

모든 정점의 경우를 다 고려한 코드이며, all의 각각의 정점을 통해 접근합니다. 

이 때, 사용되는 v는 all의 각 원소의 최소경로를 구하기 위해 사용되는 임시 집합입니다. 

각 경로의 최소값을 가지는 정점을 p집합에 더해가면서 v에서는 그 정점을 지웁니다.

v집합이 공집합이 될 경우 작업을 종료하고 최종경로를 구합니다. 

그 값을 최소경로의 값인 minW와 비교하여 minW보다 작으면 minW의 값을 변경합니다. 

 

출력

최소경로를 출력합니다.

 

코드

public static void main(String[] args){

int n = 4;

 

int[][] c = {

, , ,

,

};

 

ArrayList<Integer> all = new ArrayList<Integer>();

for(int i=1; i<=n; i++)

 

int minW = Integer.MAX_VALUE;

 

for(int j=0; j<all.size(); j++){

ArrayList<Integer> v = new ArrayList<Integer>();

v.addAll(all);

 

int w = 0;

Integer v1 = all.get(j);

Integer _v = v1;

v.remove(_v);

 

ArrayList<Integer> p = new ArrayList<Integer>();

p.add(v1);

 

while(v.size()>0){

Integer mIdx = 0;

Integer min = 100000;

for(Integer i : v){

if(c[_v][i]==0)

if(min > c[_v][i]){

mIdx = i;

min = c[_v][i];

}

}

 

p.add(mIdx);

v.remove(mIdx);

w += min;

_v = mIdx;

}

 

w += c[_v][v1];

System.out.println("경로 : "+p);

System.out.println("최소경로 : "+w);

if(minW > w)

}

 

System.out.println("최소 경로 : " + minW);

}

 

 

 

결과

 

 

참고 문헌: DISCRETE MATHEMATICS 이산수학 Express - 7장 그래프 응용, 순회판매원 문제 알고리즘