Поиск оптимального маршрута по таблице как решать

Поиск оптимального маршрута по таблице как решать

Автор: Пашковская Юлия Вадимовна

Организация: МОУ Гимназия №1

Населенный пункт: Московская область, г. Жуковский

Решение задач на определение оптимального маршрута по таблице традиционно решается перебором всех вариантов. Однако, если таблица большая, такой способ решения оказывается слишком трудоёмким и ненадёжным: а вдруг какой-то из вариантов упущен? В данной статье предлагается способ решения, гарантированно определяющий оптимальный маршрут. Он представляет собой модернизированный алгоритм Дейкстры для определения кратчайшего маршрута по таблице.

Задание №1 на ЕГЭ по информатике. Таблицы и схемы, поиск оптимального маршрута по таблице и по расписанию.

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

Модель — это искусственно созданный объект, дающий упрощенное представление о реальном объекте, процессе или явлении, отражающий существенные стороны изучаемого объекта с точки зрения цели моделирования.

Моделирование — это построение моделей, предназначенных для изучения и объектов, процессов или явлений.

Распространенными информационными моделями являются графики, схемы, таблицы, диаграммы. Одним из распространенных видов моделей являются графы. Граф – это один из способов графического едставления информации. Объекты представлены в нем как вершины (узлы), а связи между объектами как ребра (дуги). Т.е. граф – это набор вершин и связывающих их ребер.

Путь в графе – это конечная последовательность вершин, каждая из которых (кроме последней) соединена со следующей ребром. Граф может содержать циклы (первая вершина пути может совпадать с последней).

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

Граф может задаваться таблицей, в которой на пересечении строки и столбца с наименованиями вершин записано числовое значение (вес) ребра, соединяющего эти вершины.

Дерево – это граф, не имеющий циклов. В дереве существует один единственный путь между любой парой вершин. Одна из вершин дерева (корень) не имеет входящих ребер, все остальные имеют ровно одно входящее ребро. Вершины, у которых нет исходящих ребер, называются листьями.

1. Поиск графа, соответствующего таблице

Пример 1.

В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.

Сравним значения таблицы и схем:

Согласно таблице вершина A должна быть связана с вершинами B (значение 4) и D (значение 5). Т.е. AB=4, AD=5. На схеме значения указаны около соответствующего ребра. Сразу отбрасываем 1),2),3) схемы, т.к. на них AD не равно 5.

Для уверенности проверим все остальные ребра схемы 4): BC=3, BD=6, что совпадает со значениями таблицы. Правильная схема 4).

2. Анализ информации в таблице и графе

Пример 2.

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

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

На графе из вершины В выходит 5 ребер, значит в таблице соответствующий пункт должен иметь дороги в 5 других (строка должна содержать 5 заполненных клеток). Такой пункт в таблице один: П6.

На графе из вершины Е выходит 4 ребра, значит в таблице соответствующий пункт должен иметь дороги в 4 других (строка должна содержать 4 заполненные клетки). Такой пункт в таблице один: П4.

Таким образом, нам нужно найти расстояние между П6 и П4. Согласно таблице оно равно 20.

3. Поиск информации в таблице по условию

Пример 3.

Между четырьмя местными аэропортами: ЛУГОВОЕ, ДЯТЛОВО, НИКИТИНО и ОРЕХОВО, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:

Путешественник оказался в аэропорту ЛУГОВОЕ в полночь. Определите самое раннее время, когда он может попасть в аэропорт ОРЕХОВО. Считается, что путешественник успевает совершить пересадку в аэропорту, если между временем прилета в этот аэропорт и временем вылета проходит не менее часа.

1) 12:05 2) 12:50 3)12:55 4) 13:30

Решение:

Можно, конечно, решить эту задачу просто глядя на таблицу и перебирая подходящие варианты, но есть риск ошибиться или пропустить нужную строчку. Поэтому рекомендую нарисовать дерево всех возможных путей из аэропорта ЛУГОВОЕ в ОРЕХОВО:

Средняя ветка не подходит, т.к. между прилетом в аэропорт ДЯТЛОВО (11:15) и вылетом из ДЯТЛОВО в ОРЕХОВО (12:00) интервал меньше часа.

Из оставшихся двух выбираем раннее время прилета: 12:55.

Ответ: 3

4. Выбор таблицы по условию

Пример 4.

В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пункты не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта C до пункта B не больше 6». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом через любой насеченный пункт маршрут должен проходить не более одного раза.

По каждой из схем построим дерево с корнем в точке C и листьями в точке B. При этом нам не нужно строить дерево полностью. Как только найдена ветка с протяженностью больше 6, делаем вывод, что таблица не удовлетворяет указанному условию:

Таблицы 1), 2) и 4) отвергаем уже при анализе первой ветки дерева.

В таблице 3) две ветки вообще не приведут в B, а две другие имеют суммарную длину, не превышающую 6.

5. Поиск кратчайшего пути по таблице

Пример 5.

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

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

1) 13 2) 16 3) 19 4) 21

