Условие:
Курьер доставляет посылку из пункта S (Start) в пункт G (Goal). Из каждого пункта можно поехать только по указанным маршрутам. У каждого маршрута задано время в минутах.
Откуда Куда Время (мин)\nS\nA 4\nS\nB 5\nS\nC 6\nA\nD 5\nA\nE 6\nB\nD 4\nB\nE 7\nC\nE 4\nD\nG 4\nE\nG 3
Нужно найти путь от S до G, используя beam search с шириной луча (k=2). На каждом шаге выбираются только два маршрута с наименьшим суммарным временем от точки S.
Алгоритм поиска Из точки S сформируйте все возможные маршруты длиной 1. Сохраните два лучших по времени. Для каждого из этих маршрутов постройте продолжения на один шаг вперёд. Снова сохраните два лучших по суммарному времени. Продолжайте, пока хотя бы один из маршрутов не дойдёт до G. Вопросы Постройте таблицу для каждого шага: Шаг Кандидаты (пути) Время (мин) Два лучших (beam) 1 . . . . . . . . . 2 . . . . . . . . . 3 . . . . . . . . . Какой путь нашёл beam search? Совпадает ли он с абсолютно кратчайшим маршрутом (если бы рассмотреть все варианты)? Что изменится, если ширина луча будет (k=1) или (k=3)? Почему beam search может пропустить оптимальный путь?
