Порядок решения сетевых задач с помощью 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.