2014 dxdy logo

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

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




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


27/04/09
28128
ozheredov
podih
Ну серьёзно, нормально он сформулировал. Есть элементарные исходы. В каждом из них клад находится в какой-то точке. Есть функция, по стратегии и положению клада выдающая длину пути, пока мы не наткнулись на него. Значит, есть функция, дающая длину пути по стратегии и элементарному исходу. Значит, если стратегия фиксирована, есть функция из элементарного исхода в длину пути. Это случайная величина, раз мы имеем вероятностное распределение на исходах, и мы можем поинтересоваться её матожиданием. Это совершенно механическое жонглирование основными определениями теорвера.

-- Вс июл 14, 2019 17:53:32 --

Видимо, непонятно, что такое стратегия. Будем считать, что это последовательность чисел $a_i$ и реализуется стратегия так: сначала мы идём вправо, пока не попадём в $a_0$, потом влево до $a_1$, потом снова вправо до $a_2$ и так далее. То, что стратегией должно считать именно такое, очевидно если иметь в виду, что мы ничего не знаем — как только мы нашли клад, мы уже победили, а пока не нашли, мы не получаем дополнительной информации, и потому весь маршрут можем спланировать заранее, ровно один.

-- Вс июл 14, 2019 17:54:10 --

Гораздо интереснее говорить о решении.

 Профиль  
                  
 
 Re: Оптимальный маршрут
Сообщение14.07.2019, 17:02 


10/03/16
3855
Aeroport
arseniiv
А, вон оно как... ну тогда сорян, виной всему моё стереотипное мышление )) Я думал, что мы втыкаем лопату и... то есть, победа -- это накрытие точки клада хотя бы одним из звеньев маршрута. Понял. Sicker, смиренно прошу простить меня

-- 14.07.2019, 17:12 --

Ок. Пусть распределение -- дельта-функция с центром на правом конце (исходно я в левом). Now what?
А не, автор вводит какие то ограничения на плотность. Но хорошо бы поставить эту задачу как минимакс: что делать, чтобы в наихудших условиях особо не обделаться

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


13/08/13

4323
ozheredov в сообщении #1405049 писал(а):
А не, автор вводит какие то ограничения на плотность

Никаких ограничений нет, есть заданная функция распределения :-)
ozheredov в сообщении #1405049 писал(а):
Но хорошо бы поставить эту задачу как минимакс: что делать, чтобы в наихудших условиях особо не обделаться

Грубо говоря минимакс тут равен бесконечности, ибо клад может быть сколько угодно удаленным от нуля (т.к. гауссиана не затухает)
Минимакс вроде можно понимать так. Вот у нас есть функция плотности вероятности получить какую-то суммарную длину пути, т.е. по оси абцисс суммарный путь до клада, а по оси ординат плотность вероятности. Тогда сама функция плотности вероятности будет иметь примерно такой вид - на характерном расстоянии $L$ будет максимальная плотность вероятности (по идее $L$ будет совпадать или лежать близко к математическому ожиданию), которая будет спадать по мере удаления в обе стороны от $L$, и можно условно ввести характерную ширину этого холма - $\Delta L$. Я так понимаю, вы собрались минимизировать не $L$, а $L+\Delta L$? Мне кажется это немного бессмысленно от нечеткой определенности этого самого $\Delta L$

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


01/09/13
4318
arseniiv в сообщении #1405036 писал(а):
сначала мы идём вправо, пока не попадём в $a_0$,

А почему $a_0$ конечно?

 Профиль  
                  
 
 Re: Оптимальный маршрут
Сообщение14.07.2019, 18:05 


10/03/16
3855
Aeroport
Geen в сообщении #1405055 писал(а):
А почему $a_0$ конечно?


Разве не для любого расположения клада и точки старта существует маршрут

arseniiv в сообщении #1405036 писал(а):
сначала мы идём вправо, пока не попадём в $a_0$, потом влево до $a_1$, потом снова вправо до $a_2$ и так далее.



с конечным $a_0$, такой, что хотя бы одно звено накрывает точку клада? Можете плииз привести контрпример?

А, кажется понял. По-видимому, с какой-то исчезающей вероятностью мы вообще не найдем клад

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


11/12/16
13195
уездный город Н
Geen в сообщении #1405055 писал(а):
А почему $a_0$ конечно?


Если при каких-то расположениях клада на множестве ненулевой меры стратегия дает бесконечный путь, то и МО длины пути будет бесконечным. Нет?
А если так, то должен быть какой-то критерий, чтобы "перестать искать под фонарем" и вернуться к жирным россыпям :D

