Между населенными пунктами abcd построены дороги. Ещё пример задания

Представляю решение 3 задания ОГЭ-2016 по информатике из проекта демоверсии. По сравнению с демоверсией 2015 года, 3 задание не изменилось. Это задание на умение анализировать формальные описания реальных объектов и процессов (формализация описания реальных объектов и процессов, моделирование объектов и процессов).

Скриншот 3 задания.

Задание:

3. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.

Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

1) 4
2) 5
3) 6
4) 7

На основании таблицы, которая дана в задании, строим граф. Из пункта А можно попасть в пункты В, С и D, а из них — в C, D, E и т.д. Не забываем, что нам нужно именно в пункт E (некоторые варианты можно сразу отбросить, т.к. дорога до пункта Е по ним будет однозначно длинной). Затем подсчитаем длину пути по каждому маршруту и выберем наименьший из них.

ABCE=2+1+2=5
ACE=5+2 =7
ADCE=1+3+2=6

В нашем случае это маршрут АВСЕ (2+1+2=5) .

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.

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:

Разберемся с путями через B. Из B можно пойти в A (но это будет путь назад!), а также в C и E (это – разумные продолжения). Заменим в нашем списке путь A→B→ на два его возможных продолжения. Получим (новые верщины выделены жирным шрифтом):

A→B→ C →;

A→B→ E →;

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

Путь A→B→ C→ можно продолжить двумя способами (не считая путей назад): пойти в D или в E. Получим такой список неоконченных путей:

A→B→ C→ D →;

A→B→ C→ E →;

Путь A→B→ C→ D→ можно продолжить до пути в F только одним способом – пойти в E. Получим:

A→B→ C→ D→ E →;

A→B→ C→ E→;

Из 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→ 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→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 построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)



	8

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

3.2. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

3.3. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

3.4.

Решение. Есть прямой путь из 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 и Z (при условии, что передвигаться можно только по построенным дорогам).

Правильные ответы : 3.1: 15; 3.2: 15; 3.3: 20; 3.4: 22; 3.5: 23

В разделе 2 приведены два решения.

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

В первом решении используются два дополнительных соображения. Первое соображение – выделение «узких мест», которые разбивают граф на подграфы меньшего размера; такие подграфы можно исследовать независимо или почти независимо друг от друга. В рассмотренном примере «узкие места» - это вершины D и E. Второе соображение – «длинные» ребра можно игнорировать. В примере таким ребром является ребро BE.

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

1) Научить учеников уверенно рисовать граф по заданной таблице.

2) Научить решать задачу полным перебором путей (второе решение).При этом обращать внимание на особенности задачи (как в первом решении).

3) Для сильных учеников – потренироваться в решении задачи с учетом особенностей («длинные ребра», «узловые точки» - как в первом решении).

4) *Для сильных учеников - обсудить аналогию между заданием 2 и заданием 26 (С3). Решение задания 2 с помощью составления таблиц (второе решение задачи 26 (С3)). См. лекцию М.А.Ройтберга "Графы. Подсчет путей и вариантов" в разделе

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.

РЕШЕНИЕ

Таким образом, чертим остальные точки, отбрасывая повторяющиеся отрезки. Например, отрезок AB=2 и отрезок BA=2 это одно и тоже, поэтому BA не пишем. После того, как схема готова, необходимо выписать все возможные варианты получившимся отрезков. Отрезки обязательно должны начинаться с A и заканчиваться E, как того требует условие задачи. Удобнее всего выписать отрезки в виде таблицы(см. рисунок). Как видно из таблицы, получилось 3 отрезка: ABCE = 5, ACE=7 и ADCE = 6. В задаче требуется определить длину кратчайшего пути между пунктами A и Е. Кратчайший путь-это минимальное число из получившимся отрезков. Этому требованию соответствует цифра 5, а это 2 вариант ответа.

Ответ: 2

Чтобы получить хороший старт в сфере ИТ и использовать время учебы с максимальной эффективностью, очень важно правильно выбрать .

Самостоятельная работа

На рисунке справа схема дорог Н-ского района изображена в виде графа; в таблице слева содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Б в пункт В. В ответе запишите целое число – так, как оно указано в таблице.
Ответ напишите в комментариях этого поста

Такой тип задач встречается под номером 3 в тексте ОГЭ по информатика.

Пример 1

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Решение:

1. Построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4):

2. Для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее

4. Новые маршруты из С – в D и E (длины путей соответственно 3 и 4):

5. Новый маршрут из D – в E (длина пути 3):

