Оптимизационная задача

Здравствуйте, уважаемые математики

Возникла необходимость программировать одну очень важную задачу. Пытаюсь придумать алгоритм рассчёта, но не получается :) Помню по институту был симплекс-метод... Но судя по всему задачу с помощью него решить не получится. Ну и вообще я в математике слаб, поэтому просьба объяснять как можно проще. Я в программировании силён, а в математике слаб )

Даны 16 целых чисел $x_i, i = 0..15, 0 \le x_i \le 255$
Необходимо найти a, b:
$ 0 \le a < b \le 255$,
$ c = (b - a) / 7$,
$ d_i = min(7, max(0, [(x_i-a+c / 2) / c]))$,
$ \sum_{i=0}^{15} (x_i - a - c*d_i)^2 \to 0 $

квадратные скобки - это взятие целого



Редактировалось 2 раз(а). Последний 14.07.2012 22:13.

не вопрос

даны 16 значений альфаканала блока 4x4
необходимо их аппроксимировать с целью компрессии по алгоритму DXT5
необходимой найти 2 байта, с помощью которых можно представить эти 16 значений с наименьшими потерями
2 байта определяют "палитру" из 8 элементов. Которые получаются аппроксимацией от a до b с примерным шагом (b - a) / 7

ориентировочный индекс произвольного числа X в такой палитре равен: [(X - a + c/2)/c]
но здесь может получиться и число меньше 0 и больше 7
поэтому дополнительная коррекция: min(7, max(0, [(X - a + c/2)/c]))

потеря при таком кодировании примерно равна: (X - (a + c*D) ) = X - a - c*D
ну а сумма всех потерь должна стремиться к минимуму, чтобы качество было наилучшим. Правда здесь лучше сделать квадратичный критерий - поэтому такое описание

Посмотрите пример решения Вашей задачи в Maple с помощью пакета DirectSearch. Этот пакет не входит в число штатных средств Maple. Его необходимо загрузить с maplesoft.com

with(DirectSearch):
x:=seq(ithprime(n), n=21..36);

x := 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151

c:=(b-a)/7: d:=seq(min(7, max(0, floor((x-a+c/2)/c))), i=1..16):
f:=(a, b)->add((x-a-c*d)^2, i=1..16):
GlobalOptima(f(a, b), {a=0..255, b=0..255, a<=b}, number=100);

[110.901098901099, [a = 79.1428571429022, b = 149.373626374149], 479]

Код выделен болдом.

У Вас снова странная постановка. Нет смысла ее решать.
Во-первых, шаг д.б. равен $c=\frac{b-a}8$. При этом д.б. выполнено $a\le x_{min}$ и $b>x_{max}$. Искомые числа $a,b$, вообще говоря, не обязаны быть целыми.
Индекс числа $X$ в $8$-ричной палитре будет равен $\left[\frac{X-a}c\right]$. И никакой доп. коррекции, никаких минимаксов. При $x_{min}\le X<x_{max}$ этот индекс как раз будет изменятся от $0$ до $7$.

Оптимазация практически здесь не нужна. Но можно простым перебором пошевелить $a$ в диапазоне $x_{min}-\frac{с}{2}\le a\le x_{min}$ и $b$ в диапазоне $x_{max}<b \le x_{max}+\frac{с}{2}$, чтобы минимизировать CKO
$\sum_{i=0}^{15}{\left(\frac{x_i-a}c-\left[\frac{x_i-a}c\right]\right)^2 }\to \min_{a,b}$
Задача оптимизации здесь хитрая: нелинейная, негладкая и даже разрывная. Поэтому, кроме перебора ничего не могу предложить. Да и перебирать-то тут особо нечего.

$ d_i = min(7, max(0, [(x_i-a+c / 2) / c]))$
Это некорректная запись, так не пишут. Скорее всего имелся ввиду набор условий $ d_i = [(x_i-a+c / 2) / c]$, $0 \le d_i \le 7$.

Уточните пожалуйста, $c=(b-a)/7$ обязано быть целым? Т.е. надо искать такие $a,b$, что $b-a$ делится нацело на $7$?

Задачу скорее всего нужно записать так:

Даны 16 целых чисел $0 \le x_i \le 255$, $i = 0..15$.
Необходимо найти $a,b$ такие, что
$ 0 \le a < b \le 255$,
$ c = (b - a) / 7$,
$d_i=[(x_i-a+c / 2)/c]$,
$0 \le d_i \le 7$,
$\sum_{i=0}^{15} (x_i - a - c*d_i)^2 \to min$.

Чтобы задача решалась по умному, она в первую очередь д.б. по умному поставлена. И я настаиваю на том, что делить нужно на 8. Это очевидно.

Вот этим:

Цитата
dmitrynn
Нет, Вы не правы. Именно на 7. Потому что получается: a | a+(b-a)/7*1 | a+(b-a)/7*2 | a+(b-a)/7*3 | a+(b-a)/7*4 | a+(b-a)/7*5 | a+(b-a)/7*6 | b (или a+(b-a)/7*7)

