Al Zimmermann: non-coplanar points

[ctac]

Vovka17 в сообщении #1123026 писал(а):

можно отрезать и выкинуть из поиска шар точек в центре

Попробовал - ничего не дало

Цитата:

В общем, довольно безрадостная картина вырисовывается...

Неужели нет какой-то закономерности!?

[Pavlovsky]

Задача замерзла. Более суток никто не вводил новых решений. Пора вливать свежую. кровь. Сменить состав участников?!

[dimkadimon]

Я нашёл симметрию которая даёт 14 точек для N=7 и 24 точек для N=11. Результат слабенький, но даёт надежду для симметричных подходов.

[dimkadimon]

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

Идея такая. Разбиваем куб на $P$ равных частей. Части могут иметь общие координаты. Например части могут быть конусами с острием в центре куба которые равномерно распределены. Выглядит это примерно так: http://2.bp.blogspot.com/-2qh0yxLS4Ug/U ... st+Co..JPG

В каждой части живет только одна из $P$ точек. Когда переставляем точку, двигаем ее только внутри своей части. Таким образом количество возможных "ходов" значительно сокращается. Решения остаются шарообразными.

[Vovka17]

Идея неплоха. (Как я могу сказать иначе, если сам активно занимался этим вопросом месяц назад )
Куб можно разделить на 2, 4, 8, 16, 24, 48(max) равных частей (с точностью до поворотов и отзеркаливаний)
Куб разбитый на 48 частей выглядит очень заманчивым, тем, что в каждой части у нас остается по 3-4 точки (это для максимальных n !). Основная идея - собрать банк из "хороших" расположений трех-четырех точек в секторе, а затем построить куб из таких секторов. Это очень сильная идея, но надо много работать над мелочами...
Я, честно сказать, не довел это до конца - надо много кодить и думать, а на это нет ни времени, ни умения. Тем не менее, одна идея из такого подхода используется в моей текущей программе и она дает мне 90% для получения решения.

[Vovka17]

Вот и завершился очередной конкурс. Поздравляю победителей!

Немного оффтоп, но лишь немного...
В ту пору, когда я учился в универе, наш преподаватель по математике (Кайбханов К.Э.) имел такую "присказку".
Идет, например, практика, он знакомит с принципом решения задачи какого-нибудь нового типа, что-то объясняет у доски. Но тема не очень интересная для большинства, да и четвертая пара уже, все устали, и внимание аудитории постепенно падает, падает... И вот, в какой-то момент, когда внимание студентов упало ниже определенного порога, Карахан, как бы невзначай, говорит спокойно: "учтите, что такого же типа задачи будут на предстоящей контрольной".
Все мгновенно оживляются, начинают пытаться понять, о чем он тут рассказывал последние пять-десять минут, мало что понимают...
- Может не надо такую задачу.
- Уже и так много материала на контрольную, а это куда.
- Да сложная же, как такое решать то на контрольной, времени ж даёте...
, - слышится из аудитории.
Он поворачивается от доски, и с выражением полным искреннего удивления, говорит: "Вы что же, всё, что я даю на контрольной, РЕШАЕТЕ"?
Все непонимающе смотрят.
- Не надо решать, - продолжает он, - это же так трудно. Я вообще не требую от вас решения. Просто в нужных местах напишите нужные цифры и буквы. И всё!... И продолжает писать у доски.
Тут уже аудитории возразить нечего. Все погружаемся в тетрадки. И начинаем смотреть на его выкладки у доски внимательно
Касательно нашей задачи, проверять не компланарность сочетание всех точек, искать глобальный минимум сумасшедшей функции десятков переменных, оптимизировать алгоритмы и неделями мучать "железо"... - это всё не надо. Достаточно лишь просто расставить в нужных местах куба точки, и всё.

Основной принцип, который я применял - каждая новая точка ставится в то поле, которое принесет минимальное пересечение куба новыми плоскостями (при минимуме ошибок, естественно). Под пересечением я понимал количество прежде свободных точек в кубе, которые, после установки нашей новой точки, стали "запретными". Мне кажется, что этот простой принцип надо было развивать и заниматься им подробнее. Но времени на это не было... Далее, после заполнения куба, можно попробовать попереставлять некоторые точки туда-сюда, и ещё уменьшить ошибку, в идеале до нуля.
Никакого отжига, никакой генетики. Всё это не работает на такой задаче (по крайнем мере у меня не сработало). Метод градиентного спуска давал примерно такие же результаты, при гораздо меньшем времени нахождения минимума.
Большая ошибка - заполнять куб случайными точками, а потом пытаться улучшить их расположение. Поскольку, и я об этом неоднократно говорил, у нас сильная "связанность" точек и переставляя по одной-две-(да хоть три) точки плохое решение не получится превратить в хорошее. Немного улучшить - да. Но не более. При моём способе заполнения куба, хорошие решения получаются ещё на этапе расстановки точек, и, только, когда "напихиваем" уж совсем много точек в куб, начинаются ошибки.
Я долго и безуспешно старался победить $n=11$, и удивлен, что, кажется, лишь 6 человек смогли это сделать (и $n=13$ - они же). Предположу, что эти размерности возможно решить разновидностями переборных алгоритмов с отсечениями. Но я это не использовал и остался с результатами в шаге от максимума для $n=11$ и $n=13$...
Вот такой "колхозный" метод вышел у меня в этом конкурсе. Ну, вошел в десятку - уже не плохо !

