Упражнения с решениями Упражнение с решением 1
Несмотря на множество серьезных недостатков, эта система, по мнению ваших друзей, обладает одной полезной особенностью. «Раз мы идем только днем, — го- ворят они, — необходимое количество стоянок сводится к минимуму».
Так ли это? Предлагаемая система выбора является жадным алгоритмом, и мы хотим определить, минимизирует ли он количество необходимых остановок.
Чтобы уточнить формулировку, сделаем несколько упрощающих предполо- жений.
Тропа будет моделироваться длинным отрезком прямой длины L; предпо- лагается, что ваши друзья могут проходить d миль в день (независимо от рельефа, погоды и т. д.) Возможные точки остановок расположены на расстояниях x1, x2, ..., xn от начала тропы. Также будем считать (очень великодушно), что ваши друзья ни- когда не ошибаются в оценке того, успеют ли они добраться до следующей точки остановки до наступления темноты.Множество точек остановки считается действительным, если расстояние между каждой смежной парой не превышает d (для первой точки считается расстояние от начала тропы, а от последней — до конца тропы). Таким образом, действительность множества точек означает, что турист будет останавливаться только в этих точках и при этом доберется до конца тропы. Естественно, предполагается, что полное множество из n точек действительно, иначе пройти весь путь не удастся.
Теперь исходный вопрос можно сформулировать следующим образом. Являет- ся ли жадный алгоритм ваших друзей (ежедневный переход на максимально воз- можное расстояние) оптимальным в том смысле, что он находит действительное множество с минимально возможным размером?
Еще по теме Упражнения с решениями Упражнение с решением 1:
- § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
- РЕШЕНИЕ
- РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
- ПРИНЯТИЕ РЕШЕНИЙ
- РЕШЕНИЯ КСУ
- Не избегайте принятия решений
- ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
- ЗАДАЧА: РЕШЕНИЕ
- Принять решение
- Управленческие решения
- Решение проблем
- КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
- Убеждения и решения
- Убеждения и решения
- НАЙДИТЕ РЕШЕНИЕ
- НАЧНИТЕ С ПРИНЯТИЯ РЕШЕНИЯ
- Получение информации и принятие решений
- Решение измениться
- Решение измениться