Улучшено (?) решение Эрдёша по остроугольным треугольникам

[grizzly]

Sender в сообщении #1236973 писал(а):

Вот как раз сворачивание циклов в рекурсии может негативно сказаться на быстродействии, как мне кажется.

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

[fractalon]

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

Цитата:

Consider such $h_2$ parallel to $h$ X lies between $h$. Let
$h_3 = h + (0, \dots, 0, r) \subset {\mathbb R}^{d+1}$
Let $H$ be the hyperplane passing through $h_2$ and $h_3$

При этом у $h$ и $X$ последняя координата по определению там равна нулю - значит, и у $h_2$ тоже. Значит, плоскость $H$ исходит из $h_2$ под углом к последней оси координат, а не вдоль неё.

И всё бы ничего, но дальше, доказательстве proposition 4 он пишет (я сокращаю и переформулирую, оставляя смысл):

Цитата:

For each $v \in A$ we denote $C(v) \subset {\mathbb R}$ the circle with center in $v$ and orthogonal to $h$
[...]
For $(v,0,0) \in A$ Consider intersection $l$ of hyperplane $H$ with 2-plane $\left\lbrace{(v,x_d,x_{d+1})\ :\ x_i \in {\mathbb R}^{d+1}}\right\rbrace$.

Итак, поскольку по определению, гиперплоскость $h$ имеет вид $\left\lbrace{(x_1,\dots,x_{d-1},0,0)\ :\ x_i \in {\mathbb R}^{d+1} }\right\rbrace$, то $l$ будет попросту прямой, ортогональной к $h$. Далее,

Цитата:

Clearly $l$ intersect $C(v)$ in two points (one of them is $(v,0,r)$)

И вот тут загвоздка. То, что прямая пересекает окружность в двух точках - это понятно. Но ведь $l \in H$, а $H$, как говориилось выше, находится под углом к последней координатной оси. Значит, она не может пересекать окружность в крайней по этой оси точке, а, наоборот, будет пересекать в каком-нибудь $(v, \cos \alpha, \sin \alpha)$, причём для малого $\alpha$, коль скоро отклонение $h_3$ от основной гиперплоскости (равное этому самому $r$) используется там как достаточно малое.

[EvgeniiZh]

grizzly в сообщении #1236964 писал(а):

Более-менее разобрался в последней работе Дмитрия. Да, он нашёл интересный способ раздваивать точки при каждом увеличении размерности. И в каком-то смысле он выжал из этого способа максимум, я думаю (начиная с $\mathbb R^2$ точки раздваиваются "жадным" алгоритмом). Я думаю, что для следующего прорыва нужно будет отказаться от "жадности" (но не от технических идей -- они ещё сослужат службу, наверно).

Я вложил один из своих инструментов (основной) поиска ОМ. Он работает в пространстве $\mathbb R^4$. Выкладываю как есть, без подробных описаний (минимум полезных комментариев есть внутри -- основное поле деятельности для пользователя между 225 и 290 строками). Инструмент вообще был написан "под себя" (программист не я, это всё группа поддержки) и предназначался для творческого поиска решений, поэтому в нём осели какие-то малопонятные механизмы -- на них можно не обращать внимания. Если кого-то заинтересует, постараюсь ответить на возникающие вопросы. Имеется также аналогичный вариант для $\mathbb R^5$, который ищет ОМ из $2^4$ точек, я его тоже выдам, если будет спрос :)

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

-- 31.07.2017, 10:54 --

Это всё работает миллисекунды. А значит в 80-х вполне реально было посчитать на тех компах. Очень странно, что столько людей тогда прошло мимо.

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

Насчет эффективности - для начала я бы псоветовал вам dist2s переопределить как одномерный массив вместо двумерного. Впрочем на такой задаче (6ms на моем слабеньком ноуте - кстати, то что вы печатаете это не миллисекунды, для перевода во время надо разделить на CLOCKS_PER_SECOND) и с учетом того что профайлер не завелся из-за того самого огромного массива - что-то конкретное сказать сложно.