При решении этой задачи тоже не следует полагаться на простой визуальный анализ таблицы. Чтобы избежать ошибок, построим дерево с корнем в вершине A и листьями в вершине Z. При этом нам не нужно выписывать все ветки. Второй путь из A в С (AC=6) длиннее первого (ABC=5), значит и весь маршрут через него будет длиннее.

Второй путь из C в E (CE=10) длиннее первого (CDE=6), значит и весь маршрут через него будет длиннее.

Нам остается сложить длины всех отрезков и выбрать маршрут с наименьшей длиной.

Это верхняя ветка дерева с длиной 16.

Спасибо за то, что пользуйтесь нашими статьями. Информация на странице «Задание №1. Таблицы и схемы, поиск оптимального маршрута по таблице и по расписанию.» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ. Чтобы успешно сдать нужные и поступить в ВУЗ или колледж нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий. Также вы можете воспользоваться другими материалами из данного раздела.

Задание 1 ЕГЭ по информатике. Информационные модели

В заданиях этого раздела курса требуется установить соответствие между разными форматами данных, основными из которых являются таблицы и графы.

При решении задач на эту тему необходимо уметь преобразовывать таблицы в схемы и наоборот.

Граф (сетевая модель данных)

представляет собой набор вершин, соединенных ребрами, и чаще всего описывается в виде таблицы, например, матрицы смежности или весовой матрицы.

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

Особенности анализа графов в решении задания №1 ЕГЭ

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

в графе представляет собой количество ребер, соединенных с ней.

Чтобы определить степень вершины по заданной таблице (например, весовой матрице), необходимо посчитать количество ненулевых ячеек в соответствующей строке или столбце.

Например, степень вершины А равна 2, так как в строке А (выделена голубым) есть две ненулевые ячейки со значениями 6 и 9

В данном примере, . То есть, расстояние из пункта F в G равно расстоянию из G в F (11). Но, имеются задания с несимметричной матрицей.

Типы заданий

1. Поиск оптимального маршрута по таблице.
2. Однозначное соотнесение таблицы и графа.
3. Неоднозначное соотнесение таблицы и графа.

Поиск оптимального маршрута по таблице

Пример типового задания

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

Решение задания

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

Исходя из данных таблицы, из пункта А в пункт В есть единственный маршрут длиной 4.

Из пункта B можно вернуться в A (что не имеет смысла, так как это удлинит маршрут), а также добраться до C, D, E. Из B в C, расстояние 6, в D — 3, а в E — 6.

Из пунктов C и D можно добраться только в E:

Из пункта E можно добраться в пункт F

Получилось 3 маршрута: ABCEF (длина 19), ABDEF (длина 14) и ABEF (15). Самый короткий маршрут — ABDEF длиной 14.

Ответ: 14.

Однозначное соотнесение таблицы и графа

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

Типовое задание

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

Решение

Скопируем таблицу из задания в Excel вместе с рисунком графа. Это поможет нам быстро посчитать связность вершин, делать пометки (называть вершины) и выделять цветом промежуточные вычисления.

Чтобы посчитать связность вершин в таблице, заменим символы * на 1. Для этого, выделим таблицу (обязательно без названий строк и столбцов. ) нажмем Ctrl+H и сделаем замену (жмем «Заменить всё»):

Теперь вместо символов *, у нас стоят 1, и мы можем приступать к подсчету связности вершин. Для этого, будем использовать функцию СЧЕТ.

Функция СЧЕТ (ДИАПАЗОН1; ДИАПАЗОН2; ДИАПАЗОН3…), позволяет посчитать количество непустых ячеек в указанных диапазонах.

Посчитаем связность для строки П1. Для этого введем в ячейку K3 формулу: =СЧЁТ(B3:J3)

Размножим данную формулу для других строк таблицы. Для этого необходимо навести курсор мыши на угол ячейки K3 (где находится исходная формула).

Курсор сменится на значок черного крестика (как на рисунке)

После этого, зажимаем левую клавишу мыши и не отпуская, тянем вниз до самой последней строки (ячейки K11).

Результат подсчетов можно посмотреть на рисунке ниже:

Видим, что три вершины имеют связность 2 (выделены зеленым). Это П1, П4 и П9. И шесть вершин имеют связность 3 (выделены красным).

Посмотрим на нашу схему графа. По ней четко видно, что три вершины, имеющие связность два — это Б, И, Ж

Отметим это в таблице:

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

Следовательно, вершина в первой строке таблицы — это Б, а оставшиеся вершины степени 2 — это связанные между собой И и Ж. Отмечаем это в таблице

Снова смотрим на граф, и с какими вершинами связана Б. Это А и В. В таблице — это ячейки П5 и П6. Исправляем их название.

Смотрим на графе, с какими вершинами связаны И и Ж. Это Е и К. В таблице — это П2 и П8. Исправляем.

Очевидно, что две оставшиеся до сих пор неизвестными вершины Г и Д, соответствуют данным П3 и П7 таблицы. В ответе необходимо записать только их номера: 3 и 7:

Ответ: 37

Неоднозначное соотнесение таблицы и графа.

Здесь, также как и в предыдущем задании, необходимо определить соответствие вершин графа на рисунке и в таблице. Но, особенность в том, что для многих вершин — это невозможно сделать. Однако, есть вспомогательные условия, помогающие ответить на вопросы заданий.

