Помогите алгоритмом. Разбиение упорядоченных чисел

← →
DevilDevil © (2012-07-10 11:56) [0]

Здравствуйте, уважаемые форумчане

Существует ряд упорядоченных чисел. (дробных, но для простоты берём целые)
Например
5 18 19 41 44 67 69 69 70 71 78 85 87 96 115 121 144 541 834 999 1001

Необходимо подобрать 8 равноудалённых "столбиков" (чисел) чтобы с их помощью закодировать числовой ряд с наименьшими потерями

Например такими "столбиками" могут быть:
44.5 175 305.5 436 566,5 697 827,5 1058

Т.е. результат кодируется "стартом" (44.5) и "приращением" (130.5)
Все "столбики" могут выходить за диапазоны ряда
Но существуют границы возможных значений. Например от 0 до 10 000.
Все числа положительные

← →
Компромисс © (2012-07-10 12:04) [1]

Очень похоже на интерполяцию полиномом 1-ой степени, метод наименьших квадратов тебе в помощь...

← →
Дмитрий С © (2012-07-10 12:36) [2]

> с их помощью закодировать числовой ряд с наименьшими потерями

Еще бы вот это знать что значит

← →
БарЛог © (2012-07-10 12:51) [3]

А ты уверен, что такие "столбики" всегда будут существовать?

1,2,5,10,999,1000

← →
DevilDevil © (2012-07-10 13:02) [4]

Еще бы вот это знать что значит

"потеря" между числом ряда и "столбиком" = | Ч - С |
"столбик числа" - столбик максимально близкий к числу (или минимальной потерей)

"потеря" по решению = сумме потерь между (числами и их столбиками)

А ты уверен, что такие "столбики" всегда будут существовать? 1,2,5,10,999,1000

Набор чисел всегда больше восьми

Очень похоже на интерполяцию полиномом 1-ой степени, метод наименьших квадратов тебе в помощь...

а может как-то попроще ?

← →
Омлет © (2012-07-10 13:07) [5]

Выкинь слово "столбик". Это просто точки на числовой прямой.

← →
Компромисс © (2012-07-10 13:21) [6]

> а может как-то попроще ?

Куда уж проще...

http://helpstat.ru/2012/01/metod-naimenshix-kvadratov/

← →
DevilDevil © (2012-07-10 13:53) [7]

Куда уж проще...

ересь какая-то
ты можешь по-человечески объяснить ?
и у меня здесь не двумерное пространство

← →
Плохиш © (2012-07-10 14:14) [8]

Так и представляется план выпуска книг редакции:
2012 - "Метод наименьших квадратов для полных идиотов"
2013 - "Умножение и деление для полных идиотов"
2014 - "Сложение и вычитание для полных идиотов"
2015 - "Что-такое числа? Для полных идиотов"

← →
Думкин © (2012-07-10 14:16) [9]

> 2016 - "Как правильно задавать вопросы? Для полных идиотов"

← →
DevilDevil © (2012-07-10 14:21) [10]

Удалено модератором

← →
Думкин © (2012-07-10 14:25) [11]

А вопроса в нормальной постановке просто нет. Есть нечто, на что можно только делать попытки угадать, что же именно хотел автор. В такие игры играть - интереса мало.

← →
DevilDevil © (2012-07-10 14:29) [12]

Удалено модератором

← →
Компромисс © (2012-07-10 14:30) [13]

DevilDevil © (10.07.12 13:53) [7]

Двумерное. Xi=i, 1<=i<=N

ЗЫ. Посмотрел анкету, в 26 лет незаконченное высшее. Зря не закончил, тут как раз высшая математика. Объяснять дальше не буду, слишком много объяснять придется, тем более, что я уже забыл детали, только самое важное помню.

← →
Думкин © (2012-07-10 14:33) [14]

> что не понятно в вопросе ?

В первоначальной формулировке? Ну, вообще говоря все.

с пояснением в [4] уже получше. Но с кодировкой все-равно вопросы.