[grizzly]

EvgeniiZh

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

1. По поводу dist2s. Эта опция не является обязательной и в любом случае на сетке с большим количеством точек её приходится отключать (путём комментирования строки "#define precalc_dists").
2. Время задачи существенно возрастает даже в 4D, если увеличивать разрешающую способность сетки (параметр $L$) одновременно с глубиной поиска (задаётся с помощью deltas, dlist). Те параметры, которые были заданы в программе, дают только самый вершок айсберга и не позволяют увидеть другие интересные ОМ (остроугольные множества). Например, при $L=25$ и глубине поиска до 5 координатных единиц от каждого угла (плюс хотя бы несколько доп.точек по последней координате) время работы программы растёт до практической бесконечности, а результаты -- как и полагается -- становятся всё интереснее.
3. Я не программист, но думаю, что ускорить программу в разы одним улучшением кода уже не удастся. Я пару дней тому добавил в программу учёт одного типа симметрий -- это математическое улучшение дало ускорение в 3--4 раза (в зависимости от начальных данных). Есть ещё несколько симметрий, которые можно учесть. В сумме это даст ускорение для 4D примерно на десятичный порядок.
4. Учёт тех же симметрии для 5D может дать ускорение в 100--1000 раз, но этого явно недостаточно, чтобы получить там программно хоть какие-то решения. (Решение, которое я сумел найти, было найдено с помощью такой же программы в 5D, но с непомерно большими ручными трудозатратами.)

[EvgeniiZh]

grizzly в сообщении #1241235 писал(а):

EvgeniiZh

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

1. По поводу dist2s. Эта опция не является обязательной и в любом случае на сетке с большим количеством точек её приходится отключать (путём комментирования строки "#define precalc_dists").

В таком случае, еще более проблемным становится двумерный массив pset

grizzly в сообщении #1241235 писал(а):

EvgeniiZh
2. Время задачи существенно возрастает даже в 4D, если увеличивать разрешающую способность сетки (параметр $L$) одновременно с глубиной поиска (задаётся с помощью deltas, dlist). Те параметры, которые были заданы в программе, дают только самый вершок айсберга и не позволяют увидеть другие интересные ОМ (остроугольные множества). Например, при $L=25$ и глубине поиска до 5 координатных единиц от каждого угла (плюс хотя бы несколько доп.точек по последней координате) время работы программы растёт до практической бесконечности, а результаты -- как и полагается -- становятся всё интереснее.

Я так и не понял к сожалению, как менять параметры

grizzly в сообщении #1241235 писал(а):

EvgeniiZh
3. Я не программист, но думаю, что ускорить программу в разы одним улучшением кода уже не удастся. Я пару дней тому добавил в программу учёт одного типа симметрий -- это математическое улучшение дало ускорение в 3--4 раза (в зависимости от начальных данных). Есть ещё несколько симметрий, которые можно учесть. В сумме это даст ускорение для 4D примерно на десятичный порядок.

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

[grizzly]

EvgeniiZh в сообщении #1241304 писал(а):

Но, как я уже сказал, работать с кодом довольно сложно.

Да, я понимаю это. Программа, которая делалась "для себя" -- это всегда сложно передать другим. Плюс -- мой опыт в этом плане близок к нулю. См. также ответ ниже.

EvgeniiZh в сообщении #1241304 писал(а):

Я так и не понял к сожалению, как менять параметры

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

[atlakatl]

grizzly в сообщении #1241342 писал(а):

Программа, которая делалась "для себя" -- это всегда сложно передать другим

Раздражение EvgeniiZh не объективно. Любому программисту понятна своя программа. Но далеко не всякий понимает, что его код понятен только ему.
Программирование не стало литературой, - пока? Но возможен прогресс в этом направлении. Как старые китайские иероглифы несут в себе глубинный смысл, исходя именно из комбинации знаков. - Что не равно фонетическому письму.

