Автор | Сообщение |
|
Отправлено: 16.04.16 11:13. Заголовок: Онлайн-тест B3
Здравствуйте! Вопрос по заданию 6. 6. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам). Вот мое решение. Объясните, пожалуйста, в чем моя ошибка.
|
|
|
Ответов - 2
[только новые]
|
|
|
| Администратор
|
Сообщение: 1094
|
|
Отправлено: 16.04.16 14:30. Заголовок: Медко пишет: Объясни..
Медко пишет: цитата: | Объясните, пожалуйста, в чем моя ошибка. |
|
Вы пропустили ветку ABDC, она дает вариант ABDCG = 14. При рисовании дерева у каждой вершины лучше сразу писать длину пути из А в эту вершину по данному маршруту, это позволит обрубать неперспективные ветки и сокращать перебор. Например, если вы пришли из А в D с результатом 6, но есть другая ветка из А в D с результатом 4, то новую ветку (для которой уже A->D=6) можно дальше не рассматривать.
|
|
|
|
Отправлено: 16.04.16 14:56. Заголовок: Большое спасибо!..
Большое спасибо!
|
|
|
|