← →
DevilDevil © (2012-07-10 14:37) [15]

> Компромисс © (10.07.12 14:30) [13]

я давно не редактировал анкету
высшее давно окончил, по профессии работаю 6 лет. Программирую вообще уже 12.

Но меня не прёт от математического языка, особенно в задачах, которые в лёгкую объясняются на пальцах. Если не хочешь - не объясняй. Просто смысла тогда в твоём посте нет. А разбираться в этой теории, не будучи уверенным что она подойдёт для моей задачи - не буду. Лучше дождусь человека по-проще, который не только знает названия методов, но и умеет их применять в жизни

← →
Компромисс © (2012-07-10 14:42) [16]

> что не понятно в вопросе ?

Есть набор чисел: Y1=3, Y2=7, Y3=11
Нужно его интерполировать двумя точками (в данном случае ответ должен быть 5 и 9)
Значит, нужно найти функцию Y=AX+B
X1=1, X2=2, X3=3 и найти ее значения для X=1.5 и X=2.5.

Ответом будет Y=4X-1 при X=1.5 и X=2.5, то есть 5 и 9, как и ожидалось.
Я правильно понял вопрос? :-)

← →
DevilDevil © (2012-07-10 14:42) [17]

> с пояснением в [4] уже получше. Но с кодировкой все-равно
> вопросы.

давай я тебе по детсадовски объясню

- есть ряд чисел
- у нас есть "палитра" из 8ми равномерных значений
- необходимо определить наиболее эффективную "палитру" с помощью которой можно представить этот ряд чисел

эффективность здесь определяется минимизацией суммы отклонений

← →
DevilDevil © (2012-07-10 14:48) [18]

> X1=1, X2=2, X3=3 и найти ее значения для X=1.5 и X=2.5.

ээ.. вопрос то правильно..
X у нас от одного до 8 ?
и зачем нам значения X=1.5 и X=2.5 ?

B по твоей формуле - это как раз стартовая точка
а A - это коэфициент приращения

← →
БарЛог © (2012-07-10 14:50) [19]

DevilDevil © (10.07.12 13:02) [4]

> Набор чисел всегда больше восьми

Ну предоставь решение для:
1,2,5,10,999,1000,1001,1002,1003

> "палитру"

Тут без паллитры и не разберёсся :)

← →
DevilDevil © (2012-07-10 15:02) [20]

> Ну предоставь решение для:

Ну точного решения я не знаю

Но будет оно близким к:

5.00 147.29 289.57 431.86 574.14 716.43 858.71 1001.00

← →
Компромисс © (2012-07-10 15:07) [21]

> и зачем нам значения X=1.5 и X=2.5 ?

Откуда я знаю :)

У тебя есть 50 значений, а ты хочешь на их основе 8 посчитать, вот и найди A и B из Y=AX+B, а потом посчитай Y для X=1, X=8+1/7,X=15+2/7/,X=22+3/7,X=29+4/7,X=35+5/7,X=42+6/7, X=50

← →
DevilDevil © (2012-07-10 15:13) [22]

:))

т.е. брать вот эту формулу? http://helpstat.ru/wp-content/ql-cache/quicklatex.com-611eab674823fc6f8e5d92b2b2b259ee_l3.gif

Ты уверен что здесь X = i ?

← →
Компромисс © (2012-07-10 15:17) [23]

> т.е. брать вот эту формулу?

А вот детали я не помню, последний раз применял этот метод больше 10 лет назад :)

> Ты уверен что здесь X = i ?

Конечно. Ты же сам написал, что есть ряд чисел, а у каждого члена ряда чисел есть порядковый номер. То есть ты привел Y(1), Y(2), ... Y(N)

← →
DevilDevil © (2012-07-10 15:34) [24]

> Компромисс © (10.07.12 15:17) [23]

чёт мне кажется не подходит эта формула

← →
Jeer © (2012-07-10 16:19) [25]

"Гадание на кофейной гуще, когда изначально был заварен чай" (С)

