2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 13  След.
 
 Re: Al Zimmermann: non-coplanar points
Сообщение25.03.2016, 13:20 
Аватара пользователя
Pavlovsky в сообщении #1108980 писал(а):
1) Представим плоскость в виде: $ax+by+cz+d=0$
2) В цикле переберем координату z из интервала [0,N-1]
3) Получается линейное диафантово уравнение с двумя неизвестными (x,y). Решаем его расширенным алгоритмом Евклида.


You solve a diophantine equation for each z or just one? The latter is what I do.

Btw. here are the best solutions in the moment. Al has changed his policy:

{5, 8, 13, 18, 28, 32, 40, 44, 52, 62, 66, 79, 86, 88, 95, 105, 116, 119, 131, 136, 140, 150, 158, 167, 181}

I only have the best one for N=2..7

 
 
 
 Re: Al Zimmermann: non-coplanar points
Сообщение25.03.2016, 13:43 
Аватара пользователя
Herbert Kociemba в сообщении #1109028 писал(а):
You solve a diophantine equation for each z or just one?

$ax+by+cz+d=0$
Перепишем так:
$ax+by=d'$ $d'=-cz-d$

Алгоритм Евклида сначала ищет решение
$ax_0+by_0=gcd(a,b)$

Это решение не зависит от d' и его можно сделать за пределами цикла перебирающего z.

 
 
 
 Re: Al Zimmermann: non-coplanar points
Сообщение27.03.2016, 15:48 
Аватара пользователя
Ал сделал новую страницу где показывает лучшие результаты. Это очень удобно!

 
 
 
 Re: Al Zimmermann: non-coplanar points
Сообщение28.03.2016, 11:05 
Аватара пользователя
dimkadimon в сообщении #1109002 писал(а):
Pavlovsky в сообщении #1108980 писал(а):
Наконец то и я решил эту задачу для общего случая. Получился простой, красивый и эффективный алгоритм.

1) Представим плоскость в виде: $ax+by+cz+d=0$
2) В цикле переберем координату z из интервала [0,N-1]
3) Получается линейное диафантово уравнение с двумя неизвестными (x,y). Решаем его расширенным алгоритмом Евклида.

Все!

Гениально! Но будет ли это быстрее?

Все это время потратил разработкой этого метода. Расширенный алгоритм Евклида штука не простая и там много подводных камней. Результат? Этот метод оказался в два раза медленее старого! Старый метод просто перебирает координаты $x,y$, а потом находит $z$ используя уравнение плоскости. Мой совет - не тратьте время на этот новый метод!

 
 
 
 Re: Al Zimmermann: non-coplanar points
Сообщение28.03.2016, 14:57 
Аватара пользователя
dimkadimon в сообщении #1109795 писал(а):
Мой совет - не тратьте время на этот новый метод!

I am not sure about this. Looping throgh the x,y coordinates should give a runtime O(N^2), while the runtime for the "new" method seems to be about O(N).
I generated 20 million random planes for N=10, 20, 30, 40, 50, 60, 70, 80, 90, 100 and it took about 11, 15, 20, 23, 25, 28, 31, 34, 37, 40 seconds to get the grid coordinates of the planes. Is your method really faster?

 
 
 
 Re: Al Zimmermann: non-coplanar points
Сообщение28.03.2016, 15:21 
Аватара пользователя
Herbert Kociemba в сообщении #1109857 писал(а):
I am not sure about this. Looping throgh the x,y coordinates should give a runtime O(N^2), while the runtime for the "new" method seems to be about O(N).

Hmm... perhaps my implementation is terrible and has a large constant factor. I would have thought the Euclid method to be at least O(Nlog(N)) though - N for the z loop and log(N) for the Euclid algorithm. Also I am computing $gcd(a,b)$ for each new z, perhaps that's the main difference? I'll get back to you on this.

 
 
 
 Re: Al Zimmermann: non-coplanar points
Сообщение28.03.2016, 15:26 
Аватара пользователя
dimkadimon в сообщении #1109860 писал(а):
Also I am computing $gcd(a,b)$ for each new z,


Именно это делает алгоритм неэффективным.

Pavlovsky в сообщении #1109032 писал(а):
Алгоритм Евклида сначала ищет решение
$ax_0+by_0=gcd(a,b)$

Это решение не зависит от d' и его можно сделать за пределами цикла перебирающего z.

!

 
 
 
 Re: Al Zimmermann: non-coplanar points
Сообщение29.03.2016, 10:58 
Аватара пользователя
Pavlovsky в сообщении #1107336 писал(а):
Спроецируем куб на плоскость образованную осями координат x и y.
Тогда
1) При проекции на плоскость x-y не появится прямая где более трёх точек.
2) При проекции на плоскость x-y, в полученном квадрате будет количество точек равное количеству точек в исходном решении или на 1 меньше.


Продолжу эту тему.

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

 
 
 
 Re: Al Zimmermann: non-coplanar points
Сообщение29.03.2016, 11:27 
Аватара пользователя
Pavlovsky в сообщении #1109862 писал(а):
Именно это делает алгоритм неэффективным.

Добавил это в свой метод, но он все равно медленее оригинального... Получив $gcd(a,b)$ я долго перебираю подходящии координаты x,y.

 
 
 
 Re: Al Zimmermann: non-coplanar points
Сообщение29.03.2016, 11:34 
Аватара пользователя
Расширенный алгоритм Евклида дает решение ввиде

$x=a_x+b_x*t$
$y=a_y+b_y*t$

Легко вычислить диапозон $[t_n,t_k]$ при котором точка (x,y,z) будет принадлежать кубу для всех целых t из $[t_n,t_k]$ .

 
 
 
 Re: Al Zimmermann: non-coplanar points
Сообщение29.03.2016, 12:26 
Аватара пользователя
Pavlovsky в сообщении #1110134 писал(а):
$x=a_x+b_x*t$
$y=a_y+b_y*t$

It should be $x=a_x+b_x*t_1$ and $y=a_y+b_y*t_2$. If you only use one parameter t the points will lie on a single line, which is not true.

 
 
 
 Re: Al Zimmermann: non-coplanar points
Сообщение30.03.2016, 14:54 
Аватара пользователя
Ура получилось! Огромное спасибо за подсказки.

 
 
 
 Re: Al Zimmermann: non-coplanar points
Сообщение30.03.2016, 15:03 
Аватара пользователя
dimkadimon в сообщении #1109545 писал(а):
Ал сделал новую страницу где показывает лучшие результаты. Это очень удобно!


Теперь нет смысла держать свои результаты под подушкой?! :D

Цитата:
7 23.51 Dmitry Kamenetsky Adelaide, Australia 30 Mar 2016 12:22

 
 
 
 Re: Al Zimmermann: non-coplanar points
Сообщение31.03.2016, 15:17 
Аватара пользователя
Pavlovsky в сообщении #1110513 писал(а):
Теперь нет смысла держать свои результаты под подушкой?! :D

Это верно! Мне кажется Ал открыл рекорды чтобы всем дать шанс против Tomas и сделать соревнование интереснее.

 
 
 
 Re: Al Zimmermann: non-coplanar points
Сообщение31.03.2016, 15:37 
Аватара пользователя
Конечно! Знание максимальных результатов в этой задаче никак не облегчает их нахождение.

 
 
 [ Сообщений: 195 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 13  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group