Подобрать формулу

[Munuvonaza]

Здравствуйте уважаемые господа математики, прошу консультации в следующем вопросе
Имеется упорядоченное множество $E$ неких элементов $e_i$, между каждыми соседними элементами $e_i$ и $e_{i+1}$ установлено двухместное отношение $R$, которое отображает пару из двух элементов в некое действительное число; фактически отношение установлено только для соседних элементов, но для соблюдения формальности можно считать, что $R$ для любых двух элементов, не расположенных впордяд в заданном упорядоченном множестве, равно минус бесконечности
То есть упорядоченное множество $E=(e_0, e_1, ... e_N)$, значения отношения $R(e_0, e_1)=r_01$, $R(e_i, e_{i+1})=r_{0i+1}$, и так далее, в частности $R(e_i, e_{i+2})=-\inf$ - это входные условия для задачи
Далее требуется разбить изначальное упорядоченное множество на набор упорядоченных подмножеств $s_i$, так чтобы каждый элемент $e_i$ принадлежал одному и только одному упорядоченному подмножеству $s_i$, а также ни одно $s_i$ не может быть пустым; сохраняется и порядок следования элементов в подмножествах - если $e_i$ предшествовал $e_j$, то или они будут находиться в одном $s_k$, или если $e_i$ будет находиться в $s_m$, а $e_j$ в $s_n$, то обязательно $m<n$
То есть фактически требуется разделить оригинальное упорядоченное множество на несколько частей, состоящих из одного и более элементов, так чтобы при их соединении получился исходный результат

Теперь собственно суть вопроса: пусть есть некоторое отношение $Q$, которое для вектора $q=(e_i, e_{i+1}, ... e_{i+k})$ длины $k<N$ ставит в соответствие некоторое действительное число, определяющее степень совместимости этих элементов, исходя из значений $R$ входящих в него пар элементов
При этом существует некоторая критическая длина $L_q$, которая является наиболее предпочтительной для выбираемых упорядоченных подмножеств, и при приближении к которой значение $Q$ должно стремительно увеличиваться
Необходимо подобрать аналитическое выражение для $Q$ с учетом входных параметров задачи и критической длины $L_q$, которое будет позволять выбирать оптимальные в указанном смысле упорядоченные подмножества $s_i$

Иначе говоря неформально, некий упорядоченный список элементов, в котором каждые два соседних объекта имеют показатель совместимости между собой, надо разделить на набор списков меньшего размера, в котором все соседние элементы являются максимально совместимыми между собой, и при прочих равных условиях длина меньших список стремится к $L_q$
Соответственно $Q$ применяется к потенциальному выделенному меньшему списку, и показывает, насколько разделение на именно такие списки меньшего размера является оптимальным - то есть в выбранном разбиении на небольшие списки, сумма их характеристик $Q$ должна быть максимальной

То как генерируются наборы элементов, являющиеся потенциальными кандидатами для включения в список меньшего размера - НЕВАЖНО; главное что если предложено несколько таких разбиений, подсчет аналитического выражения $Q$ должен давать максимальное абсолютное значение для списка, являющегося наилучшим в вышеобозначенном смысле

Посоветуйте пожалуйста, какое решение можно использовать для указанной задачи? Задача возникла в процессе моделирования в предметной области
Заранее спасибо!

[Munuvonaza]

Пример разделений на прикрепленном изображении

[svv]

Я перескажу неформально, как я Вас понял. При этом я из формулировки задачи выброшу то, что мне кажется лишним. Выброшу много, не шокируйтесь.

Имеется список вещественных чисел, например:
0.74
0.70
0.72
0.64
0.77
0.30
0.80
0.64
0.65
...
Требуется некоторые из этих чисел пометить (звездочкой), по возможности удовлетворив двум требованиям:
а) помеченные числа меньше других (по какому-то критерию);
б) помеченные числа встречаются примерно через каждые $L$ чисел.
Например, если $L=3$, результат может быть таким:
0.74
0.70 *
0.72
0.64
0.77
0.30 *
0.80
0.64 *
0.65
...

Ясно, что результат зависит от того, какой вес мы придаем каждому из требований в разных ситуациях. Насколько выполнение одного из этих требований важнее выполнения другого. Скажем, число 0.64 явно меньше соседних, и его хочется пометить, но тогда звездочки будут идти слишком часто. Или всё же можно? С этим числом борется за звездочку 0.30 и, конечно, побеждает, если им нельзя дать каждому по звездочке.

