예시를 사용한 탐욕 알고리즘: 정의, 방법 및 접근 방식
사라 첸
그리디 알고리즘이란 무엇입니까?
In 그리디 알고리즘 리소스 집합은 특정 실행 단계에서 해당 리소스의 최대 즉시 가용성을 기준으로 반복적으로 나뉩니다.
욕심 많은 접근 방식을 기반으로 문제를 해결하려면 두 단계가 있습니다.
- 항목 목록 스캔 중
- 최적화
이러한 단계는 배열 분할 과정에서 Greedy 알고리즘 튜토리얼에서 병렬로 다룹니다.
그리디 접근 방식을 이해하려면 재귀 및 컨텍스트 전환에 대한 실무 지식이 필요합니다. 이는 코드 추적 방법을 이해하는 데 도움이 됩니다. 당신은 자신의 필요충분 진술의 관점에서 탐욕 패러다임을 정의할 수 있습니다.
두 가지 조건이 탐욕 패러다임을 정의합니다.
- 각 단계별 해결책은 가장 수용 가능한 해결책을 향해 문제를 구조화해야 합니다.
- 문제의 구조화가 유한한 수의 욕심 많은 단계에서 중단될 수 있다면 충분합니다.
이론화를 계속하면서 Greedy 검색 접근 방식과 관련된 역사를 설명하겠습니다.
그리디의 역사 Algorithms
탐욕 알고리즘의 중요한 랜드마크는 다음과 같습니다.
- 탐욕 알고리즘은 1950년대에 많은 그래프 워크 알고리즘을 위해 개념화되었습니다.
- Esdger Djikstra는 최소 스패닝 트리를 생성하는 알고리즘을 개념화했습니다. 그는 네덜란드 수도 암스테르담 내 노선 범위를 단축하는 것을 목표로 삼았습니다.
- 같은 XNUMX년 동안 Prim과 Kruskal은 가중치가 부여된 경로를 따라 경로 비용을 최소화하는 최적화 전략을 달성했습니다.
- 70년대에 미국의 학자 콜먼, 리베스트, 슈타인은 그들의 고전적인 알고리즘 입문서에서 탐욕적 솔루션의 재귀적 부분 구조화를 제안했습니다.
- Greedy 검색 패러다임은 2005년 NIST 기록에 다른 유형의 최적화 전략으로 등록되었습니다.
- 현재까지 OSPF(open-shortest-path-first) 및 기타 여러 네트워크 패킷 스위칭 프로토콜과 같이 웹을 실행하는 프로토콜은 그리디 전략을 사용하여 네트워크에서 소요되는 시간을 최소화합니다.
탐욕스러운 전략과 결정
가장 쉬운 형태의 논리는 "욕심쟁이" 또는 "욕심 없음"으로 압축되었습니다. 이러한 진술은 각 알고리즘 단계를 발전시키기 위해 취한 접근 방식에 의해 정의되었습니다.
예를 들어, Djikstra의 알고리즘은 비용 함수를 계산하여 인터넷의 호스트를 식별하는 단계적 탐욕 전략을 활용했습니다. 비용 함수에서 반환된 값은 다음 경로가 "탐욕적"인지 "비탐욕적"인지를 결정했습니다.
간단히 말해서, 어떤 단계에서든 국소적으로 탐욕스럽지 않은 단계를 수행하면 알고리즘은 탐욕을 중단합니다. 탐욕 문제는 더 이상 탐욕의 범위가 없어 중단됩니다.
그리디 알고리즘의 특징
Greedy 알고리즘의 중요한 특징은 다음과 같습니다.
- 비용이나 가치 귀속이 포함된 정렬된 리소스 목록이 있습니다. 이는 시스템의 제약 조건을 수량화합니다.
- 제약 조건이 적용되는 시간 동안 최대량의 자원을 사용하게 됩니다.
- 예를 들어, 활동 일정 문제에서 자원 비용은 시간 단위이며, 활동은 직렬 순서대로 수행되어야 합니다.
욕심 많은 접근 방식을 사용하는 이유는 무엇입니까?
탐욕적 접근법을 사용하는 이유는 다음과 같습니다.
- 탐욕적 접근 방식에는 몇 가지 장단점이 있으므로 최적화에 적합할 수 있습니다.
- 한 가지 중요한 이유는 가장 실현 가능한 솔루션을 즉시 달성하기 위한 것입니다. 활동 선택 문제(아래 설명)에서 현재 활동을 완료하기 전에 더 많은 활동을 수행할 수 있으면 이러한 활동을 동일한 시간 내에 수행할 수 있습니다.
- 또 다른 이유는 모든 솔루션을 결합할 필요 없이 조건에 따라 문제를 반복적으로 나누기 때문입니다.
- 활동 선택 문제에서 "재귀적 분할" 단계는 항목 목록을 한 번만 스캔하고 특정 활동을 고려하여 달성됩니다.
활동 선택 문제를 해결하는 방법
활동 일정의 예에는 모든 활동에 대한 "시작" 및 "종료" 시간이 있습니다. 각 활동은 참조용으로 숫자로 색인화됩니다. 두 가지 활동 카테고리가 있습니다.
- 고려된 활동: 하나 이상의 남은 활동을 수행할 수 있는 능력을 분석하는 기준이 되는 활동입니다.
- 남은 활동: 고려되는 활동보다 앞서 하나 이상의 인덱스에 있는 활동.
총 기간은 활동 수행 비용을 나타냅니다. 즉, (완료 – 시작)은 활동 비용으로 지속 시간을 제공합니다.
그리디 범위는 고려된 활동 시간에 수행할 수 있는 남은 활동의 수임을 배우게 됩니다.
ArchiGreedy 접근법의 강의
1 단계) 고려되는 인덱스로 인덱스 0부터 시작하여 활동 비용 목록을 스캔합니다.
2 단계) 고려된 활동이 끝나기 전에 더 많은 활동을 끝낼 수 있다면, 남은 활동 하나 이상을 검색하기 시작합니다.
3 단계) 더 이상 남은 활동이 없으면 현재 남은 활동이 다음으로 고려되는 활동이 됩니다. 새로 고려된 활동으로 1단계와 2단계를 반복합니다. 남은 활동이 없으면 4단계로 이동합니다.
4단계) 고려된 인덱스의 합집합을 반환합니다. 이는 처리량을 최대화하는 데 사용되는 활동 지수입니다.
코드 설명
#include<iostream> #include<stdio.h> #include<stdlib.h> #define MAX_ACTIVITIES 12
코드 설명:
- 포함된 헤더 파일/클래스
- 사용자가 제공하는 최대 활동 수입니다.
using namespace std;
class TIME
{
public:
int hours;
public: TIME()
{
hours = 0;
}
};
코드 설명:
- 스트리밍 작업을 위한 네임스페이스입니다.
- TIME에 대한 클래스 정의
- XNUMX시간 타임스탬프.
- TIME 기본 생성자
- 시간 변수.
class Activity
{
public:
int index;
TIME start;
TIME finish;
public: Activity()
{
start = finish = TIME();
}
};
코드 설명:
- 활동의 클래스 정의
- 기간을 정의하는 타임스탬프
- 모든 타임스탬프는 기본 생성자에서 0으로 초기화됩니다.
class Scheduler
{
public:
int considered_index,init_index;
Activity *current_activities = new Activity[MAX_ACTIVITIES];
Activity *scheduled;
코드 설명:
- 스케줄러 클래스 정의의 1부.
- 고려된 인덱스는 스캔의 시작점입니다. 정렬.
- 초기화 인덱스는 임의의 타임스탬프를 할당하는 데 사용됩니다.
- 활동 객체의 배열은 new 연산자를 사용하여 동적으로 할당됩니다.
- 예약된 포인터는 탐욕의 현재 기본 위치를 정의합니다.
Scheduler()
{
considered_index = 0;
scheduled = NULL;
...
...
코드 설명:
- 스케줄러 생성자 – 스케줄러 클래스 정의의 2부.
- 고려된 인덱스는 현재 스캔의 현재 시작을 정의합니다.
- 현재 그리디 범위는 처음에는 정의되지 않았습니다.
for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++)
{
current_activities[init_index].start.hours =
rand() % 12;
current_activities[init_index].finish.hours =
current_activities[init_index].start.hours +
(rand() % 2);
printf("\nSTART:%d END %d\n",
current_activities[init_index].start.hours
,current_activities[init_index].finish.hours);
}
…
…
코드 설명:
- 현재 예약된 각 활동의 시작 시간과 종료 시간을 초기화하는 for 루프입니다.
- 시작 시간 초기화.
- 종료 시간은 항상 시작 시간 이후 또는 정확히 시작 시간에 초기화됩니다.
- 할당된 기간을 인쇄하는 디버그 문입니다.
public: Activity * activity_select(int); };
코드 설명:
- 파트 4 - 스케줄러 클래스 정의의 마지막 부분입니다.
- 활동 선택 기능은 시작점 인덱스를 기준으로 그리디 퀘스트를 그리디 하위 문제로 나눕니다.
Activity * Scheduler :: activity_select(int considered_index)
{
this->considered_index = considered_index;
int greedy_extent = this->considered_index + 1;
…
…
- 범위 결정 연산자(::)를 사용하여 함수 정의가 제공됩니다.
- 고려되는 Index는 값으로 호출되는 Index이다. greedy_extent는 고려된 인덱스 바로 뒤에 초기화된 인덱스입니다.
Activity * Scheduler :: activity_select(int considered_index)
{
while( (greedy_extent < MAX_ACTIVITIES ) &&
((this->current_activities[greedy_extent]).start.hours <
(this->current_activities[considered_index]).finish.hours ))
{
printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",
(this->current_activities[greedy_extent]).start.hours,
(this->current_activities[greedy_extent]).finish.hours,
greedy_extent + 1);
greedy_extent++;
}
…
...
코드 설명:
- 핵심 논리 - 탐욕 범위는 활동 수로 제한됩니다.
- 현재 활동의 시작 시간은 고려된 활동(고려된 인덱스에 의해 제공됨)이 완료되기 전에 예약 가능한 것으로 확인됩니다.
- 가능한 한 선택적 디버그 문이 인쇄됩니다.
- 활동 배열의 다음 인덱스로 이동
...
if ( greedy_extent <= MAX_ACTIVITIES )
{
return activity_select(greedy_extent);
}
else
{
return NULL;
}
}
코드 설명:
- 조건부는 모든 활동이 포함되었는지 확인합니다.
- 그렇지 않은 경우 고려된 인덱스를 현재 지점으로 사용하여 그리디를 다시 시작할 수 있습니다. 이는 문제 설명을 탐욕스럽게 나누는 재귀 단계입니다.
- 그렇다면 탐욕을 확장할 범위 없이 호출자에게 반환됩니다.
int main()
{
Scheduler *activity_sched = new Scheduler();
activity_sched->scheduled = activity_sched->activity_select(
activity_sched->considered_index);
return 0;
}
코드 설명:
- 스케줄러를 호출하는 데 사용되는 기본 함수입니다.
- 새 스케줄러가 인스턴스화됩니다.
- 활동 유형의 포인터를 반환하는 활동 선택 함수는 탐욕스러운 퀘스트가 끝난 후 호출자에게 다시 돌아옵니다.
출력:
START:7 END 7 START:9 END 10 START:5 END 6 START:10 END 10 START:9 END 10 Schedule start:5 finish6 activity:3 Schedule start:9 finish10 activity:5
욕심쟁이 기법의 한계
정렬과 같은 모든 하위 문제에 대한 솔루션이 필요한 Greedy 문제에는 적합하지 않습니다.
이러한 Greedy 알고리즘 연습 문제에서는 Greedy 방법이 잘못될 수 있습니다. 최악의 경우에는 최적이 아닌 솔루션으로 이어질 수도 있습니다.
그러므로 탐욕 알고리즘의 단점은 현재 탐욕 상태 앞에 무엇이 있는지 알 수 없다는 것입니다.
다음은 Greedy 방법의 단점을 설명합니다.
여기에 트리로 표시된 그리디 스캔(값이 높을수록 탐욕이 높음)에서 값이 40인 알고리즘 상태는 29를 다음 값으로 사용할 가능성이 높습니다. 또한 퀘스트는 12에서 끝납니다. 이는 41의 값에 해당합니다.
그러나 알고리즘이 최적이 아닌 경로를 선택하거나 정복 전략을 채택한 경우. 25 다음에 40이 올 것이고 전체 비용 개선은 65가 될 것입니다. 이는 차선의 결정으로 24포인트 더 높은 가치를 갖습니다.
욕심쟁이의 예 Algorithms
대부분 네트워킹 알고리즘은 탐욕적 접근 방식을 사용합니다. 다음은 몇 가지 탐욕적 알고리즘 사례 목록입니다.
- Prim의 최소 스패닝 트리 알고리즘
- 여행 판매원 문제
- 그래프 – 지도 색칠
- Kruskal의 최소 스패닝 트리 알고리즘
- Dijkstra의 최소 스패닝 트리 알고리즘
- 그래프 – 정점 커버
- 배낭 문제
- 작업 일정 문제
제품 개요
요약하자면, 이 기사는 탐욕적 패러다임을 정의하고, 탐욕적 최적화와 재귀가 어떻게 어느 정도까지 최상의 솔루션을 얻는 데 도움이 될 수 있는지 보여주었습니다. 탐욕적 알고리즘은 탐욕적 알고리즘으로 많은 언어에서 문제 해결에 널리 사용됩니다. Python, C, C#, PHP, JavaGreedy 알고리즘 예제의 활동 선택은 Greedy 접근 방식을 사용하여 최대 처리량을 달성할 수 있는 전략적 문제로 설명되었습니다. 마지막으로 탐욕적 접근법의 단점을 설명하였다.
