동적 계획 시리즈 중 하나 머리말: 한 문제 에서 나 온 알고리즘

http://iprai.hust.edu.cn/icl2002/algorithm/algorithm/technique/dynamic_programming/introduction.htm
머리말 - 한 문제 에서 끌 어 낸 알고리즘
다음 과 같은 문 제 를 고려 하 다.
[예 1] 최 단 경로 문제
현재 지도 한 장 이 있 는데 각 결점 은 도 시 를 대표 하고 두 결점 간 의 연결선 은 도 로 를 대표 하 며 온라인 숫자 는 도시 간 의 거 리 를 나타 낸다.그림 1 에서 보 듯 이 결점 A 에서 결점 E 까지 의 최 단 거 리 를 찾 아 보 자.
그림 1
                우 리 는 깊이 우선 검색 법 으로 이 문 제 를 해결 할 수 있 습 니 다. 이 문제 의 재 귀 식 은?
            
              그 중에서 v 와 인접 한 노드 의 집합 이 고 w (v, u) 는 v 에서 u 까지 의 길 이 를 나타 낸다.
구체 적 인 알고리즘 은 다음 과 같다.

function MinDistance(v):integer;
begin
 if v=E then return 0
  else
   begin
    min:=maxint;
    for           i do
     if v i   then 
      begin
          i    ;
        t:=v i   +MinDistance(i);
          i    ;        
        if t<min then min=t;
      end;  
   end;
end;

 
시작 할 때 모든 정점 에 접근 하지 않 았 음 을 표시 하고, MinDistance (A) 는 A 에서 E 까지 의 최 단 거 리 를 표시 합 니 다.
이 프로그램의 효율 은 어 떻 습 니까?우 리 는 매번 이미 방문 한 도 시 를 제외 하고 다른 도 시 를 방문 해 야 하기 때문에 시간 복잡 도 는 O (n!) 이다. 이것 은 '지수 급' 의 알고리즘 이다. 그러면 더 좋 은 알고리즘 이 있 을 까?
우선 이 알고리즘 을 살 펴 보 자.B1 에서 E 까지 의 최 단 거 리 를 구 할 때 먼저 C2 에서 E 까지 의 최 단 거 리 를 구한다.B2 에서 E 까지 의 최 단 거 리 를 구 할 때 C2 에서 E 까지 의 최 단 거 리 를 구 했다.C2 에서 E 까지 의 최 단 거 리 를 두 번 이나 구 했다 는 것 이다.마찬가지 로 C1, C2 에서 E 까지 최 단 거 리 를 구 하 는 과정 에서 D1 에서 E 까지 최 단 거리 도 두 번 구 한 것 으로 나 타 났 다.전체 프로그램 에 서 는 D1 에서 E 까지 최 단 거 리 를 네 번 이나 구 했다.해답 을 구 하 는 과정 에서 구 하 는 최 단 거 리 를 '사건 에 기록' 하면 서 수시로 호출 하면 이런 상황 을 피 할 수 있다.따라서 이 알고리즘 을 개선 할 수 있 습 니 다. 매번 구 하 는 v 에서 E 까지 의 최 단 거 리 를 기록 하고 알고리즘 에서 MinDistance (v) 를 재 귀적 으로 구 할 때 예전 에 MinDistance (v) 를 구 했 는 지 확인 합 니 다. 구 했 으 면 다시 구 할 필요 가 없습니다. 예전 의 기록 만 찾 으 면 됩 니 다.이렇게 하면 모든 점 이 n 개가 있 기 때문에 서로 다른 상태 수 는 n 개가 있 고 이 알고리즘 의 수량 급 은 O (n) 이다.
더 나 아가 이런 재 귀 를 전달 으로 바 꾸 면 재 귀 호출 비용 을 줄 일 수 있다.
그림 1 을 보 세 요. A 는 Bi 와 만 인접 하고 Bi 는 Ci 와 만 인접 하 며..........................................................이렇게 하면 우 리 는 원래 문제 의 해결 과정 을 4 단계 로 나 눌 수 있다. S1 = {A}, S2 = {B1, B2}, S3 = {C1, C2, C3, C4}, S4 = {D1, D2, D3}, Fk (u) 는 Sk 에서 점 u 에서 E 까지 의 최 단 거 리 를 나타 낸다.
그리고 경계 조건 이 있 습 니 다.
분명히 F1 (A), 즉 A 에서 E 까지 의 최 단 거 리 를 점차적으로 구 할 수 있다.이 알고리즘 의 복잡 도 는 O (n) 입 니 다. 모든 상태 총수 (노드 총수) 가 n 이기 때문에 모든 상태 에 한 번 만 옮 겨 다 니 고 프로그램 이 간결 합 니 다.
구체 적 인 알고리즘 은 다음 과 같다.

procedure DynamicProgramming;
 begin
  F5[E]:=0;
  for i:=4 downto 1 do
     for each u ∈Sk do
      begin
       Fk[u]:=   ;
       for each v∈Sk+1∩δ(u) do
         if Fk[u]>w(u,v)+Fk+1[v] then Fk[u]:=w(u,v)+Fk+1[v];
   end;
    F1[A]; 
 end;

 
이런 고 효율 알고리즘 은 바로 동적 기획 알고리즘 이다.
다음은 상술 한 두 알고리즘 의 구체 적 인 실현 이다.

#include <fstream>
ifstream fin("in.txt");
#define maxLength 20
#define maxPath 20
#define MAX 1000000
int matrix[maxLength][maxLength];//      
int minPath[maxPath];//              
int trace[maxLength];//       
int v_n;//    
int visited[maxLength];
int MinDistance_1(int v)
{
	if(v==v_n-1)
	{
		return 0;
	}
	int min=MAX,t,j;
	for(int i=v+1;i<=v_n-1;i++)//          i
	{
		if(!visited[i]&&matrix[v][i]!=0)//          i
		{
			visited[i]=true;
			t=matrix[v][i]+MinDistance_1(i);
			visited[i]=false;
			if(t<min)
				min=t;
		}
	}
	return min;
}
int MinDistance(int v)
{
	if(minPath[v]>0)//                       
		return minPath[v];
	if(v==v_n-1)
		return 0;//   
	int min=1000,t,j;
	for(int i=v+1;i<v_n;i++)
	{
		if(matrix[v][i]>0)
		{
			t=matrix[v][i]+MinDistance(i);
			if(min>t)
			{
				min=t;
				j=i;
			}
		}
	}
	minPath[v]=min;
	trace[v]=j;//trace[i]           
	return minPath[v];
}
int main()
{
	fin>>v_n;
	for(int i=0;i<v_n;i++)
	{
		for(int j=0;j<v_n;j++)
		{
			fin>>matrix[i][j];
			cout<<matrix[i][j]<<"-";
		}
		cout<<endl;
	}
	memset(visited,0,sizeof(int)*maxLength);
	memset(minPath,0,sizeof(int)*maxLength);
	memset(trace,0,sizeof(int)*maxLength);
	int minD=MinDistance_1(0);

	cout<<"     :"<<minD<<endl;
	return 0;
}