10.1. Примеры представления задач в пространстве состояний

Задача коммивояжера

Коммивояжер должен построить свой маршрут так, чтобы побывать в каждом из n городов один раз и вернуться в исходный пункт. Нужно найти кратчайший маршрут.

Описание состояний. Состояние – список городов, пройденных к настоящему моменту. Начальное состояние – список, состоящий из одного города А. Не допускается повторное упоминание любого города в списке, кроме А, а А может быть повторно упомянут только тогда, когда все остальные города уже перечислены.

Операторы. Операторы – вычисления, соответствующие следующим действиям: FA – направиться в город А; FB – направиться в город B; FC – направиться в город С; FE – направиться в город Е; FD – направиться в город D. Оператор неприменим к некоторому описанию состояния, если он не преобразует его в некоторое допустимое состояние. Например, F(A) применим только к списку, содержащему все города. Целевое состояние – любое описание, начинающееся и оканчивающееся городом А и перечисляющее все остальные города один раз.

Фрагмент пространства состояний:

Задача распределения

Пусть имеются два источника жидкости А и В, А дает 100 л/мин, В – 50 л/мин. Источники должны снабжать бассейны C и D (потребность бассейнов по 75 л/мин). Максимальная пропускная способность труб составляет 75 л/мин. Соединение труб допускается только в местах расположения труб и бассейна. Как провести трубы, чтобы их длина была наименьшей.

Состояние – список величин избыточного расхода жидкости, который имеется в точках А,В,С,D.

Начальное состояние – {100, 50, 0, 0}.

Операторы – передача избытка жидкости в минуту из одной точки в другую.

Подходящий избыток – наибольший общий делитель пропускных способностей и потребностей в жидкости в различных точках.

Операторы:

1. Передать 25 литров из А в В.

2. Передать 25 литров из А в С.

3. …

Операторы применимы только тогда, когда имеется достаточный избыток в точке отбора и для такой передачи нужно иметь трубу.

Ц елевое состояние – {0, 0, 75, 75}.

Задача об обезьяне и банане

В комнате с обезьяной имеется ящик, и к потолку подвешена связка бананов.

С остояние – (x, y, z), где  – координаты обезьяны; х – единица или ноль (находится обезьяна на ящике или нет); у – координаты ящика; z – единица или ноль (достала обезьяна банан или нет).

Операторы: (1) подойти в точку (U);

(2) передвинуть ящик в точку (V);

(3) взобраться;

(4) схватить.

Целевое состояние – любое состояние при z =1.

Условия применимости операторов:

(

(1)

0, y, z) (U0, y, z);

(

(2)

0, , z) (V0, V, z);

(

(3)

0, , z) (1, , z);

(

(4)

c1, c, 0) (c1, c, 1);

г де с – координаты банана.

Начальное состояние – (a, 0, b, 0),

где а – координаты обезьяны; b – координаты ящика.

Задача управления

Т ребуется поддерживать значения переменных: Х – координата тележки,  – угол наклона,  – производная по времени, в определенных пределах.

Управляемая переменная v – скорость тележки, которая принимает значения (+v, -v), значения меняются мгновенно.

Задача – принятие решения о том, как следует перемещать тележку (со скоростью +v или со скоростью -v).

Состояние – вектор (Х, , ), переменные принимают дискретные значения с мелким шагом. Пространство состояний – решетка в трехмерном пространстве. Состояние, возникающее после применения оператора, описывается вектором (Х, , ) по истечении t c.

Целевое состояние – (Х = 0,  = 0,  = 0). Нужно найти последовательность операторов, которая преобразует любое состояние в целевое. Действия операторов могут быть представлены с помощью дифференциальных уравнений.