ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ.

Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число — время движения по этой дуге от начальной вершины до конечной. Рассмотрим пример (рис.7).

5 1

2 1

Рис.7. Исходные данные к задаче о кратчайшем пути.

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

Таблица 4.

Исходные данные к задаче о кратчайшем пути.

Начало дуги Конец дуги Время в пути
1 2 7
1 3 1
2 4 4
2 6 1
3 2 5
3 5 2
3 6 3
5 2 2
5 4 5
6 5 3

Спрашивается в задаче: как кратчайшим путем попасть из вершины 1 в вершину 4?

Январь 24, 2019 Психология труда, инженерная психология, эргономика
Еще по теме
ЗАВИСИМОСТЬ ПРОЦЕССА РЕШЕНИЯ ТЕСТОВЫХ ЗАДАЧ И ЗАДАЧ-ГОЛОВОЛОМОК ("МАЛЫХ ТВОРЧЕСКИХ ЗАДАЧ") ОТ ПАРАМЕТРОВ КОГНИТИВНОГО РЕСУРСА
ПРОВОДЯЩИЕ ПУТИ КОЖНОЙ ЧУВСТВИТЕЛЬНОСТИ: ПЕРЕДНИЙ И ЛАТЕРАЛЬНЫЙ СПИНОТАЛАМИЧЕСКИЕ ПУТИ
ПУТИ ВОЗДЕЙСТВИЯ, ИЛИ ПУТИ СИЛЫ
ТРАНСФОРМАЦИОННЫЕ ПУТИ, ИЛИ ПУТИ ПРЕОБРАЖЕНИЯ
СМЫСЛОЖИЗНЕННЫЕ ЗАДАЧИ КАК НОРМАТИВНЫЕ ЗАДАЧИ РАЗВИТИЯ.
Смысложизненные задачи как нормативные задачи развития.
ПУТИ ПРЕВРАЩЕНИЯ
ПУТИ БЕЗ КАНОНА
Часть вторая Я В ПУТИ
ПУТИ МЕДИТАТИВНЫЕ
СИТУАЦИОННЫЕ ПУТИ
УПРАЖНЕНИЕ «САМООЦЕНКА ЖИЗНЕННОГО ПУТИ».
ПЕРСПЕКТИВА ЖИЗНЕННОГО ПУТИ
Добавить комментарий