LINUX.ORG.RU

«Наиболее быстрый» путь между двумя точками

 ,


0

2

Пусть задана функция V(x, y) мгновенной скорости (например, на некотором прямоугольнике [a,b]*[c,d]) и две точки (внутри этого прямоугольника). Требуется определить траекторию, движение по которой от одной точки до другой (со скоростями, которые определяются той самой заданной функцией) заняло бы наименьшее время.

Для самого простого случая V(x, y)=const такой траекторией является отрезок, соединяющий эти точки.

Уважаемые знатоки, собственно вопрос: известно ли, как построить такую траекторию для более сложных функций? Где об этом можно почитать? Конкретно интересует случай, когда заданы значения функции в углах прямоугольника, а значения внутри получаются при помощи билинейной интерполяции.

★★

известно. Читай учебник по вариационному исчислению.

Например Больца. в твоем случае задача простая. Время прохождения - это простой интеграл по траектории, тебе нужно найти его минимум: то есть интеграл это функция от траектории, а траектория - это как бы «переменная». как ключевое слово - «первая вариация» и «дифференциальное уравнение Эйлера-Лагранжа»

dikiy ★★☆☆☆
()
Последнее исправление: dikiy (всего исправлений: 1)
Ответ на: комментарий от Eddy_Em

> Учебник матана: «задача наискорейшего спуска»

Ога, наискорейше спуститься в минимум функции скорости.

gizzka ★★
() автор топика
Ответ на: комментарий от gizzka

Т.е. у Вас есть ограничение на модуль скорости?

p.s.: как уже выше говорили скорей всего поможет вариационное исчисление (см. например, Галеев, Крус оптимизационных задач), только нужно аккуратно сформулировать условия задачи.

cool_hedin
()
Ответ на: комментарий от buddhist

Емнип, у ТСа будет функционал типа

 b
 |\  sqrt(1+y'^2)
 |   ------------ dx
\|    V(y(x), x)
 a

buddhist ★★★★★
()
Ответ на: комментарий от dikiy

> Время прохождения - это простой интеграл по траектории, тебе нужно найти его минимум: то есть интеграл это функция от траектории, а траектория - это как бы «переменная».

Ну на таком уровне я в курсе. А за ссылку на уравнение Эйлера-Лагранжа большое спасибо, вроде то, что надо, буду разбираться.

gizzka ★★
() автор топика
Ответ на: комментарий от quickquest

> Вариационное исчисление, например: Ректорис К. Вариационные методы в математической физике и технике.

Спасибо, если что - гляну.

gizzka ★★
() автор топика
Ответ на: комментарий от buddhist

фигли там формулировать:

J(x(w),y(w)) = \int\limits_0^W \frac {dw} {V(x(w),y(w))}

это если скаляр.

А если вектор, то тут вообще уже не вариационное исчисление, так как траектория полностью определяется начальным направлением движения в момент t=0.

dikiy ★★☆☆☆
()
Ответ на: комментарий от dikiy

решаем дифур x(t+\Delta t) = x(t)+V(x)\Delta t => x'(t)=V(x).

ну и теперь можно получить результат в зависимости от начального направления вектора, и потом имеем простую задачу оптимизации по одной переменной.

dikiy ★★☆☆☆
()
Ответ на: комментарий от buddhist

> Траектория нужна в аналитическом виде или набором точек?

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

Решение в виде набора точек на сетке для конкретной функции можно найти можно хоть тем же Дейкстрой (например) или чем-то аналогичным. Но долго это, а надо бы находить много раз и желательно быстро.

gizzka ★★
() автор топика
Ответ на: комментарий от cool_hedin

Это если полученное векторное поле гладкое

да неважно в общем-то. Достаточно, чтобы непрерывное было. А если даже не непрерывное, то если количество точек разрыва счетно - это не проблема. Ну а если бесконечное количество разрыва - хз.

dikiy ★★☆☆☆
()
Ответ на: комментарий от cool_hedin

> Т.е. у Вас есть ограничение на модуль скорости?

Все, осилил, о чем речь. Да, по сути функция в каждой точке задает модуль скорости.

gizzka ★★
() автор топика
Ответ на: комментарий от gizzka

кстати, заботай «Цлаф - вариационное исчисления и интегральные уравнения». Это книжка для инженеров по сабжу. Без особой мозголомной теории, но с примерами и рецептами.

dikiy ★★☆☆☆
()
Последнее исправление: dikiy (всего исправлений: 1)
Ответ на: комментарий от dikiy

А если вектор, то тут вообще уже не вариационное исчисление, так как траектория полностью определяется начальным направлением движения в момент t=0.

Почему и спрашивал.

Цлаф - вариационное исчисления и интегральные уравнения

Плюсую, годная книжка.

buddhist ★★★★★
()
Ответ на: комментарий от dikiy

Есть в элементарном виде («кривая наискорейшего спуска»). Додуматься, какое диф. уравнение для конкретного случая составить — пустяк.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

Есть в элементарном виде («кривая наискорейшего спуска»). Додуматься, какое диф. уравнение для конкретного случая составить — пустяк.

а я думаю, с фигли это математики 100 лет над этой проблемой бились. Вот тупыыые :)

dikiy ★★☆☆☆
()
Ответ на: комментарий от Eddy_Em

Ну, не зря же они бились: теперь можно быстренько взять готовое.

так вот - в учебниках по матану проблемы вариационного исчисления не рассматриваются. Проблема брахистохроны тоже не рассматривается (по крайней мере в мне известных учебниках)

dikiy ★★☆☆☆
()
Последнее исправление: dikiy (всего исправлений: 1)
Ответ на: комментарий от dikiy

