Категория B9 • задача №1
Условие задачи
Дано:
на соревнованиях по спортивному ориентированию участник должен пробежать от старта до финиша, преодолевая наименьшее число препятствий (их число на каждом отрезке пути указано на рисунке).
Найти:
какое наименьшее число препятствий может преодолеть спортсмен?
Решение
I этап: разбор представленной схемы.
Очевидно, что участник начинает свое движение из пункта "Старт" и заканчивает маршрут в пункте "Финиш". Также как видно из схемы, существует несколько вариантов траекторий, позволяющих участнику достичь пункта "Финиш", причем, только единственный вариант является оптимальным.
Над соединительными линиями между пунктами проставлены числа - числа, показывающие количество препятствий. Очевидно, чем больше препятствий следует преодолеть участнику, тем маршрут считается неоптимальнее, поэтому, надо стремиться к тому, чтобы на пути было как можно меньше возникающих препятствий.
II этап: устранение избыточных траекторий.
Рассмотрим изображение:
Очевидно, что путь синего цвета содержит 7-мь препятствий, а путь красного цвета содержит 8-мь препятствий, следовательно, путь красного цвета можно безболезненно устранить, так как данный маршрут не будет оптимальным.
Очевидно, что путь синего цвета содержит 7-мь препятствий, а путь красного цвета содержит также 7-мь препятствий (6 + 1 = 7) следовательно, любой из выделенных путей можно устранить. Удалим часть пути красного цвета.
Очевидно, что путь синего цвета содержит 8-мь препятствий, а путь красного цвета содержит также 8-мь препятствий (2 + 6 = 8) следовательно, любой из выделенных путей можно устранить. Удалим часть пути красного цвета.
Как видно из последней схемы, начальная карта существенно упрощена, и теперь, можно воспользоваться элементарным перебором, чтобы детерминировать оптимальный путь участника.
III этап: определение оптимального маршрута.
Выпишем в табличном варианте всевозможные маршруты участника от старта до финиша:
Маршрут участника | Количество препятствий |
2 + 2 + 7 | 11 |
Маршрут участника | Количество препятствий |
2 + 2 + 7 | 11 |
2 + 2 + 3 + 2 + 1 | 10 |
Маршрут участника | Количество препятствий |
2 + 2 + 7 | 11 |
2 + 2 + 3 + 2 + 1 | 10 |
8 + 3 + 7 | 18 |
Маршрут участника | Количество препятствий |
2 + 2 + 7 | 11 |
2 + 2 + 3 + 2 + 1 | 10 |
8 + 3 + 7 | 18 |
8 + 2 + 1 | 11 |
Как видно из заполненной таблицы, минимальное количество препятствий равно 10-ть: 2 + 2 + 3 + 2 + 1, следовательно, данный маршрут является оптимальным.
Вывод: |
10 - наименьшее число препятствий, которые может преодолеть спортсмен |
Резюме
разобрали предложенную маршрутную схему;
отсекли избыточные варианты;
среди оставшихся маршрутов выделили оптимальный путь.
Ответ: |
10 |
Комментарии