Поиск маршрута из
Рисунок 13. 1. Поиск маршрута из а в z на карте дорог. Через реку
можно переправиться в городах f и g. И / ИЛИ-представление этой
задачи показано на Рисунок 13.2.
странстве состояний. Соответствующее пространство состояний выглядело бы в точности, как карта Рисунок 13.1: вершины соответствуют городам, дуги - непосредственным связям между городами. Тем не менее давайте построим другое представление, основанное на естественном разбиении этой задачи на подзадачи.
На карте Рисунок 13.1 мы видим также реку. Допустим, что переправиться через нее можно только по двум мостам: один расположен в городе f, другой - в городе g. Очевидно, что искомый маршрут обязательно должен проходить через один из мостов, а значит, он должен пройти либо через f, либо через g. Таким образом, мы имеем две главных альтернативы:
Для того, чтобы найти путь из а в z,
необходимо найти одно из двух:
(1) путь из а в z, проходящий через f, или
(2) путь из а в z, проходящий через g.
