динамическое программирование задача

Andrey56

столкнулся (вернее попросили разобраться) со следующей задачей.
Имеется некоторая система, характеризуемая N состояниями. Имеется некоторая элементарная измерительная процедура, которая даёт M возможных результатов исхода, причём M<N.
Результат всего измерения состояния системы определяется серией таких элементарных измерительных процедур, каждая из которых проводится с учётом предыдущих измерений в рамках одного измерения.
Зная априорное распределение вероятности различных N состояний системы необходимо провести оптимальный с точки зрения вероятности выбор элементарных измерений на каждом шаге, т.е. необходимо найти оптимальный path.
В частности, сейчас интерес представляет случай с бинарным измерением M=2 и для числа состояний системы N=4. Нужна аналитика.
Насколько я знаю, такими вещами занимается динамическое программирование. Посоветуйте, пожалуйста, литературу по этому вопросу или наведите на ответ. Очевидно, что такая простая задача уже решена, но я пока не нашёл.

BSCurt

Перепиши ещё раз, а то не понятно, что мы оптимизируем и какие у нас действия даны,
я нуб если чё.

Andrey56

Есть чёрный ящик с одним выходом, на который выдаётся некоторый сигнал.
Известно, что число возможных значений сигнала (напряжение, например) равно N.
Я хочу узнать, какой именно сигнал выдаёт чёрный ящик в данный момент, т.е. номер n из изначально известного набора сигналов.
Для этой цели у меня имеется измерительное устройство, на которое подаётся сигнал из чёрного ящика.
Измерительное устройство состоит из множества детекторов, которые проводят измерение последовательно друг за другом. Детекторы обладают дискретным набором значений выхода - число возможных значений стрелки равно M<N.
При этом перед каждым детектированием имеется возможность преобразовывать сигнал некоторым образом. Выбор конкретного преобразования зависит от стратегии измерения и зависит от результатов предыдущих детектирований этого сигнала. Мой вопрос касается именно оптимальной стратегии для измерения сигнала таким устройством. Как следует выбирать преобразование на текущем шаге детектирования, если результаты детектирований на предыдущих шагах известны?
Вопрос даже не именно в этой задаче, а где можно найти подобные задачи с аналитическим решением?

Vlad128

Похоже на постановку задачи идентификации в общем случае. Опыта в этой области нет, только курс в универе был, конкретных книжек не подскажу. Вот есть википедия, там есть какие-то ссылки. http://en.wikipedia.org/wiki/System_identification

geki-li

Измерительное устройство состоит из множества детекторов, которые проводят измерение последовательно друг за другом. Детекторы обладают дискретным набором значений выхода - число возможных значений стрелки равно M<N
А условное распределение показания датчика, в зависимости от величины сигнала задано? Я тоже не в теме, если что, просто не могу понять, как мы собираемся измерять сигнал датчиками, связь показаний которых с входным сигналом неизвестна.

shpanenoc

Смотри, как я понял задачу.
У тебя есть функция f возвращающая одно из значений 0..N-1
Ты программируешь некую функцию M1(x которая принимает на вход x=0..N-1 и выдает одно из значений 0..M-1.
После этого, посмотрев на M1(f ты программируешь вторую функцию M2(x) такого же вида, как и M1. На самом деле, это уже M2(x, m1 которую ты затем вызываешь так:
f=f;
m1 = M1(f);
m2 = M2(f, m1);
И так далее, пока ты не узнаешь однозначно, чему было равно f.
Частный случай такой задачки: пусть f - номер гирьки, которая тяжелее всех остальных, от 0 до 8.
Наши функции M - это взвешивания, вариантов значения функции - три. Соответственно, подобрав соответствующим образом M1 и M2, можно определить f за два взвешивания.
Но, если мы знаем априори, что распределение f - не равномерное, то мы можем построить другую цепочку взвешиваний, которая будет работать в среднем быстрее 2 взвешиваний. Например, если в 90% случаем f==0, то можно первым взвешиванием сравнить 0-ю гирьку с 1-й, и только в случае равенства применить предыдущий 2-шаговый алгоритм. Тогда взвешиваний будет 0.9*1 + 0.1*3 = 1.2.

shpanenoc

Для M=2 задачка удивительно напоминает о коде Хаффмана, который, как известно, строится довольно жадно. Может, этот алгоритм и для M>2 работает?

Andrey56

в целом да, похоже.

Andrey56

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

shpanenoc

Если я правильно понял задачу, то это задача оптимального кодирования из алфавита 1..N в алфавит 1..M, если известно распределение частот символов исходного алфавита. Причем тебе, вероятно, нужны префиксные коды.
Для M=2 оптимальный префиксный код - это код Хаффмана, построить его весьма легко.
Судя по Википедии, тот же самый алгоритм можно адаптировать и для M>2, получится тоже неплохо. Правда не знаю, останется ли этот код оптимальным среди префиксных.

Andrey56

ок. благодарю.
Оставить комментарий
Имя или ник:
Комментарий: