[컴퓨터] 외판원 문제(동적계획법) 소스

소개글

외판원 문제를 동적계획으로 푼 소스입니다.

목차

총 10파일

본문내용

import java.math.*;

class Travel
{
private Graph g;
private int[][] P;
public int[][] D;
private BigInteger A;
private BigInteger one;

public Travel(Graph graph)
{
g= graph;
P = new int[g.getSize()][(int)Math.pow(2,g.getSize()-1)];
D = new int[g.getSize()][(int)Math.pow(2,g.getSize()-1)];
one = new BigInteger("1",2);
}


public int travel()
{
int i,j,k,n=9;

for(i=1;i<=n;i++)D[i][0] = g.getValue(i,0);

for(int count=1;count<=8;count++)
{
A = new BigInteger("0",2);
for(k=0;k<(int)Math.pow(2,9);k++) {
if(A.bitCount()==count) {
for(i=1;i<=9;i++){
if(!A.testBit(i-1)){
int min=-1;
for(j=0;j<9;j++){
if(A.testBit(j)){
int temp=0;
if(min==-1){
min=g.getValue(i,j+1)+D[j+1][(A.flipBit(j)).intValue()];
P[i][A.intValue()]=j+1;
}else{
temp=g.getValue(i,j+1)+D[j+1][(A.flipBit(j)).intValue()];
if(temp<min){
min=temp;
P[i][A.intValue()]=j+1;
}

참고 자료

없음

압축파일 내 파일목록

Graph.class
Graph.java
output.txt
Test.class
Test.java
Travel.class
Travel.java
Vertex.class
Vertex.java
외판원문제(동적).kawa