Как решал Тим - это, конечно, загадка. Он - большой молодец и всех именитых соперников начисто лишил всех шансов!

[dmd]

Тим уже описал свой метод на Яхе. Мне пока ничего не понятно сквозь гугл-переводчик, одно понял - симметрия относительно центральной оси куба каким-то образом использовалась.

Я использовал случайный старт, но не заполнял куб случайными точками. Сначала выбирал три случайные точки, не лежащие на одной прямой, и для них определял набор подходящих точек, одну из которых можно добавить к первым трём с сохранением условия non-coplanar для всех четырёх. Затем пробегал по всем подходящим точкам, ища наибольший набор подходящих точек, высчитанный уже от 4-х точек - 3-х первых фиксированных и 4-ой переборной из предыдущего подходящего набора. Затем повторял эту процедуру для 4+1 точек, 5+1 точек, и т.д. - пока не упирался в пустой набор подходящих точек. Т.е. получался критерий движения по дереву вариантов - наибольший набор подходящих точек на каждом шаге. Но этот критерий явно не оптимальный. Нужна была ещё какая-то эвристика для более оптимального движения по древу, которую не сумел найти. Идею симметрий тоже не сумел развить. Поэтому в конце описанного метода стал выкидывать из полученного решения половину точек случайным выбором, и снова достраивал решение, в бесконечном цикле повторяя весь процесс. Полный перебор организовывал в конце достроения решения, когда оставалось достроить 4-5 точек - тоже без особых результатов.

Описание мат.модели задачи на языках AMPL и Localsolver:

(AMPL)

param n integer, := 3;
param N integer, := n*n*n;
set M := 1..N;
param H integer, := 8;
set G := 1..H;

var X {G} integer in M;

var Wx {i in G} = ((X[i]-1 - ((((X[i]-1 - ((X[i]-1) mod n)) div n) mod n)*n + (X[i]-1) mod n)) div n) div n;
var Wy {i in G} = ((X[i]-1 - ((X[i]-1) mod n)) div n) mod n;
var Wz {i in G} = (X[i]-1) mod n;

subject to Ad {i in G, j in G : i < j} : X[j] - X[i] >= 1;

subject to St {i in 1..H-3, j in i+1..H-2, k in j+1..H-1, l in k+1..H} :
    abs(
    (Wy[i]*(Wz[j] - Wz[k]) + Wy[j]*(Wz[k] - Wz[i]) + Wy[k]*(Wz[i] - Wz[j]))*Wx[l] + 
    (Wz[i]*(Wx[j] - Wx[k]) + Wz[j]*(Wx[k] - Wx[i]) + Wz[k]*(Wx[i] - Wx[j]))*Wy[l] + 
    (Wx[i]*(Wy[j] - Wy[k]) + Wx[j]*(Wy[k] - Wy[i]) + Wx[k]*(Wy[i] - Wy[j]))*Wz[l] - 
    (Wx[i]*(Wy[j]*Wz[k] - Wy[k]*Wz[j]) + Wx[j]*(Wy[k]*Wz[i] - Wy[i]*Wz[k]) + Wx[k]*(Wy[i]*Wz[j] - Wy[j]*Wz[i]))
    ) >= 1;

#reset;
#option solver jacop;
#option jacop_options 'version timing=1 outlev=1 outfreq=10 timelimit=3600';
#model ncp.mpl;
#solve;
#print {i in G} ("(" & Wx[i] & "," & Wy[i] & "," & Wz[i] & "),");

(Localsolver)

function model()
{
N = 5; M = N*N*N; H = 13;

Wx = {0}; Wy = {0}; Wz = {0};
for[x in 0..N-1][y in 0..N-1][z in 0..N-1] {Wx.add(x); Wy.add(y); Wz.add(z);};

X[1..H] <- int(1, M);

//for[i in 1..H][j in 1..H : i < j] constraint X[i] != X[j];
for[i in 2..H] constraint X[i] > X[i-1];

for[i in   1..H-3] {x1 <- Wx[X[i]]; y1 <- Wy[X[i]]; z1 <- Wz[X[i]];
for[j in i+1..H-2] {x2 <- Wx[X[j]]; y2 <- Wy[X[j]]; z2 <- Wz[X[j]];
for[k in j+1..H-1] {x3 <- Wx[X[k]]; y3 <- Wy[X[k]]; z3 <- Wz[X[k]];

  A <- y1*(z2 - z3) + y2*(z3 - z1) + y3*(z1 - z2);
  B <- z1*(x2 - x3) + z2*(x3 - x1) + z3*(x1 - x2);
  C <- x1*(y2 - y3) + x2*(y3 - y1) + x3*(y1 - y2);
  D <- x1*(y2*z3 - y3*z2) + x2*(y3*z1 - y1*z3) + x3*(y1*z2 - y2*z1);

for[l in k+1..H]
  constraint (A*Wx[X[l]] + B*Wy[X[l]] + C*Wz[X[l]] - D) != 0;

};};};                                        

maximize 1;

}


