Rommance - Daniel Jiseok Song

Traveling Salesman Problem을 풀어보는 간단한 숙제를 하고 있습니다.

가는 길을 디스플레이 하고 싶은데 어찌할까 하다가 랩에 졸업한 친구가 만든 자바 프로그램을 쓰고 있었습니다.

그런데 비슷한 기능을 xgraph라는 매우 심플한 프로그램을 사용하여 쓸 수 있군요.

이건 졸업한 친구가 만든 것 (입력패턴이 달라서 입력을 스크립트로 좀 바꿔야 했습니다)

이건 xgraph를 가지고 만든 것

죄표가 시작하는 지점이 달라서(y축이 다르죠) 그림은 뒤집혀나옵니다만 그런건 상관 없으니까요

테스트할 때는  xgraph로 쓰면 되겠습니다.

혹시 누군가 저처럼 숙제할 때 쓸 출력 프로그램이 없다 싶으면 이걸 쓰시면 되겠네요(물론 X가 되야 합니다)

이럴 때를 위한 xgraph 사용방법은

x,y 좌표가 연속되게 덤프된 트레이스 파일을 만들어서 리다이렉션 해주면 됩니다.

예를 들어 위 저는

65  20
95  18
96  55
98  51
92  67
...
85  30
85  43
66  26
65  20

이렇게 만들었고(이 파일을 mytrace라고 합시다)

$ xgraph < mytrace

이러면 됩니다.

실제로 제가 실행한 커맨드는

$ ./convert_xgraph | xgraph -P -ng

입니다만... (-P는 점을 크게, -ng는 그리드를 없애도록)  입출력을 맞추려고 그런것 뿐입니다.

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

http://www.iba.k.u-tokyo.ac.jp/english/GA.htm

1.t=0;
  Generate initial population P(t) at random;
2.Evaluate each individual in P(t);
3.While termination condition not satisfied do
  begin
    t=t+1;
    Select some parents S(t) from P(t-1);
    Generate offspring Q(t) by applying
    crossover and mutation on S(t);
    Evaluate offspring Q(t);
    Combine old population and new 
    offspring to generate P(t);
  end;

GA에 대한 간단한 개괄입니다.

Selection method등 참조할 수 있습니다.

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

http://homepage.sunrise.ch/homepage/pglaus/gentore.htm

자바 애플릿으로 Genetic Algorithm의 예를 보여줍니다.

Landschaft를 누르면 새로운 지형이 생성되고, Population을 누르면 초기 지점들을 정해진 숫자 만큼(위 그림에선 100개) 흩뿌립니다. 그리고 Selektion 을 누르면 포인트 선택, 그리고 이름이 바뀐 같은 버튼(Rekombination)을 누르면 변환합니다. Go를 누르면 해를 찾을 때 까지 반복합니다.

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

춮처 : http://developer.apple.com/documentation/DeveloperTools/gcc-4.0.1/cpp/Variadic-Macros.html

#define DEBUG
#ifdef DEBUG
#define DBG(...)    fprintf(stderr, __VA_ARGS__)
#else
#define DBG(...)    do{}while(0)
#endif

이런식으로 사용합니다.

C99 표준이라고 돼 있고 gcc 4.0부터는 확실히 이렇게 쓰는 것 같습니다.

gcc가 이전부터 사용하는 것과 맞추려면(C99표준은 아닌 것 같습니다)

#define eprintf(format, args...) fprintf (stderr, format , ##args)

이런식으로 쓰라는군요

## args 전에는 콤마(,)와 빈칸이 꼭 있어야 한답니다.

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

Shuffling에 관한 글을 찾아보았다.

http://en.wikipedia.org/wiki/Shuffling#Shuffling_algorithms

http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

Shuffling 알고리즘이란 1~n까지의 숫자가 있을 때 이를 섞어서 임의의 순서로 만드는 것이다.

MP3 플레이어의 shuffle과 같은 것을 구현할 때 쓴다.

가장 간단하게는 배열을 두고

i가 i~n까지 돌 동안

1. 1~n까지의 랜덤한 숫자를 얻은 다음,

2. 이전에 선택됐던 번호인가를 알아보고 그렇다면 다시 아니면 다시 1번 반복

3. 중복되지 않은 값을 찾으면 i번째에 해당 값을 넣는다