[grizzly]

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

[EvgeniiZh]

atlakatl в сообщении #1241362 писал(а):

grizzly в сообщении #1241342 писал(а):

Программа, которая делалась "для себя" -- это всегда сложно передать другим

Раздражение EvgeniiZh не объективно. Любому программисту понятна своя программа. Но далеко не всякий понимает, что его код понятен только ему.

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

grizzly в сообщении #1241363 писал(а):

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

Я попробовал подправить код, в частности избавиться от глобальных переменных и смеси С/С++ - здесь. Если вам интересно такое направление, то предлагаю залить код на гитхаб и работать над ним там.

[arseniiv]

(Литература, глубинный смысл и тайны бытия)

atlakatl в сообщении #1241362 писал(а):

Программирование не стало литературой, - пока?

Чего это не стало? По-моему, все (если кроме начинающих?) программисты понимают, что если они пишут код, который будет надо хоть чуточку поддерживать (и даже если только единственным автором), это вполне себе определённый «жанр» человеческой литературы. Зависящий в большой степени от используемых языков и фреймворков, но.

atlakatl в сообщении #1241362 писал(а):

Как старые китайские иероглифы несут в себе глубинный смысл, исходя именно из комбинации знаков. - Что не равно фонетическому письму.

Это вообще непонятно как относится. У нас вот тоже письмо далеко не фонетическое, или английское, например.

[grizzly]

