Задание 3
4. Рекомендации для учителей: как разбирать задачу с учениками
Посмотрите материалы К.Ю.Полякова вот здесь
1. Общие сведения
Сложность: базовая.
Примерное время решения (для тех, кто будет выполнять часть 2): 2 минуты
Тема: Математические основы информатики
Подтема: Графы
Что проверяется: Задание графа с заданными весами ребер с помощью матрицы смежности. Поиск кратчайшего пути между заданными вершинами.
Как может выглядеть задание:
Например, так.
Дана таблица, в которой указаны длины дорог между городами. Требуется найти длину кратчайшего пути между двумя указанными городами.
2.Разбор демо варианта 2017
Условие задачи
На рисунке схема дорог Н-ского района изображена в виде графа; в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Б в пункт В. В ответе запишите целое число – так, как оно указано в таблице.
Решение
Чтобы найти нужные нам вершины Б и В в весовой матрице, подсчитаем степени каждой вершины, т. е. найдем количество ребер, с которыми связана эта вершина. В матрице степень вершины - это количество непустых клето. Ниже в таблице степени вершин показаны в синем столбце (крайнем справа), а на графе показаны рядом с обозначением вершины.
По изображению на графе находим, что вершина Б имеет степень 3, а вершина В – 4. Так как в графе есть только она вершина степени 4, то вершина В - это пункт 5 (П5). Определить однозначно вершину Б мы пока не можем: в таблице это может быть П1, П2 и П4. Разберемся, какой из пунктов П1, П2 и П4 соответствует какой из вершин Б, Г и Д.
Б - единственная из этих вершин, которая соседствует с вершиной степени 2 (это вершина А). В таблице пункт степени 2 - это П6. Пункт П6 связан дорогой с П1 и не связан дорогами с П2 и П4. Поэтому вершина Б - это П1.
Теперь мы определили нужные нам вершины Б (П1) и В (П5) и можем найти ответ в весовой таблице. Смотрим на пересечение строчки П1 и столбца П5 и получаем, что искомое расстояние равно 8.
Ответ: 8.
Бонус: определим остальные вершины.
Заметим, что вершины А и Е определяются однозначно. Из вершины Е выходит одно ребро и это соответствует П3 в таблице. Вершины А имеет степень 2, и ей соответствует П6 из таблицы.
Вершина Е соединена только с одной вершиной Д. В таблице вершина Е (П3) соединена только с вершиной П4. Таким образом П4 в весовой таблице и является вершиной Д на графе.
Оставшаяся вершина П2 в весовой таблице соответствует вершине Г в графе.
3. Пример задания
2.1. Условие задачи.
Задача 2012-А2-1.
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
|
A |
B |
C |
D |
E |
F |
A |
|
2 |
4 |
|
|
|
B |
2 |
|
1 |
|
7 |
|
C |
4 |
1 |
|
3 |
4 |
|
D |
|
|
3 |
|
3 |
|
E |
|
7 |
4 |
3 |
|
2 |
F |
|
|
|
|
2 |
|
2.2. Набросок решения.
2.2.1. Перебор путей с учетом особенностей задачи
Полезно для наглядности нарисовать схему дорог (говоря «математически», - граф), соответствующий таблице. На это уйдет меньше минуты, но дальнейшее решение упростится и уменьшится риск сделать ошибку:
Задача поиска кратчайшего пути в графе – одна из классических задач информатики. Общий подход к ее решению приведен ниже. А пока воспользуемся тем, что граф в условии задачи – небольшой, и просто переберем все возможные пути. При этом – будем наблюдательными и постараемся сократить работу.
- В пункт F можно попасть только из пункта E. Поэтому достаточно найти кратчайший путь из A в E.
- Из A можно попасть только в B и C. Из B можно попасть в C и E. Нашелся путь ABE. Его длина – 2+7 = 9.
- Все остальные пути из A в E ведут через C.
- Из А в C есть 2 маршрута: “прямой» AC, его длина 4 и через пункт B, его длина 1+2=3. Т.е. кратчайший путь из A в C имеет длину 3.
- Из C в E есть 2 маршрута: “прямой» CE, его длина 4 и через пункт D, его длина 3+3=6. Т.е. кратчайший путь из C в E имеет длину 4.
- Таким образом, кратчайший путь из A в E, проходящий через C, - это путь ABCE, его длина 3+4=7. Это меньше, чем длина маршрута ABE. Значит, кратчайший путь из A в E имеет длину 7.
- А кратчайший маршрут из A в F – это маршрут ABCEF, его длина 7+2=9.
Ответ: 9.
2.2.2. Систематический перебор вершин
Выпишем все пути из A в F в алфавитном порядке и подсчитаем их длины. Можно рассматривать только пути без «хождения по кругу», то есть не рассматривать маршруты, которые через одну вершину проходят 2 раза. Итак.
Из A можно пойти только в B и C:
A→B→;
A→C→;
Разберемся с путями через B. Из B можно пойти в A (но это будет путь назад!), а также в C и E (это – разумные продолжения). Заменим в нашем списке путь A→B→ на два его возможных продолжения. Получим (новые верщины выделены жирным шрифтом):
A→B→ C→;
A→B→ E→;
A→C→;
Теперь в нашем списке – три неоконченных маршрута, они перечислены в алфавитном порядке. Снова попробуем продолжить первый из них.
Путь A→B→ C→ можно продолжить двумя способами (не считая путей назад): пойти в D или в E. Получим такой список неоконченных путей:
A→B→ C→ D→;
A→B→ C→ E→;
A→B→ E→;
A→C→;
Путь A→B→ C→ D→ можно продолжить до пути в F только одним способом – пойти в E. Получим:
A→B→ C→ D→ E→;
A→B→ C→ E→;
A→B→ E→;
A→C→;
Из E можно пойти только в F. Значит, из пути A→B→ C→ D→ E→ мы получили полный путь A→B→ C→ D→E→F. Его длина 2+1+3+3+2 = 11.
A→B→ C→ D→E→ F. Длина 2+1+3+3+2 = 11.
A→B→ C→ E→;
A→B→ E→;
A→C→;
Пути A→B→ C→ E→ и A→B→ E→ тоже можно завершить только одним способом. Теперь наш список путей будет выглядеть так:
A→B→ C→ D→E→ F. Длина 2+1+3+3+2 = 11.
A→B→ C→ E→F. Длина 2+1+4+2 = 9.
A→B→ E→ F. Длина 2+7+2 = 11.
A→C→;
Осталось разобраться с возможными продолжениями неоконченного пути A→C→. Это можно сделать точно так же, как мы поступали с продолжениями пути A→B→. У пути A→C→ есть три продолжения: A→ C→ B→E→ F, A→ C→ D→E→ F и A→C→ E→ F. Таким образом, полный список путей из A в F выглядит так:
1) A→B→ C→ D→E→ F. Длина 2+1+3+3+2 = 11.
2) A→B→ C→ E→ F. Длина 2+1+4+2 = 9.
3) A→B→ E→ F. Длина 2+7+2 = 11.
4) A→C→ B→ E→ F. Длина 4+1+7+2 = 14.
5) A→C→ D→ E→ F. Длина 4+3+3+2 = 12.
6) A→C→ E→ F. Длина 4+4+2 = 10.
Кратчайший путь: A→B→ C→ E→ F, его длина – 9.
Ответ. Длина кратчайшего пути: 9. Правильный вариант ответа: 1.
Замечание. На практике перебор можно уменьшить. Например, если неоконченный путь длиннее, чем уже найденный полный путь, то этот неоконченный можно не продолжать. Другой пример. Сравнивая пути A→B→ C→ D→E→ F и A→B→ C→ E→ F (пути 1) и 2) ), мы выяснили, что путь C→ E→ F короче, чем путь C→ D→E→ F. Поэтому при продолжении пути A→C→, вариант A→C→ D→ E→ F можно не рассматривать.
Подобные соображения можно систематизировать и получить более экономный алгоритм поиска кратчайшего пути – алгоритм Дейкстры (Эдгар Дейкстра, 1 мая 1930 г. — 6 августа 2002 – выдающийся голландский ученый, один из создателей современного программирования). Сильным ученикам его можно объяснить, однако для выполнения ЕГЭ в этом нет необходимости.
4. Еще примеры заданий.
3.1. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
|
A |
B |
C |
D |
E |
F |
A |
8 |
3 |
|
|
|
|
B |
8 |
|
9 |
|
4 |
|
C |
3 |
9 |
|
3 |
8 |
|
D |
|
|
3 |
2 |
|
|
E |
|
4 |
8 |
2 |
|
7 |
F |
|
|
|
|
7 |
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
3.2. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
A |
B |
C |
D |
E |
F |
|
A |
2 |
19 |
||||
B |
2 |
11 |
3 |
8 |
||
C |
11 |
4 |
||||
D |
3 |
2 |
||||
E |
19 |
8 |
4 |
2 |
6 |
|
F |
6 |
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
3.3. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
|
A |
B |
C |
D |
E |
F |
A |
4 |
8 |
24 |
|||
B |
4 |
3 |
||||
C |
8 |
3 |
3 |
8 |
14 |
|
D |
3 |
12 |
||||
E |
8 |
5 |
||||
F |
24 |
14 |
12 |
5 |
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
3.4. Между населёнными пунктами A, B, C, D, E, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
|
A |
B |
C |
D |
E |
F |
Z |
A |
3 |
7 |
29 |
||||
B |
3 |
2 |
|||||
C |
7 |
2 |
4 |
7 |
14 |
||
D |
4 |
99 |
11 |
||||
E |
7 |
99 |
5 |
||||
F |
14 |
11 |
5 |
5 |
|||
Z |
29 |
5 |
Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).
Решение. Есть прямой путь из A в Z, его длина 29. Поищем другие пути.
Видно, что сначала нужно попасть из A в C, потом - из C в F и, наконец, из F в Z. И на каждом из этих участков надо выбрать самый короткий маршрут.
Из А в С есть два маршрута – по дороге AC и через пункт B. Второй маршрут короче – его длина 3+2 = 5.
Из C в F есть много маршрутов. Однако дорога DE очень длинная и ехать по ней заведомо не стоит – получится маршрут более длинный, чем по дороге AZ. Осталось сравнить длины двух маршрутов – CDF и CEF. Более короткий маршрут – CEF, его длина 7+5 = 12 (длина маршрута CDF равна 4+11 = 15).
Наконец, из F в Z есть единственная дорога, ее длина 5. Таким образом, кратчайший маршрут из A в Z (не считая прямой дороги AZ) = это маршрут ABCEFZ. Его длина 5+ 12 + 5 = 22 < 29. Таким образом, длмна кратчайшего пути из A в Z равна 22.
Ответ: 22
3.5 Между населёнными пунктами A, B, C, D, E, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
|
A |
B |
C |
D |
E |
F |
Z |
A |
3 |
7 |
11 |
27 |
|||
B |
3 |
31 |
9 |
||||
C |
7 |
31 |
3 |
||||
D |
11 |
9 |
3 |
6 |
11 |
14 |
|
E |
6 |
33 |
7 |
||||
F |
11 |
33 |
5 |
||||
Z |
27 |
14 |
7 |
5 |
Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).
Правильные ответы: 3.1: 15; 3.2: 15; 3.3: 20; 3.4: 22; 3.5: 23
5. Рекомендации для учителей: как разбирать задачу с учениками
Эти рекомендации – не догма, а попытка сделать выводы из собственного опыта. Ждем комментариев и Ваших рекомендаций.
В разделе 2 приведены два решения.
Второе решение лучше тем, что оно может быть выполнено «автоматически», в отличие от первого, оно не требует от ученика никаких догадок. Если граф путей по сложности примерно такой, как в демо-версии, или даже немного сложнее, на такое решение вполне хватит двух минут. При переборе можно использовать соображения, приведенные в замечании.
В первом решении используются два дополнительных соображения. Первое соображение – выделение «узких мест», которые разбивают граф на подграфы меньшего размера; такие подграфы можно исследовать независимо или почти независимо друг от друга. В рассмотренном примере «узкие места» - это вершины D и E. Второе соображение – «длинные» ребра можно игнорировать. В примере таким ребром является ребро BE.
Таким образом, при разборе этого задания с учениками можно поступать так.
1) Научить учеников уверенно рисовать граф по заданной таблице.
2) Научить решать задачу полным перебором путей (второе решение).При этом обращать внимание на особенности задачи (как в первом решении).
3) Для сильных учеников – потренироваться в решении задачи с учетом особенностей («длинные ребра», «узловые точки» - как в первом решении).
4) *Для сильных учеников - обсудить аналогию между заданием 2 и заданием 26 (С3). Решение задания 2 с помощью составления таблиц (второе решение задачи 26 (С3)). См. лекцию М.А.Ройтберга "Графы. Подсчет путей и вариантов" в разделе ВИДЕО.
19 комментариев
почему в А2.4 ответ 1?
как получить 22?
обьясните, пожалуйста
Выложил решение. Извини, что не сразу ответил. Что непонятно - пиши. Успехов!
A2.2
ответ будет №1 т.е 13
а у вас в ответах A2.2: №2 т.е 15
это опечатка?
Спасибо! Исправил. Наконец, понял, о чем писали михалыч и my65daysofstatic. И вам, ребята, спасибо!
опечатки вернулись обратно: цифры в условии и в решении расходятся
В связи с атакой на сайт мы откатились к более ранней версии сайта. Приносим извинения 🙁
Пересмотрел А2, исправил два бага. Уточните пож, что Вы имеете в виду Спасибо!
прочитайте еще раз пост михалыча и исправьте опечатку пожалуйста. и в таблице первого задания четверка не на месте стоит
Спасибо, четверку передвинул. 🙂
А что с михалычем? У него вроде про A2.2, A2.3 . Или я ччего не досмотрел?
у меня никак не получается с этим графиком... да и вообщем с задачей туговато...(((
Не с графмком, а с графом 🙂 Посмотри здесь http://kpolyakov.narod.ru/download/A2.doc
Я прорешала А2 варианта №5 и у меня получилось 24.
Из А в С (7), из С в Д (3), из Д в Z (14).
Сумма 24. Короче пути не нашла.
ACDEZ Длина 7+3+6+7 = 23
Ребята! Рисуйте графы (т.е. картинки, как показано при разборе демо)!
задача простая, будет обидно сделать ошибку
Ребята! При решении этой задачи стоит рисовать картинку (как показано при разборе демо). Если что непонятно - пишите. Удачи!
опечатки нет Всё верно ты не правильно посчитал!
а2.3
вообще правильного варианта нет
НЕ СОГЛАСЕН.
ABCEF Длина:4+3+8+5=20
Как и написано в ответе, вариант 2
а2.2
ответ никак не 2, кратчайший путь равен 13, 15 никак не набрать.
НЕ СОГЛАСЕН
АBDEF. Длина: 2+3+2+6 = 13
А кратчайший маршрут из A в F – это маршрут ABCEF, его длина 7+2=9.
опечатка, должно быть 9+2 = 11