maxim1000
Распечатываю, буду осмысливать...

Брошюра о разборчивой принцессе (~200 Kb):
http://www.mccme.ru/mmmf-lectures/books/books/book.25.pdf

Это сообщение отредактировал(а) MBo - 24.2.2005, 16:23

Цитата

Брошюра о разборчивой принцессе (~200 Kb):

почитал, интересная задачка
но не совсем та, которая тут стоит, хотя тот подход, который я использовал совпадает с описанным (что и не удивительно: среди подобных задач редкие не решаются с использованием динамического программирования)
здесь нет информации о распределении "качества" женихов, а только попарное сравнение
с одной стороны может показаться, что эта задача сложнее, т.к. информации меньше
но это было бы так, если бы требовался одинаковый результат, а в обеих задачах требуется найти оптимальный подход
более того, эта задача даже проще, чем та, которая сформулирована в начале темы:
дело в том, что причиной сложности этой задачи является необходимость "тянуть" за собой предысторию:
1. в случае в задачей о принцессе предыстория довольно простая - просто 1 бит (лучший из известных или нет)
2. в этой задаче предыстория представляет собой число (из большого множества), а значит, приходится оперировать функциями от этого числа...

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