역 추적 법 - 업무 분배
질문 설명:
n 개의 업무 가 n 개인 에 게 분배 되 어 있다.제 i 개인 에 게 업무 j 를 분배 하 는 데 필요 한 비용 은 c [i] [j] 이다.하나의 알고리즘 을 시험 적 으로 설계 하여 가장 좋 은 업무 분배 방안 을 계산 하여 모든 사람 에 게 1 개의 서로 다른 업 무 를 분배 하고 총 비용 을 최소 화 시킨다.
문제 풀이 방향:
모든 사람 이 반드시 업 무 를 배정 해 야 하기 때문에 여기 서 2 차원 배열 c [i] [j] 를 만들어 i 호 노동자 가 j 호 업 무 를 완성 하 는 데 필요 한 비용 을 표시 할 수 있다.모든 노동자 가 배 치 될 때 까지 순환 을 정 하고 첫 번 째 노동자 부터 순환 분배 작업 을 시작한다.i 번 째 노동 자 를 위해 업 무 를 배정 할 때 모든 업무 가 이미 분배 되 었 는 지 순환 적 으로 검사 하고 없 으 면 i 번 노동자 에 게 배정 되 며 그렇지 않 으 면 다음 업 무 를 검사 합 니 다.1 차원 배열 x [j] 로 제 j 호 작업 이 할당 되 었 는 지, 할당 되 지 않 으 면 x [j] = 0, 그렇지 않 으 면 x [j] = 1 을 표시 할 수 있 습 니 다.역 추적 사상 을 이용 하여 노동자 순환 이 끝 난 후에 이전 노동자 로 돌아 가 이번 분 배 된 일 을 취소 하고 다음 일 을 분배 할 수 있 을 때 까지 분배 한다.이렇게 해서 첫 번 째 노동자 로 거 슬러 올 라 가면 모든 실행 가능 한 해 를 얻 을 수 있다.업무 분 배 를 검사 할 때 사실은 실행 가능 한 해 를 얻 었 다 고 판단 할 때 2 차원 배열 의 하 표 는 모두 다 르 고 2 하 표 는 똑 같이 다르다.
샘플 분석:
3 가지 업 무 를 정 하고 i 번 노동자 가 j 번 업 무 를 완성 하 는 비용 은 다음 과 같다.
10 2 3
2 3 4
3 4 5
하나의 변수 count 는 작업 비용 의 총 계 를 나타 내 고 초기 에는 0 이 며 변 수 는 i 번 근로 자 를 나타 내 며 초기 에는 1 이다.n 은 총 작업량 을 나타 내 는데 여 기 는 3 을 취한 다.c [i] [j] 는 i 호 노동자 가 j 호 업 무 를 완성 하 는 비용 을 나타 내 고 x [j] 는 j 호 업무 가 분배 되 었 는 지 여 부 를 나타 낸다.알고리즘 은 다음 과 같 습 니 다.
void
work
(
int
i
,
int
count
){
if
(
i
>
n
)
return
;
for
(
int
j
=
1
;
j
<=
n
;
j
++)
if
(
x
[
j
]
==
0
){
x
[
j
]
=
1
;
work
(
i
+
1
,
count
+
c
[
i
][
j
]);
x
[
j
]
=
0
;
}
}
그렇다면 여기 서 역 추적 법 을 사용 하 는 사상 은 먼저 분 배 된 일 은:
10:c[1][1] 3:c[2][2] 5:c[3][3] count=18;
이때 모든 노동자 의 분배 가 끝 난 후에 두 번 째 노동자 로 거 슬러 올 라 가 재배 치 한다.
10:c[1][1] 4:c[2][3] 4:c[3][2] count=18;
두 번 째 노동 자 는 n 으로 거 슬러 올 라 가 첫 번 째 노동자 의 재배 치 로 거 슬러 올 라 갔다.
2:c[1][2] 2:c[2][1] 5:c[3][3] count=9;
두 번 째 노동자 로 거 슬러 올 라 가 재배 치:
2:c[1][2] 4:c[2][3] 3:c[3][1] count=9;
다시 한 번 첫 번 째 노동자 로 거 슬러 올 라 가 재배 치:
3:c[1][3] 2:c[2][1] 4:c[3][2] count=9;
두 번 째 노동자 로 거 슬러 올 라 가 재배 치:
3:c[1][3] 3:c[2][2] 3:c[3][1] count=9;
이렇게 해서 모든 실행 가능 한 해 를 얻 었 다.한편, 우 리 는 가장 적은 비용, 즉 실행 가능 한 것 과 가장 작은 것 을 받 아야 하기 때문에 전체 변수 cost 를 다시 정의 하여 최종 총 비용 을 표시 해 야 한다. 초기 cost 는 c [i] [i] 의 합, 즉 대각선 비용 을 더 해 야 한다.모든 노동자 가 일 을 분배 할 때 count 와 cost 의 크기 를 비교 합 니 다. count 가 cost 보다 작 으 면 거 슬러 올 라 갈 때 가장 좋 은 해 를 찾 았 다 는 것 을 증명 합 니 다. 이때 count 를 cost 에 부 여 했 습 니 다.
여기까지 전체 알고리즘 은 차이 가 많 지 않 고 곧 끝 날 것 이 며 이미 최종 결 과 를 얻 을 수 있다.그러나 알고리즘 의 복잡 도 를 고려 하여 여기 에는 가지치기 최적화 작업 을 할 수 있다.즉, 국 지적 비용 변수 count 의 값 을 계산 할 때마다 count 가 cost 보다 크다 고 판단 하면 더 이상 분배 할 필요 가 없습니다. 이때 얻 은 해 는 반드시 최 적 화 된 것 이 아 닙 니 다.
테스트 코드:
#include
//
/*
3
10 2 3
2 3 4
3 4 5
*/
#include <iostream>
#include
using namespace std;
int table[21][21],n,best,r[21];
int compute(int k)
{
int temp=0,i;
for(i=1;i<=k;i++)
temp+=table[i][r[i]];
return temp;
}
void search(int k)
{
if(k==n)
{
int temp=compute(n);
if(temp<best)
best=temp;
return;
}
for(int i=k;i<=n;i++)
{
swap(r[i],r[k]);
if(compute(k) < best)
search(k+1);
swap(r[i],r[k]);
}
}
int main()
{
int i,j;
while(cin>>n,n)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cin>>table[i][j];
for(i=1;i<=n;i++)
r[i]=i;
best=INT_MAX;
search(1);
cout<<best<<endl;
}
return 0;
}
： jobAssignBacktrack.exe
+
output.txt
★ n n ， 。 i j cij ，cij>0,1≦i,j≦n。 ， n n ， 。
★ input.txt 。 1 n (1≤n≤100)。
n ， n ， 。
★ output.txt。
★ 5
50 87 62 56 92
43 22 98 57 36
1 5 97 96 43
58 62 27 73 27
60 71 38 71 95
144
： 1 ： 4
： 2 ： 2
： 3 ： 1
： 4 ： 5
： 5 ： 3
★ （ 、 、 ）：
●1. ：
job[i] i ， 1， ；、
assign(int k,unsigned int cost) cost ， 。
●2. ：
●2.1 ：
#define N 100 //N
int c[N][N]; //c[i][j] i j
unsigned int mincost = 65535; // ,
int task[N], // : i task[i]
bestSolution[N], // : i bestSolution[i]
job[N]; // ，1 ，0
int njob; // 、
：
void input(int& njob, int c[][N]); // 、 njob， c[][N]
// task,bestSolution,job, 、 njob， c[][N]
void initData(int* task, int* bestSolution, int* job, int& njob, int c[][N]);
void assign(int k,unsigned int cost); // k ，cost：
// ：mincost、
void outputResult(int minCost,int njob, int* bestSolution);
●2.2 ：
void assign(int k,unsigned int cost) // k ，cost：
{
int i;
if(k > njob && cost < mincost) // ，
{
mincost = cost;
for(i=1; i<=njob; i++)
bestSolution[i] = task[i];
}
else
{
for(i=1;i<=njob;i++)
{
if(job[i]==0 && cost+c[k][i])// ，job[i]==0
{
job[i] = 1; task[k] = i;
assign(k+1,cost+c[k][i]);
job[i] = 0; task[k] = 0;
}
}
}
}
●2.3
：O(n!)
：O(n)
， c[i][j] i j
좋은 웹페이지 즐겨찾기
