Я работаю над следующей проблемой:
Учитывая набор элементов = {1,2,3,4,5,6,7,8,9, .. .., 100} и набор элементов types = {a, b, c, d, e, f, g} и набор вероятностей, прикрепленных к каждому элементу s P (1_a) = 0,4, P (2_b) = 0,6, P (3_ c) = 0,4, P (4_a) = 0,9, ..., P (100_f) = 0,9 и так далее. Видите ли, каждый элемент имеет тип, заданный предыдущим определенным набором.
Найдите две последовательности S1 и S2 с максимальной вероятностью :
так что количество элементов netto в пределах разности двух последовательностей S1 и S2 не превышает 20% от длина определяется суммой двух последовательностей.
Например: (То есть, если одна последовательность имеет длина 5 , что означает, что 20% составляет частота 1 , и мы дали S1 = 'aa bdd' и S2 = 'fgae c' ; это не будет соответствовать условиям из-за количества нетто предметов с type a = 2-1 = 1 и элементы типа d = 2-0 = 2 . Таким образом, имеется более 20% элементов одного типа ( 2 предметы типа d ) в разнице двух последовательностей.
Сейчас я ищу алгоритм для поиска наиболее вероятной последовательности при данных условиях. Может кто-нибудь помочь мне с фиг Можно решить эту проблему, применив forwardpass в автомате конечных состояний. Это разрешимо за подходящее время?
Спасибо за помощь;)