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

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

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

 Re: Al Zimmermann's: Summertime06.07.2021, 14:36

01/06/12
1016
 Herbert that was a beautiful algorithm and image you posted in the discussion group. Do you mind posting it here as well.

 Re: Al Zimmermann's: Summertime06.07.2021, 15:07

25/08/12
171
Germany
 dimkadimon в сообщении #1525466 писал(а):Herbert that was a beautiful algorithm and image you posted in the discussion group. Do you mind posting it here as well.It is a pleasure to do so.The idea is quite easy to understand if not expressed as "mathematical"as in the paper.1. Divide the vertices into 5 parts as even as possible and position theparts on a circle.2. Connect the vertices:a) within the parts with color 1b) between vertices of parts which are neighbors with color 2c) between vertices of parts which are not neighbors with color 3.A little visualization is helpful

 Re: Al Zimmermann's: Summertime06.07.2021, 17:10

25/08/12
171
Germany
 Последний раз редактировалось Herbert Kociemba 06.07.2021, 17:15, всего редактировалось 1 раз. Fun fact: color(i,j) = Floor(Abs(Abs(Floor(5 * i / N) - Floor(5 * j / N)) - 2.5))gives the color (0, 1 or 2) of the edge between vertices i and j, 0<=i,j

 Re: Al Zimmermann's: Summertime07.07.2021, 02:31

01/06/12
1016
 Herbert Kociemba в сообщении #1525483 писал(а):Fun fact: color(i,j) = Floor(Abs(Abs(Floor(5 * i / N) - Floor(5 * j / N)) - 2.5))gives the color (0, 1 or 2) of the edge between vertices i and j, 0<=i,j3$ colours. Split the nodes into groups. Interconnect the groups with $K-1$ colours such that they don't form mono triangles and interconnect nodes in the same group with one remaining colour. So for $K=4$ we can use 16 groups as they can be connected with 3 colours without mono triangles. * If the subgraph induced by a single colour is a tree or a cycle then it won't have any mono triangles. So to get a solution without any mono triangles we simply need to divide our graph into $K$ subgraphs (that are trees or cycles) that a) don't intersect and b) span the whole graph.

 Re: Al Zimmermann's: Summertime07.07.2021, 12:37

01/06/12
1016
 No forget the idea of using trees and cycles - they don't have enough edges.I also looked at triangle free strongly regular graphs. If we had one such 11-regular graph with 56 nodes then we could try to use 4 copies of it to make a 4-colouring with 56 nodes, which would be a record. However it is proven that such a graph doesn't exist. The closest is the Gewirtz graph, but it is only 10-regular:https://en.m.wikipedia.org/wiki/Gewirtz_graph

 Re: Al Zimmermann's: Summertime07.07.2021, 17:45

25/08/12
171
Germany
 dimkadimon в сообщении #1525504 писал(а):We can use this approach to search for solutions for $K>3$ colours. Split the nodes into groups. Interconnect the groups with $K-1$ colours such that they don't form mono triangles and interconnect nodes in the same group with one remaining colour. So for $K=4$ we can use 16 groups as they can be connected with 3 colours without mono triangles. It is possible that this approach also will give the configuration with a minimum number of monochromatic triangles for all N greater some N0. But for lower N this does not work very well. With K=4 and N=48 we already would have 16 monochromatic triangles, but for K=4 even for N=50 there exists a coloring without any mono triangles. dimkadimon в сообщении #1525504 писал(а):That's very nice. There is a similar one-line formula in https://oeis.org/A343608The formula you refer to is the formula for the number of monochromatic triangles in that coloring I believe. But I think it is more amazing that the complete algorithm (Divide the vertices into 5 parts as even as possible ...) can be packed into a relatively simple formula.

 Re: Al Zimmermann's: Summertime12.07.2021, 10:42

12/07/21
108
 Последний раз редактировалось traffic_lights 12.07.2021, 10:45, всего редактировалось 1 раз. dimkadimon в сообщении #1525086 писал(а):... Я наконец нашел все оптимальные решения. Первые 22 нашел методом отжига, а вот последние три никак не мог найти...Я все решения нашел методом отжига: вплоть до n=63 решения выскакивают мгновенно, решение для n=215 появилось примерно через час (на 11 ядрах).

 Re: Al Zimmermann's: Summertime12.07.2021, 16:34

25/08/12
171
Germany
 At least for N>=23 you will get the best known optimal solution for N+1 also almost immediately if you take best known solution for N, add a point and just do simulated annealing with the N new edges which end in this point. Annealing N edges instead of N(N+1)/2 edges is much faster.This incremental method also works if you have the N=17 solution (5 triangles)to get the N=18 solution (10 triangles) and to go from there to the N=19 solution (15 triangles). The N=20 solution retrieved by this method from the N=19 solution has 21 triangles instead of the best known 20 triangles, so it fails here.

 Re: Al Zimmermann's: Summertime12.07.2021, 17:32

12/07/21
108
 Последний раз редактировалось traffic_lights 12.07.2021, 18:22, всего редактировалось 1 раз. Herbert KociembaЯ приступил к реализации алгоритма только в пятницу 9 июля, т.к. онлайн работа со студентами отнимала очень много сил. К этому времени все это уже было известно, как и формула для ребер, которая сразу давала все искомые решения. В дискуссионной группе участники отмечали проблемы с отжигом. Меня это заинтересовало и действительно рабочий алгоритм отжига для данной задачи оказался нетривиальным. Поэтому я и решил поделиться с участниками конкурса своими результатами. Может быть, Ваш алгоритм отжига для работы со всей матрицей более эффективен?P.S.Забыл отметить, что скорость программы прямо пропорциональна количеству ядер: на хорошем кластере для n=215 ответ можно получить сразу. Если алгоритм кого-то заинтересует, то после окончания конкурса я его выложу.

 Re: Al Zimmermann's: Summertime14.07.2021, 14:28

