Graph Coloring Algorithm -> Monte Carlo estimate
자리에 앉아서 6시간 정도 짠거 같다...구현이 목적이기 때문에
지겹게 배운 최적화과정은 안드로메다로 보내고
일단 교제의 알고리즘을 테스트 해볼 정도만 쉽게쉽게 짜봤다
숙제는 내고봐야 할것 아닌가...
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
//######################## 226page #########################//
// 선언부
// 226p 그래프
#define NODE226 4 // 노드
#define m226 3 // 색
bool W226[NODE226][NODE226]={
/*0*/ { false, true, true, true},
/*1*/ { true, false, true, false},
/*2*/ { true, true, false, true},
/*3*/ { true, false, true, false},
};
int v226color[NODE226] = {0, 0, 0, 0};
int count226=0;
//######################## 227page #########################//
// 선언부
// 227p 그래프
#define NODE227 5
#define m227 3 // 색
bool W227[NODE227][NODE227]={
/*0*/ { false, true, true, true, false},
/*1*/ { true, false, true, false, false},
/*2*/ { true, true, false, true, true},
/*3*/ { true, false, true, false, true},
/*4*/ { false, false, true, true, false}
};
int v227color[NODE227] = {0, 0, 0, 0, 0};
int count227=0;
//######################## 247page #########################//
// 선언부
// 247p 그래프
#define NODE247 6
#define m247 3 // 색
bool W247[NODE247][NODE247]={
/*0*/ { false, true, false, true, false, false},
/*1*/ { true, false, true, false, true, false},
/*2*/ { false, true, false, false, false, true},
/*3*/ { true, false, false, false, true, false},
/*4*/ { false, true, false, true, false, true},
/*5*/ { false, false, true, false, true, false}
};
int v247color[NODE247] = {0, 0, 0, 0, 0, 0};
int count247=0;
/*###########################################################################*/
// //
// 226page 그림 5.11 //
// //
// //
/*###########################################################################*/
// 구현
void printColor226(int n){
int i = 0;
printf("{");
while(i < n){
printf("%d ",v226color[i]);
i++;
}
printf("}\n");
count226++;
}
bool promising226(int i)
{
메롱
}
void m226_coloring(int i)
{
메롱
}
/*###########################################################################*/
// //
// 227page 그림 5.11 //
// //
// //
/*###########################################################################*/
//구현
void printColor227(int n){
int i = 0;
printf("{");
while(i < n){
printf("%d ",v227color[i]);
i++;
}
printf("}\n");
count227++;
}
bool promising227(int i)
{
메롱
}
void m227_coloring(int i)
{
메롱
}
/*###########################################################################*/
// //
// 247page 연습문제 16번 //
// //
// //
/*###########################################################################*/
//구현
void printColor247(int n){
int i = 0;
printf("{");
while(i < n){
printf("%d ",v247color[i]);
i++;
}
printf("}\n");
count247++;
}
bool promising247(int i)
{
메롱
}
void m247_coloring(int i)
{
메롱
}
/*###########################################################################*/
// //
// M O N T E C A R L O //
// 226page //
// //
/*###########################################################################*/
//구현
int rand226_m(int m, bool pc[]){
메롱
}
int estimate_m226_coloring()
{
메롱
}
return numnodes;
}
/*###########################################################################*/
// //
// M O N T E C A R L O //
// 227page //
// //
/*###########################################################################*/
//구현
int rand227_m(int m, bool pc[]){
메롱
}
int estimate_m227_coloring()
{
메롱
}
/*###########################################################################*/
// //
// M O N T E C A R L O //
// 247page //
// //
/*###########################################################################*/
//구현
int rand247_m(int m, bool pc[]){
메롱
}
int estimate_m247_coloring()
{
메롱
}
//############################ 사용한 결과 변수 초기화 #########################
void init(){
int i;
for(i = 0; i<NODE226; i++)
v226color[i] = 0;
count226=0;
for(i = 0; i<NODE227; i++)
v227color[i] = 0;
count227=0;
for(i = 0; i<NODE247; i++)
v247color[i] = 0;
count247=0;
}
//##############################################################################
//#################################### M A I N #################################
void main()
{
// 주의 사항 ///
// 1. Coloring
// 교제 226page 그림 5.10
printf("교제 226page 그림 5.10 그래프 3개의 색으로 칠하기\n");
m226_coloring(-1);
printf("총 %2d개의 해답이 있습니다.\n\n", count226);
// 교제 227page 그림 5.11
printf("교제 227page 그림 5.11 그래프 3개의 색으로 칠하기\n");
m227_coloring(-1);
printf("총 %2d개의 해답이 있습니다.\n\n", count227);
// 교제 247page 연습문제
printf("교제 247page 연습문제 그래프 3개의 색으로 칠하기\n");
m247_coloring(-1);
printf("총 %2d개의 해답이 있습니다.\n\n", count247);
init(); // 전역 선언 배열들 초기화
printf("#교제 226page 그래프 Monte Carlo 추정\n");
int av226 = 0, res226 = 0;
for(int i=0; i<10; i++){
res226 = estimate_m226_coloring();
printf("%2d번째 실행, 226page 그래프 Monte Carlo 추정 방문노드 갯수 : %d\n\n", i+1 ,res226);
av226+=res226;
}
printf("총 10회 실행 평균 노드 방문 횟수 : %d\n\n", av226/10);
printf("#교제 227page 그래프 Monte Carlo 추정\n");
int av227 = 0, res227 = 0;
for(int i=0; i<10; i++){
res227 = estimate_m227_coloring();
printf("%2d번째 실행, 227page 그래프 Monte Carlo 추정 방문노드 갯수 : %d\n\n", i+1 ,res227);
av227+=res227;
}
printf("총 10회 실행 평균 노드 방문 횟수 : %d\n\n", av227/10);
printf("#교제 247page 그래프 Monte Carlo 추정\n");
int av247 = 0, res247 = 0;
for(int i=0; i<10; i++){
res247 = estimate_m247_coloring();
printf("%2d번째 실행, 247page 그래프 Monte Carlo 추정 방문노드 갯수 : %d\n\n", i+1 ,res247);
av247+=res247;
}
printf("총 10회 실행 평균 노드 방문 횟수 : %d\n\n", av247/10);
}
야이 애송이들아
숙제는 자기손으로 하란 말이다
으흐흐..
알고리즘 숙제 4 끝.
숙제제출하고 "메롱" 부분 올려줄께...ㅋㅋ