---

2022-05-30 21:00

결국 플레티넘 달성!

---

2022-01-27 18:00
골드2, 클래스4 달성!

1300b

---

2022-01-19 2:00
클래스3+ 달성

이중우선순위큐 개같이 멸망

• 정답률 개같이 멸망!
  
  

---

2022-01-18 2:50
상위100문제에서 브론즈 제거

2022-01-18 23:40
골드3 달성
다익스트라 개싫다

---

2022-01-17 04:00
Solved.ac Gold4 1000점 달성

카잉달력 빡셌다.

+
코포 승급전에서 언레됨 ㅠ

+
2021-12-29 20:40
Solved.ac 골드 입성

---

Review Matlab

Array

---

Search Problems

consist

• A state space
• A succeossor function

problem

1. Initial state

Search Strategies

1. Completeness

• Solution을 찾을 수 있는가

2. Optimality

• 최소 코스트가 항상 나오는가

3. Time complexity

4. Space complexity

Uninformed Search Strategies

• DFS
• BFS
• UNIFORM

---

Depth First Search(깊이우선탐색)

• 노드의 모든 후손노드를 방문한다. (preorder tree traversal)

State Space Tree(상태 공간 트리)

• 뿌리 노드에서 잎노드까지의 경로가 해답후보(candidate solution)가 되는 트리
• DFS를 하여 해답을 찾을 수 있음. 그러나 가능성이 없는 노드도 검색해서 비효율적

Back Tracking

• 정의: promising

  • 전혀 해답이 나올 가능성이 없는 노드: (non-promising)
  • 그렇지 않은 노드: promising

• 되추적?

  • 유망성 점검 후 유망하지 않으면, 부모노드로 돌아가서(“backtrack”) 다음 후손에 대한 검색을 진행

BackTracking 개념

• 상태공간트리에서 깊이우선검색 실시
• 유망하지 않으면 가지쳐서(pruning) 검색하지 않음
• 유망한 노드만 자식노드 검색

The 0-1 Knapsack Problem

• Optimization problem이므로 검색이 끝나기 전까진 해답을 알 수 없음

Let:

• profit: 가치 총합
• weight: 무게 총합
• totweight: 무게 count
• bound: 가치 추정치

풀이:

• 단위당 가치가 높은 순으로 sort

  • 탐욕적 방법처럼 보이지만 탐욕적인 알고리즘은 아니다.

• bound와 totweight를 profit과 weight값으로 초기화

• 탐욕적으로 아이템 취하기

• toweight이 W초과할때까지

• 남은부분에 마지막일부취하고 profit을 bound에 더함

분석

• 점검하는 마디의 수: O(2^n)

• DP보다 좋은가? 확실하지 않음

  • DP worst(O(min(2^n, nW)))
  • BT worst(O(2^n))

• –

Branch-and-Bound (분기한정법)

• backtracking과 비슷

  • state space tree 사용

• Backtracking과 차이점

  • 트리를 순회하는 방법을 제한하지 않는다.
  • 최적화 문제에서만 사용

Breadth-First Search ( 너비우선탐색)

1. 뿌리마디 먼저 검색
2. 다음 수준1에있는 모든 마디를 검색
3. 다음 수준2에있는 모든 마디를 검색
4. …

• Queue 사용

Best-First Search (최고우선탐색)

• 최고의 한계를 가진 마디를 우선으로 선택
• 우선순위 큐(Priority QUeue) 사용

---

The Travveling Salesperson Problem (TSP)

• 외판원의 집이 위치하고 있는 도시에서 출발,
  다른 도시들을 각각 한번씩만 방문하고, 다시 집으로 돌아오는
  가장 짧은 일주여행경로(tour)을 결정하는 문제

• 여러개의 징루 여행경로 중에서 길이가 최소가 되는 경로가 최적일주여행경로(optimal tour)가 된다.

• 부르트포스 알고리즘:

  • 가능한 일주여행경로의 총 개수는 (n-1)!

DP를 이용한 접근방법

• V: 모든 정점의 집합

• A: V의 부분집합

• D[vi][A]: A에 속한 각 정점을 한번씩만 거쳐서 vi에서 v1로 가는 최단경로 길이

• D[vi][V-{v1}] = min(W[1][j] + D[vj][V-{v1, vj}])

• n=40일때 DP로 6년…. O(n^2*s2^n)

분기한정법을 이용한 접근방법

상태공간트리 구축방법

• 각 마디는 출발마디로부터 일주여행경로

• 리프노드에있는 일주여행경로를 찾음

• lowerbound 가져오기

Branch-and-Bound

• Backtracking은 속해있다.

---

Minimum Spanning Tree

• 정의
• 알고리즘(Prim’s and Kruskal’s) complexities, 이게 greedy appraoch인가??

Dijkstra’s Algorithm for Single-Source Shortest Paths

• 소스코드레벨 구현

Knapsack Problem (fractional & 0-1) 차이

• Greedy approach로 Optimal(최적)한 Solution을 찾을 수 있는가? 어떨때 가능한가?
• Greedy vs. Dynamic Programming
• Backtracking & Branch-and-Bound
  • DPS, BPS, Best-First searches…
  • pruning

TSP (Traveling Salesperson Problem)

• DP vs. Greedy? or Branch-and-Bound?
• 유전 알고리즘, 다른것들과 차이, 장단점, 최적의 Solution을 가질 수 있는가?

