Simplex Method1 선형 계획법과 치환 (1) - Examples of LP References Algorithms (Sanjoy Dasgupta) Contents Introduction to Linear Programming Reduction (치환) Simplex Method 최단 경로나 최소 비용 신장 트리(cheapest spanning tree), 최장 증가 부분 수열(longest increasing subsequence)와 같은 알고리즘들에 대한 많은 문제들은 최적화(optimization) 작업들입니다. 이와 같은 경우, (1) 특정 제약(예를 들어, 경로는 반드시 그래프의 간선을 사용해야 하고, s에서부터 t로 이동해야 하며 트리의 모든 노드를 지나야 한다)을 만족하고, (2) 잘 정의된 기준에 부합하면서 이들 제약들을 만족하는 모든 솔루션 가운데 가장 최적의 솔.. 2022. 4. 16. 이전 1 다음
