Сходил вот на городскую олимпиаду по кодингу. Кому интересно, могу выслать на мыло задания. И там было одно задание связанное с алгоритмами нахождения кратчайшего пути, причем не в лабиринте, а в прямоугольной системе координат, где препятствиями служат отрезки, произвольно расположенные в этой системе. Я эту задачу решил-таки, но наверное не очень рационально. Где можно почитать на тему алгоритмов поиска пути в таких условиях?
Последние комментарии
-
OlegL, 17 декабря в 15:00 →
Перекличка
21
-
REDkiy, 8 июня в 9:09 →
Как «замокать» файл для юниттеста в Python?
2
-
fhunter, 29 ноября 2022 года в 2:09 →
Проблема с NO_PUBKEY: как получить GPG-ключ и добавить его в базу apt?
6
-
Иванн, 9 апреля 2022 года в 8:31 →
Ассоциация РАСПО провела первое учредительное собрание
1
-
Kiri11.ADV1, 7 марта 2021 года в 12:01 →
Логи catalina.out в TomCat 9 в формате JSON
1
ecobeing.ru
Экология и вегетарианство на благо всем живым существам Планеты.
слушай, а решение не приведешь. Просто интересно….:) И еще, точную формулировку задания…
Где почитать не знаю, но достоверно известно, что один из лучших алгоритмов следующий:
1. Строим отрезок (X0) из начала в конец.
2. Если пересечений с препятствиями нет, то КОНЕЦ.
3. Выбираем любое препятствие и двигаемся по нему от точки пересечения с X(n) к обоим краям одновременно.
4. Как только дошли до какого-то края получаем 2 отрезка: X(n+1) и X(n+2). Выполняем для них тоже самое.
хорошее решение…
Я тут ещё оптимизацию придумал. Так как координаты начала/конца препятствия нам известны (пусть это будут точки A и B), то шаг 3 можно упростить. Полагая координаты начала X(n) A' и конца B’, смотрим что меньше: A’A + AB' или A’B + BB’, то и выбираем.
В принципе такой алгоритм можно обобщить на случай произвольных геометрических фирур в качестве препятствий, т.е. где препятствия не многоугольники, а скажем, окружности и эллипсы, но придётся сделать небольшой pre-calc…
Ищем путь вообще, или кратчайший?
Если вообще, то тогда в принипе пофик. А вот если кратчайший, то тут не факт, что такое разбиение в сумме будет кратчайшим.
Короче задача:
Я ее решал так: беру и прокладываю путь от кактуса по ближайшим точкам. При этом я рассмотрел также случаи когда коза огорожена забором или кактус огорожен забором. Затем я меряю длину этого пути и сравниваю ее с длиной поводка.
Я сначала тоже так пытался. Беда в том что я так и не смог там на олимпиаде вывести формулу, по которой можно было бы зная координаты концов двух отрезков найти координтау пересечения если вообще таковая имеется. Подскажите кто-нить, как это сделать?
Ну это запросто. Пусть два отрезка будут AB и CD, координаты точек такие:
A=(a1,a2), B=(b1,b2), C=(c1,c2) и D=(d1,d2).
Теперь, точки (x,y) отрезка AB все удовлетворяют
параметрической системе
x = t a1 + (1 — t) b1
y = t a2 + (1 — t) b2
с t между нулем и единицей. Соответственно, точки отрезка CD описываются системой
x = s c1 + (1 — s) d1
y = s c2 + (1 — s) d2
0 <= s <= 1
Мы хотим точку принадлежащую обоим отрезкам, стало быть, решаем систему:
t a1 + (1 — t) b1 = s c1 + (1 — s) d1
t a2 + (1 — t) b2 = s c2 + (1 — s) d2
находим t и s. (Можно переписать в виде
t(a1-b1)-s(c1-d1)=d1-b1
t(a2-b2)-s(c2-d2)=d2-b2
)
Если у системы нет решения, т.е.
(a1-b1)(c2-d2) = (c1-d1)(a2-b2),
то отрезки параллельны. Если есть решени в виде (t0, s0), то смотрим, если
0 <= t0 <= 1 и 0 <= s0 <= 1
то точка принадлежит внутренности обоих отрезков если одно из условий нарушено, пересекаются только прямые, на которых отрезки лежат. Саму точку находим, подставив t0 (или s0) в самую первую (самую вторую систему). И все дела.
Систему такого типа легко решить алгоритмически, но уж больно писать много влом…
Good Luck,
UT
Спасибо. Буду знать. А то я пробовал вывести что-нить, но так и не получилось :( За 3,5 часа некогда еще формулы выводить :(
Только вот че за переменная s в твоих формулах?
Не понял вопроса. s — параметр для второй прямой.
Кстати, интересный вопрос, если они параллельны, то как они параллельны. Возможны 3 случая: параллельны и не совпадают, совпадают, но отрезки не пересекаются, совпдают, и отрезки имеют общую часть. Как эти случаи различать?
Кто-нибудь хочет попробовать?
Ладно, мне на лекцию пора. Час меня не будет.
Good Luck,
UT
Будет.
Доказываю:
1) будем считать, что для любых двух точек A и B участок прямой a, такой что A и B принадлежат a, лежащий между A и B есть крачайший путь из A в B.
2) пусть при прокладке пути мы встречаем препятсятвие. При этом мы отклоняемся на минимально необходимое расстояние (см. пункт 3 алгоритма).
3) (1, 2) справедливо для двух полученных в результате обхода препятствия отрезков…
Не будет. Для этого надо предоставить хотя бы одно опровержение.
Например:
На пути у козы петляющий лабиринт из заборов, до входа близко, и тогда по твоему алгоритму надо идти в лабиринт, вместо того чтобы обойти его сбоку.
Еще пример
* — кактус
———————————--
——————————
—————--
* — коза
По твоему алгоритму коза будет обходить все время по левой стороне, хотя очевидно, что справа короче!
Опроверг?
Для поиска пути нельзя пользоваться таким сканирующим алгоритмом, т.к. каждый шаг пути сначала неочевиден. Нужно использовать что-то наподобие волнового алгоритма или алгоритм Дейкстры (А*)
В инете про них много.
Для данной задачи (опуская для краткости частные случаи, когда заборы пересекаются) кратчайший путь можно найти по следующему алгоритму:
Каждая точка хранит кратчайший путь S до нее от начальной точки, сначала эти значения неопределены — S=null (#define null -1) , для начальной точки — S=0
1) Текущая_точка = начальная,
2) из текущей_точки находим расстояния R до всех достижимых по прямой концов заборов и до кактуса. Для этих точек
if (S==null) || (S<Текущая_точка.S+R)
S=Текущая_точка.S+R
3) Текущей точкой становится точка с наименьшим S, но большим чем с старой текущей точки.
Если текущей точкой стал кактус, то конец
Иначе, повторяем шаг 2
Конец) Расстояние до кактуса найдено, если нужны точки по которым проложен путь, то надо от кактуса найти точку, в которой S==кактус.S-R, где R — расстояний от кактуса до этой точки. Дальше аналогично
Во 2-ом примере форматирование не сохранилось — там параллельные заборы левый край, которого ближе правого. Далее такой же забор, только левее менее чем наполовину, то есть до левого края забора опять ближе — так и пойдет коза в обход
А теперь как надо (через месяц после олимпиады были оглашены правильне решения). Данная задача решалась с помощью графов легко и просто. Вот так. Так что я их сейчас изучаю.
Алгоритм тот же самый, если мы сначала найдем все расстояния от каждой точки до каждой (если они имеются конечно), то мы получим веса ребер графа между соответствующими точками — вершинами графа.
Построение графа для данной задачи — только предвычисления. Но в итоге не все эти вычисления окажутся нужными.