-- 14.07.2019, 18:17 --

ozheredov в сообщении #1405056 писал(а):
По-видимому, с какой-то исчезающей вероятностью мы вообще не найдем клад

В условиях задачи если не вернёмся, то не найдем клад с вероятностью одна вторая, которая никуда не исчезает.

 Профиль  
                  
 
 Re: Оптимальный маршрут
Сообщение14.07.2019, 18:31 


10/03/16
3855
Aeroport
EUgeneUS в сообщении #1405059 писал(а):
Если при каких-то расположениях клада на множестве ненулевой меры стратегия дает бесконечный путь, то и МО длины пути будет бесконечным.


Самый прикол будет, если для распределений с отсутствующим средним (тяжелый хвост!) МО длины некоторых решающих задачу траекторий окажутся конечными. Интуиция естетсвенно подсказывает, что этого не может быть, потому что не может быть никогда, но то ж интуиция :-)

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


27/04/09
28128
Geen в сообщении #1405055 писал(а):
А почему $a_0$ конечно?
Ну можно расширить определение, да, это вы хорошую дырку нашли — сделаем последовательности не обязательно бесконечными, и тогда, когда числа кончаются, мы идём в текущем направлении в бескрайнюю даль (и назад нам уже возвращаться не понадобится).

Правда, как уже заметили, в этой задаче такие стратегии заведомо проигрышные.

ozheredov в сообщении #1405056 писал(а):
А, кажется понял. По-видимому, с какой-то исчезающей вероятностью мы вообще не найдем клад
Нам важно не просто найти клад, нам важно найти его поскорее. А так да, если $[0; a_0]\subsetneq [a_1; a_0]\subsetneq [a_1; a_2]\subsetneq [a_3; a_2]\subsetneq \ldots$, то мы найдём клад обязательно, и наоборот, если это неверно, то клад мы найдём не достоверно.

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


01/08/06
3049
Уфа
Я в сообщении #1404831 писал(а):
Первое метание — на $\sqrt{2\pi}\sigma$?
Напишу, как я дошёл до жизни такой.
Во-первых, вычислений немало, где-то я мог наврать, так что следите за руками!
Во-вторых, я сразу принял $\sigma=1$, потому что понятно, что результат потом можно просто умножить на правильное $\sigma$.
В-третьих, у меня немного другие обозначения, чем у arseniiv.
Идём вправо до точки $x_0$. Потом влево до точки $-x_1$. Потом опять вправо до $x_2 > x_0$ и опять влево до $-x_3 < -x_1$. И т.д. Таким образом, все $x_i>0$.
Интересующее нас матожидание складывается из кусков, вычисляемых только на тех участках, на которые мы вступили впервые. Вычисляется стандартным образом: текущее значение пройденного пути умножается на плотность вероятности в текущей точке и интегрируется. Вспомним для начала плотность вероятности нормального распределения с нулевым средним и единичной дисперсией:
$$p(x)=\frac{1}{\sqrt{2\pi}}e^{-x^2/2}.$$
Поехали! На нулевом участке получается:
$$M_0=\frac{1}{\sqrt{2\pi}}\int\limits_0^{x_0} xe^{-x^2/2}dx=\frac{1-e^{-x_0^2/2}}{\sqrt{2\pi}}.$$
На первом уже возникает не берущийся в элементарных функциях интеграл. Введём для него стандартное обозначение:
$$E(x)=\mathrm{erf}(x)=\frac{2}{\sqrt{\pi}}\int\limits_0^t e^{-t^2}\,dt.$$ Кусок матожидания получается:
$$M_1=\frac{1}{\sqrt{2\pi}}\int\limits_0^{x_1} (x+2x_0)e^{-x^2/2}dx=\frac{1-e^{-x_1^2/2}}{\sqrt{2\pi}}+x_0 E\left(\frac{x_1}{\sqrt{2}}\right).$$
(тут мы пользуемся симметричностью распределения). Подынтегральная добавка $2x_0$ означает, что мы бесплодно дошли до $x_0$ и обратно. На втором шаге, когда мы пойдём опять вправо, эта добавка будет уже $2x_0+2x_1$ (хотя на самом деле мы бесплодно пройдём ещё больше: $4x_0+2x_1$, но $2x_0$ из этого пути будет уже учтено в $x$). И т.д. На $n$-м шаге ($n>1$) получается такой кусок матожидания:
$$M_n=\frac{1}{\sqrt{2\pi}}\int\limits_{x_{n-2}}^{x_n} \left(x+2\sum\limits_{i=0}^{n-1} x_i\right)e^{-x^2/2}dx=\frac{e^{-x_{n-2}^2/2}-e^{-x_n^2/2}}{\sqrt{2\pi}}+\left(\sum\limits_{i=0}^{n-1} x_i\right) \left(E\left(\frac{x_n}{\sqrt{2}}\right)-E\left(\frac{x_{n-2}}{\sqrt{2}}\right)\right).$$
Искомое матожидание:
$$M=\sum\limits_{n=0}^{\infty}M_n=\sqrt\frac{2}{\pi}+x_0 E\left(\frac{x_1}{\sqrt{2}}\right)+\sum\limits_{n=2}^\infty\left(\sum\limits_{i=0}^{n-1} x_i\right) \left(E\left(\frac{x_n}{\sqrt{2}}\right)-E\left(\frac{x_{n-2}}{\sqrt{2}}\right)\right)$$
Первую часть суммы я сразу выписал, потому что она "сворачивается" легко: в ней осталось только две единицы из числителей дробей $M_0$ и $M_1$, которые мы складываем и делим на знаменатель, остальные слагаемые взаимно уничтожаются.
С остатком сложнее. Снизим его громоздкость, введя обозначение $E_k=E\left(\frac{x_k}{\sqrt{2}}\right)$:
$$x_0E_1+\sum\limits_{n=2}^\infty\left(\sum\limits_{i=0}^{n-1} x_i\right) \left(E_n-E_{n-2}\right)$$
Соберём вместе коэффициенты перед $x_i$:
\begin{align*}
&x_0\left(E_1+E_2-E_0+E_3-E_1+E_4-E_2+E_5-E_3+\dots\right)+\\
+&x_1\left(E_2-E_0+E_3-E_1+E_4-E_2+E_5-E_3+\dots\right)+\\
+&x_2\left(E_3-E_1+E_4-E_2+E_5-E_3+\dots\right)+\\
+&\dots
\end{align*}

