Прочее образование
интересная задачка. исследовательская.
Здравствуйте!Пару дней назад натолкнулся на одну интересную задачку:Существуют точки А и В. Между ними находятся несколько многоугольных преград (непересекающиеся друг с другом многоугольники) . Все параметры заданы. Определить наикратчайший путь от А до В.Эта задачка собственно решается достаточно просто: строятся "зоны видимости" всех узловых точек (А, В, и все вершины многоугольников), доказываются ряд лемм о минимуме далее проводятся прямые, составляются "зоны видимости" точек, рисуется граф , и по известному алгоритму находят наикратчайший путь.Но в связи с этой задачей возникает следующая, по моему мнению интересная задача.Формулировка та же, но преграды имеют коэффициент проницаемости . То есть допустим, скорость в нормальной среде v0; в первом многоугольнике v0/n1; во втором v2/n2 и т.д. Какой наикратчайший путь? Понятно, что это первая задачка при всех n=1.Самому думать над решением пока времени нет, все же надо готовиться к конференции по немного другой теме и к поступлению, но все же интересно))Во-первых, решена ли данная задача? Если нет, то она открывает собой очень даже неплохую математическую модель.(Для n0=n1=...=ni=1 задача решена вроде не очень давно) Вообще, появилось предположение, что задача сводится к ТРЕХМЕРНОМУ графу (длины ребер вглубь - коэффициент проницаемости)Вообщем, жду Ваших комментариев =) Прошу отвечать любые мысли по делу, можно далее обсудить в комментахСпасибо!С уважением, Алексей.
В такой формулировке как Вы задали в общем виде задача является слишком сложной для решения.
Приведенная Вами аналогия что введение дополнительного параметра, такого как коэффициент проницаемости превращает задачу в трехмерную не совсем верна.
Резкое усложнение этой задачи по сравнению с начальной связано с тем, что дискретная задача заменяется на непрерывную. Таким образом задача из теории графов переходит в теорию поиска экстремума функции большого числа переменных.
Вот один из простейших случаев:
Между точками A и B расположен один прямоугольник с n=2.
Например: A(0,0), B(5,5). Вершины прямоугольника: (0,2), (5,2), (5,3), (0,3).
Пусть путь является ломаной трех отрезков и проходит последовательно через точки A, (x,2), (y,3), B, где 0 < x < 5, 0 < y < 5.
Время прохождения по пути равно
корень (x^2+4)/v0 + 2*корень ((y-x)^2+1)/v0 + корень (y^2+4)/v0
Даже в этом простом случае задача сводится к задаче поиска минимума функции двух переменных.
Дискретность теории графов также никуда не ушла из задачи, так как помимо указанного мной варианта пути есть варианты пути, обходящего прямоугольник стороной.
Несмотря на сложность задачи, есть некоторые общие закономерности:
I (это просто) Если все n равны n0, то быстрейший путь -- отрезок AB
II В случае одного многоугольника из всех путей, проходящих через стороны (но не проходящих через вершины) этого многоугольника, быстрейшим будет путь, который удовлетворяет закону преломления на каждой из сторон, через которые он проходит.
Приведенная Вами аналогия что введение дополнительного параметра, такого как коэффициент проницаемости превращает задачу в трехмерную не совсем верна.
Резкое усложнение этой задачи по сравнению с начальной связано с тем, что дискретная задача заменяется на непрерывную. Таким образом задача из теории графов переходит в теорию поиска экстремума функции большого числа переменных.
Вот один из простейших случаев:
Между точками A и B расположен один прямоугольник с n=2.
Например: A(0,0), B(5,5). Вершины прямоугольника: (0,2), (5,2), (5,3), (0,3).
Пусть путь является ломаной трех отрезков и проходит последовательно через точки A, (x,2), (y,3), B, где 0 < x < 5, 0 < y < 5.
Время прохождения по пути равно
корень (x^2+4)/v0 + 2*корень ((y-x)^2+1)/v0 + корень (y^2+4)/v0
Даже в этом простом случае задача сводится к задаче поиска минимума функции двух переменных.
Дискретность теории графов также никуда не ушла из задачи, так как помимо указанного мной варианта пути есть варианты пути, обходящего прямоугольник стороной.
Несмотря на сложность задачи, есть некоторые общие закономерности:
I (это просто) Если все n равны n0, то быстрейший путь -- отрезок AB
II В случае одного многоугольника из всех путей, проходящих через стороны (но не проходящих через вершины) этого многоугольника, быстрейшим будет путь, который удовлетворяет закону преломления на каждой из сторон, через которые он проходит.
Упс! В 5 утра ...и такое? Пошел с балкона выгляну.... ОПЯТЬ ГИТЛЕР НА НАС ВОЙНОЙ?
полный песец! это была мысль не по делу!))
Это Вы сейчас с кем разговаривали?
Но идея мне понравилась!
Но идея мне понравилась!
Задача сводится к трехмерному графу, точно!!!
Математическая модель конечно интересная.
Насколько я понимаю, v0/n1……и т. д. — это определённые числа.
Тогда, эта модель напоминает взвешенный граф.
Граф называется взвешенным, если определена любая функция на множестве ребер . Сама функция называется в этой ситуации весовой, а ее значение на том или ином ребре называется весом этого ребра. Любой подграф данного графа и любой путь в данном графе имеют свой вес: это - сумма весов ребер, входящих в этот подграф или в этот путь.
Для поиска остова минимального веса во взвешенном графе существует алгоритм Краскала
Для поиска кратчайших путей в графе существует классический алгоритм Форда.
Если я неправильно понял Ваше условие задачи — сообщите.
Насколько я понимаю, v0/n1……и т. д. — это определённые числа.
Тогда, эта модель напоминает взвешенный граф.
Граф называется взвешенным, если определена любая функция на множестве ребер . Сама функция называется в этой ситуации весовой, а ее значение на том или ином ребре называется весом этого ребра. Любой подграф данного графа и любой путь в данном графе имеют свой вес: это - сумма весов ребер, входящих в этот подграф или в этот путь.
Для поиска остова минимального веса во взвешенном графе существует алгоритм Краскала
Для поиска кратчайших путей в графе существует классический алгоритм Форда.
Если я неправильно понял Ваше условие задачи — сообщите.
Samat Mursaliev
Спасибо за ответ!
Но, если я не ошибаюсь, тут на ребре вес будет непостоянным.
Но, если я не ошибаюсь, тут на ребре вес будет непостоянным.
афигеть!!!! не блондинка, но туго доходит или просто не вдумалась
я обалдела!!!! Какой вы умный!!!! Респект
Умри все живое!!!!
класс
Похожие вопросы
- Интересная задачка)) кто первый догадается тому +10 баллов))
- Есть вопрос! Не могу определиться с темой исследовательской работы по литературе.
- Подобрать название исследовательской работы
- помогите разгадать задачку...
- Задачка по теории горения взрывчатых веществ (если я правильно поняла). Надо объяснить малому :) Заранее спасибо большое
- Как вычислить вероятность. Никак не могу понять. Помогите на примере такой задачки:
- Как вы думаете, актуальна ли тема "Подростковый сколиоз" для исследовательской работы? Если можно обоснуйте свой ответ
- Подскажите темы для научно-исследовательских работ, связанные с биологией, медициной))
- придумайте тему исследовательской работы по биологии/химии.
- помогите найти исследовательскую работу по дисциплине обж, тема здоровое поколение.
Если сейчас рассмотреть алгоритм "в лоб", то:
1) Вначале необходимо определить, проходит ли кратчайший путь через сторону или вершину каждого многоугольника. Если через сторону, то надо использовать физические законы преломления для среды. Очевидно, что в случае выпуклых многоугольных препятствий наименьшие пути проходят через вершину или через сторону с указанным углом преломления
Если верен пункт 1, то необходимо рассмотреть минимум прохождения, и так для каждой преграды. Но для большого их количества алгоритм будет иметь очень высокую сложность. Возможно можно найти какие-то общие соображения и поисках этих самых минимумов?
Большое спасибо Вам за ответ!