← →
Думкин_ (2012-07-10 16:59) [26]

> DevilDevil ©

Вот смотри. Не будем 8 точек, а рассмотрим 2 как и предлагает Компромисс. Для начала.

Как я могу понять то, что ты описал и что из этого выходит.

1. При условии наличия "столбиков" числа из набора разбиваются на непересекающиеся множества, по принципу - какой столбик ближе (в случае равенства прибиваем к любому, но одному).

2. Для всех чисел в группе считается расстояние до столбика и потом их сумма.

3. потом сумма по всем группам.

4. Надо предложить такую систему из столбиков, чтобы указанная сумма минимизировалась.

----------

Теперь есть группа - 3,7, 11 что предложил Компромисс. Какие будут столбики? Что ты ожидаешь увидеть?

Минимизировать тут будут такие наборы столбиков

1. Первый - 3, второй число из отрезка 7-11.
2. Первый - 11, второй число из отрезка 3-7.

В обоих случаях суммарное отклонение 4. Но скорее всего, тебе бы понравилось решение (5,9). Но в этом случае отклонение будет 6.

---------

Собственно и возникает вопрос - а что минимизируем? Может при заданном наборе столбцов считаем максимальное отклонение и потом ищем набор который имеет минимум по этому максимуму?

В такой постановке, учитывая п.1. задача становится сложнее. Но главное в другом - тебе что надо то? Правильная постановка задача - зачастую 75% ее решения.
-----------

А по детсадовски - не надо. Я в такой постановке почти каждый день получаю задания - желания убить постановщиков присутствует. Надо исходить из того, что надо то в конце концов.

← →
БарЛог © (2012-07-10 17:15) [27]

> Правильная постановка задача - зачастую 75% ее решения.

Сейчас пойдет разговор о том, что на Мастерах одни тролли, и помочь не могут :)

← →
DevilDevil © (2012-07-10 19:35) [28]

1. Первый - 3, второй число из отрезка 7-11. 2. Первый - 11, второй число из отрезка 3-7. В обоих случаях суммарное отклонение 4. Но скорее всего, тебе бы понравилось решение (5,9). Но в этом случае отклонение будет 6.

Хороший пример
Исходя из постановки задачи и 7-11 и 3-7 будут оптимальными решениями. Потому что считаем разницу по модулю

Решение (5,9) наверное подойдёт если считать отклонением сумму квадратов. 16 против 12

В целом мне интересны оба способа решения. Но если найти хотя бы один - уже было бы не плохо

← →
Думкин_ (2012-07-10 20:10) [29]

> Решение (5,9) наверное подойдёт если считать отклонением
> сумму квадратов. 16 против 12

Тут не понял. Это решение можно формализовать в требовании

> Может при заданном наборе столбцов считаем максимальное
> отклонение и потом ищем набор который имеет минимум по этому
> максимуму?

И с оговоркой еще по выбору столбца и разбиением. Т.к. в этом случае надо, чтобы 7 работало на два фронта - вправо и влево. Иначе оптимальным будет или (3,9) или (11,5).
----------

С первым подходом понятно тогда в постановке. Но как с ходу искать ответ для 8 и произвольной группы - не скажу сейчас, т.к. не знаю.

← →
DevilDevil © (2012-07-15 20:49) [30]

По поводу метода наименьших квадратов ?

Метод не подходит, потому что количество X совпадает с количеством Y

У нас по другому. Палитра из 8 элементов, а массив поступающих данных - больше

← →
картман © (2012-07-15 23:49) [31]

> DevilDevil © (15.07.12 20:49) [30]

> Палитра из 8 элементов,

любой алгоритм кластеризации, среде-арифметические кластеров будут "столбиками"

← →
DevilDevil © (2012-07-17 17:10) [32]

> любой алгоритм кластеризации, среде-арифметические кластеров
> будут "столбиками"

