Прочее образование

интересная задачка. исследовательская.

Здравствуйте!Пару дней назад натолкнулся на одну интересную задачку:Существуют точки А и В. Между ними находятся несколько многоугольных преград (непересекающиеся друг с другом многоугольники) . Все параметры заданы. Определить наикратчайший путь от А до В.Эта задачка собственно решается достаточно просто: строятся "зоны видимости" всех узловых точек (А, В, и все вершины многоугольников), доказываются ряд лемм о минимуме далее проводятся прямые, составляются "зоны видимости" точек, рисуется граф , и по известному алгоритму находят наикратчайший путь.Но в связи с этой задачей возникает следующая, по моему мнению интересная задача.Формулировка та же, но преграды имеют коэффициент проницаемости . То есть допустим, скорость в нормальной среде v0; в первом многоугольнике v0/n1; во втором v2/n2 и т.д. Какой наикратчайший путь? Понятно, что это первая задачка при всех n=1.Самому думать над решением пока времени нет, все же надо готовиться к конференции по немного другой теме и к поступлению, но все же интересно))Во-первых, решена ли данная задача? Если нет, то она открывает собой очень даже неплохую математическую модель.(Для n0=n1=...=ni=1 задача решена вроде не очень давно) Вообще, появилось предположение, что задача сводится к ТРЕХМЕРНОМУ графу (длины ребер вглубь - коэффициент проницаемости)Вообщем, жду Ваших комментариев =) Прошу отвечать любые мысли по делу, можно далее обсудить в комментахСпасибо!С уважением, Алексей.
Samat Mursaliev
Samat Mursaliev
4 627
В такой формулировке как Вы задали в общем виде задача является слишком сложной для решения.
Приведенная Вами аналогия что введение дополнительного параметра, такого как коэффициент проницаемости превращает задачу в трехмерную не совсем верна.
Резкое усложнение этой задачи по сравнению с начальной связано с тем, что дискретная задача заменяется на непрерывную. Таким образом задача из теории графов переходит в теорию поиска экстремума функции большого числа переменных.
Вот один из простейших случаев:
Между точками 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 В случае одного многоугольника из всех путей, проходящих через стороны (но не проходящих через вершины) этого многоугольника, быстрейшим будет путь, который удовлетворяет закону преломления на каждой из сторон, через которые он проходит.
Александр Левагин
Александр Левагин
22 753
Лучший ответ
Samat Mursaliev Спасибо!
Если сейчас рассмотреть алгоритм "в лоб", то:
1) Вначале необходимо определить, проходит ли кратчайший путь через сторону или вершину каждого многоугольника. Если через сторону, то надо использовать физические законы преломления для среды. Очевидно, что в случае выпуклых многоугольных препятствий наименьшие пути проходят через вершину или через сторону с указанным углом преломления
Если верен пункт 1, то необходимо рассмотреть минимум прохождения, и так для каждой преграды. Но для большого их количества алгоритм будет иметь очень высокую сложность. Возможно можно найти какие-то общие соображения и поисках этих самых минимумов?
Большое спасибо Вам за ответ!
Samat Mursaliev хотя... если преграда бесконечной длины(прямоугольная полоса), с маленькой скоростью прохождения, всё равно выгодней идти по отрезку, соединяющую прямую А и В!
Упс! В 5 утра ...и такое? Пошел с балкона выгляну.... ОПЯТЬ ГИТЛЕР НА НАС ВОЙНОЙ?
_____ ______
_____ ______
61 171
полный песец! это была мысль не по делу!))
СК
С К
48 632
Это Вы сейчас с кем разговаривали?
Но идея мне понравилась!
Хася !
Хася !
23 627
Задача сводится к трехмерному графу, точно!!!
Математическая модель конечно интересная.
Насколько я понимаю, v0/n1……и т. д. — это определённые числа.
Тогда, эта модель напоминает взвешенный граф.

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

Для поиска остова минимального веса во взвешенном графе существует алгоритм Краскала
Для поиска кратчайших путей в графе существует классический алгоритм Форда.

Если я неправильно понял Ваше условие задачи — сообщите.
Samat Mursaliev Спасибо за ответ!
Но, если я не ошибаюсь, тут на ребре вес будет непостоянным.
афигеть!!!! не блондинка, но туго доходит или просто не вдумалась
Ayhan Bengi
Ayhan Bengi
4 598
я обалдела!!!! Какой вы умный!!!! Респект
Умри все живое!!!!
класс