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

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

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

 Re: Al Zimmermann: Reversing Nearness09.08.2019, 15:03

25/08/12
143
Germany
 Последний раз редактировалось Herbert Kociemba 09.08.2019, 15:03, всего редактировалось 1 раз. Yes you are right. I now implemented your idea(thanks again for sharing it)and it runs correctly. The update of the precomputed sums is indeed $O(N)$ but the advantage of the algorithm is not as large in the range N<=30 as I expected. For N = 30 it is currently only about twice as fast as my old method. Maybe there are some ways for optimizations...

 Re: Al Zimmermann: Reversing Nearness09.08.2019, 17:29

01/06/12
949
 12d3, большое спасибо за ваш метод. Он очень хороший. Я думаю с таким методом можно победить :)

 Re: Al Zimmermann: Reversing Nearness12.08.2019, 00:23

25/08/12
143
Germany
 Последний раз редактировалось Herbert Kociemba 12.08.2019, 00:25, всего редактировалось 1 раз. jcmeyrignac в сообщении #1408933 писал(а):Is it possible to find two different grids that have the same score ?For almost all grids there is a different grid with the same score.Take for example this normalized 6x6 grid with a raw score of 10016.(AA, AB, BC, AD, DE, AF),(BF, EE, AE, FC, EA, DC),(BA, FB, DB, EC, BB, BE),(EF, EB, AC, CA, FF, CD),(DA, FE, DD, CC, CB, FA),(FD, CE, CF, BD, ED, DF)If (grid[i,j].x ,grid[i,j].y) describes the entry at position (i,j) the inverse grid is defined byinvgrid[grid[i, j].x, grid[i, j].y].x := iinvgrid[grid[i, j].x, grid[i, j].y].y := jThe inverse grid always has the same score as the original grid.After normalization the inverse grid for the example is(AA, AB, DC, AD, BC, AF),(CA, CE, AC, FD, CF, BA),(DD, EE, ED, DF, FB, FC),(EA, CC, BF, EC, AE, FF),(BE, DB, CD, FE, BB, DA),(EF, CB, BD, FA, EB, DE)Al could include the inversion process into the normalization procedure to get a case reduction by a factor of 2.Why did I write "For almost all grids..."? A grid may be selfinverse (inverse grid = grid) or may have some antisymmetry (the inverse grid is a rotation/reflection/translation of the grid) in which case we get no new grid.

 Re: Al Zimmermann: Reversing Nearness12.08.2019, 12:10

25/08/12
143
Germany
 Последний раз редактировалось Herbert Kociemba 12.08.2019, 12:53, всего редактировалось 5 раз(а). Herbert Kociemba в сообщении #1409931 писал(а):After normalization the inverse grid for the example is(AA, AB, DC, AD, BC, AF),(CA, CE, AC, FD, CF, BA),(DD, EE, ED, DF, FB, FC),(EA, CC, BF, EC, AE, FF),(BE, DB, CD, FE, BB, DA),(EF, CB, BD, FA, EB, DE)Sorry for some confusion, but the correct inverse is(AA, AC, DD, AE, EB, FE), (BA, EC, EE, CC, BD, BC),(CD, CA, DE, FB, DC, DB),(DA, DF, FD, CE, EF, AF),(CB, FC, BF, EA, BB, BE),(FA, AB, CF, FF, AD, ED)The grid I posted erroneously is generated bynewgrid[grid[i, j].y, grid[i, j].x].x := j;newgrid[grid[i, j].y, grid[i, j].x].y := i;But his transformation also leaves the rawscore invariant.You can combine the two operations (they commute) to get another variant which in its normalized form is(AA, BA, CB, DA, ED, FA),(DF, EC, FC, DB, DE, FD),(AD, EF, DD, CC, BC, AF),(FE, BE, CA, AC, FF, DC),(AB, BF, BD, CE, BB, EB), (FB, EE, EA, CF, AE, CD) So there usually are at least 4 normalized boards, which have the same score.

 Re: Al Zimmermann: Reversing Nearness12.08.2019, 21:14

25/08/12
143
Germany
 Al's equivalence classes contain 8 N^2 grids based on rotation, reflection and shift of the grid. There are other nongeometrical transformation except inversion which preserve the raw score. You can do for examplenewgrid[i, j].x := (grid[i, j].x + c1) mod Nnewgrid[i, j].y := (grid[i, j].y + c2) mod Nfor any 0<=c1,c2< Nif you think the coordinates not as letters but as numbers from 0.. N-1. This alone usually gives N^2 "new" normalized boards. Or in other words, if you include this operation an equivalence class woud have 8 N^4 grids.

 Re: Al Zimmermann: Reversing Nearness13.08.2019, 16:36
 Заслуженный участник

19/12/10
1546
 Herbert Kociemba в сообщении #1409970 писал(а):Sorry for some confusion, but the correct inverse isИмхо, вы исправили правильное значение на ошибочное. Из вашего определения:Herbert Kociemba в сообщении #1409931 писал(а):If (grid[i,j].x ,grid[i,j].y) describes the entry at position (i,j) the inverse grid is defined byinvgrid[grid[i, j].x, grid[i, j].y].x := iinvgrid[grid[i, j].x, grid[i, j].y].y := jThe inverse grid always has the same score as the original grid.следует, чтоgrid[1, 2].x = 1grid[1, 2].y = 2invgrid[1, 2].x = 1invgrid[1, 2].y = 2поэтому invgrid[1, 2] = AB, а не AC.

 Re: Al Zimmermann: Reversing Nearness13.08.2019, 23:40

25/08/12
143
Germany
 whitefox в сообщении #1410144 писал(а):Имхо, вы исправили правильное значение на ошибочное.Sorry, but I disagree. The confusion results because Al defines the grid differently as usually. On his page you can see that the default grid isAA BA CA......AB BB CB......AC BC CC.....and not - as me and you are used to -AA AB AC......BA BB BC......CA CB CC.....I made the same mistake on my first try.

 Re: Al Zimmermann: Reversing Nearness14.08.2019, 12:34
 Заслуженный участник

19/12/10
1546
 Последний раз редактировалось whitefox 14.08.2019, 12:50, всего редактировалось 1 раз. Herbert Kociemba в сообщении #1410207 писал(а):Sorry, but I disagree. The confusion results because Al defines the grid differently as usually. On his page you can see that the default grid isПонятно. Довольно необычное решение, но я исходил из вашего определения.-- 14 авг 2019, 12:50 --Herbert Kociemba в сообщении #1410051 писал(а):Al's equivalence classes contain 8 N^2 grids based on rotation, reflection and shift of the grid. There are other nongeometrical transformation except inversion which preserve the raw score. You can do for examplenewgrid[i, j].x := (grid[i, j].x + c1) mod Nnewgrid[i, j].y := (grid[i, j].y + c2) mod Nfor any 0<=c1,c2< Nif you think the coordinates not as letters but as numbers from 0.. N-1. This alone usually gives N^2 "new" normalized boards. Or in other words, if you include this operation an equivalence class woud have 8 N^4 grids.И, вообще, можно поступить следующим образом: каноническую форму исходной решётки включим в поколение 0; чтобы построить поколение $p+1$ для каждой решётки поколения $p$ найдем $8n^2$ эквивалентных решёток и инвертируем их, канонические формы этих решёток включаем в поколение $p+1$.Для примера Herbert Kociemba, в поколение 0 входит 1 решётка, в поколение 1 — 288, и т.д.

 Re: Al Zimmermann: Reversing Nearness14.08.2019, 14:15

