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

Будем считать, что подпоследовательности длины равной 1, всегда полезны, так как обычно в домене планирования действия описываются так, что при применении производят какие-либо изменения в состоянии. Поэтому, далее будем рассчитывать вероятность для подпоследовательностей длиной больше чем 1.

Множество = {| |seq| = 𝓁} является множеством событий появления бесполезной подпоследовательности действий mseq↻ произвольной длины (|mseq|≤|seq|-2) в произвольной последовательности seq, при фиксированном |seq| = 𝓁.

Множество событий :

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

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

Заметим, что мощность || = k, где k - количество собственных подпоследовательностей в некоторой последовательности seq, которое подсчитывается по формуле:

(3)

Определим вероятность prob||), которая рассчитывается по формуле сложения вероятности k совместных и независимых событий.

Однако вначале для более удобной записи формулы упорядочим множество в ряд из к элементов следующим образом: для каждого |mseq| = 2 до 𝓁-2 расположим в конце ряда в произвольном порядке очередные (𝓁-|mseq|)+l событий . Далее, запись означает элемент с номером і ряда .