# Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки

 На страницу Пред.  1, 2, 3, 4
 Печатать страницу | Печатать всю тему Пред. тема | След. тема

 Re: Al Zimmermann: Reversing Nearness19.10.2019, 16:27

25/08/12
171
Germany
 Archimedes в сообщении #1421408 писал(а):Чем больше копаюсь в задаче, тем больше удивляюсь. Казалось бы, причём тут число 17? Почему именно 17... :)If you draw two lines with gradients (slopes) -1/4 and 4 onto the flat torus you get 17 squares.

 Re: Al Zimmermann: Reversing Nearness25.10.2019, 04:50

25/08/12
171
Germany
 I would like to discuss the case $N\to\infty$. If you code a coordinate $0\leqslant x < N$ as continuous hue value $h=x \frac{360}{N}$ of the hsv-color space the original board (left square x-coordinate, right square y-coordinate) looks like this. Here (0,0) = (red,red) is in the center of the board, x increases to the right, y increases upwards.The indices of the 17 squares drawn into the y-coordinates (with only five squares drawn here) are not choosen arbitrary. We have$square(k) = square(0)+\frac{k}{17} 360$The equation should be read pointwise for corresponding points of square(0) and square(k) of course. square(k) is a color-shifted version of sqare(0). Observe that the x-coordinate picture is just a 90° rotated version of the y-coordinate. What seems to be the "optimal" solution has the same property, so we only need to draw the y-coordinate picture.The following picture gives the result of simulated annealing for N= 272, y-coordinate picture shown It seems that this picture can be generated by slightly rearranging the points of the original squares in a continuous way and then interweaving the squares by sending square(k) to the position of square(2*k mod 17). So for example square(9) is sent to the position of square(1) since 2*9 = 1 mod 17.If newsquare(k) denotes the slightly rearranged version of square(k) it is also remarkable that$newsquare(k) = newsquare(0)+\frac{k}{17} 360$So all squares are distorted in the same way and there essentially is only one square. square(0) has obviously additional symmetry (point reflection with color change h -> 360 - h. The same seems to hold for newsquare(0).

 Re: Al Zimmermann: Reversing Nearness27.10.2019, 19:32

25/08/12
171
Germany
 Последний раз редактировалось Herbert Kociemba 27.10.2019, 19:48, всего редактировалось 3 раз(а). First of all congratulations to the winners of this great contest! I was very curious to see finally the best results and to visualize them. Here is an analysis of the optimal solution for N=30, appropriately transformed by a score preserving transformation, left square x-coordinates, right square y-coordinates:For any N you always can draw the black grid lines with slopes -1/4 and 4 in such a way, that the lines and in particular the "square" in the center have rotational symmetry. To do so you start in the upper left corner with 2 units to the right (r), 1 unit down (d) and then repeat 4 r and 1 d until you are back in the upper left corner. For the perpendicular line you start in the upper right corner (which of course topologically is the same as the upper left corner) and go 2 d, 1 left (l) and then repeat 4 d and 1 l until you are back. - The solution nicely fits into this grid, there is only 1 of the 900 cells which does not match the grid (the red square in the upper right of square 6 of the y-coordinates).- If you rotate the y-coordinates picture 90° clockwise, you do not get exactly the x-coordinates picture but still the resemblance is impressive. Many of the best solutions for smaller N have perfect symmetry.- If you compare the y-coordinates picture with the y-coordinates picture of the "continuous" case (N=272) I showed in my last post it looks like a rasterized version of the latter.

 Re: Al Zimmermann: Reversing Nearness27.10.2019, 21:36

25/08/12
171
Germany
 For N=19 the optimal solution given in the final report also is not completly symmetric. But such solutions exist, here the optimal solution I submitted:Not only is the the x-coordinate picture exactly the y-coordinate picture rotated by 90°. There also is a point symmetry with color change hue h -> 360 - h.Код:(EF, EG, RD, RE, SG, RN, SN, AO, BP, SD, AE, BE, BF, DG, BM, CO, DP, EP, FP),(EE, FE, FF, GF, FL, GO, AM, AN, BO, AD, BD, CE, CF, DF, CM, CN, DO, EO, GP),(ED, FD, GE, HF, GM, GN, HN, HO, JO, ID, CC, CD, DD, DE, DM, DN, EN, FO, DC),(FC, GC, GD, HE, GL, HM, IN, IO, KO, IC, JD, JE, KE, KL, EL, EM, FM, FN, EC),(HB, HC, HD, IE, HL, IL, IM, JN, IB, JC, KC, KD, LE, KK, LM, LN, MN, LO, GB),(ND, OD, PD, IK, JK, JL, JM, KN, JB, KB, LC, LD, ME, LK, LL, MM, NN, ON, NC),(OB, OC, QD, PK, PL, PM, QM, KM, KA, LA, LB, MC, MD, MK, ML, NL, NM, MA, NB),(PB, PC, QC, PJ, QK, QL, RM, SM, RB, SC, AC, MB, MJ, NJ, NK, OL, OM, NA, OA),(PA, QB, RC, QJ, RK, RL, SL, RA, SA, SB, AB, BC, AJ, BK, BL, OJ, OK, OS, PS),(QS, QA, QI, RI, RJ, SK, AL, RS, SS, AA, BB, CB, AI, BJ, CK, CL, DL, DA, DB),(EB, FB, FJ, FK, SI, SJ, AK, SR, AS, BS, BA, CA, BI, CI, CJ, DK, CR, DS, EA),(FA, GA, FH, FI, GJ, GK, HK, HS, AR, BR, CS, BH, CH, DI, DJ, EK, DR, ER, ES),(GS, HA, GH, GI, HI, HJ, HQ, HR, IS, IA, JA, JH, DH, EH, EI, EJ, DQ, FR, FS),(GR, FG, GG, HH, II, IJ, HP, IQ, IR, JS, KS, JG, KH, KI, KJ, LJ, EQ, FQ, GQ),(NS, IF, HG, IG, IH, JJ, IP, JQ, JR, KR, LS, KG, LH, LI, MI, LP, MQ, MR, MS),(PR, OG, OH, PH, PI, JI, JP, KP, KQ, LR, JF, LF, LG, MH, NI, MP, NQ, NR, OR),(QR, OF, PG, QG, QH, QP, QQ, RQ, RR, LQ, KF, MF, MG, NG, NH, MO, NP, OQ, PQ),(NE, PF, QF, RG, RH, QO, RO, RP, SQ, AQ, SF, AG, AH, NF, OI, NO, OO, OP, PP),(OE, PE, QE, RF, SH, QN, SO, SP, AP, BQ, SE, AF, BG, CG, BN, CP, CQ, PN, PO)

 Re: Al Zimmermann: Reversing Nearness28.10.2019, 14:21

07/06/16
45
Омск
 Также поздравляю всех с окончанием конкурса, Herbert'а с 20-м местом, себя с 44-м. Как обычно, постараюсь максимально точно описать свой путь решения.Прочитал условия задачи почти сразу после старта, написал самую простую программу с методом Монте-Карло, какую только можно себе представить. Если мне не изменяет память, то этот алгоритм дал не только "пристрелочные" решения до 5х5, но и один реальный - 6х6.Скажу также, что в этот раз решил использовать для программ язык Java, а не C#, как в прошлые разы. В общем, совмещал приятное с полезным - нужно было освежить навыки написания программ на Java.К сожалению, на основной работе был аврал, поэтому вернулся к задаче только в середине августа, да и то урывками. В тот момент я переписал алгоритм так, что он стал реализовывать случайные блуждания по совокупности всех вариантов матриц, естественно с ограничениями по удалению от найденного промежуточного оптимума. Это позволило получить решения по N=8 включительно.Было понятно что для накопления статистики нужно ускорять алгоритм пересчёта рейтинга при перестановке двух ячеек. Алгоритм, реализующий 2*n операций вместо n*n, был написан довольно-таки быстро: день на написание и день на отладку. Получилась такая функция:(Оффтоп) public static long Swap2Cells(int i, int j, long lastRate) { return Swap2Cells(i, j, lastRate, false); } public static long Swap2Cells(int i, int j, long lastRate, boolean bForce) { long deltaRate = 0; long deltaAllRate = 0; int x1,x2,x3,x4,y1,y2,y3,y4; int i1 = i; int j1 = j; if (i1 > j1) { i1 = j; j1 = i; } // Запоминаем старые частные рейтинги for (int i2=0; i2 0) { deltaAllRate = tempRate[i1-1]; deltaRate = 0; for (int i2 = 0; i2 < i1; i2++) { x1 = abs(i1 % Dim - i2 % Dim); y1 = abs(i1 / Dim - i2 / Dim); x2 = abs(field.Coor[j1] % Dim - field.Coor[i2] % Dim); y2 = abs(field.Coor[j1] / Dim - field.Coor[i2] / Dim); deltaRate += Way[x1][y1] * Way[x2][y2]; } deltaAllRate += deltaRate; tempRate[i1] = deltaAllRate; } // Заменяем по одному числу между i1 и j1 for (int i2=i1+1; i2 tempRate[fsize-1]) | bForce) { int tmp = field.Coor[i1]; field.Coor[i1] = field.Coor[j1]; field.Coor[j1] = tmp; for (int i2=0; i217 не имеют более чем 17 областей ячеек, которые в первоначальной матрице стояли не далее 2-х клеток друг от друга.Например, кандидат для N=18:Здесь видно что областей всего 17.Herbert написал здесь после моего вопроса почему это происходит, но я к тому времени уже и сам догадался.Вот с тем как применить полученное знание для получения результата, у меня были большие проблемы. Я попытался дополнительно ограничить перебор, используя координаты этих "криволинейных квадратов", но это не дало никакого результата.Очевидно что нужно было заново переписывать программу, реализуя новый алгоритм уже на этапе заполнения матриц-кандидатов в оптимумы, но времени уже не оставалось.За день до окончания я написал небольшой алгоритм, переставляющий близлежащие ячейки. Я пропустил через него свои кандидаты в оптимумы, и это дало ещё маленькое дополнение к рейтингу - примерно +0,002.На этом всё закончилось. :)Задача на первый взгляд была не очень интересной - слишком быстро находились на начальном этапе решения простыми численными методами. Задача раскрылась позднее, к концу времени стало более интересно. К сожалению, опять не хватило времени. :) Но, это опять дополнительный опыт, который, несомненно, даст свои плоды при решении следующей задачи.Всем спасибо, всем благ и успехов!

 Показать сообщения за: Все сообщения1 день7 дней2 недели1 месяц3 месяца6 месяцев1 год Поле сортировки АвторВремя размещенияЗаголовок по возрастаниюпо убыванию
 Страница 4 из 4 [ Сообщений: 50 ] На страницу Пред.  1, 2, 3, 4

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы

#### Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

 Вы не можете начинать темыВы не можете отвечать на сообщенияВы не можете редактировать свои сообщенияВы не можете удалять свои сообщенияВы не можете добавлять вложения

 Найти: