'프로그래밍 기초/자료구조 & 알고리즘'에 해당되는 글 15건

  1. 2010.06.21 유전알고리즘(2)
  2. 2010.06.10 유전 알고리즘
  3. 2010.06.10 영향력 분포도
  4. 2010.05.14 연결리스트를 이용한 이진트리의 순회방법
  5. 2010.05.14 트리의 배열표현 방법
  6. 2010.05.14 큐 만들기
  7. 2010.05.13 스택만들기
  8. 2010.05.13 LCD 디스플레이
  9. 2010.05.11 여행(The Trip)
  10. 2010.05.03 지뢰찾기

유전 알고리즘을 이해하기 위한 간단한 프로그램을 짜보자.


시나리오 -  { } 중 3개를 골라서 20으로 만드는 문제가 있다고 하자. 여기서 유전체는 각 숫자이며, 유전자는 (1,5,3)와 같이 유전체 3개의 집합으로 이루어진다. 적합도 함수를 20과 얼마나 가까운지를 나타내는 값으로 둔다면, (1,5,3)에 대한 적합도는 f( (1,5,3) ) = 11이 된다.

먼저 첫 세대를 아무렇게나 생성한다. 첫 세대가 만약 { (1,5,3) (8,0,9) (9,9,8) (3,7,5) } 으로 형성되었다고 하자. 각각의 적합도를 구하면, { 11, 3, 7, 5 }이 되며, 이 값이 높을수록 20에서 멀기 때문에 해로서 부적당하다는 것을 의미하며, 따라서 세대를 거침에 따라 살아남을 확률이 낮게 된다.

다음 세대를 형성하기 위해, 이 세대의 개체중 2개의 유전자를 선택한다. 이때 선택은 적합도를 기준으로 확률적선택(룰렛 알고리즘이 자주 쓰인다)이다. 따라서 위의 예에서 (8,0,9)는 (9,9,8)에 비해 훨씬 높은 선택 기회를 가진다. 선택된 2개의 유전자의 유전체는 랜덤한 위치에서 교환되어 새로운 세대가 형성된다. 예로 (8,0,9), (9,9,8) 이 선택되었고 교배위치가 2번째 자리로 무작위로 결정되었다면 다음 세대의 개체는 (8,9,8) ,(9,0,9)로 된다.

출처 - 위키백과


1. 먼저 {1~15} 까지 만들고 여기서 랜덤하게 유전자를 3개를 선택하였다.

2. 유전자 3개중 적합도 함수를 통해 20에 가까운 유전자 2개를 선택하였다. (부모유전자) - 선택연산

3. 선택된 2개의 유전자를 부분 결합하여 새로운 해를 만들어 낸다. - 교차연산

4. 부모유전자중 적합도가 낮은 2개의 유전자를 새롭게 만든 유전자 2개랑 바꿔준다. -대치연산

5. 값들이 20이 되기전에 3개가 모두 같아져 버리는 현상이 있다. 이런 현상이 생길때 변이를 시켜준다. -변이연산




원래대로라면 변이연산을 특정한 확률로 랜덤하게 해줘야 되는 거 같은데

프로그램을 하다보니까 대치연산을 하다보면 어느 순간부터 모든 유전자들이 같게 되는 순간이 있다.

그래서 그 순간에 변이연산을 시켜줘서 20이 나올 때 까지 계속 찾게만들었다.

유전알고리즘에 대해서 아주~~~사아아알~~짝 어떤것인지 알 것 같다.

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

유전알고리즘(2)  (0) 2010.06.21
유전 알고리즘  (0) 2010.06.10
영향력 분포도  (0) 2010.06.10
연결리스트를 이용한 이진트리의 순회방법  (0) 2010.05.14
트리의 배열표현 방법  (0) 2010.05.14
큐 만들기  (0) 2010.05.14
Posted by 아몰라

댓글을 달아 주세요


열심히 알고리즘도 찾는 중인데 우선 유전 알고리즘이라는걸 찾아서 정리해봤다.

책에 나온 내용은 거의 400 ~500쪽이라서 대략 어떠한 알고리즘인지만 이해했고

더 조사해서 우리 프로젝트에 적합한지 확인해봐야겠다.


유전알고리즘

 

 

100개의 초기 염색체 집단을 만들고 다음과 같이 해보자.

1. 각 염색체게 문제를 푸는데 얼마나 적당한가를 검사하고 그에 상응하는 적응도를 부여한다.

2. 현재 집단에서 두 개를 선택한다. 선택되는 확률은 적응도에 비례한다. 이런 선택 방법은 흔히 룰렛 선택이라고 한다.

3. 두 염색체의 비트들 중에서 임의의 비트를 선택하여 교차 확률로 교차시킨다.

4. 선택된 염색체의 비트들을 돌연변이 확률로 뒤집는다.

5. 100개의 새로운 염색체가 생길 때까지 2, 3, 4단계를 반복한다.

 

 

룰렛선택 염색체를 적응도에 비례하여 선택하는 방법입니다. 적응도가 높은 염색체일수록 선택될 확률은 높다. 적응도가 가장 높은 염색체가 반드시 다음 세대로 유전된다는 것을 보장하지 않는다.

 

  

 


교차 선택된 두 염색체가 새로운 자식 염색체를 만들기 위해서 그들의 비트를 서로 바꾸는 것

 

 

돌연변이 염색체에서 어떤비트가 뒤집어지는 것을 말한다. , 0 1이 되고 1 0이 되는 것을 말한다. 돌연변이는 매우 희박하게 일어난다. 0.001의 확률로 일어난다.

 

 

갼략한 시나리오

-       염색체 집단에서 염색체를 염색체를 선택할 때마다 교차를 적용해야 하는지를 검사해야 한다. 교차 과정이 끝난 자식 염색체들은 돌연변이 적용 여부를 검사한다. , 자식 염색체의 각 비트들에 대해서 돌연변이 확률로 돌연변이를 적용한다.

 

 

 

 

상세 시나리오

1.     초기 염색체 집단을 임의로 생성합니다.

2.     인공 신경망을 훈련시키고 에러에 따라서 적응도를 부여한다. 인공 신경망이 커질수록 적응도를 삭감하는 것도 좋다. 이렇게 하면 적은 수의 뉴런과 연결을 가진 인공 신경망을 얻을 수 있다.

3.     선택 방법(적응도 비례 선택 혹은 토너먼트 선택 등)으로 두 개의 염색체를 선택한다. 선택된 염색체들은 부모가 된다.

4.     교차 연산자를 적용한다.

5.     돌연변시 연산자를 적용한다.

6.     새로운 집단이 원하는 크기의 다다를 때까지 3~5단꼐를 반복한다.

7.     만족스러운 인공 신경망을 얻을 때까지 2단계로 돌아간다.

 

실시간 진화 게임이 실행되는 동안 악당들을 진화시킬 수 있는 간단한 테크닉

              (악당들의 풀을 관리한다.)

 


 

시나리오

1.     게임에서 필요한 개체는 이 풀에서 만들어진다.

2.     게임에서 개체가 사라지는 즉시 새로운 개체가 게임으로 투입된다.

3.     , 게임에서 사라진 개체보다 적응도가 높은 개체를 선택하여(퓰에 있는 최소 적응도보다 낮으면 풀에 들어갈 수 없다) 돌연변이를 적용한 다음 그것을 게임에 투입한다.




참고 - 쉽게 풀어 쓴 인공지능 게임 프로그래밍  (정보문화사)

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

유전알고리즘(2)  (0) 2010.06.21
유전 알고리즘  (0) 2010.06.10
영향력 분포도  (0) 2010.06.10
연결리스트를 이용한 이진트리의 순회방법  (0) 2010.05.14
트리의 배열표현 방법  (0) 2010.05.14
큐 만들기  (0) 2010.05.14
Posted by 아몰라

댓글을 달아 주세요


시작할 때 밭을 구성할 때 쓰면 괜찮을 것 같은 알고리즘
이것 역시 가능한지 더 조사해봐야함~


영향력분포도 기법 – AI 에이전트가 세계에 대해 지니고 있는 지식을 공간적으로 표현한 것으로, 게임 환경의 물리적/지형적 표현과 현재의 게임 상태(유닛 배치 등등)에 기반해서 전략적 결정에 필요한 정보만을 적절히 추출한 것이다.

 

영향력분포도의 이점

1.     어디에 유닛들을 배치할 것인지, 적이 어디에 있는지(또는 어디쯤에 가면 찾을 수 있는지 알 수 있다)

2.     두 객체 사이에 전선 어디이고 가장 격력한 전투가 벌어지는 또는 벌어질 만한 곳은 어디인지 같은 전략/전술적으로 매우 유용한 정보를 얻을 수 있다.

3.     지형 지물에 관한 정보도 제공할 수 있다.(전술적 가치가 가장 높은 지점이라던가 방어의 허점이 될 만한 지점, 매복 할 지점 등을 제공 받을 수 있다.)

 

간단한 영향력분포도

-       게임이 시작되면 모든 칸들은 0으로 초기화 된다.

-       그리고 각 칸에 대해, 그 칸이 가질 수 있는 영향력 값이 배정된다.

-       전투의 효율성을 영향력 값을 간주하며, 아군 유닛은 양, 적군은 음의 값을 가진다고 한다.

 

 

 

 

 

 

+2

아군

 

 

 

 

 

-1

적군

-1

적군

 

 

 

<초기의 영향력분포>

 

 

 

 

 

 

