Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 2 |
[ Сообщений: 16 ] | На страницу 1, 2 След. |
|
Автор | Сообщение | ||
---|---|---|---|
Emelya |
|
||
|
|||
Вернуться к началу | |||
Andy |
|
||
Я думаю, что коротких вариантов будет много. Например, рассмотрим для простоты точки [math](0,~0)[/math] и [math](2,~3).[/math] Тогда короткие варианты имеют длину [math](2-0)+(3-0)=5.[/math] Их несколько, в чём можно убедиться, сделав рисунок. Например, можно отрезок, соединяющий заданные точки, представить как гипотенузу прямоугольного треугольника, а звенья ломаной - как его катеты, лежащие на сетке.
|
|||
Вернуться к началу | |||
swan |
|
||
Вам нужно кратчайший путь в графе найти?
Берете одну из точек. Всем ее соседям приписываете расстояние до выбранной точки. Затем находите кратчайшее расстояние для соседей "соседей". Записываете это расстояние и узел, его реализующий. И т.д., пока не доберетесь до второй точки. |
|||
Вернуться к началу | |||
Emelya |
|
|
swan писал(а): Вам нужно кратчайший путь в графе найти? Берете одну из точек. Всем ее соседям приписываете расстояние до выбранной точки. Затем находите кратчайшее расстояние для соседей "соседей". Записываете это расстояние и узел, его реализующий. И т.д., пока не доберетесь до второй точки. К сожалению, ребра графа разной длины, а точки лежат не всегда на вершинах. Посмотрите файл, пожалуйста. https://yadi.sk/i/VFAT45yWogq4d |
||
Вернуться к началу | ||
Emelya |
|
|
Andy писал(а): Я думаю, что коротких вариантов будет много. Например, рассмотрим для простоты точки [math](0,~0)[/math] и [math](2,~3).[/math] Тогда короткие варианты имеют длину [math](2-0)+(3-0)=5.[/math] Их несколько, в чём можно убедиться, сделав рисунок. Например, можно отрезок, соединяющий заданные точки, представить как гипотенузу прямоугольного треугольника, а звенья ломаной - как его катеты, лежащие на сетке. Спасибо. Очень интересное решение и если бы сетка имела одинаковые ребра, было бы годное. Но тут особенность, что разные длины ребер и точки не всегда могут совпадать с вершинами графа. Посмотрите, может возникнут еще мысли: https://yadi.sk/i/VFAT45yWogq4d |
||
Вернуться к началу | ||
Avgust |
|
||
Тут, мне кажется, логика простая: из двух конкурирующих путей более короткий красный.
|
|||
Вернуться к началу | |||
Emelya |
|
|
Avgust писал(а): Тут, мне кажется, логика простая: из двух конкурирующих путей более короткий красный. Я с вами согласен. Но самая сложность алгоритмом описать математику построения такого пути. |
||
Вернуться к началу | ||
Emelya |
|
|
Andy писал(а): Я думаю, что коротких вариантов будет много. Например, рассмотрим для простоты точки [math](0,~0)[/math] и [math](2,~3).[/math] Тогда короткие варианты имеют длину [math](2-0)+(3-0)=5.[/math] Их несколько, в чём можно убедиться, сделав рисунок. Например, можно отрезок, соединяющий заданные точки, представить как гипотенузу прямоугольного треугольника, а звенья ломаной - как его катеты, лежащие на сетке. Вот кстати я попытался историю с катетами применить на свой пример и вроде что-то получилось, но у такого решения есть ряд недостатков: не всегда путь оптимален. https://yadi.sk/i/h7gnO3spogvC6 Логика такая: 1 проводим линию между точками. 2 поиск пересечений с ребрами графа 3 у точки пересечения Ишим ближайшую, через которую можно построить гипотенузу так, чтобы ребра были катетами. 4 по катетам и прямым движемся из одной точки в другую. Вроде маршрут строиться. Но не всегда оптимальный. |
||
Вернуться к началу | ||
Andy |
|
||
Какими числами являются координаты заданных на сетке точек?
|
|||
Вернуться к началу | |||
За это сообщение пользователю Andy "Спасибо" сказали: Emelya |
|||
swan |
|
||
Emelya писал(а): К сожалению, ребра графа разной длины, а точки лежат не всегда на вершинах Походу вы ничего не поняли. Я нигде не предполагал одинаковую длину ребер. Перечитайте еще раз. |
|||
Вернуться к началу | |||
На страницу 1, 2 След. | [ Сообщений: 16 ] |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 32 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |