Greedyアルゴリズム

グリディアルゴリズムは最適化問題を解決するアルゴリズムである.階調アルゴリズムは、入力データ間の関係を考慮するのではなく、実行中に最小値または最大値を持つデータを選択します.
最適化(Optimization)の問題:可能な年の中で最大または最小の年を検索
この選択は「短視的」選択とも呼ばれる.なぜなら,短視で部分的な最適解を探し,これらの解を集中して問題の最適解を得るからである.グリディアルゴリズムは簡単で、選択すると繰り返しません.

小銭をさがす

買い物は小銭をコインにしなければならない。最低硬貨の数で探す場合、それぞれ500元、100元、50元、10元、1元硬貨の個数を求めます。

残りの小銭額を超えない場合は、Greedyアルゴリズムと呼ばれる最大額硬貨のアルゴリズムを選択し続けます.

#include<stdio.h>
#include<stdlib.h>

void CoinChange(int money, int* change);
int main() {
	int* change = malloc(sizeof(int) * 5);//500원 동전 개수, 100원 동전 개수, 50원 동전 개수, 10원 동전 개수, 1원 동전 개수 배열
	int money;

	printf("거스름돈 액수: ");
	scanf_s("%d", &money);

	CoinChange(money, change);
	free(change);
}
// 거스름돈을 가장 적은 수의 동전으로 바꿔주는 함수
void CoinChange(int money, int * change) {
	int Money = money;
    for(int i=0; i<5; i++)
    	change[i] = 0;
	while(Money >= 500){
    	change = change - 500;
        change[0]++;
    }
    while(Money >= 100){
    	change = change - 100;
        change[1]++;
    }
    while(Money >= 50){
    	change = change - 50;
        change[2]++;
    }
    while(Money >= 10){
    	change = change - 10;
        change[3]++;
    }
    while(Money >= 1){
    	change = change - 1;
        change[4]++;
    }
	printf("500원 동전 %d개, 100원 동전 %d개, 50원 동전 %d개, 10원 동전 %d개, 1원 동전 %d개", change[0], change[1], change[2], change[3], change[4]);
}

500元硬貨を処理する時、何個の異なる硬貨を探すか全然考えません.この部分からGredyアルゴリズムの短視特性が分かる.

最小長ツリー

指定したグラフィックの最小長ツリーを見つけます。

伸張ツリーとは、すべての点を接続するツリーであり、所与の重み付け図では、伸張ツリーの幹線の重み付けと最小のツリーである.図の頂点数がn個の場合,伸長木にはちょうど(n−1)本の幹線がある.

グラフィックデータ構造

#include <stdio.h>
#include <stdlib.h>

/*간선 구조체*/
typedef struct Edge
{
    char v1, v2; // 시작 정점과 끝 정점 이름
    int weight; // 가중치
    struct Edge* next; // 그래프의 간선 리스트에서 다음 간선을 가리키는 포인터
}Edge; 

/* 정점 aName에 부착된 간선을 표현하는 간선 구조체 */
typedef struct IncidentEdge
{
    char aName; // 정점 이름
    Edge* e; // 부착된 간선
    struct IncidentEdge* next; // 정점 aName의 부착 간선 리스트에서 다음 간선을 가리키는 포인터
}IncidentEdge; 

/*정점 구조체*/
typedef struct Vertex
{
    char vName; // 정점 이름
    IncidentEdge* iHead; //  정점 vName의 부착 간선 리스트의 헤더 간선 포인터
    struct Vertex* next; // 그래프의 정점 리스트에서 다음 정점을 가리키는 포인터
}Vertex;

/*그래프 구조체*/
typedef struct
{
    Vertex* vHead; // 정점 리스트의 헤드 정점 포인터
    Edge* eHead; // 간선 리스트의 헤드 간선 포인터
    int eCount, vCount; // eCount: 간선 개수 m, vCount: 정점 개수 n
}Graph; 

/* 그래프 초기화 함수*/
void init(Graph* G)
{
    G->vHead = NULL;
    G->eHead = NULL;
    G->vCount = G->eCount = 0;
}