Я не уверен, что алгоритм кластеризации в точности подойдёт
Потому что наши "столбики" идут друг за другом, на равном отдалении друг от друга
кроме того как быть с начальной точкой a ?
(т.е. в какой точке начинается первый столбик)

← →
картман © (2012-07-17 17:47) [33]

> кроме того как быть с начальной точкой a ?
> (т.е. в какой точке начинается первый столбик)

метод к-средних - начальные центры могут быть случайными

← →
DevilDevil © (2012-07-17 20:44) [34]

опиши схематично что в какой последовательности "такой" алгоритм должен сделать

← →
картман © (2012-07-17 22:21) [35]

есть шеть чисел: 1,2,3,7,11,13 разбить на два "столбика", выбираем случайно два, например, х1=7 и х2=16, потом считаешь отклонения(в одномерном пр-ве просто разность) е1=abs(1-7) и т .д., в первом столбике будут w1=1,2,3,7,11 во-втором w2=13, пересчитываешь "столбики" с1=(1+2+3+7+11)/5=4.8 , с2=13/1 перемещаешь числа
w1=1,2,3,7; w2=11,13 и т.д. пока числа бегают

← →
DevilDevil © (2012-07-18 00:52) [36]

завтра обдумаю
спасибо !

← →
Студент (2012-07-18 01:04) [37]

Сортировка слиянием? Когда до меньшего деления доходишь вместе массив не собираешь?

← →
DevilDevil © (2012-07-18 01:36) [38]

> картман © (17.07.12 22:21) [35]

Опиши ещё раз.. Если чисел допустим 8, а столбиков 4. Потому что с двумя - принцип не ясен

> Студент (18.07.12 01:04) [37]

что ты имеешь ввиду ?
давай цифрами что ли )

← →
Студент (2012-07-18 03:20) [39]

DevilDevil © (18.07.12 01:36) [38]

http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC

> Студент (18.07.12 03:20) [39]

а почему не быстрой сортировкой ? )))))))))))))))

up
взываю мозги мирового сообщества программистов )

> Потому что с двумя - принцип не ясен

цепляешь число к ближайшему столбику

> картман © (19.07.12 23:18) [42]

ты опиши пример с 4мя столбиками и 8ю числами
сдаётся мне у тебя "столбики" не на равном расстоянии друг от друга, а по задаче - должны быть равноудалены друг от друга

равноудаленными не будут

> ну и в чём тогда прикол твоего мега алгоритма ?

он не гига

DevilDevil ©

По-моему, уже должно было стать очевидным, что готового решения нет и быть не может ввиду специфики задачи. Если нужно точное решение, остается только один путь: написать целевую функцию (она будет min и abs использовать) и попытаться найти ее минимум. На кандидатскую по математике потянет, я думаю...

> Компромисс © (20.07.12 13:14) [47]

ты же говорил метод наименьших квадратов )

> готового решения нет и быть не может ввиду специфики задачи.

почему нет ?
неужели ни кластерный метод, ни метод наименьших квадратов, ни аналогичные алгоритмы - не могут помочь решить задачу ?

Я больше склоняюсь к мнению - что вы (и я соответственно) просто не можем подобрать нужный алгоритм.

> неужели ни кластерный метод, ни метод наименьших квадратов,
> ни аналогичные алгоритмы - не могут помочь решить задачу
> ?

Я думаю, вряд ли есть метод, который находит N столбиков, расстояния между которыми равны. Дело именно в этой специфике

Компромисс © (20.07.12 14:55) [49]

а что если адаптировать идею метода наименьших квадратов ?
я правда не врубился как она считается и как переделать под наш случай

> как переделать под наш случай

зачот

а по теме: допустимая величина отклонения от оптимального решения чему равна?

> а по теме: допустимая величина отклонения от оптимального
> решения чему равна?

--> 0

← →
_Картман (2012-07-21 23:38) [53]

задача не имеет решения

← →
_Картман (2012-07-21 23:38) [54]

задача не имеет решения

Помогите алгоритмом. Разбиение упорядоченных чисел Найти похожие ветки