+0.7

+1

+0.7

+0.35

+1

+2

아군

+1

+0.5

+0.7

+1

+0.7

+0.35

+0.35

+0.5

+0.35

+0.24

<영향력의 전파>

 

 

0.51

0.79

0.47

0.06

0.66

1.66

0.53

-0.06

0.07

0.40

0.03

-0.74

-0.74

-0.17

-0.25

-0.39

<최종적인 영향력분포도>

 

-       이 분포도를 보면 아군과 적군의 역관계를 확실히 알 수 있다.

-       음의 값과 양의 값이 맞부딪히는 칸들을 이으면 전선이 된다.


참고 - GameProgramming Gems2

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

유전알고리즘(2)  (0) 2010.06.21
유전 알고리즘  (0) 2010.06.10
영향력 분포도  (0) 2010.06.10
연결리스트를 이용한 이진트리의 순회방법  (0) 2010.05.14
트리의 배열표현 방법  (0) 2010.05.14
큐 만들기  (0) 2010.05.14
Posted by 아몰라

댓글을 달아 주세요


연결리스트를 위해 구조체를 정의하였다.


typedef struct TreeNode{
char * data;
struct TreeNode * left;
struct TreeNode * right;
}TreeNode;

그리고 3가지의 순회방법이 있는데

전위, 중위, 후위가 있다.

전위는
root-left-right
중위는
left-root-right
후위는
left-right-root


트리구조는 이렇게 만들었다.


순회를 시키면
이런 순으로 트리를 순회하는 것이다.

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

유전 알고리즘  (0) 2010.06.10
영향력 분포도  (0) 2010.06.10
연결리스트를 이용한 이진트리의 순회방법  (0) 2010.05.14
트리의 배열표현 방법  (0) 2010.05.14
큐 만들기  (0) 2010.05.14
스택만들기  (0) 2010.05.13
Posted by 아몰라

댓글을 달아 주세요


우선 이진트리란 루트노드가 있으면  하나의 루트노드당 왼쪽노드와 오른쪽노드 두개의 노드만 있을 수 있는 트리 구조이다.

배열로 이진트리를 표현하는 방법은 부모 노드의 인덱스가 i라하면
왼쪽자식노드는 [i*2] 오른쪽자식노드는[i*2+1]이 된다.

반대로 자식의 부모를 알아볼려고 할 때는 [i/2]를  하여서 나온 몫이 부모가 되게 된다.
그러므로 루트노드는 1부터 시작한다. 아무리 나눠도 0으로 나눌수 없기 때문이다.

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

영향력 분포도  (0) 2010.06.10
연결리스트를 이용한 이진트리의 순회방법  (0) 2010.05.14
트리의 배열표현 방법  (0) 2010.05.14
큐 만들기  (0) 2010.05.14
스택만들기  (0) 2010.05.13
LCD 디스플레이  (0) 2010.05.13
Posted by 아몰라

댓글을 달아 주세요

큐는 스택과는 다르게 FIFO 방식으로 먼저 들어온 녀석이 먼저나가는 방식이다.

그냥 일반큐를 만들어보았다.

구조체를 이용해 front, rear, count, q 를 하나로 통합시켰다.

typedef struct{
 int q[QueueSize+1];
 int front;
 int rear;
 int count;
}queue;


front에서는 Dequeue할 원소를 가르키고 있고 rear에서는 삽입할 자리를 가르키고있다. 또 count를
이용해 Deque나 Enqueue가 가능한지 확인하도록 사용하였다.

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

연결리스트를 이용한 이진트리의 순회방법  (0) 2010.05.14
트리의 배열표현 방법  (0) 2010.05.14
큐 만들기  (0) 2010.05.14
스택만들기  (0) 2010.05.13
LCD 디스플레이  (0) 2010.05.13
여행(The Trip)  (0) 2010.05.11
Posted by 아몰라

댓글을 달아 주세요

예전에 자료구조 배울때 못해보았던

스택만들기를 해보았다.

스택에 대한 간단한 이해만 있으면 어렵지 않게 만들 수 있는 것 같다.

현재 스택에 위치는 top 변수를 만들어서 사용했고

스택에 크기는 10으로 고정하였다.


맨 위에 3은 View가 3번이라서 그렇다. 스택이 아니다 -_-;;;

요 근래 계속 느끼는건데 c랑 c++에 대한 이해가 부족하다.
기본적인 배열이나 int 나 char나 뭔가가 부족하다. 확실하게 못짚겠다.
기초플러스 한번도 제대로 안봤는데 짬내서 봐야겄다.

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

트리의 배열표현 방법  (0) 2010.05.14
큐 만들기  (0) 2010.05.14
스택만들기  (0) 2010.05.13
LCD 디스플레이  (0) 2010.05.13
여행(The Trip)  (0) 2010.05.11
지뢰찾기  (0) 2010.05.03
Posted by 아몰라

