Guessing Game Weighted Best Guess

Question

Я столкнулся со следующим вопросом в интервью для стажировки, и я все еще не задавался вопросом, какое лучшее решение для него.

Вопрос:

Предположим, вы играете в угадайку. Вы можете угадать число от 1 до n, и у вас есть api, чтобы рассказать вам, если вы выше или ниже.

Теперь предположим, что каждое предположение взвешивается (т.е. вы догадываетесь 20, так что стоимость 20)

Создать алгоритм, чтобы найти лучшее первое предположение, что сводит к минимуму затраты.

То, что я думал:

В нормальном варианте задачи (без весов) решение тривиально бинарный поиск.

В этом случае, однако, мне кажется, что мне нужно будет провести анализ среднего случая по всем возможным вариантам догадок, которые взорвут сложность решения. Например, я начинаю с предположения о 20, поэтому я включаю стоимость, если число было 20, а затем найти следующее лучшее предположение (учитывая, что я больше не могу угадать 20), выполняя аналогичную операцию на меньшем пространстве. Я выполняю это для всех первых догадок, а затем беру минимум.

Любая помощь будет оценена по достоинству.

Answer 1

Я думаю, что это динамическая задача программирования, и вы будете в конечном итоге разработка стоимости наилучшей стоимости для всех отрезков [I, J] с 1 < = я < = у < = 20.

Для i = j стоимость угадывания {i} равна i.

Чтобы найти наилучшую стоимость угадывания на интервале [i, j], вы учитываете все возможные догадки k для i < = k < = j. Общая стоимость с использованием предположения k является k + p * лучшей стоимостью для [i, k-1] + q * лучшей стоимости для [k + 1, j]. (оценка 0 для [i, j] при i> j). Предполагая, что вы собираетесь на среднюю стоимость, тогда p будет (k - i)/(j + 1 - i), а q будет (j - k)/(j + 1 - i), и это должны быть вероятности того, находится в [i, k - 1] и [k + 1, j].

Вы начинаете с наилучшей стоимости для всех интервалов размера 1. Из них вы можете рассчитать оптимальную стоимость для всех интервалов размера 2, и оттуда вы сможете найти оптимальную стоимость для всех интервалов размера 20 Затем вы обычно возвращаетесь, чтобы узнать, какие решения принимаются на каждом этапе, возможно, используя информацию, которую вы сохранили, когда вы вычислили затраты. Но в вашем случае вам нужно только знать наилучшее первое предположение, поэтому вы можете просто сохранить это, когда вы его вычислите.

Для N = 20 у вас есть O (N^2) наилучшие издержки для разработки, при этом каждая стоимость занимает не более O (N), поэтому у нас есть алгоритм O (N^3). Не большой, но ничего подобного экспоненциальный, а для N = 20 вполне доступным.

Answer 2

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).