Задание 4

ТЕМА 4

"Анализ простейших моделей объектов "

Пример 1

Между населёнными пунк­та­ми А, В, С, D, Е по­стро­е­ны дороги, протяжённость ко­то­рых (в километрах) при­ве­де­на в таблице:

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

Решение

Способ 1

Найдём все возможные ва­ри­ан­ты маршрутов из A в E по таблице и вы­бе­рем самый короткий.

Из пунк­та A можно по­пасть в пунк­ты B, C, D.

Из пунк­та B можно по­пасть в пункт C.

Из пунк­та C можно по­пасть в пунк­ты D, E. Возможны следующие три маршрута:

  • A — B — C — E: длина марш­ру­та 8 км.
  • A — C — E: длина марш­ру­та 7 км.
  • A — D — C — E: длина марш­ру­та 12 км.

Самый ко­рот­кий путь: A — C — E. Длина марш­ру­та 7 км.

Способ 2

Можно построить взвешенный граф маршрутов в виде дерева, соответствующий исходной таблице. На дереве можно выделить все возможные варианты маршрутов. Среди них легко определить длину крат­чай­ше­го пути между пунк­та­ми А и E.

Ответ: 7

Пример 2

Между населёнными пунк­та­ми А, В, С, D, Е по­стро­е­ны дороги, протяжённость ко­то­рых (в километрах) при­ве­де­на в таблице:

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

Решение

Способ 1

Найдём все возможные ва­ри­ан­ты маршрутов из A в E по заданной таблице и выбе­рем самый короткий.

Из пунк­та A можно по­пасть в пунк­ты B и D.

Из пунк­та B можно по­пасть в пункты C, D, E.

Из пунк­тов C и D можно по­пасть в пунк­т E.

Возможны следующие шесть маршрутов:

  • A — B — E: длина марш­ру­та 9 км.
  • A — B — D — E: длина марш­ру­та 11 км.
  • A — B — C — E: длина марш­ру­та 8 км.
  • A — D — E: длина марш­ру­та 10 км.
  • A — D — B — E: длина марш­ру­та 12 км.
  • A — D — B — C — E: длина марш­ру­та 11 км.

Самый ко­рот­кий путь: A — B — C — E. Длина марш­ру­та 8 км.

Способ 2

Построим взвешенный граф маршрутов в виде дерева, соответствующий заданной таблице. На дереве видны все возможные варианты маршрутов. Среди них легко определить длину крат­чай­ше­го пути между пунк­та­ми А и E.

Ответ: 8

Пример 3

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

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

Решение

Способ 1

Найдём все варианты маршрутов из A в E, проходящие через пункт С и выберем самый короткий используя исходную таблицу. Таких оптимальных маршрутов можно построить только три, т.к. остальные будут с циклами.

  • A — B — C — D — E: длина маршрута 9 км.
  • A — C — D — E: длина маршрута 8 км.
  • A — C — B — D — E: длина маршрута 14 км.

Способ 2

Можно построить взвешенный граф маршрутов в виде дерева, соответствующий данной таблице. На дереве видны все возможные варианты маршрутов. Среди них легко определить длину крат­чай­ше­го пути между пунк­та­ми А и E, проходящего через пункт С.

Ответ: 8

Пример 4

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

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

Решение

Способ 1

Найдём все варианты маршрутов из A в E, проходящие через пункт С и выберем самый короткий используя заданную таблицу.

  • A — C — B — D — E: длина маршрута 9 км.
  • A — C — D — E: длина маршрута 9 км.
  • A — C — E: длина маршрута 8 км.
  • A — B — C — D — E: длина маршрута 8 км.
  • A — B — C — E: длина маршрута 7 км.
  • A — D — C — E: длина маршрута 12 км.
  • A — D — B — C — E: длина маршрута 12 км.

Из полученных 7 вариантов самый ко­рот­кий путь: A — B — C — E. Длина маршрута 7 км.

Способ 2

Можно построить взвешенный граф маршрутов в виде дерева, соответствующий данной таблице. На графе видны все возможные варианты маршрутов. Среди них легко определить длину крат­чай­ше­го пути между пунк­та­ми А и E, проходящего через пункт С.

Ответ: 7

Пример 5

Между населёнными пунк­та­ми А, В, С, D, Е, F по­стро­е­ны дороги, протяжённость ко­то­рых (в километрах) при­ве­де­на в таблице:

Определите длину крат­чай­ше­го пути между пунк­та­ми А и F, проходящего через пункт D.

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

Решение

Построим взвешенный граф маршрутов в виде дерева, соответствующий исходной таблице. На дереве можно выделить все возможные варианты маршрутов. Среди них легко определить длину крат­чай­ше­го пути между пунк­та­ми А и F, проходящего через пункт D.

Ответ: 8

  • Примеры, рассмотренные на этой странице в формате pdf: скачать
  • Задания для тренировки в формате pdf: скачать

Задания для тренировки

Задача 1

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

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

Задача 2

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

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

Задача 3

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

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

Задача 4

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

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

Задача 5

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

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

Задача 6

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

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

Задача 7

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

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

Задача 8

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

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

Задача 9

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

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

Задача 10

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

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

ссылка на видео: http://fizinfika.ru/

Комментарии, отзывы и предложения Вы можете направить на e-mail, указанный в контактах или оставить в гостевой книге, указав тему вопроса: перейти в гостевую книгу