7. Почтальон выходит из почтамта (Р) и должен разнести посылки в три района (Q, R, S), посетив каждый из них только один раз, после чего вернуться на почтамт. Найдите маршрут с минимальной общей стоимостью проезда, построив дерево возможных маршрутов по матрице стоимости проезда (в условных единицах)

Для решения задачи необходимо рассмотреть все возможные маршруты, начинающиеся и заканчивающиеся в пункте P, посещая каждый из пунктов Q, R, S ровно один раз. Стоимость каждого маршрута рассчитывается как сумма стоимостей переездов между пунктами.

Возможные маршруты:

1. P - Q - R - S - P: 5 + 8 + 6 + 9 = 28
2. P - Q - S - R - P: 5 + 10 + 8 + 11 = 34
3. P - R - Q - S - P: 11 + 5 + 10 + 9 = 35
4. P - R - S - Q - P: 11 + 6 + 5 + 5 = 27
5. P - S - Q - R - P: 9 + 5 + 8 + 11 = 33
6. P - S - R - Q - P: 9 + 6 + 5 + 5 = 25

Минимальная общая стоимость проезда составляет 25 условных единиц.

Ответ: P - S - R - Q - P, стоимость 25