EDIT: Я написал до последней части, но потом понял, что не могу это доказать, поэтому я создал эту вики сообщества, чтобы кто-то с правильным знанием мог ее исправить.
Это мое решение; медведь со мной, будет какая-то математика.Предполагаю, что вы хотите минимизировать ожидаемую стоимость, что является средним из затрат, которые ваш алгоритм будет тратить на каждое из возможных значений ответа n (0 < n ≤ N).
Во-первых, какова ваша догадка о ответе? Это больше или меньше, чем N/2?
(Вы: "Меньше")
Вы говорите, что меньше? Это кажется правдоподобным, потому что выбор большего числа для начала имеет большую стоимость. Но если вы угадаете меньше, вам, скорее всего, скажут, что ответ выше, чем вы догадались. Тогда вы понесете больше затрат, потому что более высокий регион стоит больше, чтобы догадываться.
В случае невзвешенной проблемы, если вы выберете что-то меньшее, чем N/2 для начала, вам будет больше известно, что ответ выше, и вы понесете еще большую стоимость. Не хорошо.
(Вы: «Тогда это должно быть больше?»)
Ну это должно быть, если не меньше. (Если я не задал трюк, и ответ на самом деле был N/2, но я этого не сделал.) Но насколько велика? Снова рассмотрите невзвешенную проблему. Мы выбрали число посередине, т. Е. N/2. Можем ли мы выбрать что-то среднее здесь? Наиболее очевидным является число K, такое, что 1 + 2 + 3 + 4 + ... + K = (K + 1) + (K + 2) + (K + 3) + (K + 4) +. .. + N. (Это K = N/sqrt (2).) Получается, что это правильный ответ.
(Вы: «Почему Как вы можете ожидать, что я поверю вам просто так?»)
Вот почему:
Рассмотрим невзвешенную задачу первым. Почему мы сначала выбираем N/2? Неужели вы не просто поверили моему мучительному аргументу выше? Что, если вместо этого выбрать K < N/2?
(Вы: "K меньше (N - K), поэтому он не будет оптимальным.")
Ну, почему не он является оптимальным, что путь? Это не большой аргумент, если я не знал, что бинарный поиск работает в первую очередь. (Или, если я не согласен с людьми, которые научили меня, что работает бинарный поиск.) Рассмотрим следующее:
Пусть A (x) - средняя стоимость, необходимая для угадывания числа из диапазона, содержащего x элементов, и пусть S (x) - общая стоимость, т. е. S (x) = xA (x).
Допустим, мы выбрали средний элемент, N/2. Общая стоимость S (N) = S (N/2) + S (N - N/2) + N = 2S (N/2) + N. (Термин N - общая стоимость выбора среднего элемента - стоимость 1 за возможное значение ответа n)
Что делать, если мы выбрали что-то меньшее, K < N/2? Общая стоимость S (N) = S (K) + S (N - K) + N.
Чтобы показать, что выбор среднего элемента не хуже, чем выбор чего-то меньшего, нам нужно показать, что 2S (N/2) + N ≤ S (K) + S (N - K) + N, т.е. 2S (N/2) ≤ S (K) + S (N - K).
Рассмотрим функцию A (x). Это возрастающая функция, потому что, когда есть более широкий выбор, вы не сможете тратить меньше.(Я мог бы утверждать, что если бы я мог потратить меньше для большего диапазона, чем текущий, я бы просто увеличил текущий до размера большего диапазона.) * (Примечание: я не утверждаю, что функция строго потому что это не нужно в моем доказательстве.) *
Это означает, что S (x), которое является умножением identity function с возрастающей функцией, является convex function. (. Доказательство этого утверждения остается в качестве упражнения для читателя)
Следовательно, 2S (N/2) ≤ S (К) + S (N - K), является следствием Jensen's inequality. (Особый случай неравенства Йенсена требуется, это следующее: для любой выпуклой функции е, 2е (х) ≤ F (х + к) + е (х - к).)
Если вы выбираете K > N/2, аргумент аналогичен.
Теперь перейдем к вашему вопросу. Что произойдет, если он взвешен? Мы можем следовать аналогичной стратегии.
Мы переопределим S и A, чтобы принять два параметра: начало и конец диапазона (соответственно), так как это два разных диапазона одного и того же размера могут иметь разную среднюю стоимость и общую стоимость.
Если мы выбираем элемент, который, как я утверждаю, является лучшим, N/sqrt (2), общая стоимость S (1, N) = S (1, N/sqrt (2)) + S (N/sqrt (2) + 1, N) + N * N/sqrt (2).
А как насчет выбора K < N/sqrt (2)? Общая стоимость S (1, N) = S (1, K) + S (K + 1, N) + N * K.
Нам нужно будет показать, что S (1, N/sqrt (2)) + S (N/sqrt (2) + 1, N) + N * N/sqrt (2) ≤ S (1, K) + S (K + 1, N) + N * K.
A (x, y) - выпуклая функция, так как B (x, y) = A (x, y)/avg (x, y) - возрастающая функция, где avg - некоторая функция усреднения.
Доказательство этого, вероятно, потребует двумерных выпуклых функций, где f (x, y + p) - f (x, y) < = f (x + q, y + p) - f (x + q, y).
Средняя оценка может быть неплохой. Вы всегда должны предполагать, что всякий раз, когда вы придумываете стратегию, это будет против противника, который идет на самую слабую часть. Учитывая это, вы должны свести к минимуму максимум. –
@ Raziman Я согласен, что если предположить, что худший случай противник обычно разумный. Я выбрал средний/ожидаемый здесь, потому что оригинальный вопрос упоминал об этом. Надеюсь, мы согласны с тем, что мы можем рассчитать минимальную стоимость наихудшего случая во многом таким же образом, просто используя стоимость текущей гипотезы + max (стоимость наилучшего решения для каждого из двух интервалов по обе стороны от точки). – mcdowella