Формирование натурального ряда разностями

@atlakatl · Регистрация: 05.04.2018

Author24 — интернет-сервис помощи студентам

Добрый день.
Занимаюсь следующей задачей целочисленного программирования:
Разностями последовательности чисел получить наибольшее число членов натурального ряда, причём без "окон", - окно сразу прерывает серию.
Так из 3 членов [0, 1, 3] получаем 1=1-0, 2=3-1, 3=3-0
Приведу полученные мной последовательности до 32. Здесь q число членов, N - число натурального ряда, до которого удалось добраться:

Кликните здесь для просмотра всего текста

q=2, N=3
0 1
q=3, N=3
0 1 3
q=4, N=6
0 1 4 6
q=5, N=9
0 1 2 6 9
q=6, N=13
0 1 4 5 11 13
q=7, N=18
0 2 7 14 15 18 24
q=8, N=23
0 1 4 10 16 18 21 23
q=9, N=29
0 1 4 10 16 22 24 27 29
q=10, N=35
0 1 4 10 16 22 28 30 33 35
q=11, N=41
0 1 4 10 16 22 28 34 36 39 41
q=12, N=46
0 7 16 28 29 31 34 42 44 48 67 74
q=13, N=62
0 5 12 18 36 50 51 52 53 54 61 73 80
q=14, N=62
0 5 12 18 36 50 51 52 53 54 61 73 80 111
q=15, N=70
0 7 11 14 20 26 31 32 54 62 64 70 72 80 99
q=16, N=74
0 7 11 14 20 26 31 32 54 62 64 70 72 80 85 99
q=17, N=81
0 9 13 23 28 36 38 44 46 54 76 77 88 94 97 101 116
q=18, N=104
0 1 2 3 48 55 60 65 70 75 80 85 90 94 98 101 104 141
q=19, N=110
0 1 2 3 4 48 56 61 66 71 76 81 86 91 96 98 102 107 110
q=20, N=120
0 1 2 3 4 48 58 64 70 75 80 85 90 95 100 105 109 113 117 120
q=21, N=125
0 1 2 3 4 48 58 64 70 75 80 85 90 95 100 105 109 113 118 123 125
q=22, N=147
0 1 2 3 4 5 10 69 76 80 85 90 95 100 106 112 118 124 130 136 143 147
q=23, N=153
0 1 2 3 4 5 10 69 76 80 85 90 95 100 106 112 118 124 130 136 143 147 153
q=24, N=168
0 1 2 3 4 5 75 82 87 90 95 101 107 113 118 124 129 135 141 147 153 159 163 168
q=25, N=183
0 1 2 3 4 5 89 93 98 103 109 115 121 127 133 138 144 150 156 162 168 174 175 181 183
q=26, N=191
0 1 2 3 4 5 65 90 97 101 107 113 119 125 132 136 142 148 154 160 166 172 178 181 186 191
q=27, N=206
0 1 2 3 4 5 15 99 105 107 113 119 125 131 137 143 149 155 161 167 173 179 185 192 196 201 206
q=28, N=212
0 1 2 3 4 5 15 99 105 107 113 119 125 131 137 143 149 155 161 167 173 179 185 192 196 201 206 212
q=29, N=235
0 1 2 3 4 5 114 115 122 123 129 135 141 147 153 159 165 171 177 183 189 195 201 207 213 219 225 230 235
q=30, N=247
0 1 2 3 4 5 6 7 88 107 119 128 132 140 149 154 161 169 177 185 191 196 203 211 216 223 229 234 239 247
q=31, N=255
0 1 2 3 4 5 6 7 88 107 119 128 132 140 149 154 161 169 177 185 191 196 203 211 216 223 229 234 239 247 255
q=32, N=284
0 1 2 3 4 5 6 7 67 127 129 138 140 149 158 166 174 182 190 198 206 214 221 228 233 238 246 254 262 270 277 284

