욕심 산법 기본 개념 과 활동 선택 문제 의 풀이

1. 개념
   욕심 알고리즘 (Greedy Algorithm): 모든 단계 에서 현재 보기에 가장 좋 은 선택 입 니 다.즉, 그것 은 항상 국 지적 으로 가장 좋 은 선택 을 하고 이런 선택 이 전체적인 최 적 화 를 얻 기 를 바란다.   욕심 산법 이 반드시 최 적 화 를 얻 을 수 있다 는 것 은 아니 지만 많은 문제 에 대해 서 는 확실히 최 적 화 를 얻 을 수 있다.
   욕심 전략 을 이용 하여 디자인 한 알고리즘 은 최소 생 성 트 리, 단원 점 최 단 경로 의 Dijkstra, 0 - 1 점수 가방 문제, 활동 선택 문제 가 있 습 니 다.
2. 욕심 산법 의 원리
     욕심 산법 은 일련의 선택 을 통 해 문제 의 최 적 화 를 구 합 니 다. 모든 결정 점 에서 욕심 선택 은 현재 보 이 는 가장 좋 은 선택 입 니 다.이런 계발 식 전략 은 항상 가장 좋 은 해 를 찾 을 수 있다 고 보장 하 지 는 않 지만 일부 문제 에 대해 확실히 효과 가 있다. 예 를 들 어 활동 선택 문제 등 이다.
    욕심 산법 을 사용 할 수 있 는 문 제 는 두 가지 성질 을 가 져 야 한다. 1. 욕심 선택 성격 은 국부 적 인 최 적 화 를 통 해 전체적인 최 적 화 를 구성 할 수 있다.2. 가장 좋 은 서브 구조, 한 문제 의 가장 좋 은 해 제 는 서브 문 제 를 포함 하 는 가장 좋 은 해 제 를 포함한다.
3. 이벤트 선택 문제
    경쟁 공유 자원 의 여러 활동 을 호출 하 는 문 제 는 서로 호 환 되 는 가장 큰 활동 집합 을 선택 하 는 것 이 목표 이다.주의: 요구 하 는 '하나 가 가장 크다' 는 것 은 모든 것 이 가장 큰 것 이 아니 라 욕심 산법 이 문제 의 가장 좋 은 해 를 얻 는 것 중 하나 이 고 모든 것 이 아니 라 문제 의 가장 좋 은 해 를 얻 는 것 이 유일한 것 이 아니 라 는 것 을 설명 합 니 다.또 '최대' 는 도 출 된 활동 집합 에 포 함 된 활동 개 수 를 가장 많이 나타 낸다.
     모든 활동 i 는 시작 시간 과 끝 시간 이 있 습 니 다.실현 의 원 리 는 우리 가 가장 먼저 끝 난 활동 을 반복 적 으로 선택 하고 이 활동 과 호 환 되 는 활동 을 보류 하 며 이 과정 을 반복 하여 더 이상 남 은 활동 이 없 을 때 까지 하 는 것 이다.
    재 귀적 인 방식 으로 실 현 될 때 입력 한 네 개의 매개 변수 ：
 @param s 는 종료 시간 에 정렬 된 활동 순서 에 대응 하 는 활동 시작 시간 집합 에 대응 합 니 다. @param f  이벤트 가 끝 난 시간 은 이벤트 가 끝 난 시간 에 따라 정렬 되 었 습 니 다. @param k 는 해 제 를 요구 하 는 하위 문 제 를 지적 했다. @param n 은 활동 의 총 개 수 를 가리킨다.
     이 방법 을 호출 하기 전에 초기 화 알고리즘 을 더욱 편리 하 게 하기 위해 가상 활동 번 호 를 0 (시작 과 끝 시간 은 0) 으로 추가 합 니 다. 이렇게 원래 문 제 를 풀 때 k 는 0 으로 시작 합 니 다. 즉, 진실 한 모든 활동 의 해 를 구 합 니 다.
   실 현 된 자바 코드 는 다음 과 같 습 니 다:

/**
	 *          ,    ：                   k             ，      ，          。
	 *         ，           ，           0（         0）.           k   0，    
	 *          。
	 * 
	 * @param s                          。
	 * @param f        ，                。
	 * @param k          Sk(Sk    k            )。
	 * @param n         。
	 * @return     Sk             。
	 */
	public ArrayList<Integer> recurActSelector(int[] s,int[] f,int k,int n){
		ArrayList<Integer> list = new ArrayList<Integer>();
		int m = k+1;
		/*           k             */
		while(m<=n && s[m]<f[k]){
			m++;
		}
		if(m<=n){
			list.add(m);
			/*         */
			list.addAll(recurActSelector(s,f,m,n));
			return list;
		}else{
			return list;
		}
	}

위의 재 귀 실현 과정 을 보면 꼬리 재 귀 의 형식 으로 꼬리 재 귀 방식 에 대해 교체 실현 으로 전환 할 수 있다.

/**
	 *          ,    ：                                    ，      ，          。
	 * @param s                          。
	 * @param f        ，                。
	 * @return                      。
	 */
	public ArrayList<Integer> iterActSelector(int[] s,int[] f){
		ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(0);//           
		int k = 0;//k           
		int size = s.length;
		for(int i=1;i<size;i++){
			if(s[i]>=f[k]){//         k       
				list.add(i);
				k=i;
			}
		}
		return list;
	}

특히 재 귀적 실현 을 호출 할 때 처음에 가상 번 호 를 0 (시작 과 끝 시간 은 0) 으로 추가 하 는 활동 에 주의해 야 한다.

public static void main(String[] args){
		int[] s = {0,1,3,0,5,3,5,6,8,8,2,12};
		int[] f = {0,4,5,6,7,9,9,10,11,12,14,16};
		ActivitySelector test = new ActivitySelector();
		ArrayList<Integer> list1 = test.recurActSelector(s, f, 0, 11);
		System.out.println("list1 = "+list1);
		
		int[] s1 = {1,3,0,5,3,5,6,8,8,2,12};
		int[] f1 = {4,5,6,7,9,9,10,11,12,14,16};
		ArrayList<Integer> list2 = test.iterActSelector(s1, f1);
		System.out.println("list2 = "+list2);
		
	}