/*새로운 정점 추가 함수*/
void makeVertex(Graph* G, char vName)
{
	Vertex* v = (Vertex*)malloc(sizeof(Vertex)); // 새로운 정점에 동적 메모리 할당
	v->vName = vName; // 새로운 정점의 이름 저장
	v->iHead = NULL;
	v->next = NULL;
	G->vCount++; // 그래프 정점 개수 +1
	
	Vertex* q = G->vHead; // q에 그래프의 정점 리스트 헤더 정점 포인터 저장
	if (q == NULL)
		G->vHead = v;
	else
	{
		while (q->next != NULL)
			q = q->next;
		q->next = v; // 그래프의 정점 리스트에 새로운 정점 추가
	}
}

/*정점 v에 부착된 간선 리스트에 간선을 추가하는 함수*/
void makeIncidentEdge(Vertex* v, char aName, Edge* e) 
{
    IncidentEdge* p = (IncidentEdge*)malloc(sizeof(IncidentEdge)); // 새로운 간선에 동적 메모리 할당
    p->aName = aName; // 정점 v의 이름 저장
    p->e = e; // 간선 저장
    p->next = NULL; 
    IncidentEdge* q = v->iHead;
    	if (q == NULL)
		v->iHead = p;
	else
	{
		while (q->next != NULL)
			q = q->next; 
		q->next = p; // v의 부착 간선 리스트에 새로운 간선 추가
	}
}

/*정점 탐색 함수*/
Vertex* findVertex(Graph* G, char vName)
{
	Vertex* v = G->vHead; // v에 그래프의 정점 리스트 헤더 정점 저장
	while (v->vName != vName)
		v = v->next; 
	return v; // 정점 이름이 vName인 정점 리턴
}

/*간선 추가 함수*/
void insertEdge(Graph* G, char v1, char v2, int w)
{
    Edge* e = (Edge*)malloc(sizeof(Edge)); // 새로운 간선에 동적 메모리 할당
    e->weight = w; // 가중치 저장
    e->v1 = v1; // 시작 정점 저장
    e->v2 = v2; // 끝 정점 저장
    e->next = NULL;
    G->eCount++; // 그래프의 간선 개수 +1
    
    Edge* q = G->eHead; 
	if (q == NULL)
		G->eHead = e;
	else
	{
		while (q->next != NULL)
			q = q->next;
		q->next = e; // 간선 리스트에 새로운 간선 추가
	}
    Vertex* v = findVertex(G, v1);
    makeIncidentEdge(v, v1, e); // 새로운 간선을 v1 정점의 부착 간선 리스트에 추가
    v = findVertex(G, v2);
    makeIncidentEdge(v, v2, e); // 새로운 간선을 v2 정점의 부착 간선 리스트에 추가
}

/*그래프 출력 함수*/
void print(Graph* G)
{
	Vertex* p;
	IncidentEdge* q;
	for (p = G->vHead; p != NULL; p = p->next)
	{
		printf("[%c] : ", p->vName); // 정점 이름 출력
		for (q = p->iHead; q != NULL; q = q->next)
			printf("[%c, %d] ", q->aName, q->e->weight); // 정점 p의 부착 간선 리스트를 순회하며 부착된 간선 정보 출력
		printf("\n");
	}
	printf("\n");
}
Edge partition(Edge* e[], int left, int right){
	Edge pivot = e[left];
    int temp;
    int low=left, high=right+1;
    do{
    	do{
    		low++;
    	}while(e[low] < pivot);
    	do{
    		high--;
    	}while(e[high] > pivot):
        
        if(low<high){
        	temp = e[low];
        	e[low] = e[high];
        	e[high] = temp;
        }
    }while(low < high);
    temp = e[left];
    e[left] = e[high];
    e[high] = temp;
    return high;
}
void quickSort(Edge* e[], int left, int right){
	if(left<right){ 
    	int p = partition(e, left, right);
        quickSort(e, left, p-1);
        quickSort(e, p+1, right);
    }
}
/*가중치 오름차순 퀵정렬 함수 (e[]에 정렬된 간선 배열이 저장됨)*/
void incSort(Graph* G, Edge* e[])
{
	Edge* p = G->eHead;
    for(i = 0; i < G->eCount; i++)
    {
        e[i] = p;
        p = p->next;
    }
    quickSort(e, 0, G->eCount-1);
}

（1）Kruskalアルゴリズム

重みが最も小さい幹線が周期を生じない場合に限って、幹線を追加することに貪欲である。

Kruskalアルゴリズムを以下のように擬似コードに整理する.