Есть и другие закономерности, но на больших q я, скорее всего, оптимума не нашёл.
Для генерации пробовал:
1. Чистый рандом. Перестаёт выдавать оптимум же с q=10
2. Формирование из прошлых и будущих последовательностей. Самый плодотворный метод. Изменяем значения 1-5 членов, оставляя другие прежними.
3. Малые изменения значений оптимума. Уточняет метод 2.
4. Модификация только "вялых", дающих меньший вклад в создании N. Уточнение незначительное.
5. Поиск на основе "почти оптимальных" последовательностей. Вклад небольшой.
6. Рандомное изменение членов для "заделывания окон". Окон становится ещё больше.
7. Сейчас решил попробовать штрафную функцию: допускать окна. но штрафовать за их наличие. Результат пока неясен.
Традиционные МО не работают совсем, - критерий оптимальности очень уж сложный.
Может, я ломлюсь в открытые двери. и метод на поверхности? Вряд ли. В OEIS этой последовательности нет. Но при достижении качественного результата я её обязательно попрошу включить в базу.
Программирую на Pascal ABC NET. Но мне нужна просто идея для качественной оптимизации.

Байт · 24.01.2019, 11:54

atlakatl, Дернуло меня прочитать ваш пост перед сном! И снилась мне ваша задача всю ночь.

И вот выспались такие простые соображения.
N <= (q-1)q/2
Помимо тех критериев, которые вы привели в списке, можно еще рассматривать количество повторов разностей. Чем их меньше - тем лучше.
Интересно, как вы получили свои ряды? Полный перебор? Как он устроен? Иногда удается его здорово сократить. Эвристики?
Да, традиционные МО здесь работать не должны.
А задача любопытная.
И еще. Я бы на вашем месте попросил тему перенести в "Алгоритмы". Или в "Комбинаторику". Имхо, это ближе.

@atlakatl · 24.01.2019, 21:28 **[ТС]**

Рад, что откликнулись.
Константа, что вы привели, присутствует в программе во множестве.
Полный перебор это факториал от числа членов. Что не работает уже на втором десятке чисто физически.
Основные методы я перечислил. Пробую в ручном режиме, выбираю лучшее отовсюду.
Метод №7 упростился. Чисто штрафные функции не пошли. А получилось вот что.
В результате рандомных малых изменений в подавляющем большинстве случаев получается каша из повторов. Это да.
Так вот. Если повторов - я рассматриваю не их как таковые, а пропуски чисел вплоть до текущего достигнутого максимума - мало, то данный вариант я "дожимаю" серией испытаний. Многодырные же варианты игнорируются.
Но ещё не отработана тема "мало-много дырок". Пробую варианты.
В идеале неплохо бы подгрузить ИИ. Но это желаемое для любого метода оптимизации.
Да, главное.
Последовательность - почти эту - мне нашли в OEIS: http://oeis.org/wiki/User:Pete... conjecture
Только её автор рассматривает варианты, когда ряд заканчивается на сам максимум. Так в большинстве случаев и бывает. Но уже для q=7 мой ряд даёт на единицу больше: не 17, а 18.
Но автор свои максимумы считал профессионально. Не то что я. Зайдёте - убедитесь.

Байт · 24.01.2019, 22:54

atlakatl, спасибо за ссылочку. Оченно красиво. Но к сожалению, я английский читаю с большим словарем

Да, я понимаю, что мое "открытие" совершенно тривиально.

Сообщение от atlakatl

Полный перебор это факториал от числа членов.

Это понятно. Но есть всякие штуки, его ограничивающие. Типа "ветвей и границ". И вот как именно построить "рубку ветвей", я не вижу. Вообще плохо вижу эту задачу. Хотя и понимаю. Но если чего приснится - я вам обязательно доложу. Даже если это будет опять полная тривиальщина.
Удачи!

Кстати, созерцая ваши ряды, наткнулся на, видимо, ошибочку (строки 23-26)

Код

q=13, N=62
0 5 12 18 36 50 51 52 53 54 61 73 80
q=14, N=62
0 5 12 18 36 50 51 52 53 54 61 73 80 111