25/08/12
171
Germany
 Последний раз редактировалось Herbert Kociemba 14.07.2021, 14:28, всего редактировалось 1 раз. traffic_lights в сообщении #1525905 писал(а):Если алгоритм кого-то заинтересует, то после окончания конкурса я его выложу.Yes, I would be interested. I realized that my incremetal method is the same what dmd describes in his post. You can start with the solution with N=16 and 0 triangles. By adding point after point you get solutions for N=17, 18, 19, 20, 21, 22, 23, 24 with 5, 10, 15, 20, 25, 33, 41, 50 triangles. The solutions get worse than the default method for N>=22. It is interesting that all solutions in this series up to N=21 have only triangles of a single color, which is not the case for N>=22.If you start with the default solution for some N, the incremental method obviously gives the default solution for N+1. And it seems, that that all known best solutions for all N >=22 are the default solutions. So basically, solutions with fewest (currently known) triangle numbers all can be generated with the incremental method from the two chains N=16 (0 triangles)->17->18->19->20->21 and N=22(default solution)->23->24->25-> ..... infinityIt also is interesting that though the N=19 solution obtained incrementally has 15 triangles of one color, there also exists a solution with 5 triangles of each color which I never happened to see with simulated annealing. Plotting only the triangles the solution looks like this:The thick lines are the base of all triangles of one color.Herbert Kociemba в сообщении #1525518 писал(а):It is possible that this approach also will give the configuration with a minimum number of monochromatic triangles for all N greater some N0. But for lower N this does not work very well. With K=4 and N=48 we already would have 16 monochromatic triangles, but for K=4 even for N=50 there exists a coloring without any mono triangles. I realized that this method is not as bad as I thought with K=4 colors. The number of triangles with m=Floor(N/16) and r = Mod(N,16) isr*Binomial(m+1,3)+ (16-r)*Binomial(m,3)and for N= 55, 56, 57 it gives 37, 40, 43 triangles. If you compare this with the data Martin Piotte gave in AZsPCs@groups.io it seems that the default method with 4 colors gives good values for N>=56.Код:n     | number of monochromatic triangles------+----------------------------------<= 50 | 051    | 152    | 453    | 1054    | 2155    | 3256    | 4057    | 43

 Re: Al Zimmermann's: Summertime16.07.2021, 06:49

12/07/21
108
 Рассматривалась ли задача о минимальном количестве треугольников, все стороны которых имеют разный цвет?

 Re: Al Zimmermann's: Summertime16.07.2021, 10:17

20/03/16
5
Киев
 traffic_lights в сообщении #1525835 писал(а):dimkadimon в сообщении #1525086 писал(а):... Я наконец нашел все оптимальные решения. Первые 22 нашел методом отжига, а вот последние три никак не мог найти...Я все решения нашел методом отжига: вплоть до n=63 решения выскакивают мгновенно, решение для n=215 появилось примерно через час (на 11 ядрах).Я отжег с достаточно хорошим качеством (но не до оптимума) для n=400 (порядка пары часов на одном ядре, при довольно медленной реализации), после чего начал последовательно выбрасывать вершины, дающие наибольшее количество одноцветных треугольников. Это дало оптимумы для всех значений n кроме 17, к-е пришлось дожечь отдельно.

 Re: Al Zimmermann's: Summertime16.07.2021, 11:05

12/07/21
108
 Последний раз редактировалось traffic_lights 16.07.2021, 11:11, всего редактировалось 2 раз(а). erraenГде Вы взяли оптимум для n=400? Можете поточней "качество" полученного Вами решения указать? И каково Ваше время для n=215?

 Re: Al Zimmermann's: Summertime16.07.2021, 16:24

12/07/21
108
 traffic_lights в сообщении #1526285 писал(а):Рассматривалась ли задача о минимальном количестве треугольников, все стороны которых имеют разный цвет?Не минимальном количестве треугольников, а максимальное.

 Re: Al Zimmermann's: Summertime16.07.2021, 20:55

20/03/16
5
Киев
 traffic_lights в сообщении #1526304 писал(а):erraenГде Вы взяли оптимум для n=400? Можете поточней "качество" полученного Вами решения указать? И каково Ваше время для n=215?Моя реализация не очень эффективная и на не очень подходящем для числодробилок языке, писалась сугубо для "покрутить задачу", но как оказалось, этого было достаточно.Она слишком медленна, чтобы найти оптимум "с нуля" за разумное время даже для 47, так что для 215 это бы заняло вечность.Поэтому появилась идея построить бОльший граф, более-менее оптимальный, в надежде что он потом самооптимизируется при уменьшении, и это сработало.Изначальный граф для n=400 построен последовательным добавлением точек, выбирая цвет рёбер при добавлении исходя из минимизации кол-ва одноцветных треугольников.После отжига он имел 482622 полноцветных треугольника.Точного значения оптимума для n=400 на тот момент я не знал, значение никак не выбиралось, действовал по принципу "достаточно долго улучшения нет, попробую поуменьшать".Построение по асимтотической формуле от Herbert Kociemba дает 410800.Т.е. фактически это похоже на то, что делал Vovka17, но с однократной оптимизацией и запасом по размеру для нивелировки неоптимальности графа после отжига

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

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

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

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

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

 Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group