6. Новый маршрут из E – в F (длина пути 2):

7. Нужно проехать из А в F, по схеме видим, что в любой из таких маршрутов входит ребро EF длиной 2; таким образом, остается найти оптимальный маршрут из A в E

8. Попробуем перечислить возможные маршруты из А в Е:

А – В – Е длина 9
А – В – С – Е длина 7
А – В – C – D – Е длина 9
А –C – Е длина 8
А –C – B – Е длина 12
А –C – D – Е длина 10

9. Из перечисленных маршрутов кратчайший – A-B-C-E – имеет длину 7, таким образов общая длина кратчайшего маршрута A-B-C-E-F равна 7 + 2 = 9

10. Таким образом, правильный ответ - 9.

Пример 2

Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 4
2) 5
3) 6
4) 7

Решение:

1. Построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B, C и D (длины путей соответственно 2, 5 и 1)

2. Для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее. Например, ВА=АВ=2. Если нижняя часть таблицы отличается от верхней, то строим отдельный маршрут. В задачах, как правило, таблица симметрична.

3. Из вершины В можно проехать в вершину C (длина пути 1):

4. Из вершины C можно проехать в вершины D, E (длины путей 3 и 2):

5. Нужно проехать из А в Е, по схеме видим, что в любой из таких маршрутов входит ребро СE длиной 2; таким образом, остается найти оптимальный маршрут из A в С

Попробуем составить все возможные варианты маршрутов из точки А в точку С:

А-С = 5
А-В-С = 3
А-D-С = 4

Видно, что самый короткий маршрут от А до С это маршрут А-В-С. Добавляем последнее ребро С-Е, получим длину маршрута А-В-С-Е = 3 + 2 = 5. Это второй вариант ответа.

Ответ: 2

Каталог заданий.
Поиск оптимального маршрута по таблице

Сортировка Основная Сначала простые Сначала сложные По популярности Сначала новые Сначала старые
Пройти тестирование по этим заданиям
Вернуться к каталогу заданий
Версия для печати и копирования в MS Word

	A	B	C	D	E	F
A		4
B	4		6	3	6
C		6			4
D		3			2
E		6	4	2		5
F					5

Решение.

Варианты маршрутов:

A-B-C-E-F. Длина маршрута 4 + 6 + 4 + 5 = 19

A-B-D-E-F. Длина маршрута 4 + 3 + 2 + 5 = 14

A-B-E-F. Длина маршрута 4 + 6 + 5 = 15

Видно, что кратчайший путь равен 14.

Ответ: 14

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.

	A	B	C	D	E	F
A		2	4	8		16
B	2			3
C	4			3
D	8	3	3		5	3
E				5		5
F	16			3	5

Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E. Передвигаться можно только по указанным дорогам.

Решение.

Заметим, что в Е можно попасть только из D и F, следовательно, в маршруте также обязательно должен присутствовать пункт D. Составим маршрут следующим образом: стартуя из пункта А, будем всегда выбирать тот пункт, расстояние до которого наименьшее. Получим маршрут A-B-D-E-F, его длина равна 15 км. Теперь, начиная с начала маршрута, будем изменять путь, пользуясь следующим соображением: если расстояние, например, A-B-D больше расстояния A-D, то заменяем участок маршрута A-B-D на A-D. Попробовав произвести все такие замены, получим, что маршрут A-B-D-E-F - самый короткий из тех, что удовлетворяют условию задачи.

Любое другое изменение пути, через которые проходит маршрут, приводит к увеличению его длины.

Ответ: 15.

Гость 16.02.2015 00:31

Рассмотрите вариант A-B-D-F, A-B=2, B-D=3, D-F=3, 2+3+3=8

Сергей Никифоров

Обратите внимание, что нужно найти такой путь, который проходит через пункт Е.

Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.

	A	B	C	D	E	F	G
A		2		6
B	2		5	3
C		5		1			8
D	6	3	1		9	7
E				9			5
F				7			7
G			8		5	7

Решение.

A−B−C−D−E−G. Длина маршрута 22.

A−B−C−D−F−G. Длина маршрута 22.

A−B−C−G. Длина маршрута 15.

A−B−D−E−G. Длина маршрута 19.

A−B−D−F−G. Длина маршрута 19.

A−D−F−G. Длина маршрута 20.

A−D−E−G. Длина маршрута 20.

A−B−D−С−G. Длина маршрута 14.

Кратчайший путь равен 14.

Ответ: 14.

Ответ: 14

Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.