weightedmatching (2) 썸네일형 리스트형 온라인 메트릭 이분 매칭 (Online Metric Bipartite Matching) 지난 포스트에서는 온라인 가중치 이분 매칭(online weighted bipartite matching)에 대해서 알아 보았습니다. 이 문제에서는 택시에 대한 정보는 미리 알고 있으며, 승객의 정보는 시간이 흐르면서 한 명씩 들어옵니다. 매 순간 어떤 승객의 정보가 알려질 때마다 우리는 이 승객을 택시에 할당할지 말지를 결정해야 하며, 만약 할당한다면 어느 택시에 태울지도 결정해야 합니다. 지난 포스트에서는 언젠가 승객을 어떤 택시에 할당했을 때 이를 더이상 번복할 수 없다면 좋은 경쟁비(competitive ratio)를 얻을 수 없다는 것을 확인하였습니다. 자세한 사항은 이전 포스트를 참고하시기 바랍니다. 2021.02.14 - [온라인 알고리즘/Online matching] - 온라인 가중치 이분.. 온라인 가중치 이분 매칭 (Online Weighted Bipartite Matching) 저번 글에서는 온라인 이분 매칭 문제(online bipartite matching problem)가 무엇인지 설명하고 이를 경쟁적으로 해결하는 알고리즘에 대해서 알아 보았습니다. 문제를 간략히 다시 소개하도록 하겠습니다. 처음에는 가용할 수 있는 택시 몇 대가 주어진다. 이후 시간이 흐르면서 승객이 한 명씩 들어오며, 그때마다 그 승객을 태울 수 있는 택시가 무엇인지 정해진다. 이 승객을 태울 수 있는 택시 중 이전에 승객을 태운 적이 없는 택시 가운데 하나를 골라 이 승객을 태우든지, 아니면 승객을 태우지 않을 것을 매번 바로 결정해야 한다. 이 결정은 차후에 번복될 수 없다. 이때, 최대한 많은 승객을 태우시오. 위 예시에서 한 가지 현실과는 약간 동떨어진 점이 있다면 바로 건당 정액을 받는 수익 .. 이전 1 다음
