탐욕 알고리즘 과 분할 알고리즘 - 2 차원 최근 점 문제 상세 설명

선언:
      그 동안 밤 에 실습 하 는 일 을 했 기 때문에 학습 진도 가 좀 느 려 졌 다.그러나 기 초 는 매우 중요 하기 때문에 기 초 를 내 려 서 는 안 되 고 평소에 시간 을 내 서 나 와 도 책 을 잘 읽 고 공부 해 야 한다.
이 책 은 현재 10 장 에 이 르 렀 고, 아직 두 장 이 있다.9 월말 에 이 책 을 꼭 끝내 야 겠 다 고 생각 했 는데 너무 많은 일이 벌 어 졌 지만 최선 을 다 해 앞으로 나 아가 야 한다.
나의 github:
제 가 실현 한 코드 는 모두 제 github 에 붙 어 있 습 니 다. 참관 을 환영 합 니 다.
https://github.com/YinWenAtBIT
소개:
1. 탐욕 알고리즘:
1. 정의:
탐욕 알고리즘 은 단계별 로 작업 하고 모든 단계 에서 현재 선택 할 수 있 는 가장 좋 은 선택 을 선택 하 며 미래의 결 과 를 고려 하지 않 습 니 다.매번 의 선택 은 부분 적 으로 가장 좋 고 마지막 결과 가 전체 국면 에서 가장 좋 기 를 기대 하 며 그의 전략 은 바로 그의 이름 의 이유 이다.
2. 탐욕 알고리즘 의 응용:
1. Dijkstra 알고리즘 은 그림 이론 에서 사용 하 는 가장 짧 은 경로 우선 알고리즘 은 탐욕 알고리즘 입 니 다. 현재 보 이 는 경 로 를 선택 할 때마다 가장 낮은 가중 변 을 가 집 니 다.탐욕 전략 을 쓴 것 이다.
2. Prim 알고리즘, 도 론 에서 최소 생 성 트 리.기 존 나무 와 연 결 된 최소 가중 변 을 선택 할 때마다 탐욕 전략 이다.
3. Kruskal 알고리즘 역시 최소 생 성 트 리 를 구하 고 탐욕 전략 을 사용 합 니 다.
이 몇 개의 알고리즘 을 나 는 이미 이전의 학습 에서 배 웠 고 모두 실현 해 냈 다.다음은 이 장 에서 언급 한 새로운 알고리즘 이다.
4. 스케줄 문제;
이 문 제 는 가장 짧 은 평균 완성 시간 을 얻 으 려 면 단일 프로세서 의 경우 가장 짧 은 작업 을 우선 호출 하면 된다 는 것 이다.
다 중 프로세서 에서 같은 전략 을 사용 하면 가장 짧 은 평균 완성 시간 을 얻 을 수 있 지만 마지막 완성 시간 이 가장 적 으 면 NP 완전 문제 가 되 고 이 문 제 는 더 이상 간단하게 처리 할 수 있 는 문제 가 아니다.이 문 제 는 어 려 운 것 은 너무 어렵 고 간단 한 것 은 너무 간단 하 며 인 코딩 이 실현 할 필요 가 없 으 며 직접 생략 했다.
5. Huffman 인 코딩
이 Huffman 인 코딩 은 말하자면 정말 역사가 있 습 니 다. 학부 의 데이터 구조 과정 에서 배 웠 습 니 다. 그러나 그 당시 에 저 는 이 알고리즘 만 외 웠 습 니 다. 이 알고리즘 을 어떻게 진정 으로 실현 하 는 지 에 대해 속수무책 이 었 습 니 다. 지난 학기 까지 저 는 이미지 처리 과정 을 배 웠 습 니 다. 그 중에서 matlab 를 사용 하여 Huffman 인 코딩 을 완성 하 라 고 요 구 했 습 니 다. 그 당시 에 저도 어떻게 해 야 할 지 몰 랐 습 니 다.다른 사람의 블 로 그 를 보 니 링크 로 이 루어 지 는 것 이 매우 좋 았 고 갑자기 링크 가 이렇게 사용 되 었 다 는 것 을 알 게 되 었 다.마지막 으로 그 숙제 는 다른 사람의 것 을 베 낀 것 입 니 다. 왜냐하면 저 는 matlab 에 링크 를 어떻게 쓰 는 지 모 르 기 때 문 입 니 다.
오늘 이 알고리즘 을 보면 트 리 를 만 드 는 것 에 불과 합 니 다. 먼저 모든 노드 를 우선 대기 열 에 넣 고 매번 두 개 를 꺼 내 새로운 노드 를 구성 한 다음 에 대기 열 에 넣 습 니 다. 시간 복잡 도 O (N * logN), N 은 인 코딩 이 필요 한 요 소 를 대표 합 니 다.또는 링크 를 직접 사용 하여 O (N ^ 2) 의 복잡 도 를 씁 니 다.책 에 위조 코드 를 제시 하지 않 았 으 니 나 도 필요 없다 고 생각한다.그 동안 의 훈련 을 통 해 나 는 이런 알고리즘 을 다시 쓰 는 것 도 기본적으로 시간 을 낭비 하 는 것 이 라 고 느 꼈 다.직접 손 으로 쓰 세 요. 이전에 작 성 된 우선 대기 열 이나 링크 를 사용 하면 20 분 이면 완 료 될 것 같 습 니 다.근 데 지금 은 20 분 도 이 위 에 쓰 고 싶 지 않 아 요.반년 동안 많이 늘 었 다 고 생각 합 니 다.
6. 포장 문제
이 문제 의 주요 난점 은 온라인 알고리즘 과 오프라인 계산 에 있다.
온라인 알고리즘 은 한 번 에 한 물품 의 크기 만 알 수 있 는 정 보 를 대표 하고 한 물품 의 포장 을 처리 해 야 다른 물품 의 정 보 를 알 수 있다.그래서 이런 상황 에서 최 적 화 는 달성 하기 어렵다. 이때 얻 을 수 있 는 최 적 화 는 4 / 3 배 와 최 적 화 된 상자 수 이다.그러나 이 한도 에 이 르 는 알고리즘 은 없다.
탐욕 전략 을 사용 하 는 두 가지 알고리즘: 첫 번 째 적합 법 과 최 적 적합 법 은 모두 17 / 10 최 적 상자 의 해 를 얻 을 수 있 습 니 다.이 알고리즘 을 실현 하려 면 링크 나 우선 대기 열 을 사용 할 수 있 습 니 다.
오프라인 시 모든 물품 의 크기 정 보 를 알 고 포장 을 하면 11 / 9 가 가장 좋다.여 기 는 증명 만 했 을 뿐 실행 가능 한 알고리즘 을 제시 하지 않 았 다.
3. 인 코딩 실현:
새로운 인 코딩 이 필요 한 곳 은 거의 없습니다. 허 프 맨 인 코딩 은 지금 저 에 게 너무 간단 합 니 다. 더 이상 시간 을 낭비 하지 않 아 도 됩 니 다.
2. 분할 알고리즘:
1. 정의: 분할 알고리즘 은 두 부분 으로 구성 된다.
분: 작은 문 제 를 재 귀적 으로 해결 합 니 다.
치: 하위 문제 의 해체 와 건설 원 문제 의 해체
전통 적 으로 본문 에 적어도 두 개의 재 귀 호출 규칙 을 포함 하고 있 는 것 을 분 치 알고리즘 이 라 고 하 는데 우 리 는 보통 서브 문 제 를 서로 교차 하지 않 는 다 (즉, 기본적으로 중첩 되 지 않 는 다).
2. 분할 알고리즘 의 응용:
1. 가장 큰 하위 서열, 이 문 제 는 서열 을 두 부분 으로 나 눌 수 있 고 가장 큰 서열 은 왼쪽 이나 오른쪽, 또는 중간 에 나타난다.시간 복잡 도 O (N * logN)
2. 정렬 과 빠 른 정렬 을 병합 하 는 것 은 모두 분리 사상, 알고리즘 복잡 도 O (N * logN) 를 사용 합 니 다.
3. 최근 점 문 제 는 똑 같이 분할 알고리즘 을 사용 하여 x 좌표 에 따라 정렬 된 점 을 좌우 두 부분 으로 나 눈 다음 에 가장 가 까 운 점 은 왼쪽, 오른쪽, 또는 중간 에 있 습 니 다.
3. 분할 알고리즘 의 운행 시간:
방정식 에 대한:
T(N) =aT(N/b)+O(N^k)
의 해:
T(N) = O(N^(lga/lgb))  a > b ^ k 시
        = O(N^(N^k*logN))  a = b ^ k 시
        = O(N^(N^k))  a
