#0616

1. branch and bound로 tsp문제 풀기

    1 시작점 잡아(a)

    2 모든 점에서 연결된 간선들 중 가장 weight 낮은 간선 2개 선택

    3 weight 2개씩 노드별로 다 합쳐서 2로나눔 -> bound

    4 그뒤로 시작점 제외 다른점 골라서(b,c,d,e), 그점과 잇는 간선 포함시켜서 똑같이 정점별로 weight 가장 낮은 간선 2개 선택

    5 3 반복해서 정점별로([a,b],[a,c],[a,d],[a,e]) bound 구함

    6 해당 계층의 bound 비교, 최솟값만 선택 후 나머지는 계산하지 않음

    7 그런식으로 끝까지 방문, bound가 가장 작은 게 답이 된다. 

 

2. 유전 알고리즘 계산 과정

    시작 - Initialization - Fitness evaluation - Selection - Crossover - Mutation - 멈출지 결정(계속할경우 fitness evaluation부터 반복) - 종료

 

GA Cycle

    population - Evaluation(fitness) - selection - crossover&mutation

 

selection : 유전적으로 우수한 개체 선택, 단 local optimum 문제 해결 위해 열등한 개체도 낮은확률로 선택시킴

ex) 룰렛휠, stochastic universal sampling(비율대로 선 나눠놓고 난수생성해서 어디 들어가는지 봄), 토너먼트, 랭크, elitism

crossover: 무작위로 유전자 한쌍 선택, 교체

ex) 1-point crossover, 2-point crossover, cycle crossover

 

3.

search problem, optimization problem, decision problem

각각 해답이 존재하는지(ex: 특정 조건에서 거리가 b이하인 경로가 존재하는가 ), 최적해(OPT)가 무엇인지(주로 최대, 최소를 물음), 어떤 경우에 대해 참인지 묻는 문제

 

P : polynomial time안에 해결 가능한 알고리즘이 존재

NP: 어떤 instance에 대해 polynomial time 안에 검산 가능

NP-Hard Problem: NP에 속하는 모든 decision problem들을 poly-time 내에 환산할 수 있는 문제

NP-Completeness Problem: NP이자 NP-Hard인 문제

 

Horn Formula: 모든 clause들이 한개이하의 positive literal을 가질 경우. 이경우 그리디로 풀 수 있다.

 

TSP가 poly-time안에 해결가능하다면 tsp-opt도 가능함(이분탐색으로 logn만에 가능)

 

Independent set : 간선들 간에 같은 간선을 공유하지 않는 독립적인 정점의 집합

 

independent set의 여집합이 vertex cover 만족

 

클리크: vertex cover의 decision 버전으로, 그래프에서 상수 g가 주어졌을때 모든 정점 사이를 연결하는 간선이 있으면서 g개의 정점으로 연결돼야함