@eropegov · 25.01.2019, 16:46

Сообщение от atlakatl

Занимаюсь следующей задачей целочисленного программирования:
Разностями последовательности чисел получить наибольшее число членов натурального ряда

А откуда эта задача, если не секрет? Она чисто учебная или что-то поинтереснее?

@atlakatl · 26.01.2019, 02:56 **[ТС]**

eropegov, просто интересно. Ну и при должной загрузке темой и удаче можно и научный результат сварганить. Тем более, приближать можно не только натуральный ряд, но и, к примеру, простые числа. Есть думка получить ряд, который хуже всего приближается разностями.

@eropegov · 27.01.2019, 09:30

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

А если попробовать наоборот - идти не от $https://www.cyberforum.ru/cgi-bin/latex.cgi?q$ к $https://www.cyberforum.ru/cgi-bin/latex.cgi?N$ , а от $https://www.cyberforum.ru/cgi-bin/latex.cgi?N$ к $https://www.cyberforum.ru/cgi-bin/latex.cgi?q$ ? То есть сначала мы берём таблицу размером $https://www.cyberforum.ru/cgi-bin/latex.cgi?(N+1)\times(N+1)$ (нумерация строк и столбцов - от 0 до $https://www.cyberforum.ru/cgi-bin/latex.cgi?N$ ), в ячейку $https://www.cyberforum.ru/cgi-bin/latex.cgi?(i,j)$ вписываем разность $https://www.cyberforum.ru/cgi-bin/latex.cgi?i-j$ . Значения разностей выстроятся по диагональным линиям. А потом начинаем вычёркивать как можно больше строк и столбцов таким образом, чтобы каждое значение разности осталось в таблице.