댓글을 달아 주세요

입력 파일은 여러 줄로 구성되며 표시될 각각의 숫자마다 한 줄씩 입력된다. 각 줄에는 s와 n이라는 두 개의 정수가 들어있으며 n은 출력될 숫자(0<=n<=99,999,999), s는 숫자를 표시하는 크기(1<=s<=10)를 의미한다. 0이 두 개의 입력된 줄이 있으면 입력이 종료되며 그 줄은 처리되지 않는다.

기본적인 문법이나 활용하는면에서 많이 미숙함을 느꼈던 문제

프로그래밍을 많이안해봐서 그런듯하다. 책보단 역시 코딩을 해봐야되는거같다 -_-

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

큐 만들기  (0) 2010.05.14
스택만들기  (0) 2010.05.13
LCD 디스플레이  (0) 2010.05.13
여행(The Trip)  (0) 2010.05.11
지뢰찾기  (0) 2010.05.03
3n+1  (0) 2010.05.03
Posted by 아몰라

댓글을 달아 주세요

일년에 한번 씩 다른 여행지로 여행을 가는 학생 모임이 있다. 이 학생들은 여행 경비를 모두 똑같이 부담하기로 합의했지만 돈을 쓸 때마다 나눠서 내는 것은 별로 실용적이지 못하다. 그래서 한명씩 식비, 호텔비, 택시비, 비행기표를 부담하기로 한다. 여행이 끝난 후에 각 학생이 지출한 내역을 계산한 다음 1센트 단위 내에서 모든 학생들이 쓴 돈이 같도록 돈을 주고 받는다. 하지만 이전 여행의 경험에 비추어보면 돈을 주고 받는 과정은 정말 지루하고 오랜 시간을 요하는 작업이었다. 지출 내역이 주어졌을 때 모든 학생이 쓴 돈이(1센트 단위 내에서)똑같아지기위해 전달되어야 하는 최소 액수를 구해보자.

각 여행에 대해 각 학생이 사용한 금액이 똑같아지기 위해 전달되어야 하는 금액의 총합을 출력한다.

입력                      출력
3                           10.00
10.00                      12.00
20.00
30.00
4
15.00
15.01
3.00
3.01



재밌는 문제였던거같다. 처음에는 엄청 간단해보였는데 문제를 잘못이해해서 아주 쉽게 생각했었다.
이 문제의 해결은 학생들의 평균을 구해서 그 값보다 큰 것들을 모두 더하면 금액이 같아지기위해서 이동하는 돈의 총액이 된다. 가장 문제였던게 계산후에 자리수를 맞추기위해 반올림을 할려고 했는데 c랑 c++에서는 반올림 함수를 제공해주지 않는걸 몰라서 찾는데 시간이 좀 걸린것같다.

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

스택만들기  (0) 2010.05.13
LCD 디스플레이  (0) 2010.05.13
여행(The Trip)  (0) 2010.05.11
지뢰찾기  (0) 2010.05.03
3n+1  (0) 2010.05.03
스케줄링 (라운드 로빈)  (0) 2009.12.17
Posted by 아몰라

댓글을 달아 주세요


각 칸에는 최대 여덟 개의 인접한 칸이 있을 수 있다. 아래에서 왼족에 있는 4*4지뢰밭에는 두 개가 있으며 각각은 '*'문자로 표시되어 있다. 이 지뢰밭을 방금 설명한 힌트 숫자로 표기하면 오른쪽에 있는 것과 같은 필드가 만들어진다.


입력                  출력
4 4 
*...                   *100
....                    2210
.*..                   1*10
....                    1110




일단 허접한 알고리즘으로 하긴했는데

두가지 문제점이 있다.

1. 해당 값이 * 일 경우 주변 값도 * 이면 *에 +1을 하지 못하도록 하여야한다.

2. 위에서 . * .
         -> . . . 가장 왼쪽에 점의 경우에 그 점이 지뢰라고하면 그 주위에 값들이 +1을 하게 알고리즘이 구성되었는데 저 위치 같은 경우에는 왼쪽에 아무것도 없는 벽이라는것을 표현해줘야한다. 그것이 안되어서 상단 오른쪽에 값이 엉뚱하게 들어가 버린다.


             . * .

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

LCD 디스플레이  (0) 2010.05.13
여행(The Trip)  (0) 2010.05.11
지뢰찾기  (0) 2010.05.03
3n+1  (0) 2010.05.03
스케줄링 (라운드 로빈)  (0) 2009.12.17
병합정렬 & 퀵 정렬 비교 및 기수정렬  (0) 2009.12.17
Posted by 아몰라

댓글을 달아 주세요

이전버튼 1 2 이전버튼