상용 알고리즘 의 위조 코드
18767 단어 PAT 알고리즘
분 (Divide) 은 n 규모 의 문 제 를 k 개의 규모 가 작은 하위 문제 치료 (Conquer) 로 분해 하여 k 개의 키 문 제 를 각각 해결 한 다음 에 각 키 문제 의 해 제 를 합 쳐 원래 의 문 제 를 해결 하 는 분해 전략 은 아래 에서 위로 해결 하고 합병 하 는 것 이다.
Begin
a[], x, i， j
i->0,j->a.length
1.while(i<=j) :
1.1 m =(i+j)/2;
1.2 if(x==a[m]) return m;
1.3 if(x<a[m]) j=m-1; else i=m+1;
2.return -1;
End
2. 동적 계획
동적 계획 알고리즘 은 분 치 법 과 유사 하 다. 그 기본 사상 도 해결 해 야 할 문 제 를 몇 개의 키 문제 로 분해 하고 서브 문제 가 서로 독립 되 지 않 을 때 일부 상황 에서 서로 다른 서브 문제 의 수량 은 여러 가지 등급 만 있다. 즉, 분 치 법 으로 해결 할 때 일부 서브 문 제 는 반복 적 으로 계산 되 었 다.
/*0-1 */
int knapSack(int W, int wt[], int val[], int n)
{
if (n == 0 || W == 0)
return 0;
if (wt[n-1] > W)
return knapSack(W, wt, val, n-1);
else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
knapSack(W, wt, val, n-1));
}
3. 욕심 산법
말 그대로 욕심 산법 은 항상 현재 로 서 는 가장 좋 은 선택 을 한다.즉, 욕심 산법 은 전체적인 최 적 화 를 고려 하지 않 고 특정한 의미 에서 국 지적 으로 최 적 화 된 선택 일 뿐 입 니 다. 물론 욕심 산법 이 얻 은 최종 결과 도 전체적으로 가장 좋 기 를 바 랍 니 다.욕심 산법 은 모든 문제 에 대해 전체적인 최 적 화 를 얻 을 수 는 없 지만 많은 문제 에 대해 서 는 전체적인 최 적 화 를 이 룰 수 있다.예 를 들 어 단원 최 단 경로 문제, 최소 생 성 트 리 문제 등 일부 상황 에서 욕심 산법 이 전체적인 최 적 화 를 얻 지 못 하 더 라 도 그 최종 결 과 는 최 적 화 된 근사치 이다.
욕심 산법 은 고려 해 야 할 부분 이다.
/*dijkstra */
Begin
1 s={1},v={2...n},dist[i]=c[i][j];
2
2.1 u=min{dist[i][j]|i v}
2.2 s=sU{v},v=v-{u};
2.3 v i
if(dist[u]+c[u][i]<dist[i][j]) dist[i]=dist[u]+c[u][j]
3. dist
End
4. 역 추적 법
역 추적 법의 기본 적 인 방법 은 검색 이나 질서정연 하 게 조직 되 어 불필요 한 검색 을 피 할 수 있 는 궁 거 식 검색 법 이다.이런 방법 은 조합 수가 상당히 큰 문 제 를 푸 는 데 적용 된다.역 추적 법 은 문제 의 해 공간 트 리 에서 깊이 우선 전략 에 따라 뿌리 노드 에서 공간 트 리 를 검색 합 니 다.알고리즘 은 공간 트 리 의 임 의 한 점 을 검색 할 때 이 노드 에 문제 의 해 가 포함 되 어 있 는 지 여 부 를 판단 합 니 다.만약 에 포함 되 지 않 는 다 면 이 결점 이 뿌리 인 나무 에 대한 검색 을 뛰 어 넘 고 조상 들 의 결점 을 거 슬러 올라간다.그렇지 않 으 면 이 하위 트 리 에 들 어가 깊이 우선 정책 에 따라 계속 검색 합 니 다.
기본 사상
/*0-1 */
Begin
Backtrakc(i) i
1. if(i>n) bestp,
2. if cw+w[i]<c,
2.1 cw+=w[i]; cp+=v[i];
2.2 Backtrack(i+1);
2.3 ,cw-=w[i],cp=v[i]];
3. Bound(i+1)>bestp, , Backtrack(i+1)
End
5. 분기 한계 법
구 해 목표: 역 추적 법의 구 해 목 표 는 공간 트 리 에서 제약 조건 을 만족 시 키 는 모든 해 를 찾 는 것 이 고 분기 한계 법의 구 해 목 표 는 제약 조건 을 만족 시 키 는 해 를 찾 거나 제약 조건 을 만족 시 키 는 해 에서 특정한 의미 에서 가장 좋 은 검색 방식 의 차 이 를 찾 는 것 이다. 역 추적 법 은 깊이 우선 의 방식 으로 공간 트 리 를 검색 하 는 것 이다.한편, 분기 한계 법칙 은 너비 우선 또는 최소 소모 우선 방식 으로 공간 트 리 검색 방식 이 다 릅 니 다. 역 추적 법 은 깊이 우선 방식 으로 공간 트 리 를 검색 하고 분기 한계 법칙 은 너비 우선 또는 최소 소모 우선 방식 으로 공간 트 리 를 검색 합 니 다.
기본 사상
분지 한계 법 에서 모든 활 결점 은 단지 한 번 의 기회 만 이 확장 결점 이 된다.활성 점 이 확장 점 이 되면 모든 아들 의 결점 이 한꺼번에 생 긴 다.이 아들 들 의 결점 에서 풀 수 없 거나 가장 잘 풀 리 지 않 는 아들 의 결점 이 버 려 졌 고 나머지 아들 의 결점 은 활성 점 표 에 들 어간 후에 활성 점 표 에서 다음 결점 을 떼 어 내 현재 확장 점 이 되 었 으 며 상기 결점 확장 과정 을 반복 했다.이 과정 은 필요 한 해 나 활성 점 표를 찾 을 때 까지 계속 되 었 다.
/*0-1 */
/* */
Begin
1 down; up;
2. ；
3. for(i=l;i<=n;i++)
x[i]= 0;
4. k=l;i=0; // k ，i k-1
5. while (k>=l)
5.1 x[k]=l;
5.2 while (x[k]<=n)
5.2.1 k x[k] ，
5.2.1.1 lb;
5.2.1.2 lb<=up, i，<x[k]，k>lb ;
5.2.2 x[k]=x[k]+l;
5.3 k==n lb ,
;
5.4 ， k==n lb ,
5.4.1 up= lb ；
5.4.2 ；
5.5 i= lb x k] ；
5.6 k= lb k ;k++;
End
좋은 웹페이지 즐겨찾기