이러면 어떤 경우엔 무한반복하게 된다. 1,2번에서 계속 걸릴 수 있기 때문에

이 때문에 나온 알고리즘이 몇가지 있다는데 두가지 방법이 유명하다고 한다.

하나는 O(N*logN)의 시간이 들고 하나는 O(N)이 든다.

첫번째는 일련번호가 있는 카드들을 두고 랜덤 숫자를 붙이고 나서 그걸 숫자로 정렬하면 카드번호가 섞이게 되는 것을 이용한다. 정렬하는 알고리즘의 효율성에 따라 효율이 정해지는데 가장 빠른 정렬방식이 O(N*logN)이다.

둘째는 Fisher-Yates shuffle 이라고 불리는데

1. 일단 배열(카드들)에 1~N까지 숫자를 순서대로 넣는다. (A[i] = i)

2. 1~N 사이의 랜덤 숫자를 뽑고 이를 k라 하면 k번째 숫자와 N번째 숫자를 바꿔치기한다. ( swap(A[k],A[n]) )

3. N을 하나 빼서 N-1로 만든다.

4. N이 2보다 작아질때까지 2와 3을 반복한다.

이걸 보면서 생각한건데,

예전에  MP3 플레이어를 만들 때 shuffle 기능 구현에 고민했던 게 생각난다.

그때는 단순히 어떤 수열을 만들면 1~N까지 반복되지 않는 랜덤 숫자를 만들 수 있지 않나 했었지만 찾지를 못했다.

위의 두 방법을 쓰면 쉽게 구현이 가능한데..

그러나 문제가 있다. 메모리를 N에 비례해서 쓴다는 것. 그리고 N이 많이 크면 초기에 배열을 만드는 데 시간이 많이 들 것이다.

실제 MP3 플레이어는 분명히 램 크기가 엄청 작을 것이다. 이를 어떻게 해결할까?

어쩌면 그냥 호스트(PC)가 만들어주는 플레이리스트만 쓸 지도 모르겠다.

아니면 shuffle로 하지 말고 단순히 random 만 쓰는 수도 있겠다(이러면 예전에 들었던 곡이 또 나올 때도 있을 것이다)

시간문제는, 만일 이런 방법을 쓸 경우 N이 크다면 초기 리스트 만드는 데 딜레이가 생길텐데 처음 10곡 정도는 임의로 생성한 리스트를 사용해서 초기 셋업이 일단 된 것처럼 시작시키고 내부적으로 나머지 리스트를 완성하면 어떨까한다.

그러면 사용자 입장에선 기다리는 시간이 없을 것이다.

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

#include  <stdio.h>   /* Required to use printf() */
typedef unsigned long long u64;
typedef long long i64;
//#define i64   (long long)
/* Function l(n1,n2,n) calculates f(n) using parameters n1 and n2
 *  * to store the two previously calculated Fibonacci numbers */
long long l(long long n1,long long n2,long long n) {
        //printf("l(%lld,%lld,%lld)=%lld\n", n1, n2, n, (n<2 ? n1 : l(n1+n2, n1, n-1)));
    return n<2 ? n1 : l(n1+n2, n1, n-1);
}
/* Function f(n) returns the n'th Fibonacci number
 *  * It uses ALGORITHM 2B: SIMPLE RECURSION
 *   */
long long f(long long n) {
    return l(1,1,n);
}
/* Function f_print(n) prints the n'th Fibonacci number */
void f_print(long long n) {
    printf("%lldth Fibonacci number is %lld\n",n,f(n));
}
/* Function main() is the program entry point in C */
int main(int argc, char* argv[])
{

        long long n=45;
        if (argc > 1)
                n = (long long) atoi( argv[1]);
    f_print(n);
    return 0;
}

#include <stdio.h>
unsigned int f(int n) {
    int i;
    unsigned int n1=1,n2=1;

    for(i=1; i<=n; i++) {
        n1+=n2;
        n1^=n2^=n1^=n2; /* C trick to swap n1 and n2 */
    }
    return n1;
}
/* Function f_print(n) prints the n'th Fibonacci number */
void f_print(int n) {
    printf("%dth Fibonacci number is %lu\n",n,f(n));
}

int main(int argc, char* argv[])
{

        int n=45;
        if (argc > 1)
                n = atoi( argv[1]);
        f_print(n);

        return 0;
}

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.