KruskalMST(G)
입력: 가중치 그래프 G=(V, E) (단, |V|=n, |E|=m, V: vertex 정점, E: edge 간선)
출력: 최소 신장 트리 T
1. 가중치의 오름차순으로 간선들을 정렬: L = 정렬된 간선 리스트
2. T를 초기화
3. while(T의 간선 수 < n-1) {
	L에서 가장 작은 가중치를 가진 간선 e를 가져오고, e를 L에서 제거
	if(간선 e가 T에 추가되어 사이클을 만들지 않으면) e를 T에 추가
	else e를 버린다.
}
4. return T 

これをコードとして次のように書きます.

/*사이클 체크 함수*/
int vFind(int v[], int vNum)
{
    if(v[vNum] == -1)
        return vNum;
        
    while(v[vNum] != -1)
        vNum = v[vNum];
    
    return vNum;    
}

void vUnion(int v[], int vNum1, int vNum2)
{
    int r1 = vFind(v, vNum1);
    int r2 = vFind(v, vNum2);
    
    if(r1 != r2)
        v[r2] = r1; 
}
/* v에 사이클 시작 정점 저장. (Ex) v[2]=0이면 'c'->'a'로 연결된 것. 
만약 v1-97=0, v2=97=2이고 vNum1=0, vNum2=0이면 'c'->'a'로 가는 path가 존재하는 것이므로
간선 'a'-'c'는 최소 신장 트리에 추가하지 않는다. (추가할 경우 사이클이 발생한다.)*/
void kruskal(Graph* G, Edge* e[], int v[]) 
{
    int eCnt = 0, i = 0;
    int vNum1, vNum2;
    Edge* p;
    
    while(eCnt < G->eCount - 1) // 그래프의 간선 리스트 순회
    {
        p = e[i]; // 가장 작은 가중치를 가진 간선을 p에 저장
        vNum1 = vFind(v, p->v1 - 97); // 97은 소문자 'a'=>v1-97의 값은 0부터 시작한다.
        vNum2 = vFind(v, p->v2 - 97);
        
        if(vNum1 != vNum2) // 간선 p가 추가되어 사이클을 만들지 않으면
        {
            printf("%d. [%c%c (%d)]\n", eCnt+1, p->v1, p->v2, p->weight);
            eCnt++; // 최소 신장 트리의 간선 개수
            vUnion(v, vNum1, vNum2);
        }
        i++;
    }
}

高速ソートを用いて幹線をソートすると,幹線の個数mにO(mlogm)時間が必要になるが,while−リングは最大m回実行され,while−リング内で周期をチェックするのにO(1)時間がほとんど必要であり,時間複雑度はO(mlogm)である.

(2)Primアルゴリズム

いずれかの点を選択した後、ツリーTの内部の点とTの外部の点とを結ぶ幹線において最小重み付けを持つ幹線を求め、その幹線を結ぶ外部点をTに追加する。T以外のポイントは常に追加されるため、ループは作成されません。

PrimMST(G)
입력: 가중치 그래프 G=(V, E) (단, |V|=n, |E|=m, V: vertex 정점, E: edge 간선)
출력: 최소 신장 트리 T
1. G에서 임의의 점 p를 시작점으로 선택. D[p]=0 
/*  D배열: T에 속한 점과 연결된 간선들 중 가중치가 가장 작은 간선의 가중치를 저장. 
	D[v]엔 T에 속한 점과 점v 사이의 간선들 중 가중치가 가장 작은 간선의 가중치를 저장. */
2. for(점 p가 아닌 점 v에 대하여){ // D배열 초기화
	if(간선 (p,v)가 그래프에 있으면)
    	D[v] = 간선(p,v)의 가중치
    else
    	D[v]= ∞
}
3. T={p} // 초기 트리 T에 점 p 추가
4. while(T에 있는 점의 수 < n){ // n은 그래프 정점의 개수
	T에 속하지 않은 각 점 v에 대하여, D[v]가 최소인 점 $$V_{min}$$과 연결된 간선을 T에 추가.
    for(T에 속하지 않은 각 점 w에 대하여){
    	if(간선($$V_{min}$$,w)의 가중치 <D[w])
        	D[w] = 간선 ($$V_{min}$$,w)의 가중치 //D[w]를 갱신
    }
}
5. return T