Алгоритм обхода графика с поворотом - минимальное количество остановок

Question

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

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

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

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

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

Answer 1

Ваш алгоритм правильный.

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

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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