Кратчайший путь между прообразом до любой точки На графике

Я не смог понять эту проблему за долгое время. Предположим, что мы имеем двумерную плоскость с предопределенным корнем, которая всегда находится в начале (0,0). Эта 2D-плоскость не будет иметь ограничений на то, насколько она может быть большой.Кратчайший путь между прообразом до любой точки На графике

Давайте также скажем, что пользователь может ввести любое количество конечных чисел на этом графике (и каждая точка может лежать на этой плоскости в любом месте). Эти точки определяются как S0, S1, ... Sn, и пользователь также дает соответствующее местоположение координат X, Y этих точек.

Я хочу найти кратчайшую длину пути от корневой точки до каждой точки на графике.

Что я имею в виду под этим ?: Ну, допустим, что кратчайший путь определяется как 6. Это означает, что длина пути от корневой точки до точки S0 равна 6, длина пути от корень S1 равно 6, длина пути от корня до Sn равно 6.

, что я сделал, чтобы попытаться решить эту проблему:

Смотрите мою диаграмму: ОТКАЗА: цель моей диаграммы является покажите мне мой мыслительный процесс. Он НЕ является представителем того, как я хочу подходить к этой проблеме. enter image description here

В этом примере, который я создал, предположим, что все точки равномерно разнесены друг от друга. То, что я пытался сделать, это продолжать находить средние точки между очками. Например, средняя точка между S0 и S1 равна A. Средняя точка между S2 и S3 равна B. И средняя точка между A и B - C. Корневые головки сверху до C и могут перемещаться на равное расстояние до любой точки на графике. В этом примере кратчайшая длина пути от корня до ЛЮБОЙ точки на графике равна 4. Другими словами, мне нужен самый короткий путь от root до S0, который эквивалентен кратчайшему пути от root до S1, что эквивалентно кратчайшему пути от root до S2, что эквивалентно кратчайшему пути получения от корня до S3

Проблема в том, что этот метод не будет работать ВСЕ ВРЕМЯ, особенно если у вас есть нечетное число ненулевых точек, которые случайно разбросаны по плоскости. Я не могу найти алгоритм. У кого-нибудь есть указатели/советы для меня?

источник

2015-02-01 Joffrey Baratheon

Я не совсем понял вопрос. Пользователь определяет точки, S0, S1 и т. Д., Но я не понимаю, откуда берутся строки. Самый короткий путь между любыми двумя точками - это прямая линия между ними. Что мне не хватает? A, B и C кажутся совершенно произвольными. –

@ErikPhilips Я не совсем понимаю ваше замешательство. Линии представляют путь, который я рисую, чтобы лучше представить длину пути. S0, S1, S2 и S3 - точки на графике, а A, B и C - средние точки. –

Тогда зачем их создавать, в вашем примере кратчайшее расстояние между S0 и S2 является прямой линией между ними. Зачем беспокоиться о средних очках? (кратчайшее расстояние без A, B и C от корня до S0 и S3 составляет 2 мм при допущении на 90 градусов). –

-1

Here is the formula чтобы определить расстояние между двумя точками. Просто вычислите расстояние от корня для всех заданных пользователем точек (s0, s1 ... sN) и получите минимальное значение из набора результатов.

источник

2015-02-01 09:38:32

Как это ответить на вопрос? Он не ищет минимального значения. –

прочитайте выше комментарии – hyades

В этом примере кратчайшая длина пути от корня до ЛЮБОЙ точки на графике равна 4. Другими словами, мне нужен самый короткий путь от root до S0, который эквивалентен кратчайшему пути от root до S1, что эквивалентно кратчайшему пути от root до S2, что эквивалентно кратчайшему пути получения от корня до S3.

Они не должны быть 90 градусов.

Так что вы действительно говорят:

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

Найдите самую дальнюю точку от корня и вычислите расстояние (X). Для всех точек, которые находятся на одном и том же расстоянии от корня как X, линия является прямой линией. Во всех остальных точках создается произвольная кривая, расстояние которой равно X.

Пример (линии не идеально подходят для масштабированного расстояния, просто пример).

equidistant lines

источник

2015-02-01 09:55:43

Эрик, это на самом деле довольно умный. Спасибо за комментарий. Не могу поверить, что я об этом не думал. Это звучит довольно очевидно, теперь, когда я думаю об этом. Что, если линии должны были быть прямыми, хотя? Как бы изменился ответ? –

Кроме того, что я имел в виду под термином «им не нужно быть под углом 90 градусов» Я имел в виду, что они все равно должны быть прямыми, но они могут быть любого склона. Ваш метод решает проблему, но не так, как я изложил. Извините за двусмысленность. –

Чтобы уточнить, строки должны быть прямыми. Они могут образовывать любой угол. Значит, они не должны быть 90 градусов, но они могут быть. –

Я склонен согласиться с Эриком Philips, что соединение от начала координат до самой дальней точки должна быть прямой. Если несколько точек разделяют честь более отдаленной, то все они получают прямые линии. Для любых оставшихся точек речь идет только о том, где можно подключиться к существующим прямым линиям.

Примените эту технику к вашей проблеме образца и расстояние от начала координат до каждой точки √10 ≈ 3,16

enter image description here

источник

2015-02-01 11:24:02 user3386109

Кратчайший путь между прообразом до любой точки На графике

ответ

Смежные вопросы