25/08/12
143
Germany
 Последний раз редактировалось Herbert Kociemba 14.08.2019, 14:37, всего редактировалось 1 раз. whitefox в сообщении #1410297 писал(а):Для примера Herbert Kociemba, в поколение 0 входит 1 решётка, в поколение 1 — 288, и т.д.I do not believe that generation 1 contains 288 elements, I think it is only 72. From the original grid, the inverse of the original grid and the 36 coordinate shifts (0<=c1,c2<6) you get 72 grids which all are in different equivalence classes. I think thats all you can get. So I am quite sure that from your 288 grids always 4 grids fall into the same equivalence class. And generation 2 will not give any new grids at all.

 Re: Al Zimmermann: Reversing Nearness15.08.2019, 13:26
 Заслуженный участник

19/12/10
1546
 Herbert Kociemba в сообщении #1410331 писал(а):I do not believe that generation 1 contains 288 elements, I think it is only 72.Проверено, 288.Собственно говоря, не важно какое определение инверсии использовать — первое или второе. В обоих случаях в первом поколении содержится до $8n^2$ канонических решёток. Во втором поколении тоже — до $8n^2$ канонических решёток. Объединением этих двух поколений всё и заканчивается. Всего таким способом можно получить до $128n^4$ решёток с одинаковой оценкой, из них до $16n^2$ канонических.Для вашего примера получаем 576 канонических решёток. Список приведу попозже.

 Re: Al Zimmermann: Reversing Nearness15.08.2019, 15:53

25/08/12
143
Germany
 whitefox в сообщении #1410512 писал(а):Herbert Kociemba в сообщении #1410331wrote:I do not believe that generation 1 contains 288 elements, I think it is only 72. Проверено, 288.Отлично. It's already the second time in this thread that I am too fast in not believing something. Thank you for the verification!

 Re: Al Zimmermann: Reversing Nearness15.08.2019, 16:16
 Заслуженный участник

19/12/10
1546
 Последний раз редактировалось whitefox 16.08.2019, 12:25, всего редактировалось 3 раз(а). Выкладываю обещанный список 576 существенно различных решёток. В архиве: список 576 решёток; отдельный список 288 решёток поколения 1; счётная программа; исходный код.

 Re: Al Zimmermann: Reversing Nearness15.08.2019, 21:11

25/08/12
143
Germany
 Thanks. I think I have now complete understood what happens. In the summary below all computations are mod N. Also to avoid confusion again we assume the default grid uses numbers from 0 ... N-1 and uses the order00 10 20 ....01 11 21 ....02 12 22 ...In 02, we call 0 the x-coordinate und 2 the y-coordinate,We have three basic geometric grid transformations which do not change the raw score1. shiftgrid (shift grid by vector (dx,xy)):newgrid[i, j].x := grid[i + dx, j + dy].x 0 <= dx, dy

 Re: Al Zimmermann: Reversing Nearness16.08.2019, 12:43
 Заслуженный участник

19/12/10
1546
 Последний раз редактировалось whitefox 17.08.2019, 13:28, всего редактировалось 1 раз. 12d3 в сообщении #1409284 писал(а):Итого, для подсчета оценки после обмена двух фишек нам потребуется $O(N)$ времени. Ну хорошо, поменяем местами фишки в позициях $(i_0,j_0)$ и $(i_1,j_1)$, за время $O(N)$ вычислим новые оценки фишек в этих позициях $F'(i_0,j_0)$ и $F'(i_1,j_1)$. А что с остальными фишками? Ведь их оценки тоже изменятся, и если даже сложность вычисления такого изменения для одной фишки $O(1)$, самих фишек $O(N^2)$.UPD: Вопрос снимается. Используя вашу технику действительно можно вычислять изменение оценки решётки за время $O(N)$.

 Re: Al Zimmermann: Reversing Nearness16.08.2019, 14:05

25/08/12
143
Germany
 whitefox в сообщении #1410713 писал(а):А что с остальными фишками? Ведь их оценки тоже изменятсяThe values of the other chips change but this does not matter until you remove one of these chips. And then you can recompute the value of the chip in $O(N)$.

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

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

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

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

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

 Найти: