랭킹 (1) 썸네일형 리스트형 온라인 이분 매칭 랭킹 알고리즘 (Ranking Algorithm for Online Bipartite Matching) 지난번에 온라인 이분 매칭 문제(online bipartite matching problem)에 대해서 알아 보았습니다. 그 문제는 다음과 같이 정의되었습니다. 처음에는 가용할 수 있는 택시 몇 대가 주어진다. 이후 시간이 흐르면서 승객이 한 명씩 들어오며, 그때마다 그 승객을 태울 수 있는 택시가 무엇인지 정해진다. 이 승객을 태울 수 있는 택시 중 이전에 승객을 한 명도 태우지 않은 택시 가운데 한 대를 골라 이 승객을 태우든지, 아니면 승객을 태우지 않을 것을 바로 결정해야 한다. 이 결정은 번복될 수 없다. 이때 목표는 승객을 최대한 많이 태우는 것이다. 저번 글에서 공부한 내용을 요약하면 다음과 같습니다. 승객이 매번 들어올 때마다 가능한 택시 중 아무 하나에 이 승객을 태우는 방법은 1/2의 .. 이전 1 다음
