Упражнения с решениями Упражнение с решением 1

Предположим, что трое ваших друзей, вдохновившись неоднократными про- смотрами культового фильма «Ведьма из Блэр», решили отправиться по Аппа- лачской тропе. Они хотят проходить как можно большее расстояние в дневное время, но по очевидным причинам не после наступления темноты.
На карте обозначено множество хороших точек для разбивки лагеря. Чтобы выбрать место для остановки, они используют следующее правило: подходя к очередной возможной точке, они определяют, удастся ли им добраться до следующей точки до наступления темноты. Если время позволяет, то они продолжают идти, а если нет — останавливаются.

Несмотря на множество серьезных недостатков, эта система, по мнению ваших друзей, обладает одной полезной особенностью. «Раз мы идем только днем, — го- ворят они, — необходимое количество стоянок сводится к минимуму».

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

Чтобы уточнить формулировку, сделаем несколько упрощающих предполо- жений. Тропа будет моделироваться длинным отрезком прямой длины L; предпо- лагается, что ваши друзья могут проходить d миль в день (независимо от рельефа, погоды и т. д.) Возможные точки остановок расположены на расстояниях x1, x2, ..., xn от начала тропы. Также будем считать (очень великодушно), что ваши друзья ни- когда не ошибаются в оценке того, успеют ли они добраться до следующей точки остановки до наступления темноты.

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

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Упражнения с решениями Упражнение с решением 1:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. РЕШЕНИЕ
  3. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  4. ПРИНЯТИЕ РЕШЕНИЙ
  5. РЕШЕНИЯ КСУ
  6. Не избегайте принятия решений
  7. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
  8. ЗАДАЧА: РЕШЕНИЕ
  9. Принять решение
  10. Управленческие решения
  11. Решение проблем
  12. КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
  13. Убеждения и решения
  14. Убеждения и решения
  15. НАЙДИТЕ РЕШЕНИЕ
  16. НАЧНИТЕ С ПРИНЯТИЯ РЕШЕНИЯ
  17. Получение информации и принятие решений
  18. Решение измениться
  19. Решение измениться