Al Zimmermann: Primorial Soup

[ctac]

Geen
Thank you!

[dimkadimon]

jcmeyrignac в сообщении #1262098 писал(а):

Some benchmarks on a I7-4790S at 3.2Ghz:

N=10, 18 seconds with 3523 vertices
N=11, 16114 seconds with 11589 vertices

Ok I can get similar times, but I analyse much fewer nodes and just get lucky to get the optimum... I can't analyse that many nodes in such short time.

[jcmeyrignac]

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

Ok I can get similar times, but I analyse much fewer nodes and just get lucky to get the optimum... I can't analyse that many nodes in such short time.

It's an exhaustive search, which returned15 solutions.
Note that I have not been able to find heuristics to approximate solutions.

[Herbert Kociemba]

jcmeyrignac в сообщении #1262098 писал(а):

N=10, 18 seconds with 3523 vertices
N=11, 16114 seconds with 11589 vertices

For N=11 I also have exactly 11589 vertices with a vertexrawscore less than 8691987. But for N=10 I have 5114 vertices with a vertexrawscore less than 2229731. I wonder why you need much less vertices for a full search for N=10.

[as73251]

jcmeyrignac в сообщении #1262551 писал(а):

It's an exhaustive search,,,

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

Ok I can get similar times, but I analyse much fewer nodes and just get lucky to get the optimum... I can't analyse that many nodes in such short time.

Непонятно, какое время имеет в виду jcmeyrignac: общее время решения или только время обработки vertices.

-- 06.11.2017, 07:54 --

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

,,, for a full search ,,,

Я понимаю под полным поиском нахождение действительного минимума:
post1252958.html#p1252958

[jcmeyrignac]

To be clearer, with 11589 vertices, the full search for N=11 took 16114 seconds and returned 15 solutions.
The top was the thirteenth solution.

N=12 is a lot bigger, but I just got a good result.

[dimkadimon]

jcmeyrignac в сообщении #1262682 писал(а):

N=12 is a lot bigger, but I just got a good result.

So our current N=12 is not optimal?

[Geen]

12d3 в сообщении #1256335 писал(а):

А вот и график.

Кстати, при $n=12$ перестаёт хватать int64

[dimkadimon]

Geen в сообщении #1264003 писал(а):

Кстати, при $n=12$ перестаёт хватать int64

А я просто double использую. Да неточно, но работает.

[as73251]

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

Geen в сообщении #1264003 писал(а):

Кстати, при $n=12$ перестаёт хватать int64

А я просто double использую. Да неточно, но работает.

Можно работать с int64 и при n=12.

[Herbert Kociemba]

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

jcmeyrignac в сообщении #1262682 писал(а):

N=12 is a lot bigger, but I just got a good result.

So our current N=12 is not optimal?

Possible or not. I searched about 5% of the complete searchspace within two days until I found the current best solution for N=12. So a complete search should be possible at least in principle. But I stopped the search now except for one CPU-core and will see if I can find something useful for N=13.

Btw. a complete search for N=11 now takes less than 1 hour for me with one CPU-core and my improved program.

[dimkadimon]

Wow Jarek has 25.00!

[as73251]

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

Wow Jarek has 25.00!

При этом Best Raw Score несколько дней не обновлялось: не хватает знаков для отображения изменений!

P.S.
Я же Вам говорил, что 25 баллов обязательно будет!

-- 16.11.2017, 06:04 --

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

Btw. a complete search for N=11 now takes less than 1 hour for me with one CPU-core and my improved program.

Это полный поиск? Кстати, Jarek вчера обновил рекорд для n=13.

[Herbert Kociemba]

as73251 в сообщении #1265683 писал(а):

Это полный поиск?

Yes, 1 hour for the complete search space. The optimal solution already appears after 4 minutes with my order of computation.

For N=13 I use a list of about 200000 vertices. But within 12 hours I did not find even 8 vertices that "fit together". So I need a different approach for N>=13.

[dobrichev]

The algorithm that helped me in advancing for N=12 and partially for 13, finds 8 (out of 13) compatible vertices roughly once per hour per CPU.
My vertices list is about 20% larger. So far I have only 10 completed graphs and all of them have at least one vertex close to the threshold.

The estimation for exhaustive search using this algorithm is that 13 could be completed in the lifetime of the solar system but not in ours.

For N=14 the things are significantly worse even when targeting below the current best result.

With realistic assumption that the current best results are obtained using less than several thousands CPU cores, the right approach is different.

Congratulations to Jarek Wroblewski for these fantastic achievements!