검색어 입력폼

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

등록일 2004.04.11 파일확장자압축파일 (zip) | 1페이지 | 가격 3,000원

소개글

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

목차

총 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;
}
다운로드 맨위로