@atlakatl 1 / 1 / 0 Регистрация: 05.04.2018 Сообщений: 36
		1
	Формирование натурального ряда разностями 20.01.2019, 11:07. Показов 685. Ответов 6 Метки оптимизация (Все метки) Добрый день. Занимаюсь следующей задачей целочисленного программирования: Разностями последовательности чисел получить наибольшее число членов натурального ряда, причём без "окон", - окно сразу прерывает серию. Так из 3 членов [0, 1, 3] получаем 1=1-0, 2=3-1, 3=3-0 Приведу полученные мной последовательности до 32. Здесь q число членов, N - число натурального ряда, до которого удалось добраться: Кликните здесь для просмотра всего текста q=2, N=3 0 1 q=3, N=3 0 1 3 q=4, N=6 0 1 4 6 q=5, N=9 0 1 2 6 9 q=6, N=13 0 1 4 5 11 13 q=7, N=18 0 2 7 14 15 18 24 q=8, N=23 0 1 4 10 16 18 21 23 q=9, N=29 0 1 4 10 16 22 24 27 29 q=10, N=35 0 1 4 10 16 22 28 30 33 35 q=11, N=41 0 1 4 10 16 22 28 34 36 39 41 q=12, N=46 0 7 16 28 29 31 34 42 44 48 67 74 q=13, N=62 0 5 12 18 36 50 51 52 53 54 61 73 80 q=14, N=62 0 5 12 18 36 50 51 52 53 54 61 73 80 111 q=15, N=70 0 7 11 14 20 26 31 32 54 62 64 70 72 80 99 q=16, N=74 0 7 11 14 20 26 31 32 54 62 64 70 72 80 85 99 q=17, N=81 0 9 13 23 28 36 38 44 46 54 76 77 88 94 97 101 116 q=18, N=104 0 1 2 3 48 55 60 65 70 75 80 85 90 94 98 101 104 141 q=19, N=110 0 1 2 3 4 48 56 61 66 71 76 81 86 91 96 98 102 107 110 q=20, N=120 0 1 2 3 4 48 58 64 70 75 80 85 90 95 100 105 109 113 117 120 q=21, N=125 0 1 2 3 4 48 58 64 70 75 80 85 90 95 100 105 109 113 118 123 125 q=22, N=147 0 1 2 3 4 5 10 69 76 80 85 90 95 100 106 112 118 124 130 136 143 147 q=23, N=153 0 1 2 3 4 5 10 69 76 80 85 90 95 100 106 112 118 124 130 136 143 147 153 q=24, N=168 0 1 2 3 4 5 75 82 87 90 95 101 107 113 118 124 129 135 141 147 153 159 163 168 q=25, N=183 0 1 2 3 4 5 89 93 98 103 109 115 121 127 133 138 144 150 156 162 168 174 175 181 183 q=26, N=191 0 1 2 3 4 5 65 90 97 101 107 113 119 125 132 136 142 148 154 160 166 172 178 181 186 191 q=27, N=206 0 1 2 3 4 5 15 99 105 107 113 119 125 131 137 143 149 155 161 167 173 179 185 192 196 201 206 q=28, N=212 0 1 2 3 4 5 15 99 105 107 113 119 125 131 137 143 149 155 161 167 173 179 185 192 196 201 206 212 q=29, N=235 0 1 2 3 4 5 114 115 122 123 129 135 141 147 153 159 165 171 177 183 189 195 201 207 213 219 225 230 235 q=30, N=247 0 1 2 3 4 5 6 7 88 107 119 128 132 140 149 154 161 169 177 185 191 196 203 211 216 223 229 234 239 247 q=31, N=255 0 1 2 3 4 5 6 7 88 107 119 128 132 140 149 154 161 169 177 185 191 196 203 211 216 223 229 234 239 247 255 q=32, N=284 0 1 2 3 4 5 6 7 67 127 129 138 140 149 158 166 174 182 190 198 206 214 221 228 233 238 246 254 262 270 277 284 Есть и другие закономерности, но на больших q я, скорее всего, оптимума не нашёл. Для генерации пробовал: 1. Чистый рандом. Перестаёт выдавать оптимум же с q=10 2. Формирование из прошлых и будущих последовательностей. Самый плодотворный метод. Изменяем значения 1-5 членов, оставляя другие прежними. 3. Малые изменения значений оптимума. Уточняет метод 2. 4. Модификация только "вялых", дающих меньший вклад в создании N. Уточнение незначительное. 5. Поиск на основе "почти оптимальных" последовательностей. Вклад небольшой. 6. Рандомное изменение членов для "заделывания окон". Окон становится ещё больше. 7. Сейчас решил попробовать штрафную функцию: допускать окна. но штрафовать за их наличие. Результат пока неясен. Традиционные МО не работают совсем, - критерий оптимальности очень уж сложный. Может, я ломлюсь в открытые двери. и метод на поверхности? Вряд ли. В OEIS этой последовательности нет. Но при достижении качественного результата я её обязательно попрошу включить в базу. Программирую на Pascal ABC NET. Но мне нужна просто идея для качественной оптимизации. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	24.01.2019, 11:54	2
	atlakatl, Дернуло меня прочитать ваш пост перед сном! И снилась мне ваша задача всю ночь. И вот выспались такие простые соображения. N <= (q-1)q/2 Помимо тех критериев, которые вы привели в списке, можно еще рассматривать количество повторов разностей. Чем их меньше - тем лучше. Интересно, как вы получили свои ряды? Полный перебор? Как он устроен? Иногда удается его здорово сократить. Эвристики? Да, традиционные МО здесь работать не должны. А задача любопытная. И еще. Я бы на вашем месте попросил тему перенести в "Алгоритмы". Или в "Комбинаторику". Имхо, это ближе. 1

