스키 렌탈 문제와 같은 온라인 알고리즘을 해결하려고하는데 문제가 조금 다릅니다.온라인 알고리즘 - 스키 대여
문제는 내가 N 상자가 있고 각 상자에 X < M < Y와 각각 다른 상자에서 다를 수있는 M 동전이 있다는 것입니다. 하나의 상자를 선택하여 동전 수를 확인할 수 있으며이 상자를 선택하거나 건너 뛰어도됩니다 (이 상자를 건너 뛸 경우 나중에이 상자로 돌아갈 수 없음).
내 목표는 동전 수를 최대화하기 위해 하나의 상자를 선택하는 것입니다.
알고리즘이 매개 변수 G를 선택하고 첫 번째 상자를 열고 동전 수가 G보다 크면 상자를 선택하고 아무 것도 선택하지 않은 경우 어쨌든 마지막 상자를 선택합니다.
당신이 먼저 N/E 박스 (E = 2.7 ...) 확인하실 수 있습니다 N 박스가 알고있는 경우 오프라인 솔루션
에 대해 경쟁 배급을 최적화하며, 최대 상자를 추적 할 G를해야한다 무엇 (모두 건너 뛰면 최대 값을 찾습니다.) 이제는 G = 최대 크기입니다. 그 다음에 G보다 크거나 상자를 마지막으로 선택하지 않으면 첫 번째 상자를 선택하십시오.
Chris가 그의 코멘트에서 언급했듯이 이것은 Secretary Problem이며이 문제에 대한 최적의 해결책은 링크에서 더 자세히 볼 수 있지만 잘 모르겠습니다. 주어진 알고리즘이 있다면 무엇을 선택합니까? G는 의미하니? 입력 분포 및 몇 가지 추가 정보에 따라 다릅니다.
감사합니다. 의견을 말씀 드린 바 있지만, 내가 언급 한대로 알고리즘을 변경할 수는 없지만 변경할 수있는 것은 변경 사항입니다. 최대 동전을 얻기 위해 (내가 더 명확하게하기 위해 질문을 편집 한 것처럼) 최적의 해결책을 얻으려면 +1 ( – csuo
) +1. 이것은 비서 문제 http://en.wikipedia.org/wiki/Secretary_problem입니다. 또한, e = 2.71828 ... –
@mahD 알고리즘에 아무런 영향을 미치지 않고'G'를 어떻게 바꿀 수 있을지 모르겠습니다. –
상수 G를 설정하면 데이터를 알고있는 상대방이 데이터를 준비했다고 가정해야합니다. 그들은 당신에게 그것을 선택하게하는 상자를 줄 수 있고 마지막 상자에 Y가 포함되도록하여 오프라인 알고리즘 Y/G 시간을 더 수익성있게 만듭니다. OTOH 그들은 당신에게 그것을 거부 할 수있는 상자를 줄 수 있고 마지막 상자에 X가 포함되도록하여 오프라인 알고리즘 G/X 시간을 더 수익성있게 만듭니다. 그다음 가장 나쁜 G는 sqrt (XY) 인 것처럼 보이며,이 경우 오프라인 알고리즘은 sqrt (Y/X) 배 더 수익성이 있습니다.
상자를 받기 전에 G를 무작위로 선택하는 옵션이 있습니까?이 경우 적의 배포 만 알면됩니까? X = 1 일 때 간단한 예제에 대한 유망한 행동을 기반으로, 나는 ln X와 ln Y 사이에서 무작위로 ln G를 선택 하겠지만, 아마도이 경우 더 좋은 해결책이있을 것이다. 그것들을 찾는 한가지 방법은 불연속 값만을 고려하는 것입니다.이 값은 아마도이 예제에서 실제적인 경우 일 것입니다. 그런 다음 상황을 당신과 당신의 적 사이의 제로섬 게임으로 간주하십시오.
X와 Y는 무엇입니까? 주어진 값? –
문제를 잘 설명하고, 모호함이 너무 많으며 원하는 결과가 무엇인지 모릅니다. –
X는 최소값입니다. 각 상자에있는 동전, 그리고 Y는 각 상자에있는 동전의 최대 개수입니다. 즉, 각 상자에 Y 동전 이상을 가질 수는 없습니다. – csuo