Search Algorithms

• Actual tree searches…

  • 방문하는 노드들 & 최적경로 ()
  • 방문 트리 구성

• 장단점

• 최적의 해를 찾는 보장은?

• Complexities & 구현방법(data structures?)

---

Nonlinear Unconstrained Optimizations

• Heuristic: 짐작, 경험등 규칙을 통하여 수행하는 알고리즘
• Optimality: X

Genetic Algorithms (GE) : 유전 알고리즘

• N개의 hypotheses(가설), 유지해나가는 알고리즘
• 집단 유전학의 개체 진화 원리르 이용하는 문제해결공간 탐색 방법

• In population:
  • Selection: 어떤것을 선택할것인가
  • Crossover: Selection한 후보중 어떤식으로 Mixable 할것인가
  • Mutation: 어떻게 변이를 줄건가
  • Replacement: 새로운 N개를 대치

유전알고리즘 표현

• 순서 기반 표현: 각각의 노드들을 하나하나 index줘서 표현

선택 연산

• 교차에 쓰이는 두개의 부모 해를 고르기 위한 연산
  • 우수한 해가 선택될 확률이 높아야함

품질 비례 룰렛휠 선택

• 각 해의 품질을 평가한 다음 가장 좋은 해의 적합도가 가장 나쁜 해의 적합도의 k배가 되도록 조절
• fi = (Cw - Ci) + ( Cw - Cb ) / (k - 1), k>1
  • Cw : 해집단 내에서 가장 나쁜 해의 비용
  • Cb : 해집단 내에서 가장 좋은 해의 비용
  • Ci : 해 i의 비용

순위기반 선택

• 해잡단 내에서 해들을 품질 순으로 순위를 매긴 후 다음 가장 좋은 해부터 일차 함수적으로 적합도 배정
• fi = max + ( i - 1 ) X (min - max ) / (n - 1)

교차 연산

• 유전 알고리즘의 대표 연산
• 연산 중 가장 다양한 대안 존재

일점 교차(point crossover)

• 길이가 n인 일차원 문자열로된 염색체 상에서 일점 교차로 자르는 방법(총 n-1가지)

다점 교차(multipoint crossover)

• 염색체의 길이가 n일 때 k점 교차로 자르는 방법의 총 수는 n-1Ck가지

• 일점교차보다 교란의 정도가 커서 보다 넓은 탐색 공간을 탐색할 수 있음

• 교란이 강하면 수렴성이 떨어져 주어진 시간 예산내에 제대로 수렴하지 않을 가능성

균등 교차(uniform crossover)

• 자름선을 이용하지않음
• 이론적으로 완벽(모든 재조합 가능성 open)
• 난수를 사용

사이클 교차(cycle crossover)

• 염색체가 순열일경우 사용
• S2[index] = S1

순서 교차(order crossover)

• 염색체가 순열일경우 사용
• 한 부분집합을 고정함, 남은부분 부분집합 뒤부터 순서대로

간선 재조합

• TSP를 위해 개발된 교차연산

• 부모해의 특성을 보존, 변이가 적으면 교란이 너무 적음

• 인접도시목록을 이용하여 TRACKING

• 장단점?

  • 각각이 생각했던 최종 SOLUTION을 유지해나갈 수 있음

BFS를 이용한 유전자 재배치

• 유전알고리즘 시작 전에 문제에 깃든 정보(유전자들 간의 관계)를 이용하여 유전자들의 위치를 재배치

변이 연산

• 부모해에 없는 속성을 도입하여 탐색 공간을 넓히려는 목적을 가진 연산

전형적 변이

비균등 변이

수선

기타 변이 연산

세대형 유전 알고리즘

• 해집단 내에서 염색체가 대부분(전체) 대치되므로 대치 연산이 비교전 간단

• convergence(수렴)이 일어나기 어려움

• 안정 상태 유전 알고리즘은 한 개 또는 소수의 해가 생기는 즉시 해집단 내의 해들과 대치하게 되므로 대치될 대상을 고르는 작업이 매우 중요한 영향을 미침
  -> 부분적인 최적화가 어렵다

GA가 유용한 문제들

• 전통적 방법으로(결정론적인(deterministic)방법으로) 좋은 해를 잘 구하지 못하는 문제

GA가 소용 없는 문제들

• 결정론적 알고리즘(deterministic algorithm)으로 쉽게 풀리는 문제

• 결정론적 알고리즘(deterministic algorithm)으로 쉽게 풀리지 않으나 크기가 너무 작은 문제

  • 5-city TSP 등

• Solution Space가 가늠할 수 없는 근사치 최대값을 찾기 유용한 알고리즘이다.

GA 장단점

장점

• 빠르다 (메모리 사용량 적음) 엄청 큰 Search space에서.
• 쉽다.

단점

• Randomized - optimal하지 못하고 complete하지 못함
• local maxima에 빠질 수 있음

---

Downhill Simplex Method

• Starting Guess
• N+1 각형을 유지

N+1개의 꼭짓점 갖는 구조
하나 이상의 테스트 포인트 유지

기본적인 Operation

• 4개의 scalar parameters을 지정
  • reflection p
  • expansion w
  • contraction y
  • shrinkage a
    • Standard: p = 1, w = 2, y = 1/2 and a = 1/2

진행방식

1. Order: 어떤 포인트가 가장 유명한지 판단
2. Reflect
3. Expand
4. Contract

• outside
• inside