Видим, что почти всё уничтожается и остаётся
$$x_0\left(2E_\infty-E_0\right)+x_1\left(2E_\infty-E_0-E_1\right)+x_2\left(2E_\infty-E_1-E_2\right)+\dots$$
Учитывая, что $E_\infty=\mathrm{erf}(\infty)=1$, имеем:
$$M=\sqrt\frac{2}{\pi}+\sum\limits_{n=0}^{\infty}x_n\left(2-E_{n-1}-E_n\right),$$ где для пущей компактности доопределено $x_{-1}=0$, соответственно, $E_{-1}=E(0)=0$.
Вот эту вещь нам и предстоит минимизировать.
Давайте-ка для ещё большей компактности определим $F(x_i)=F_i=1-E_i=1-\mathrm{erf}(x_i/\sqrt{2})$ (напоминаю, что $F_{-1}=1$ — константа):
$$M(x_0,x_1,\dots)=\sqrt\frac{2}{\pi}+\sum\limits_{n=0}^{\infty}x_n\left(F(x_{n-1})+F(x_n)\right) \to\min$$
Функция $F$ — гладкая, поэтому со спокойной душой (и тяжёлым сердцем, ибо $M$, как функция счётного числа аргументов, по-хорошему, требует к себе отдельного уважения) дифференцируем по каждой переменной:
$$\frac{\partial M}{\partial x_n}=F(x_{n-1})+F(x_n)+F'(x_n)(x_n+x_{n+1})=0.$$
Отсюда следует рекуррентная формула:
$$x_{n+1}=-\left(x_n+\frac{F(x_{n-1})+F(x_n)}{F'(x_n)}\right).$$
К сожалению, этого недостаточно для определения $x_0$ :cry:
Но если мы обнаглеем :D и продлим эту формулу на $n=-1$ (для этого ещё понадобится доопределить $x_{-2}=0$), то получим: $$x_0=0-\frac{1+1}{F'(0)},$$ откуда, вспоминая, что такое $F$, получаем: $x_0=\sqrt{2\pi}$.
Что можно сказать в оправдание такой наглости? Ну, например, вот что: допустим, нулевому шагу вправо предшествовал "минус первый" шаг влево на неизвестную величину, а потом будем уменьшать эту величину до нуля. На итоговое поведение это не повлияет. Так себе оправдание, но я смутно чувствую, что в нём что-то есть.

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


01/09/13
4318
Похоже меня не поняли :-) - почему первый шаг не бесконечно малый?

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


24/01/19

265
arseniiv в сообщении #1405073 писал(а):
нам важно найти его поскорее

Т.е. надо максимилизировать МО.
Тогда да. Возможно, поворотов будет бесконечно много. Интуиция здесь не работает. Считать надо...
Путь растёт линейно, а прибыль с объеденного куска обратно-экспонентуально. А на недоеденном куске сравнительно жирнее. Но надо возвращаться...
Плюнуть на теорию и зарубиться в численном эксперименте?
Почитал worm2. Да, мне здесь делать нечего.

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


27/04/09
28128
Geen
Ну пусть он бесконечно малый, погоды-то он не сделает и в вещественных числах не выразится. :-) Какая ему стать быть бесконечно малым?

podih в сообщении #1405085 писал(а):
Т.е. надо максимилизировать МО.
Минимизировать МО, как написано притом в первом посте.

podih в сообщении #1405085 писал(а):
Да, мне здесь делать нечего.
Спасибо, наконец-то. :mrgreen:

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


01/09/13
4318
arseniiv в сообщении #1405086 писал(а):
Какая ему стать быть бесконечно малым?

В терминах поста worm2 я уверен лишь в том, что $x_{-\infty}=0$...

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


27/04/09
28128
Мы не можем ходить много на мелкие шаги — так мы слишком много раз пройдём уже проверенные места зазря.

Кстати если бы распределение было экспоненциальным, нам было бы полезнее всего идти не останавливаясь вправо. Но если бы оно было сдвинутым левее, то (сейчас будет от балды) скорее всего нам будет полезнее идти сначала влево до точки скачка плотности, а потом поворачивать вправо и не останавливаться.

-- Вс июл 14, 2019 22:38:46 --

Кстати а нельзя ли тут стратегию с бесконечными поворотами получить как-то из стратегий с конечным числом поворотов (и их друг из друга)? Лучшая стратегия с нулём поворотов и единственная, лучшая стратегия с одним поворотом должна очевидно выбираться, стратегия с двумя могла бы быть в удачном случае модификацией предыдущей (можно раньше повернуть в первый раз, потому что всё равно вернёмся, зато шагнуть дальше (кажется) до второго поворота, чем в предыдущей стратегии).

-- Вс июл 14, 2019 22:42:48 --

А вот можно наоборот выдать бедолаге одну канистру воды и отправить на поиски фонтана молодости (где заодно стоит телепортер домой), то есть искать стратегию, максимизирующую вероятность успеха найти клад (как кому-то и хотелось) при возможности протопать только данное заранее расстояние. Ещё можно искать лучшую из стратегий, дающих неединичную фиксированную заранее вероятность успеха. Вот теперь у нас будет большое пространство, где возможно (или нет) всё связать. Кто хочет попытаться? :D

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


29/06/15
277
[0,\infty )
worm2 в сообщении #1405082 писал(а):
Отсюда следует рекуррентная формула:
$$x_{n+1}=-\left(x_n+\frac{F(x_{n-1})+F(x_n)}{F'(x_n)}\right).$$

Извините, у меня немножко другая формула получается
$x_{n+1}=x_n+\frac{(-1)^{n}+F(x_{n-1})-F(x_n)}{F'(x_n)}$
Вот ее обоснование. $x_n$ при n четном точка поворота влево. точка $x_n+dx_n$ даст меньшее итоговое матожидание, если клад на отрезке между ними, что будет с вероятностью $\sim F'(x_n)dx_n$ ,причем меньше на величину $2|x_n-x_{n+1}|$ , то есть не при следующем проходе за точку $x_n$, а сразу.В остальных случаях даст большее матожидание на величину $2dx_n$, с вероятностью, эквивалентной при $dx_n\to 0$ той, что клад не был найден ранее, $1-|F(x_n)-F(x_{n-1})|$. Если $x_n$ оптимальная точка поворота, получаем равенство
$|x_n-x_{n+1}|F'(x_n)+|F(x_n)-F(x_{n-1})|=1$ Под модулями оба положительные, если точка поворота влево, и оба отрицательные, если n было нечетное и точка поворота вправо.
Поэтому раскрываются $(x_n-x_{n+1})F'(x_n)+F(x_n)-F(x_{n-1})=(-1)^n$. При $n=0$ $F(x_{-1}):=\frac 12$
Получаются $x_0=\sqrt{2\pi},x_1=-84,14753$

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

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



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

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


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

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