Главная страница
Навигация по странице:

  • Решение (вариант 1, использование схемы)

  • Решение (вариант 2, с начала маршрута)

  • Решение (вариант 3, с конца маршрута)

  • Возможные ловушки и проблемы

  • ege полякова 1. Использование и анализ информационных моделей (таблицы, диаграммы, графики)


    Скачать 1.12 Mb.
    НазваниеИспользование и анализ информационных моделей (таблицы, диаграммы, графики)
    Анкорege полякова 1
    Дата06.02.2022
    Размер1.12 Mb.
    Формат файлаdoc
    Имя файлаege1.doc
    ТипДокументы
    #352780
    страница6 из 8
    1   2   3   4   5   6   7   8

    Ещё пример задания:


    Р-03. Между населёнными пунктами A, B, C, D, E, 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




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

    Решение (вариант 1, использование схемы):

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



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

    2. например, из вершины В можно проехать в вершины C и E (длины путей соответственно 1 и 7):



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



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



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



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

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

    А – В – Е длина 9

    А – В – С – Е длина 7

    А – В – C – D – Е длина 9

    А –C – Е длина 8

    А –C – B – Е длина 12

    А –C – D – Е длина 10

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

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

    Решение (вариант 2, с начала маршрута):

    1. составим граф, который показывает, куда (и как) можно ехать из пункта А, рядом с дугами будем записывать увеличение пути, а рядом с названиями пунктов – общую длину пути от пункта A:



    1. видно, что напрямую в пункт F из A не доехать

    2. строим граф возможных путей дальше: определяем, куда можно ехать из B и C (конечно, не возвращаясь обратно); из B можно ехать только в A (обратно), в C и в E;

    3. узел C уже есть на схеме, и оказывается, что короче ехать в него по маршруту A-B-C, чем напрямую A-C, длина «окольного» пути составляет 3 вместо 4 для «прямого»;
      при движении по дороге B-E длина увеличивается на 7:



    1. строим маршруты из пункта C; кроме A и B, из пункта C можно ехать в D (длина 3) и E (длина 4), причем кратчайший маршрут из A в E оказывается A-B-C-E (длина 7); «невыгодные» маршруты на схеме показывать не будем:



    1. из пункта D, кроме как в С и E, ехать некуда; путь D-C – это возврат назад (нас не интересует), путь D-E тоже не интересует, поскольку он дает длину 6 + 3 = 9, а мы уже нашли, что в E из A можно доехать по маршруту длины 7

    2. из пункта E можно ехать в F, длина полного маршрута 7 + 2 = 9



    1. Ответ: 9

    Решение (вариант 3, с конца маршрута):

    1. можно точно так же начинать с пункта F и искать кратчайший маршрут до A; судя по таблице, из F можно ехать только в E:




    1. из E ведут дороги в B, C и D



    1. из B можно сразу попасть в A, длина пути будет равна 11:



    1. из пункта C есть прямая дорога в A длиной 4, таким образом, существует маршрут длиной
      6 + 4 = 10



    1. кроме того, есть дорога C-B, которая дает маршрут F-E-C-B-A длиной 9



    1. рассмотрение пути C-D не позволяет улучшить результат: оптимальный маршрут имеет длину 9

    2. Ответ: 9

    Возможные ловушки и проблемы:
    1   2   3   4   5   6   7   8


    написать администратору сайта