function output()
{
  solFile = openAppend(solFileName);
  for[i in 1..H]
  {
    t = getValue(X[i]); x = Wx[t]; y = Wy[t]; z = Wz[t];
    print("(", x, ",", y, ",", z, "),");
    print(solFile,"(", x, ",", y, ",", z, "),");
  };
  println(solFile); println(solFile);
}


function param()
{
  if(lsTimeLimit == nil) lsTimeLimit=3600;
  if(lsTimeBetweenDisplays == nil) lsTimeBetweenDisplays=10;
  if(lsNbThreads == nil) lsNbThreads=3;
//  if(lsSeed == nil) lsSeed=4;
  if(solFileName == nil) solFileName= "ncp"+N+".txt";
}

Если мат.модель возможно описать более просто (или более полно) - приглашаю по-дискутировать.

[Pavlovsky]

Прав dimkadimon человеку очень трудно освоить 3D-мышление. А вот tim foden это удалось. Он смог увидеть симметрию в оптимальных решениях под кодовым названием "Самолет". Надо будет серьезно поработать над 3D-мышлением.

[dimkadimon]

Vovka17 поздравляю за хороший результат на конкурсе! "Колхозный" подход оказался вполне хорошим. Кстати очень интересный оффтоп. Даже P==NP можно решить найдя всего один пример этого.

Похоже что самое большое улучшение дала симметрия. Ее нашли Tomas и Tim, соответсвенно заняв первые два места. Они говорят что симметрия 3-x кратная вокруг длинной диагонали куба $(1,1,1)-(N,N,N)$. Никак не могу представить эту симметрию. Кто-нибудь в этом разобрался?

[dmd]

Быть может так? Пересечём диагональ перпендикулярными ей плоскостями, на каждой такой плоскости расположим не более чем 3 точки по некому правилу (какому?). Тогда все такие точки будут удовлетворять условию задачи (будут ли?).

[dimkadimon]

dmd в сообщении #1129147 писал(а):

Быть может так? Пересечём диагональ перпендикулярными ей плоскостями, на каждой такой плоскости расположим не более чем 3 точки по некому правилу (какому?). Тогда все такие точки будут удовлетворять условию задачи (будут ли?).

Кажется я понял после объяснения Moritz. На каждой такой плоскости можно найти 3 точки которые на одинаковом расстоянии от диагонали и между ними 120 градусов.

[dmd]

Следующие три точки на соседней плоскости должны располагаться с некоторым поворотом и радиальным смещением?

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

[Pavlovsky]

dimkadimon в сообщении #1129148 писал(а):

На каждой такой плоскости можно найти 3 точки которые на одинаковом расстоянии от диагонали и между ними 120 градусов.

Вроде как все намного проще. Есть группа точек. Меняем в них местами координаты x и y местами, получаем вторую группу точек. Затем меняем местами в исходной группе, координаты y и z, получаем третью группу. Вместе три группы составляют решение. Сформулировать условия, чтобы это было именно решение, нетрудно.

[Herbert Kociemba]

First my congratulations for the winners! What is quite funny that during the contest I gave symmetric solutions about the main diagonal a try but discarded the idea again because it did not give better solutions on the first try. This was obviously very stupid. The idea to look for symmetric solutions in general was quite obvious for me (and I believe for Tom too) because from our work on Rubiks cube we knew that permutations which have some symmetry have a bias towards longer solution length and this analogy was a good hint.
Most symmetries of the cube (see for example http://kociemba.org/symmetric2.htm) would define more than three points in one plane so they cannot be used in the problem, but the C3 or the higher symmetry S6 are possible. Explaining C3 symmetry is very simple. With P1(x,y,z) you also add P2(y,z,x) and P3(z,x,y).
In the two pictures below you see Tim Fodens solution for N=37 from 2 slightly different viewing angles. You see the C3 symmetry in the second picture.

[Herbert Kociemba]

Herbert Kociemba в сообщении #1129174 писал(а):

but the C3 or the higher symmetry S6 are possible

Sorry, S6 is not possible. If you reflect 2 points at the center of the cube all 4 points are in the same plane.