@atlakatl 1 / 1 / 0 Регистрация: 05.04.2018 Сообщений: 36
	24.01.2019, 21:28 [ТС]	3
	Рад, что откликнулись. Константа, что вы привели, присутствует в программе во множестве. Полный перебор это факториал от числа членов. Что не работает уже на втором десятке чисто физически. Основные методы я перечислил. Пробую в ручном режиме, выбираю лучшее отовсюду. Метод №7 упростился. Чисто штрафные функции не пошли. А получилось вот что. В результате рандомных малых изменений в подавляющем большинстве случаев получается каша из повторов. Это да. Так вот. Если повторов - я рассматриваю не их как таковые, а пропуски чисел вплоть до текущего достигнутого максимума - мало, то данный вариант я "дожимаю" серией испытаний. Многодырные же варианты игнорируются. Но ещё не отработана тема "мало-много дырок". Пробую варианты. В идеале неплохо бы подгрузить ИИ. Но это желаемое для любого метода оптимизации. Да, главное. Последовательность - почти эту - мне нашли в OEIS: http://oeis.org/wiki/User:Pete... conjecture Только её автор рассматривает варианты, когда ряд заканчивается на сам максимум. Так в большинстве случаев и бывает. Но уже для q=7 мой ряд даёт на единицу больше: не 17, а 18. Но автор свои максимумы считал профессионально. Не то что я. Зайдёте - убедитесь. 1

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	24.01.2019, 22:54	4
	atlakatl, спасибо за ссылочку. Оченно красиво. Но к сожалению, я английский читаю с большим словарем Да, я понимаю, что мое "открытие" совершенно тривиально. Сообщение от atlakatl Полный перебор это факториал от числа членов. Это понятно. Но есть всякие штуки, его ограничивающие. Типа "ветвей и границ". И вот как именно построить "рубку ветвей", я не вижу. Вообще плохо вижу эту задачу. Хотя и понимаю. Но если чего приснится - я вам обязательно доложу. Даже если это будет опять полная тривиальщина. Удачи! Кстати, созерцая ваши ряды, наткнулся на, видимо, ошибочку (строки 23-26) Код q=13, N=62 0 5 12 18 36 50 51 52 53 54 61 73 80 q=14, N=62 0 5 12 18 36 50 51 52 53 54 61 73 80 111 0

@eropegov $Эксперт по математике/физике$ 505 / 465 / 100 Регистрация: 30.01.2017 Сообщений: 1,371
	25.01.2019, 16:46	5
	Сообщение от atlakatl Занимаюсь следующей задачей целочисленного программирования: Разностями последовательности чисел получить наибольшее число членов натурального ряда А откуда эта задача, если не секрет? Она чисто учебная или что-то поинтереснее? 0

@atlakatl 1 / 1 / 0 Регистрация: 05.04.2018 Сообщений: 36
	26.01.2019, 02:56 [ТС]	6
	eropegov, просто интересно. Ну и при должной загрузке темой и удаче можно и научный результат сварганить. Тем более, приближать можно не только натуральный ряд, но и, к примеру, простые числа. Есть думка получить ряд, который хуже всего приближается разностями. 0

@eropegov $Эксперт по математике/физике$ 505 / 465 / 100 Регистрация: 30.01.2017 Сообщений: 1,371
	27.01.2019, 09:30	7
	Понятно. Раз задача не учебная, а своя - она может быть интереснее, а никакой гарантии продвижения нет. А если попробовать наоборот - идти не от $https://www.cyberforum.ru/cgi-bin/latex.cgi?q$ к $https://www.cyberforum.ru/cgi-bin/latex.cgi?N$ , а от $https://www.cyberforum.ru/cgi-bin/latex.cgi?N$ к $https://www.cyberforum.ru/cgi-bin/latex.cgi?q$ ? То есть сначала мы берём таблицу размером $https://www.cyberforum.ru/cgi-bin/latex.cgi?(N+1)\times(N+1)$ (нумерация строк и столбцов - от 0 до $https://www.cyberforum.ru/cgi-bin/latex.cgi?N$ ), в ячейку $https://www.cyberforum.ru/cgi-bin/latex.cgi?(i,j)$ вписываем разность $https://www.cyberforum.ru/cgi-bin/latex.cgi?i-j$ . Значения разностей выстроятся по диагональным линиям. А потом начинаем вычёркивать как можно больше строк и столбцов таким образом, чтобы каждое значение разности осталось в таблице. 0