Пример задания

На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам A и G на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Решение задания

Копируем таблицу и граф в Excel, делаем замену звездочек на символы «1». Как это сделать, описано в предыдущем решении.

Считаем степени вершин графов в таблице через функцию СЧЁТ.

Одна из вершин имеет степень 6 (выделена красным). По рисунку, определяем, что это вершина F. Отмечаем ее в таблице:

Две вершины (4 и 5) имеют степень 2. На графе мы видим, что — это C и E.

Обе эти вершины (C, E) соединены с вершиной F, а также с вершинами D, B.

В таблице, им соответствуют номера 1 и 2.

Оставшиеся ячейки, которые идут под цифрами 6 и 7 таблицы — это G и A.

Это и есть ответ на задачу. Вершинам A, G соответствуют ячейки 6 и 7 таблицы.

Ответ: 67

Видеорешение задачи 1 ЕГЭ по информатике

Для тех, кто не любит читать, видео с нашего канала. Подписывайтесь!

Подготовиться к ЕГЭ с репетитором

Чтобы сдать ЕГЭ по информатике на высокие баллы, нужно владеть следующими навыками:

1. Общая теория информации: системы счисления, измерение информации, представление информации, передача информации, логические операции, теория множеств, динамическое программирование.
2. Уметь работать в электронных таблицах: Excel или аналоги
3. Уметь работать с текстовыми редакторами: Word, Notepad
4. Уверенно владеть одним языком программирования: знать основные конструкции, уметь составлять алгоритмы и реализовывать их на алгоритмическом языке.
5. Уметь работать с файлами, представлять как они хранятся на диске, понимать что такое путь, имя и расширение.

Наша школа готова помочь вам с подготовкой к компьютерному ЕГЭ по информатике. Небольшие мини-группы по 5 человек, индивидуальный подход и темп освоения материала. У нас большой опыт подготовки новичков с нулевыми навыками программирования. Записывайся:

Решение задачи о нахождении кратчайшего пути в Excel

Рассмотрим методику решения в Excel задачи о нахождении кратчайшего пути.

Задача 3. Задача выбора кратчайшего пути задана сетью, изображенной на рис. 3.1. Найдите кратчайший путь от узла с номером 1 до узла с номеров 8, если c₁₂=1 км, c₁₃=4 км, c₁₄=6 км, c₂₃=3 км, c₂₆=5 км, c₂₇=1 км, c₃₄=3 км, c₃₅=5 км, c₄₅=1 км, c₄₈=4 км, c₅₄=1 км, c₅₆=1 км, c₅₈=2 км, c₆₅=1 км, c₆₇=3 км, c₆₈=4 км, c₇₂=1 км, c₇₆=3 км, c₇₈=7 км.

На рис. 3.2 представлены Таблица кратчайших расстояний и План перевозок товара по кратчайшему пути, сформированные на рабочем листе Excel. Здесь в Таблице кратчайших расстояний мы видим, что если между отдельными складами отсутствует возможность перевозки товара, то в соответствующие ячейки таблицы (выделенные темным фоном) заносится любое большое число (большее на порядок или два порядка, в данном случае 100).

Не сложно заметить, что данная задача решается аналогично решению транспортной задачи с промежуточными пунктами. В целевую ячейку, в данном случае C24, необходимо занести формулу: =СУММПРОИЗВ(C4:I10;C16:I22).

Рис. 3.2. Таблицы задачи поиска кратчайшего пути (до поиска решения)

Рис. 3.3. Окно поиска решения с накладываемыми ограничениями

Используя меню СервисПоиск решения открываем диалоговое окно Поиск решения (см. рис. 3.3), в котором устанавливаем целевую ячейку равной минимальному значению, определяем диапазон изменяемых ячеек и ограничения и запускаем процедуру вычисления, щелкнув по кнопке Выполнить.

Рис. 3.4. Таблицы задачи поиска кратчайшего пути (после поиска решения)

Результат решения данной задачи представлен на рис. 3.4.

После того, как Excel найдет решение, можно определить кратчайший путь следующим образом. В первой строке Плана перевозок товара по кратчайшему пути нетрудно видеть, что из первого пункта автомобиль следует в пункт 2, так как в столбце под потребителем 2 стоит единица в ячейке, что означает заезд в этот пункт. Далее смотрим на строку 2 (поставщик 2), так как следующее отправление автомобиля происходит из этого пункта. В этой строке единица стоит в столбце 7, значит автомобиль движется из пункта 2 в пункт 7. После этого смотрим строку с поставщиком 7, и так далее пока не появится конченый пункт 8.

Таким образом, мы видим, что кратчайший путь перевозки товара следующий: 127658. Расстояние перевозки при этом составит 8 км. Аналогично данную задачу можно решить и на максимум, т.е. найти самый длинный путь доставки товара.

Задания к лабораторной работе № 3 «Задача о нахождении кратчайшего пути»

Решите задачу 3, используя данные о расстояниях между узлами транспортной сети, представленные в табл. 3.1.