Давно я учился: могу и попутать вариационное счисление с матаном. Но все-таки, сдается мне, в элементарном виде эта задача рассматривалась у Фихтенгольца.

// погуглил: действительно, в третьем томе фихтенгольцевского матана есть задача о брахистохроне

Eddy_Em ☆☆☆☆☆
()
Последнее исправление: Eddy_Em (всего исправлений: 1)
Ответ на: комментарий от Eddy_Em

я только что глянул в Зориче - там тоже есть. Но это все лишь начала. методов решения много. Уравнение Эйлера Лагранжа обычно решить не удается. Лучше сразу брать нужную книжку, так как вариационное исчисление - это отдельная крупная область математики.

dikiy ★★☆☆☆
()

Вообще то, судя по постановке, это задача на геометрическую оптику (ну или аналогичная ей), V это просто обратный показатель преломления. Свет, как известно, выбирает путь требующий минимального времени, как свет этот путь находит - ХЗ (принцип наименьшего действия однако).

Соответственно, будь у ТС задача динамики, было бы вариационное исчисление и связанные с ним трэш, угар и содомия. А так гуглим уравнение эйконала, решаем его (при V задаваемом по 4м угловым точкам интерполяций это должно быть не сложно) для произвольного начального угла, и выбираем решение проходящее через конечную точку. Начальный угол может быть не единственный, но времена для всех подходящих углов будут одинаковые.

Вариационное исчисление в данном случае то самое у-е эйконала и должно дать, чудес то не бывает... ;-)

AIv ★★★★★
()
Последнее исправление: AIv (всего исправлений: 1)
Ответ на: комментарий от AIv

спасибо, почитал. Узнал кое-что новое.

я не спец конечно в решении дифуров в частных производных, но таки мне кажется, что |\grad u(x))|^2=f(x) совсем не просто решить. Это же нелинейное уравнение получается.

dikiy ★★☆☆☆
()
Ответ на: комментарий от AIv

Вот кстати да, про уравнение Эйконала - годная мысль. Спасибо большое.

gizzka ★★
() автор топика
Ответ на: комментарий от dikiy

Это ж зависит от правой части.

В случае ТС, при билинейной интерполяции в ячейке, справа стоит a x + b y + d x y + c. В воскресный вечер думать лень, но внутренний голос мне подсказывает, что u будет тоже полином?;-)

Если ф-я более сложная, то ее можно представить на сетке, с билинейной интерполяцией в ячейках... знакомьтесь, вот он какой метод конечных элементов!;-) Дальше алгоритмы, аналогичные построению алгоритмам линий уровня для сеточной ф-ии.

AIv ★★★★★
()
Последнее исправление: AIv (всего исправлений: 1)
Ответ на: комментарий от AIv

Ну собственно все как-то примерно так и есть. Есть ячейки «с интерполяцией» и в них хочется очень быстро аналитически «кратчайшие» пути искать. (На самом деле я так подумал, если сильно захотеть - можно даже численно ур-е эйконала порешать для каждой ячейки для конкретной функции с конкретными коэффициентами, если очень захочется какую-то более хитрую функцию. Весь алгоритм замедлит, но не смертельно)

Мне пока думать тоже лень (у нас тоже воскресенье вечер :) ), но кажется, что для данного конкретного случая аналитическое решение найти вполне реально - тогда все вообще хорошо.

gizzka ★★
() автор топика
Ответ на: комментарий от AIv

Для магистерской работы сколько-то лет назад писал алгоритм, который обратную задачу сейсм. томографии решал для некоторого конкретного случая (грунтовые массивы, двумерный случай (продольное или поперечное сечение), небольшие размеры (десятки метров), звуковые волны). Разбивал на прямоугольные ячейки с постоянной скоростью звука внутри, ну и для трассировки лучей использовал слегка допиленный shortest path method (на таких ячейках «кратчайший путь» - это ломаная, одна ячейка - один отрезок; делаем граф, ребрам которого сопоставляем все возможные отрезки в каждой из ячеек, и вперед, искать кратчайший путь в графе).

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

gizzka ★★
() автор топика
Ответ на: комментарий от gizzka

А, так мы почти коллеги - мы в частности решаем прямые задачи сейсмики (полноволновое 3D моделирование синтетических сейсмограмм). Но сейчас же вроде появились алгоритмы для решения обратных волновых задач?

AIv ★★★★★
()
Ответ на: комментарий от dikiy

Это же нелинейное уравнение получается.

Вообще для |\grad u|^2 = \const решение как ни странно \sqrt{x^2+y^2} (я его просто угадал, поскольку известно что в этом случае волновой фронт есть окружность;-)), так что даже в случае билинейной интерполяции может все оказаться непросто...

AIv ★★★★★
()
Ответ на: комментарий от AIv

У меня как-то так получается, что я больше в свободное от основной работы время занимаюсь, плюс заинтересованные практики есть (которые на практике считают и могут отзывы давать), а товарищей ученых, кто примерно в этих областях бы специализировался, под боком нет. Поэтому, к сожалению, какая сейчас общая картина с научными достижениями - представляю не очень. Вроде про *SPM и FMM методы (хитрые сетки, 3д, учет не только первых вступлений, «sensitivity» и т.д.) народ до сих пор публикуется, то есть их используют, а что там для обратных задач - совсем не в курсе.

Поэтому за ссылки на статьи (по тем же алгоритмам для обратных задач, например) был бы очень благодарен, если не сложно, конечно. :)

gizzka ★★
() автор топика

волновой алгоритм

// топик не читай- сразу отвечай

pacify ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.