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