Вы разбиваете интервал $(a,b)$ на 7 равных отрезков, а должно быть 8. Отсюда растут ноги у всех ваших проблем. Вам приходится лепить какие-то несусветно кривые формулы.
Вот, например, 16 последовательных чисел: 10,11,12, ..., 25. Берем $a=x_{min}=10$, $b=x_{max}+1=26$, получаем $c=16/8=2$. Имеем:
числам 10 и 11 соответствует код 0
числам 12 и 13 соответствует код 1
...
числам 24 и 25 соответствует код 7

Все четко и ясно. А теперь примените свои "формулы".

8 - число точек, границ, делящих интервалы, а интервалов -7. Код числа определяется номером интервала в который он попадает. Так должно быть, но у Вас не так. Поэтому, я перестаю спорить: есть уровень ниже которого спорить бесмыссленно. Я сделаю вот что. Напишу полный алгоритм решения вашей задачи, как я его сейчас вижу. Это очень простой алгоритм.

1) Из 16 чисел $x_i$ находим минимальное и максимальное: $x_{min}, x_{max}$.

2) Полагаем $b=x_{max}+1$. Если $x_{max}=255$, полагаем $b=255$. Если $b<8$ полагаем $b=8$.

3)При выборе $a$ исходим из 2 условий: $a\le x_{min}$ и $с$- целое, т.е. $b-a$ кратно 8.
Выбрать такое число несложно: полагаем $a= x_{min}$ и, если нужно, уменьшаем его на 1, до тех пор пока не выполнится $(b-a) \mbox{mod}\, 8=0$.

4) $c=\frac{b-a}8$.

5) Вычисляем код числа $x_i$: для всех полагаем $d_i=\left[\frac{x_i-a}c \right]$, для $x_i=255$ полагаем $d_i=7$.

..... И никакой оптимизации

6) Profit

Спорить не нужно, просто реализуйте этот алгоритм и сравните с вашим. Успехов!

Имеется 16 целых чисел $x_i$ из интервала $[0,255]$. Здесь $[a,b]$ - обозначение замкнутого интервала.
Нужно их перекодировать в значения из интервала $[0,7]$.
Для этого любой разумный человек выберет интервал $[a,b] \subset [0,255]$ и такой, что все $x_i\in[a,b]$.
Потом разобьет интервал $[a,b]$ на 8 (восемь) интервалов длиной $c=(b-a)/8$, каждому из подъинтервалов длины $c$ сопоставит значение от 0 до 7.
Далее он (разумный человек) возьмет конкретное число $x_i$ и проверит в какой из подъинтервалов это число попадет. Такой у этого числа и будет новый код. И выражение для этого кода простое: $d_i=\mbox{frac}((x_i-a)/c)$

Вы же делаете практически то же самое, но через жопу. Вы строите 8 чисел от $a$ до $b$, разделенных интервалами длиной $c'=(b-a)/7$. При этом Вы (чтобы все для себя еще более запутать ) вообще не интересуетесь, как числа $a$ и $b$ соотносятся с числами $x_i$. Дальше Вы вокруг каждого числа откладываете $\pm c'/2$ и получаете тоже 8 интервалов, разбивающих отрезок $[a-c'/2,b+c'/2]$. И тоже пытаетесь проверить в какой интервал попадает$x_i$. Поскольку о числах $a$ и $b$ Вы ничего не полагаете, то $x_i$ может попасть куда угодно или вообще никуда. Чтобы избежать этого Вы продолжаете лепить новые нелепости в виде каких-то минимаксов...
В результате действительно Вы считаете непонятно что и очень долго.

Теперь об этом:

Цитата

Если P[0] = 5, а P[1] = 8, то index(7) = 1, а не 0 как у Вас поэтому все рассчёты у Вас неверны

А с чего Вы взяли, что неверны? Как раз верны.
Да, если $a=5$ и $с=3$, то все числа из подъинтервала [5, 8) имеют индекс 0. А почему, собственно, нет? В моей модели числа 7 и 8 имеют разные индексы. А в вашей числа 6 и 7 имеют разные индексы. И что?
Такая модель. Не устраивает --- смените $a$ и $b$, сменится дkина интервалов, сменится и индекс у 7. Мы же обсуждаем не конкретные примеры, а общий подход. И как я уже показал, ваш подход математически ничем не отличается от моего. Только кривизной.

Цитата
dmitrynn
vpro,
a может быть меньше Xmin
b может быть больше Xmax
поэтому все Ваши рассчёты неверны

Именно это я и полагаю в своем алгоритме. Поэтому все мои расчеты верны.

Цитата
dmitrynn
* может быть и иначе. a > Xmin, b < Xmax. Главное - чтобы потери при таком кодировании были минимальны

Мочь то он может, да кто ж ему даст!? Именно в этих случаях потери при кодировании будут не просто большими --- катострофическими.

Устал я спорить с Вами. Странный Вы человек; просили о помощи, но от помощи отказываетесь.

...



Редактировалось 1 раз(а). Последний 17.07.2012 12:32.