Разработка алгоритмов планирования

Домен планирования "Задача о коммивояжоре" содержит:

объектов (городов),

фактов,

действия.

Для данных доменов планирования построим графики зависимости мощностей | и || от длины 𝓁, где длина 𝓁 варьируется от 1 до 11 действий.

На графике: по горизонтальной оси отложена длина 𝓁, по вертикальной оси - мощность ||= (на рисунке - SEQ), а также - мощность || (на рисунке - SEQ (БПД)).

Рис.13 - "Мир Кубиков"

Рис. 14 - "Логистика"

Рис. 15 - "Задача о коммивояжёре"

Примечание.

Из графиков видно, что мощность последовательностей действий, содержащих бесполезные подпоследовательности, довольно внушительна. Приведём некоторые примеры.

Пример 1.

Для домена планирования "Мир кубиков" количество последовательностей длины 5 равно 1445 = 61 917 364 224. Из них количество последовательностей, содержащих БПД, равно 1 609 851 470, что составляет примерно 2% от общего количества.

Пример 2.

Для домена планирования "Логистика" количество последовательностей длины 3 равно 12 812 904. Из них количество последовательностей, содержащих БПД, равно 384 387, что составляет примерно 3% от общего количества.

Пример 3.

Для домена планирования "Задача коммивояжёра" количество последовательностей длины 8 равно 1 099 511 627 776. Из них количество последовательностей, содержащих БПД, равно 87 960 930 222, что составляет примерно 8% от общего количества.

В

соответствии с пунктом (2.2.3.)

графики SEQ и SEQ (БПД) сойдутся при некоторой длине L.

Очевидно, что график SEQ (БПД) всегда возрастает.

Алгоритм TCRPA, использующий технику выявления бесполезной подпоследовательности действий, будет осуществлять перебор в множестве SEQ' = / , где n - наибольшая длина плана, который не содержит бесполезные подпоследовательности действий, - множество всех последовательностей длиной меньше либо равной n. Алгоритмы, не использующие соответствующей техники, будут искать план во всём множестве .