Выбор баланса между требованиями оставляет широкий простор для множества реализаций. Выбор той, а не иной функции $Q$, которая «на глазок» столь же хороша, ничем не обусловлен — в этом и проблема.

[Munuvonaza]

svv, спасибо за внимание к теме и удачное упрощение поставленного вопроса
Указанные в списке числа, некоторые из которых необходимо пометить звездочкой, обязательно имеют значение от 0 до 1, и действительно нужно выбрать меньшие из них по определенным критериям

svv в сообщении #850196 писал(а):

помеченные числа встречаются примерно через каждые $L$ чисел.

Не совсем так - в действительности не известно, как часто встречаются эти числа, но хотелось бы, чтобы в среднем они встречали через указанный интервал
Тем не менее, если будет иметься последовательность близких к единице числе вроде 0.97, 0.98, 0.96 и так много раз, то даже если их число будет превышать $L_q$ во много раз, помечать звездочкой ничего не будет нужно
В то же время, если будет иметься последовательность близких к нулю чисел вроде 0.03, 0.02, 0.04 и так много раз, то даже если их число будет меньше $L_q$ во много раз, то каждое из них нужно будет пометить звездочкой

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

[svv]

Я не возьмусь подбирать формулу, но пару вопросов задам:

1) Бывают ли у Вас такие последовательности, в которых в одних местах идут подряд большие числа достаточно долго, а в других местах тоже достаточно долго идут подряд маленькие числа?

2) Если такое бывает, как надо действовать в такой ситуации. Пусть где-то в одном месте последовательность такая:
...0.98,0.96,0.50,0.98,0.97...
А где-то в другом такая:
...0.02,0.03,0.50,0.01,0.02...
Правильно ли, что на первом участке 0.50 надо пометить звездочкой как место разделения, потому что локально это малое число? А на втором — не надо, потому что локально это большое число? Т.е. верно ли, что важно не просто значение, а значение относительно соседей?

Munuvonaza в сообщении #849957 писал(а):

При этом существует некоторая критическая длина $L_q$, которая является наиболее предпочтительной для выбираемых упорядоченных подмножеств, и при приближении к которой значение $Q$ должно стремительно увеличиваться

Назовём такое повышение «пряником». А сильное снижение $Q$ на неудачных разбиениях «кнутом». Функция $Q$ стремится к прянику, пытаясь избежать кнута. Так вот: если использовать только пряник, без кнута (или если кнут не очень выраженный), то возможна такая нежелательная ситуация. Функция $Q$ будет добиваться идеального разбиения на некоторых участках (такие обычно можно найти), наплевав на остальные, так как пеня за плохое разбиение на них небольшая, а пряник эту пеню перекрывает.

[Munuvonaza]

svv в сообщении #850482 писал(а):

Бывают ли у Вас такие последовательности, в которых в одних местах идут подряд большие числа достаточно долго, а в других местах тоже достаточно долго идут подряд маленькие числа?

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

svv в сообщении #850482 писал(а):

.е. верно ли, что важно не просто значение, а значение относительно соседей?

Абсолютно верно, хотя числа колебляется только в интервале от 0 до 1, фактически важны именно перепады в значениях, причем чем ближе числа к единице, тем более редко будут встречаться звездочки, но важно - что обязательно будут

svv в сообщении #850482 писал(а):

Правильно ли, что на первом участке 0.50 надо пометить звездочкой как место разделения, потому что локально это малое число? А на втором — не надо, потому что локально это большое число?

Тоже совершенно правильно, хотя надо признать, что приведенный Вами пример довольно простой, поскольку числа слишком близки к нулю, и поэтому очень стремятся быть обозначенными звездочкой
Если же вместо $...0.02,0.03,0.50,0.01,0.02...$ будет $...0.32,0.33,0.50,0.31,0.32...$ действовать сложнее, но не очень понятно как, ибо четких границ нет в принципе - но видимо должно обозначться 0.33 и 0.31 соответственно

svv в сообщении #850482 писал(а):

. Так вот: если использовать только пряник, без кнута (или если кнут не очень выраженный), то возможна такая нежелательная ситуация

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

Спасибо