근사 알고리즘 (14) 썸네일형 리스트형 [k-Center Problem] 문제 정의 이번에 다룰 주제는 \(k\)-center problem입니다. 이 문제는 입력된 자료들을 몇 개의 덩어리로 묶음을 짓는 군집화(clustering) 문제 중 하나입니다. 군집화를 할 때 사용하는 상황이나 목적에 따라 어떤 군집이 좋고 나쁜지를 판가름하는 척도가 달라지게 될 것입니다. 이 문제의 목표는 최대한 공정하게 덩어리 짓는 방법을 찾는 것입니다. 다음 예시를 통해서 이 문제의 목표가 무엇인지 자세히 살펴보도록 하죠. 들어가기 자, 여러분이 회사를 하나 경영하고 있다고 하죠. 회사가 규모가 커서 다음 그림처럼 곳곳에 지부가 있다고 합시다. 이번에 사업을 확장하게되어 고가의 장비를 들여오게 되었습니다. 이 장비는 모든 지부의 부서들이 이용할 만큼 매우 요긴한 것이죠. 다만, 하도 가격이 비싸다보니 모.. [외판원 문제 / TSP] 크리스토피데스 알고리즘 (Christofides' Algorithm) 지난 포스팅에서 traveling salesman problem이 (우리말로 외판원 문제) 무엇인지 알아보았습니다. 안타깝게도 일반적인 거리에 대해서는 적절한 근사 알고리즘이 존재하기 어렵다는 것을 보였습니다. 하지만 metric인 경우에는 2-근사 알고리즘이 존재한다는 것을 보였습니다. 아직 보지 않으셨다면 다음 링크를 참조해 주세요. :) 2019/07/20 - [근사 알고리즘/Traveling salesman problem] - [Traveling Salesman Problem] Metricity & 2-Approximation [외판원 문제 / Traveling Salesman Problem] 메트릭 & 2-근사 (Metricity & 2-Approximation) 안녕하세요. 이번에는 trave.. [외판원 문제 / TSP] 메트릭 & 2-근사 (Metricity & 2-Approximation) 안녕하세요. 이번에는 traveling salesman problem에 대해서 알아보도록 하겠습니다. 주로 줄여서 TSP라고도 부르며, 제가 알기로 우리말로는 외판원 문제로 불립니다. 개괄적인 설명은 이전 글에서 했습니다. 2019/07/10 - [근사 알고리즘] - 근사 알고리즘 근사 알고리즘 (Approximation Algorithm) 현대 사회는 컴퓨터와 떼어낼 수 없는 관계를 맺고 있습니다. 우리는 컴퓨터를 통해 문제를 해결하고, 다른 이들과 소통하며, 여가를 즐기기도 합니다. 그렇다면, 과연 컴퓨터는 모든 것을 해줄 수 있을까요? 아.. gazelle-and-cs.tistory.com 그러니 이번에는 서두 없이 바로 문제를 정의해 보도록 하겠습니다. 문제의 입력으로 지점들의 집합 \(V\)와 .. 근사 알고리즘 (Approximation Algorithm) 현대 사회는 컴퓨터와 떼어낼 수 없는 관계를 맺고 있습니다. 우리는 컴퓨터를 통해 문제를 해결하고, 다른 이들과 소통하며, 여가를 즐기기도 합니다. 그렇다면, 과연 컴퓨터는 모든 것을 해줄 수 있을까요? 아시는 분들은 아시겠지만, 컴퓨터가 모든 것을 해결해 줄 수는 없습니다. 가장 유명한 예시로는 halting problem이 있습니다. 이는 어떤 컴퓨터 프로그램과 그 프로그램의 한 입력이 주어졌을 때, 프로그램이 언젠간 끝이 나는지 아니면 영원히 동작할지를 판단하는 문제입니다. 저명한 수학자 Alan Turing은 이 문제가 컴퓨터로는, 좀 더 정확히는 Turing machine으로는, 해결할 수 없다는 것을 증명하였습니다. 이번에는 약간 결이 다른 이야기를 해보겠습니다. 여러분들이 유명 밴드의 매니저.. 이전 1 2 다음
