Блог

Я зашел в тупик из-за этой домашней задачи. Я думаю, что у меня есть правильный ответ, но я не уверен, как это доказать. Я также не уверен в том, как подойти к доказательству. Вот в чем проблема:

Профессор Гекко всегда мечтал покататься на роликовых коньках по Северной Дакоте. Он планирует пересечь штат по шоссе США 2, которое проходит от Гранд-Форкса, на восточной границе с Миннесотой, до Уиллистона, недалеко от западной границы с Монтаной. Профессор может нести два литра воды, и он может проехать m миль, прежде чем у него закончится вода. (Поскольку Северная Дакота относительно равнинная, профессору не нужно беспокоиться о том, что на участках с подъемом расход питьевой воды больше, чем на плоских участках с подъемом) Профессор начнет в Гранд-Форксе с двумя полными литрами воды. На его официальной карте штата Северная Дакота показаны все места вдоль США 2, где он может пополнить запас воды, и расстояния между этими местами.

Цель профессора — минимизировать количество остановок под водой на его маршруте по штату. Дайте эффективный метод, с помощью которого он может определить, какие остановки воды он должен сделать. Докажите, что ваша стратегия дает оптимальное решение, и укажите время его выполнения.

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

Я не уверен, как поступить. Я бы поспорил, что это делалось раньше, но я довольно новичок в этой области CS и мог бы воспользоваться некоторыми рекомендациями.

Ваш алгоритм верен.

Попробуйте доказать следующее путем индукции по количеству пройденных остановок. После прохождения каждой точки с водой никакая другая стратегия не могла бы сделать меньше остановок, а из тех, которые сделали одинаковое количество остановок, никакая другая стратегия не может оставить вам больше воды.

При 0 остановках все стратегии равны, поэтому доказать утверждение тривиально.

Если вы не пьете на остановке в соответствии с этой стратегией, результат легко доказать.

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

Этого достаточно, чтобы заполнить индукционное доказательство.

Если вы затрудняетесь с концепцией того, что требуется для формального доказательства и как это сделать, посмотрите, Как я делаю доказательства. Я также написал в блоге о своем опыте использования этого раздаточного материала здесь.

Я надеюсь, что моя первая попытка действительно удалена. Это было неправильно.

Эскиз доказательства: если greedy потерпел неудачу, должно быть, оптимальным было выбрать город ближе к начальной точке (дальше от финишной черты), чем тот, который greedy выбрал в какой-то момент. Игнорируйте проблему вплоть до этого выбора и посмотрите на две подзадачи: одна начинается с города, выбранного greedy, а другая — которая включает в себя точку greedy в подзадаче. Чтобы избежать противоречия, город, начинающийся дальше от финишной черты, должен иметь оптимальное решение с меньшим количеством переходов, чем оптимальное решение, начинающееся в жадной точке. Игнорируйте, как вы приходите к этому оптимальному решению для обеих подзадач, только то, что оно существует. Поскольку нежадная начальная точка включает в себя жадную подзадачу, она должна либо иметь те же оптимальные переходы по подпути, либо больше (Докажите это утверждение. Это можно сделать методом индукции, но я полагаю, что есть более простое доказательство, о котором я просто слишком устал думать. Возможно, вы можете просто сказать, что это очевидно?). Если они были равны, то жадность работала нормально. Если их больше, противоречие.

Хитрость с такого рода вопросами заключается в том, чтобы сформулировать проблему как другую проблему, для которой вы можете что-то доказать.

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