Использование метода динамического программирования при решении задания №13 ЕГЭ по информатике
Инфоурок Информатика СтатьиИспользование метода динамического программирования при решении задания №13 ЕГЭ по информатике

Использование метода динамического программирования при решении задания №13 ЕГЭ по информатике

Скачать материал

Использование метода динамического программирования при решении задания №13 ЕГЭ по информатике

Динамическое программирование  — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной [1].

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

Задание №1

Рассмотрим на примере конкретную задачу поиска количества путей в графе. Это задание №15 ЕГЭ по информатике.

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? [2]

Первое, что приходит в голову – это пересчитывать количество путей вручную, начиная с вершины А  и заканчивая вершиной К. Используя этот метод легко допустить ошибку и запутаться в подсчете. 

Чтобы не ошибиться в расчетах будем записывать количество путей для каждой вершины в таблицу (см. таб. 1).  Для вершины A  есть один способ оставаться в ней и никуда не идти. Запишем число 1 в столбец А.  В вершину Б мы можем попасть только из вершины А (смотрим на стрелку). Значит, число способов попасть в вершину Б равно 1. В город В можно попасть из города А, Б или Г (смотрим на стрелки, входящие в вершину В). Количество путей для вершин А и Б уже было рассчитано. Чтобы определить количество способов попасть в город В, определим число способов попасть в Г. В вершину Г можно попасть только из А. Следовательно, количество способов попасть в город В=А+Б+Г=1+1+1=3. В вершину Д можно попасть из Б или из В. Количество способов для вершины В мы уже рассчитали, поэтому количество способов попасть в  Д=Б+В=1+3=4.   

В город  Е можно попасть только из города Г, поэтому поставим в этом столбце число 1. В город Ж можно попасть из Д, из В, либо из Е. Для вершины Д количество способов мы уже рассчитали (4 способа), для вершины В – 3 способа и для Е – 1 способ. Значит, количество способов попасть в город Ж=4+3+1=8. В город И можно попасть только из города  Д, а значит число способов попасть в город И равно 4. Наконец, в вершину К можно попасть из И, Ж или Е. Просуммируем уже рассчитанные способы для этих вершин.

 

A

Б

В

Г

Д

Е

Ж

И

К

1

1

А+Б+Г

(1+1+1=3)

1

Б+В

(1+3=4)

1

Д+В+Е

(4+3+1=8)

4

И+Ж+Е

(4+8+1=13)

табл. 1

Следовательно, общее количество способов попасть из города А в город К равно 13.

Ответ: 13.

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

Разберем несколько примеров, где может быть использован описанный метод.

Задание №2

На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н. Сколько существует различных путей из пункта А в пункт Н, не проходящих через пункт Е? [3]

Решение

Задание №2 будем также решать методом динамического программирования. Построим таблицу, в которую будем записывать количество возможных путей для каждой вершины. До вершины Е идем согласно заданию №1. Так как по условию задания нам следует исключить пути, проходящие через пункт Е, то для этой вершины не будем считать количество путей. Проще всего в таблицу в столбец Е поставить число 0. Для остальных вершин правило заполнения таблицы не изменится (см. таб. 2). 

А

Б

В

Г

Д

Е

Ж

И

К

Л

М

Н

1

1

2

А+В

(1+2=3)

Б+В

(1+2=3)

0

3

Е+В+Г

(0+2+3=5)

Ж+Д+Е+И

(3+3+0+5=11)

11

11

Л+М+К

11+11+11=33

 

таб. 2

Заполнив таблицу, получим количество путей из пункта А в пункт Н, равное 33.

Ответ: 33.

Задание №3

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, 3, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город М, проходящих через город Л, но не проходящих через город Е? [4]

Решение

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

А

Б

В

Г

Д

Е

Ж

З

И

К

Л

М

1

1

А+Б+Г

(1+1+2=4)

А+Д

1+1=2

1

0

Е+В+З

(0+4+7=11)

В+Г+Д

(4+2+1=7)

Е+Ж+З

(0+11+7=18)

0

18

18

Таб. 3

Ответ: 18.

Итак, метод динамического программирования может с успехом применяться при решении заданий на подсчёт количества путей в графе.

Список использованных источников

1.      Википедия: [Электронный ресурс]. URL: https://ru.wikipedia.org/wiki/Динамическое_программирование (Дата обращения: 17.06.2019).

2.      Решу ЕГЭ: [Электронный ресурс]. URL: https://inf-ege.sdamgia.ru/test?id=4982063 (Дата обращения: 17.06.2019).

3.        Решу ЕГЭ: [Электронный ресурс]. URL: https://inf-ege.sdamgia.ru/test?theme=361 (Дата обращения: 17.06.2019).

4.      Решу ЕГЭ: [Электронный ресурс]. URL: https://inf-ege.sdamgia.ru/test?theme=365

(Дата обращения: 17.06.2019).

5.      С. М. Окулов, О. А. Пестов. Динамическое программирование, М.:, Бином, 2012.

 

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

Пожаловаться на материал
Скачать материал

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

также Вы можете выбрать тип материала:

Проверен экспертом

Общая информация

Учебник: «Информатика (базовый и углублённый уровни) (в 2 частях)», Поляков К.Ю., Еремин Е.А.
Тема: § 45. Динамическое программирование
Скачать материал

Похожие материалы

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.