여기 서 원 방정식 은 처리 알고리즘 의 복잡 도 방정식 을 대표 한다. 그 중에서 a 는 분 단 된 하위 문제 의 갯 수 이 고 b 는 하위 문제 가 원 문제 의 크기 에 비해 역수 이 며 마지막 하 나 는 매번 재 귀 할 때마다 해 야 할 추가 작업 이다.
다음은 2 차원 최근 문 제 를 어떻게 구 하 는 지 상세 하 게 설명 할 것 이다.
3. 최근 질문:
1 문제 모델:
평면 에 n 개의 점 을 지정 하고 그 중의 한 쌍 의 점 을 찾 아 n 개의 점 의 모든 점 쌍 에서 이 점 이 맞 는 거 리 를 최소 화 합 니 다.엄 밀 히 말 하면 가장 가 까 운 점 은 한 쌍 보다 많 을 수 있다.간단하게 보기 위해 서 여 기 는 그 중의 한 쌍 만 찾 는 것 에 국한 된다.
2. 1 차원 최근 질문:
1 차원 의 최근 점 문제 에 대해 서 는 분 치 법 을 사용 할 수 있 습 니 다. 방법 은 정렬 한 후에 중간 에서 분리 되 고 최근 에 왼쪽, 오른쪽, 또는 좌우 두 부분 을 가로 지 를 수 있 습 니 다.1 차원 의 분 치 법 이 잘 실현 되 고 반복 잡 도 O (N * logN) 라 고 할 수 있 습 니 다.실제로 머 릿 속 에서 이 재 귀 과정 을 호출 하면 실제로 쉽게 발견 할 수 있다. 사실은 인접 한 두 점 에 대해 거 리 를 구하 고 가장 가 까 운 것 을 찾 는 것 이다.우 리 는 여기 서 동태 계획 의 사상 을 이용 하여 순 서 를 잘 배열 하 는 점 에 대해 인접 점 의 거 리 를 구하 고 정렬 의 복잡 도 O (N * logN) 를 구 할 수 있다.복잡 도가 같다.
3. 2 차원 최근 질문:
차원 이 높 아 지면 이전 처럼 인접 점 의 거 리 를 직접 구 할 수 없다. 이때 x 좌표 에 따라 정렬 하면 y 는 이때 순서대로 배열 되 지 않 기 때문이다.그럼 인접 점 의 의미 가 없 는 거 야.
그러면 이때 이 문 제 를 어떻게 간소화 합 니까? 방법 은 분 치 법 을 이용 하여 먼저 x 에 따라 순 서 를 매 긴 다음 에 왼쪽, 오른쪽, 중간 을 나 눕 니 다.이렇게 먼저 문 제 를 간소화 하 다.그 다음 에 모든 가장 간단 한 x 구역 에 대해 이 구역 안의 모든 점 의 거 리 를 계산 하기 때문에 가장 간단 할 때 계산 하 는 복잡 도 는 O (N) 이다.하지만 이때 결함 이 하나 있다.모든 점 이 고 르 게 분포 되 어 있다 면 이 알고리즘 은 복잡 도가 O (N * logN) 이지 만 모든 점 이 같은 일대 에 떨 어 지면 이 알고리즘 은 효력 을 잃 게 된다.만약 에 이때 Y 도 순서대로 배열 할 수 있다 면 비교 할 때 Y 의 '인접' 점 만 비교 할 수 있다.실제로 y 의 차 이 는 epsilon 보다 작은 점 이다.
알고리즘 프로 세 스:
예비 처리: 모든 점 을 x 좌 표를 병합 하여 정렬 하고 배열 X 에 넣 은 다음 X 배열 의 데 이 터 를 y 로 정렬 하여 배열 Y 에 넣 습 니 다.
1. 입력 한 X 배열 의 데 이 터 를 중간 에서 분리 하고 중간 점 을 경계 로 Y 배열 을 중간 x 에 따라 좌우 두 부분 으로 나 누 어 배열 Z 에 넣 고 왼쪽 x 는 중간 점 의 x 좌표 보다 작 으 며 오른쪽 은 반대 이다.
2. 좌우 배열 의 최 단 거 리 를 재 귀적 으로 구한다.
3. 좌우 배열 의 최소 거 리 를 취하 고 Z 중의 배열 을 합 친 다음 에 좌우 최소 거리 에 있 는 점 에 대해 거 리 를 구한다.
더욱 구체 적 인 해석 은 여러분 이 참고 하 실 수 있 습 니 다.http://blog.csdn.net/liufeng_king/article/details/8484284
4. 인 코딩 실현 2 차원 최근 문제:
우선 클래스 정의:

class PointX
{
public:
	PointX(){}
	bool operator 

여기 PointX 와 Pointy 가 다 무 거 워 졌어 요.
전처리:
예비 처리 후 직접 진정한 처리 함 수 를 호출 하여 처리 결 과 를 되 돌려 주 었 다.
4. 567913. 분할 처리 핵심:
이 부분 은 처리 코드 가 비교적 길 고 잘 모 르 기 때문에 문 제 를 반복 적 으로 생각 하 는 모델 이 있어 야 비교적 잘 알 수 있다.

void getNearDis(PointX X[], int N, PointX &a, PointX &b, float &d)
{
	MergeSort(X, N);

	PointY *Y = new PointY[N];

	for(int i=0; i

테스트 결과
여 기 는 2 차원 최근 점 문제 만 인 코딩 했 고 테스트 도 이 코드 만 테스트 했다.
1000 개의 무 작위 x, y 좌 표를 만 들 고 알고리즘 은 곧 답 을 얻 었 다.
요약:
이번에 2 차원 최근 문제 에 대한 학습 과 인 코딩 은 기본적으로 저 로 하여 금 분 치 알고리즘 에 대해 더욱 깊이 이해 하 게 했 습 니 다.좋 은 분 치 알고리즘 을 생각해 내 려 면 먼저 전체 분 치 의 절 차 를 잘 생각해 야 한다.알 고 나 서 인 코딩 을 하 는 것 이 훨씬 쉽다.