nixp.ru v3.0

29 мая 2017,
понедельник,
01:23:04 MSK

DevOps с компанией «Флант»
Longobard написал 5 февраля 2004 года в 07:42 (547 просмотров) Ведет себя как мужчина; открыл 291 тему в форуме, оставил 2499 комментариев на сайте.

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

decvar

слушай, а решение не приведешь. Просто интересно….:) И еще, точную формулировку задания…

myst

Где почитать не знаю, но достоверно известно, что один из лучших алгоритмов следующий:

1. Строим отрезок (X0) из начала в конец.

2. Если пересечений с препятствиями нет, то КОНЕЦ.

3. Выбираем любое препятствие и двигаемся по нему от точки пересечения с X(n) к обоим краям одновременно.

4. Как только дошли до какого-то края получаем 2 отрезка: X(n+1) и X(n+2). Выполняем для них тоже самое.

decvar

хорошее решение…

myst

Я тут ещё оптимизацию придумал. Так как координаты начала/конца препятствия нам известны (пусть это будут точки A и B), то шаг 3 можно упростить. Полагая координаты начала X(n) A' и конца B’, смотрим что меньше: A’A + AB' или A’B + BB’, то и выбираем.

В принципе такой алгоритм можно обобщить на случай произвольных геометрических фирур в качестве препятствий, т.е. где препятствия не многоугольники, а скажем, окружности и эллипсы, но придётся сделать небольшой pre-calc…

Genie

Ищем путь вообще, или кратчайший?

Если вообще, то тогда в принипе пофик. А вот если кратчайший, то тут не факт, что такое разбиение в сумме будет кратчайшим.

Longobard

Короче задача:

У фермера есть когза, привязанная к колышку в начале координат на веревке длиной L. На Ферме есть N заборов, параллельных осям координат. Про каждый забор известный координты его концов. В точке с координатами (X,Y) растет кактус фермера. Он хочет узнать, сможет ли коза добраться до кактуса.

Примечания от меня: заборы и кактус могут иметь вещественные координаты. Коза может ходить по любым координатам (в том числе им вещественным). Вопросы на тему для на хуа козе кактус не обсуждаются. Габариты козы стремятся к нулю и поэтому она можнт находится в одной точке с краем забота. Перепрыгнуть через забор коза не может.

Я ее решал так: беру и прокладываю путь от кактуса по ближайшим точкам. При этом я рассмотрел также случаи когда коза огорожена забором или кактус огорожен забором. Затем я меряю длину этого пути и сравниваю ее с длиной поводка.

Longobard
myst
Где почитать не знаю, но достоверно известно, что один из лучших алгоритмов следующий:

1. Строим отрезок (X0) из начала в конец.

2. Если пересечений с препятствиями нет, то КОНЕЦ.

3. Выбираем любое препятствие и двигаемся по нему от точки пересечения с X(n) к обоим краям одновременно.

4. Как только дошли до какого-то края получаем 2 отрезка: X(n+1) и X(n+2). Выполняем для них тоже самое.

Я сначала тоже так пытался. Беда в том что я так и не смог там на олимпиаде вывести формулу, по которой можно было бы зная координаты концов двух отрезков найти координтау пересечения если вообще таковая имеется. Подскажите кто-нить, как это сделать?

anonymous
LONGOBARD
Беда в том что я так и не смог там на олимпиаде вывести формулу, по которой можно было бы зная координаты концов двух отрезков найти координтау пересечения если вообще таковая имеется. Подскажите кто-нить, как это сделать?

Ну это запросто. Пусть два отрезка будут 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

Longobard

Спасибо. Буду знать. А то я пробовал вывести что-нить, но так и не получилось :( За 3,5 часа некогда еще формулы выводить :(

Longobard

Только вот че за переменная s в твоих формулах?

anonymous

Не понял вопроса. s — параметр для второй прямой.

Кстати, интересный вопрос, если они параллельны, то как они параллельны. Возможны 3 случая: параллельны и не совпадают, совпадают, но отрезки не пересекаются, совпдают, и отрезки имеют общую часть. Как эти случаи различать?

Кто-нибудь хочет попробовать?

Ладно, мне на лекцию пора. Час меня не будет.

Good Luck,

UT

myst
Genie
Ищем путь вообще, или кратчайший?

Если вообще, то тогда в принипе пофик. А вот если кратчайший, то тут не факт, что такое разбиение в сумме будет кратчайшим.

Будет.

Доказываю:

1) будем считать, что для любых двух точек A и B участок прямой a, такой что A и B принадлежат a, лежащий между A и B есть крачайший путь из A в B.

2) пусть при прокладке пути мы встречаем препятсятвие. При этом мы отклоняемся на минимально необходимое расстояние (см. пункт 3 алгоритма).

3) (1, 2) справедливо для двух полученных в результате обхода препятствия отрезков…

anonymous
myst
Будет.

Доказываю:


Не будет. Для этого надо предоставить хотя бы одно опровержение.

Например:

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

Еще пример

* — кактус

———————————--

——————————

—————--

* — коза

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

Опроверг?

Для поиска пути нельзя пользоваться таким сканирующим алгоритмом, т.к. каждый шаг пути сначала неочевиден. Нужно использовать что-то наподобие волнового алгоритма или алгоритм Дейкстры (А*)

В инете про них много.

Для данной задачи (опуская для краткости частные случаи, когда заборы пересекаются) кратчайший путь можно найти по следующему алгоритму:

Каждая точка хранит кратчайший путь 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 — расстояний от кактуса до этой точки. Дальше аналогично

anonymous

Во 2-ом примере форматирование не сохранилось — там параллельные заборы левый край, которого ближе правого. Далее такой же забор, только левее менее чем наполовину, то есть до левого края забора опять ближе — так и пойдет коза в обход

Longobard

А теперь как надо (через месяц после олимпиады были оглашены правильне решения). Данная задача решалась с помощью графов легко и просто. Вот так. Так что я их сейчас изучаю.

anonymous

Алгоритм тот же самый, если мы сначала найдем все расстояния от каждой точки до каждой (если они имеются конечно), то мы получим веса ребер графа между соответствующими точками — вершинами графа.

Построение графа для данной задачи — только предвычисления. Но в итоге не все эти вычисления окажутся нужными.