Логическое программирование на языке Visual Prolog. Солдатова О.П - 72 стр.

UptoLike

Составители:

Рубрика:

Вершинами a,b,c,d,f,h,z – представлены города. Расстояние между

городами обозначено весом дуги из одной вершины графа в другую. На карте

есть река. Допустим, что переправиться через реку можно только по двум

мостам: один находится в городе f, а второй – в городе d. Очевидно, что

искомый маршрут обязательно должен проходить через один

из мостов, а

значит должен проходить либо через f, либо через d. Таким образом, мы

имеем две главные альтернативы:

• путь из a в z, проходящий через f;

• путь из a в z, проходящий через d.

Затем, каждую из этих двух альтернативных задач можно, в свою

очередь, разбить следующим образом:

1. для того, чтобы найти путь из a

в z через f, необходимо:

• найти путь из a в f и

• найти путь из f в z.

2. для того, чтобы найти путь из a в z через d, необходимо:

• найти путь из a в d и

• найти путь из d в z.

Таким образом, в двух альтернативах мы получили четыре подзадачи,

которые можно решать независимо друг от друга

. Полученное разбиение

исходной задачи можно изобразить в форме И/ИЛИ – графа,

представленного на рисунке.

ечка

h z