(НАСЧЁТ РАЗВИТИЯ ПРОЕКТА НА GITHAB'е)

EvgeniiZh в сообщении #1241389 писал(а):

Если вам интересно такое направление, то предлагаю залить код на гитхаб и работать над ним там.

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

Со своей стороны я буду делиться свежими идеями и результатами в этой теме. С той же симметрией например -- это просто и я расскажу об этом на выходных.

(ФОРМУЛИРОВКА ГИПОТЕЗЫ)

Обычно, когда описывают пример остроугольного множества (далее ОМ) в $\mathbb R^3$, приводят в пример бипирамидку. Я смотрю на неё чуть иначе: как на пирамиду с квадратным основанием, в котором две диагональные вершины квадрата совсем чуть приподняты над плоскостью основания. Отсюда идея проверить аналог в $\mathbb R^4$ -- взять там 3D-кубик и некоторые его вершины чуть "приподнять" в четвёртом измерении. По аналогии с тем квадратом. Дальше будем говорить только об этом 3D-кубике.

Таким образом, я предположил, что для максимальной мощности ОМ $S$ в $\mathbb R^d$ верна формула $|S_d|=2^{d-1}+1$, но ищу только $2^{d-1}$ точек.

(ИЗНАЧАЛЬНЫЕ ЦЕЛИ ПРОГРАММЫ)

Программа изначально была сделана как инструмент, с которым непрерывно работает пользователь -- он запускает программу при разных начальных данных, анализирует результаты и в соответствии с анализом изменяет входные данные. Этот процесс представлялся слишком творческим и важным для понимания, поэтому не было цели его автоматизировать.

Была надежда получить разные решения в $\mathbb R^4$ и $\mathbb R^5$ и попытаться заметить общую схему. Надежда пока не умерла и уже можно получить многие принципиально различные примеры ОМ в $\mathbb R^4$ (скорость работы программы здесь уже позволяет обойтись без творческого пользователя), но пример в $\mathbb R^5$ пока только один и на построение его было затрачено 100+ человекочасов кропотливой работы.

(ПРИНЦИПЫ РАБОТЫ ПРОГРАММЫ)

Я не буду пока описывать взаимодействие программы с пользователем-творцом, остановлюсь на автоматическом варианте. Здесь говорим только об $\mathbb R^4$.

Мы берём 3D-кубик со стороной $L$, разбиваем его по всем осям равномерной прямоугольной решёткой с расстоянием между ближайшими узлами delta. Каждая из 8 точек (будущего) искомого ОМ привязана к своему углу этого 3D-кубика. Пока почти все углы у нас -- $90^\circ $. Наша цель: небольшими шевелениями этих 8 вершин по узлам решётки добиться обострения всех этих углов. Шевеления вершин производятся без выхода за границы кубика.

В программе перебираются только 4 точки, которые находятся в плоскости $XOY$ (при $Z=0$), остальные точки получаются центрально симметричным переносом на параллельную плоскость при $Z=L$. Центр симметрии, естественно, в центре куба.

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

Подробности бэктрекинга.
Для каждой вершины 3D-кубика создаётся своё Допустимое Множество (ДМ) -- набор возможных вариантов её расположения в узлах решётки вблизи своего угла. Эти варианты создаются с помощью покоординатных массивов deltas. Я разберу чуть позже, как это задаётся и работает на конкретном примере с более подробными объяснениями.

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

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

[grizzly]

Продолжим.
Рассмотрим в качестве примера использования программы решение самой простой из интересных задач: какой минимальный размер куба в $\mathbb R^4$ нужно взять, чтобы на целочисленной решётке нашлось ОМ из 8 точек.

Я буду объяснять всё на примере программы, вложенной в это сообщение. В программе по умолчанию рассмотрена целочисленная решётка (то бишь, при delta равном 1) на кубе со стороной 10 (соответствует $L=10$).

Мы возьмём куб меньшего размера -- $L=7$. delta оставляем 1 (это целочисленная решётка, других пока рассматривать не будем). Чтобы перебрать все интересующие нас варианты 8-точечных множеств в этом кубе, мы должны для любой точки, соответствующей некоторому углу 3D-куба, задать Допустимое Множество (ДМ) для перебора по этой точке от угла до середины стороны по каждой координате. Скажем проще: каждая точка должна пробегать всю целочисленную решётку в своей осьмушке 3D-куба. Четвёртую координату будем пробегать полностью -- от 0 до 7.

Значит, для всех точек нужно задать ДМ от 0 до 3 включительно по первым трём координатам и от 0 до 7 по последней. Это делается так: создаём где-то в районе 250-й строки новые dlist (в данном случае они есть, но если бы не было, мы бы их сделали так):

  dlist g03={0, +delta, +2*delta, +3*delta};
  dlist g30={0, -delta, -2*delta, -3*delta};

upd: Таким образом, мы задаём отклонение нашей угловой точки не более чем на 3 шага внутрь куба по каждой координате.
В блоке присвоения deltas (строки в районе 260--270) заменяем dlist на нужные (либо убеждаемся, что там стоят нужные):

  for (int i=0; i<sol_size/2; i++) {
    for (int j=0; j<D-1; j++) {
      //if (i==0 || i==1) { deltas[i][j]=g00; } 
      //else { 
      switch (grid_base[i][j]) {
        case 0:
          deltas[i][j]=g03; break;  // здесь для этой задачи должно быть g03
        case L:
          deltas[i][j]=g30; break; // здесь для этой задачи должно быть g30
        default:  
          deltas[i][j]=g11;
      }

Последнее по default в данной задаче не будет задействовано, его можно проигнорировать.
Для перебора по четвёртой координате создаём там же dlist gt ($t$ -- это по имени координаты):

dlist gt={0,1,2,3,4,5,6,7};

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

Для окончательного решения поставленной задачи нам нужно попытаться снизить $L$ до 6 и убедиться, что в этом случае решений не будет. Для $L=6$ мы оставляем те же dlist g30 и dlist g03, а из списка dlist gt убираем 7. Запускаем и убеждаемся, что решений нет.

[grizzly]

На этих выходных мне наконец удалось найти в $R^4$ такое ОМ из 8 точек, за которым я давно охотился (я уже начинал было сомневаться, что такое существует).

a = (0,    0,      0,  L/a)
b = (L/a,  L-L/a,  1,  L)
c = (L,    0,      1,  0)
d = (L,    L,      0,  L/a + 1)

e = (L,      L,     L,    L/a)
f = (L-L/a,  L/a,   L-1,  L)
g = (0,      L,     L-1,  0)
h = (0,      0,     L,    L/a + 1)

Как обычно, последние 4 точки -- центрально-симметричные отображения первых 4-х (по первым трём координатам; последняя координата сохраняется).

Это решение имеет несколько отличительных особенностей:

Во-первых, первая и четвёртая точки находятся в своих родных углах куба. Поэтому такое решения является прямым обобщением моего любимого решения в $R^3$ -- квадрат из 4-х точек, две диагональные точки чуть приподняты.
Во-вторых, -- и это самое ценное -- это решение работает в самом широком диапазоне параметров: при любом $a\in [4;10000]$ и при $L\in [a^2; 10^9]$ (ограничения сверху здесь связаны с разрешающей способностью программы, наверное -- в общем я верхнюю границу аккуратнее не рассматривал, но в этих границах точно всё работает). Это ведь явно на что-то намекает (особенно $a^2$).

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

Мне всё это нравится, потому что это явно что-то закономерное и есть шанс найти подобное в R^5 выше и, если получится, то доказать это можно будет простым подсчётом углов, наверное.

Продолжение следует, надеюсь :)

-- 21.08.2017, 13:27 --

PS. Я нарочно затеял в самом начале участвовать в этой теме, решая по мере сил задачу в "прямом эфире". Я хотел таким образом честно проследить путь настоящего творческого решения со всеми трудностями, ошибками, достижениями и т.п. И старался как-то проследить / объяснить, каким образом возникают успехи (локальные и прорывы). Но при всём желании я не смогу объяснить, как получились те 3 прорыва (включая этот, последний). Никакого объяснения, кроме какого-то совершенно маловероятного чуда в голову не приходит.

-- 21.08.2017, 13:28 --

PPS. Само собой, размышления в стиле последнего комментария будут иметь какое-то значение, только если благодаря всей этой деятельности мне (или кому-то другому) удастся решить задачу

[Sender]

grizzly в сообщении #1242144 писал(а):

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

Хм, углы не считал, но вот, как ни странно, удалось аналитически найти точные допустимые значения параметров. Я обозначил L/a=r и ввёл в wolfram mathematica вот такой код:

points = {{0, 0, 0, r}, {r, L - r, 1, L}, {L, 0, 1, 0}, {L, L, 0, 
   r + 1}, {L, L, L, r}, {L - r, r, L - 1, L}, {0, L, L - 1, 0}, {0, 
   0, L, r + 1}}; tests = 
 Reduce[And @@ ((# > 0) & /@ 
     Union[FullSimplify /@ 
       Flatten[(p0 = #; ((#[[1]] - p0).(#[[2]] - p0)) & /@ 
            Subsets[Complement[points, {p0}], {2}]) & /@ 
         points]]), {L, r}, Reals]

(Оффтоп)

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

В итоге получилось

$$L>\text{Root}\left[\text{\#1}^3-15 \text{\#1}^2+15 \text{\#1}-5\&,1\right]\land \sqrt{L-1}<r<\frac{1}{3} (2 L-1)-\frac{1}{3} \sqrt{L^2+5 L-5}$$

На человеческом языке первое условие означает, что L должно быть больше первого корня уравнения $x^3-15x^2+15x-5=0$. Численно нижняя граница L чуть меньше 14.

[Sender]

Если рассуждать в терминах a и L, то a может принимать любое значение, большее 3, но в итоге дело всё равно не обходится без корня кубического уравнения. Если интересно, могу потом выписать эти выражения.