Порядок решения сетевых задач с помощью QSB рассмотрим на следующем примере.
Подготовьте исходные данные задачи для решения на ЭВМ: определите количество этапов в задаче (4 задачи), тип задачи (задача о дилижансе).
Выберите опцию 8 – Динамическое программирование в главном меню системы.
В функциональном меню выберите опцию 2 – Ввод новой задачи, введите название задачи (например, prim7 ), ответьте на вопрос о количестве этапов в задаче (4 этапа). Данные вводятся, начиная с первого этапа. Нумерация узлов выполняется автоматически с 1 (для первого этапа) до последнего узла. Длина несуществующего пути задаётся большим числом (например, в нашей задаче 999). Введите данные как показано ниже:
этап 1: Сколько конечных узлов в этом этапе? 3
от начал. узла 1 к конеч. узлу 2: расстояние/затр? 2
от начал. узла 1 к конеч. узлу 3: расстояние/затр? 5
от начал. узла 1 к конеч. узлу 4: расстояние/затр? 1
этап 2: Сколько конечных узлов в этом этапе? 3
от начал. узла 2 к конеч. узлу 5: расстояние/затр? 10
от начал. узла 2 к конеч. узлу 6: расстояние/затр? 12
от начал. узла 2 к конеч. узлу 7: расстояние/затр? 999
от начал. узла 3 к конеч. узлу 5: расстояние/затр? 5
от начал. узла 3 к конеч. узлу 6: расстояние/затр? 10
от начал. узла 3 к конеч. узлу 7: расстояние/затр? 7
от начал. узла 4 к конеч. узлу 5: расстояние/затр? 999
от начал. узла 4 к конеч. узлу 6: расстояние/затр? 15
от начал. узла 4 к конеч. узлу 7: расстояние/затр? 13
этап 3: Сколько конечных узлов в этом этапе? 2
от начал. узла 5 к конеч. узлу 8: расстояние/затр? 7
от начал. узла 5 к конеч. узлу 9: расстояние/затр? 5
от начал. узла 6 к конеч. узлу 8: расстояние/затр? 3
от начал. узла 6 к конеч. узлу 9: расстояние/затр? 4
от начал. узла 7 к конеч. узлу 8: расстояние/затр? 7
от начал. узла 7 к конеч. узлу 9: расстояние/затр? 1
этап 4: Сколько конечных узлов в этом этапе? 1
от начал. узла 8 к конеч. узлу 10: расстояние/затр? 1
от начал. узла 9 к конеч. узлу 10: расстояние/затр? 4
По окончании нажмите любую клавишу. В функциональном меню выберите опцию 5 – Решение задачи. На экране появится меню опции <Решение>:
Меню опции <Решение> prim 7
Опция
1---- Решение и просмотр по шагам
2---- Решение без просмотра по шагам
3---- печать итогового решения
4---- Возврат в функциональное меню
Выберите опцию 2 – Решение с показом результатов. На экране появятся результаты решения задачи:
итоговый кратчайший путь prim7
этап
ветвь
расстояние до пункта назнач.
1-3
3-7
7-9
9-10
Итоговый кратчайший путь проходит через пункты 1-3-7-9-10, суммарное расстояние равно 17.