2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Оптимальный маршрут
Сообщение15.07.2019, 13:10 
Заслуженный участник


10/01/16
2187
iancaple
Ну, с учетом разницы в обозначениях, это как раз и есть то...

 Профиль  
                  
 
 Re: Оптимальный маршрут
Сообщение15.07.2019, 13:17 
Заслуженный участник
Аватара пользователя


01/08/06
2760
Уфа
DeBill, iancaple, да, так и есть, формулы совпадают.
У меня просто с самого начала повелось, что все иксы положительны, а знаки я уже в самом конце расставляю.
Т.е. если истинные координаты поворотов кладоискателя взять за $a_n$, то мои $x_n=(-1)^na_n$, и формула преобразуется к такой:
$$a_{n+1}=a_n+\frac{2(-1)^n+F(a_{n-1})-F(a_n)}{F'(a_n)}.\eqno{(1)}$$
Тут у меня вместо $(-1)^n$ стоит $2(-1)^n$. Вероятно, вы, iancaple, за $F$ обозначаете половину той функции $F$, которая у меня, тогда совпадение будет полным. Это также объясняет вашу формулу $F(x_{-1})=\frac 1 2$ (у меня $F(x_{-1})=F(0)=1$). Поэтому тут я должен расписать свою $F$ подробно: $$F(x)=\mathrm{erfc}\left(\frac{x}{\sqrt{2}}\right)=1-\mathrm{erf}\left(\frac{x}{\sqrt{2}}\right)=\sqrt\frac{2}{\pi}\int\limits_{x}^{+\infty}e^{-t^2/2}\,dt \quad \Rightarrow\quad \frac{1}{F'(a_n)}=-\sqrt\frac{\pi}{2}e^{a_n^2/2}.$$ (определения $\mathrm{erf}$ и $\mathrm{erfc}$ взяты, как они приняты в Wolfram).
Далее, рассмотрим дробь в (1). Функция $F$ на $\mathbb{R}$ убывает от 2 до 0, знак $a_n$ совпадает со знаком $(-1)^n$, поэтому знак $F(a_{n-1})-F(a_n)$ противоположен знаку $2(-1)^n$, а по модулю всегда меньше модуля этой величины (двойки). Поэтому знак числителя в (1) совпадает со знаком $(-1)^n$, и можно переписать (1) как:
$$a_{n+1}=a_n-(-1)^n e^{a_n^2/2}\left(\sqrt{2\pi}-\left|\int\limits_{a_{n-1}}^{a_n}e^{-t^2/2}\,dt\right|\right).$$
По крайней мере, эта формула не страдает от неоднозначностей. По ней получается $a_1\approx -26.8494$.

 Профиль  
                  
 
 Re: Оптимальный маршрут
Сообщение15.07.2019, 14:22 
Заслуженный участник


10/01/16
2187
Пусть $F(x)$ - некий функционал, и мы ищем его экстремум, прравнивая производную к нулю.
Пусть у нас нашлось целое семейство $x_t$ решений: $F'(x_t) =0$.
Посчитаем значения функционала $f(t)=F(x_t) $ в энтих точках.
Тогда: $\dot{f}=F'(x_t)\dot{x_t}=0$. Значит, $f$ - константа....

Так что для нашей задачи, $x_0$ можно выбирать произвольно - значения экстремума не зависит...(ну, если, конечно, работают все оговоркиworm2, связанные с бесконечномерномерностью, и еще такие же добавить...)

 Профиль  
                  
 
 Re: Оптимальный маршрут
Сообщение15.07.2019, 15:05 
Аватара пользователя


29/06/15
272
[0,\infty )
worm2 в сообщении #1405157 писал(а):
По крайней мере, эта формула не страдает от неоднозначностей. По ней получается $a_1\approx -26.8494$.
Да у меня тоже теперь $a_1\sim -26.84944$, была ошибка.
$F$ у меня была интегральная функция распределения места клада, для общности, обязательно непрерывная.
А вот начинать поиски с $x_{-1}=0$ неоптимально, но это уже другая задача, так? И ответ я не знаю

 Профиль  
                  
 
 Re: Оптимальный маршрут
Сообщение15.07.2019, 16:32 
Аватара пользователя


13/08/13
4087
arseniiv в сообщении #1405091 писал(а):
Кстати а нельзя ли тут стратегию с бесконечными поворотами получить как-то из стратегий с конечным числом поворотов (и их друг из друга)?

Т.к. гауссиана никогда не затухает до нуля то нет, нельзя. Т.е. при любой стратегии с конечным числом поворотов у нас есть ненулевая вероятность никогда не наткнуться на клад. В принципе стратегия с конечным числом поворотов сработала бы в случае если распределение угасает ровно в ноль вне какого-то отрезка.
Я короче распишу случай для предельной функции распределения зеркальных плотностей $f(x)=\frac{1-|x+L|}{2}$ на $[-L-1;-L+1]$ и $f(x)=\frac{1-|x-L|}{2}$ на $[L-1;L+1]$ при $L\rightarrow \infty$. Там тогда можно радиусы метаний разложить как $L+1+a_0 d+a_1 d^2+...$, где $d=\frac{1}{L}$

 Профиль  
                  
 
 Re: Оптимальный маршрут
Сообщение15.07.2019, 16:54 
Заслуженный участник
Аватара пользователя


27/04/09
27145
Sicker в сообщении #1405187 писал(а):
Т.е. при любой стратегии с конечным числом поворотов у нас есть ненулевая вероятность никогда не наткнуться на клад.
Это да, это бы было бы как-то учтено.

 Профиль  
                  
 
 Re: Оптимальный маршрут
Сообщение19.07.2019, 20:25 
Заслуженный участник
Аватара пользователя


01/08/06
2760
Уфа
Я тут, попробовал численно посчитать, подставляя различные значения $a_0$ и $a_1$ (в моей терминологии $x_0$ и $x_1$), и считая дальше по рекуррентной формуле.
И у меня, знаете ли, фигня получается.
Ситуацию осложняет то, что по рекуррентной формуле абсолютные значения абсцисс очень быстро растут, буквально, как "степенная башня". И в процессе вычислений очень быстро наступает переполнение, хотя я ещё не уверен, что остаток ряда мал, и его можно отбросить.
Но это ещё не самое странное.
По рекуррентной формуле запросто может получиться, что $|a_n| < |a_{n-2}|$, т.е. мы должны поворачивать раньше, чем достигаем границы, которую посетили в прошлый раз.
Отсюда можно сделать неутешительный вывод: то, что я там дифференцирую функцию бесконечного числа аргументов и приравниваю производные к нулю — это ведь только необходимое условие глобального минимума. Нужно ещё, чтобы матрица вторых производных была положительно определена (что бы это ни значило в бесконечномерном случае), а она, похоже, не всегда.
Могу лишь поделиться странным результатом: минимум матожидания, который я получил, равен примерно 2.91 и достигается примерно при $a_0=+1.4$, $a_1=-2.6$ (получен на сетке с шагом 0.1). Причём этот минимум лежит на границе "допустимой области": рядом с ним наблюдается фигня ($|a_n| < |a_{n-2}|$).
Значение при $a_0=0$, $a_1=-\sqrt{2\pi}$, которое я считал минимальным, даёт матожидание примерно 3.66233, т.е. существенно большее.

 Профиль  
                  
 
 Re: Оптимальный маршрут
Сообщение22.07.2019, 00:03 
Заслуженный участник
Аватара пользователя


01/08/06
2760
Уфа
На предыдущем допросе я искал решение среди различных $a_0$ и $a_1$, совершенно забыв, что $a_1$ однозначно определяется через $a_0$ (ведь $a_{-1}=0$ и $F_{-1}=1$).
Поэтому достаточно произвести одномерный поиск $a_0$. После того, как я это осознал, дела пошли гораздо веселее.
Увеличивая точность, у меня слетела шляпа от удивления. Чем ближе я подходил к оптимальной точке, тем менее полученная последовательность проявляла склонность к взрывному росту: она неторопливо гуляла туда-сюда, и всё позже, как бы нехотя говорила: мол, засиделась я тут, пора и честь знать, и наконец резко взмывала в свою "степенную башню".
Причём шаг влево от оптимальной точки приводил к бесполезному "замыканию в себе" ($|a_{n+2}|<|a_n|$), а шаг вправо — к гораздо более раннему старту в космос.
К двенадцатому знаку после запятой до меня этот намёк начал доходить. Оптимальная последовательность вообще никуда не улетает, а территорию захватывает потихоньку!
Вот ряд, рассчитанный для точности $a_0$ в 15 значащих цифр (стандартная двойная точность компьютерных чисел):
+1.44085409998362
-2.6275801141085
+3.63220011457
-4.5203424258
+5.32668133
-6.0715776
+6.76811
-7.425
+8.0

Уменьшение числа знаков после запятой означает уменьшение соответствующей точности. Точность рассчитывалась исходя из примерного совпадения членов последовательности для начальных значений $a_0$ и $a_0+10^{-14}$. Помимо "естественного" падения точности, обусловленного чрезвычайной чувствительностью к начальному значению $a_0$, есть ещё и вычислительные сложности. Напомню расчётную формулу:
$$a_{n+1}=a_n-(-1)^n e^{a_n^2/2}\left(\sqrt{2\pi}-\left|\int\limits_{a_{n-1}}^{a_n}e^{-t^2/2}\,dt\right|\right).$$
Её можно переписать так (пользуясь симметрией плотности распределения):
$$a_{n+1}=a_n-(-1)^n e^{a_n^2/2}\left(\int\limits_{|a_{n-1}|}^{+\infty}e^{-t^2/2}\,dt+\int\limits_{|a_n|}^{+\infty}e^{-t^2/2}\,dt\right).$$
С ростом $|a_n|$ коэффициент перед интегралами $e^{a_n^2/2}$ очень быстро растёт, в то время как сами интегралы очень быстро убывают, но насколько быстро? Используемая библиотечная функция для расчёта $\mathrm{erfc}(x)$ имеет сомнительную относительную погрешность для больших значений агрумента, и не совсем понятно, что с этим можно сделать. Да, есть асимптотическая формула, но спасает ли она в данном случае?
Тем не менее, несмотря на все эти сложности, тенденция ощущается. Видно, что разность между соседними точками не растёт, а даже уменьшается, что, согласитесь, более соответствует интуитивному представлению о том, как должно быть.
Итак, численный эксперимент подсказывает нам, что начальное значение оптимальной последовательности — замечательное число. Оно, с одной стороны, является минимальным числом, для которого выполняется необходимое условие $D_n=|a_{n+2}|-|a_n|>0$, а, с другой стороны — максимальным числом, для которого эта последовательность разностей $D_n$ ограничена сверху.
Попытка засунуть оптимальное начальное значение 1.44085409998362 (как и минимальное значение математического ожидания времени поиска 2.903665477166) в Inverse Symbolic Calculator успеха не дала: эта база данных математических констант ничего о них не знает.
Да, ещё хорошая новость: та часть "бесконечной матрицы" вторых производных, которую удалось рассчитать, имеет совершенно явное и сильное диагональное преобладание, что даёт "положительную определённость", а значит, и основание считать, что найденный экстремум — именно минимум.

 Профиль  
                  
 
 Re: Оптимальный маршрут
Сообщение22.07.2019, 15:30 
Заслуженный участник
Аватара пользователя


01/08/06
2760
Уфа
Похоже, всё уже придумано и решено до нас :-)
https://math.stackexchange.com/question ... d-solution
Там есть и ссылки на статьи, например:
https://link.springer.com/article/10.1007%2FBF02786568

 Профиль  
                  
 
 Re: Оптимальный маршрут
Сообщение27.07.2019, 14:12 
Заслуженный участник
Аватара пользователя


01/08/06
2760
Уфа
Оптимальное значение первого прыжка 1.440854... близко к корню уравнения
$$1+\mathrm{erfc}\left(\frac{x}{\sqrt{2}}\right)=\sqrt{\frac{2}{\pi}}x.$$ Это уравнение получается, если попробовать продлить последовательность в другую сторону, полагая $a_{-1}=0$, и вычисляя $a_{-2}=1.44084546...$. К сожалению, получившееся $a_{-2}$ не равно в точности $a_0$ :-( Причина такого близкого совпадения неизвестна. Разность составляет примерно 0.00000863, что, в свою очередь, недалеко от $\mathrm{erfc(\pi)}\approx0.00000888$. Возможно, существует какой-то быстро сходящийся алгоритм, с помощью которого можно эффективно вычислить оптимальное $a_0$. Но вряд ли его можно получить таким нумерологическим способом, подбирая подходящие константы :roll:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 40 ]  На страницу Пред.  1, 2, 3

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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