Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Оптимальное соединения двух точек по заданным
СообщениеДобавлено: 11 фев 2016, 00:28 
Не в сети
Начинающий
Зарегистрирован:
11 фев 2016, 00:16
Сообщений: 8
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Есть сетка образованная отрезками в декартовой системе координат. На сетке существуют две точки. Необходимо соединить эти две точки так, чтобы соединяющая ломаная линия проходила по сетке, и при этом это был самый оптимальный (=короткий) вариант. Прошу подсказать в какую сторону копать. Или какие есть мысли по решению данной задачи.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимальное соединения двух точек по заданным
СообщениеДобавлено: 11 фев 2016, 06:56 
Не в сети
Любитель математики
Аватара пользователя
Зарегистрирован:
16 июл 2011, 08:33
Сообщений: 22268
Откуда: Беларусь, Минск
Cпасибо сказано: 2096
Спасибо получено:
4958 раз в 4631 сообщениях
Очков репутации: 845

Добавить очки репутацииУменьшить очки репутации
Я думаю, что коротких вариантов будет много. Например, рассмотрим для простоты точки [math](0,~0)[/math] и [math](2,~3).[/math] Тогда короткие варианты имеют длину [math](2-0)+(3-0)=5.[/math] Их несколько, в чём можно убедиться, сделав рисунок. Например, можно отрезок, соединяющий заданные точки, представить как гипотенузу прямоугольного треугольника, а звенья ломаной - как его катеты, лежащие на сетке.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимальное соединения двух точек по заданным
СообщениеДобавлено: 11 фев 2016, 09:34 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Вам нужно кратчайший путь в графе найти?
Берете одну из точек. Всем ее соседям приписываете расстояние до выбранной точки. Затем находите кратчайшее расстояние для соседей "соседей". Записываете это расстояние и узел, его реализующий. И т.д., пока не доберетесь до второй точки.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимальное соединения двух точек по заданным
СообщениеДобавлено: 11 фев 2016, 22:31 
Не в сети
Начинающий
Зарегистрирован:
11 фев 2016, 00:16
Сообщений: 8
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Вам нужно кратчайший путь в графе найти?
Берете одну из точек. Всем ее соседям приписываете расстояние до выбранной точки. Затем находите кратчайшее расстояние для соседей "соседей". Записываете это расстояние и узел, его реализующий. И т.д., пока не доберетесь до второй точки.

К сожалению, ребра графа разной длины, а точки лежат не всегда на вершинах. Посмотрите файл, пожалуйста.
https://yadi.sk/i/VFAT45yWogq4d

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимальное соединения двух точек по заданным
СообщениеДобавлено: 11 фев 2016, 22:34 
Не в сети
Начинающий
Зарегистрирован:
11 фев 2016, 00:16
Сообщений: 8
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Andy писал(а):
Я думаю, что коротких вариантов будет много. Например, рассмотрим для простоты точки [math](0,~0)[/math] и [math](2,~3).[/math] Тогда короткие варианты имеют длину [math](2-0)+(3-0)=5.[/math] Их несколько, в чём можно убедиться, сделав рисунок. Например, можно отрезок, соединяющий заданные точки, представить как гипотенузу прямоугольного треугольника, а звенья ломаной - как его катеты, лежащие на сетке.

Спасибо. Очень интересное решение и если бы сетка имела одинаковые ребра, было бы годное. Но тут особенность, что разные длины ребер и точки не всегда могут совпадать с вершинами графа. Посмотрите, может возникнут еще мысли: https://yadi.sk/i/VFAT45yWogq4d

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимальное соединения двух точек по заданным
СообщениеДобавлено: 11 фев 2016, 22:55 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 13534
Откуда: Москва
Cпасибо сказано: 1290
Спасибо получено:
3616 раз в 3175 сообщениях
Очков репутации: 678

Добавить очки репутацииУменьшить очки репутации
Тут, мне кажется, логика простая: из двух конкурирующих путей более короткий красный.

Изображение

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимальное соединения двух точек по заданным
СообщениеДобавлено: 11 фев 2016, 23:08 
Не в сети
Начинающий
Зарегистрирован:
11 фев 2016, 00:16
Сообщений: 8
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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

Изображение

Я с вами согласен. Но самая сложность алгоритмом описать математику построения такого пути.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимальное соединения двух точек по заданным
СообщениеДобавлено: 11 фев 2016, 23:13 
Не в сети
Начинающий
Зарегистрирован:
11 фев 2016, 00:16
Сообщений: 8
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
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 по катетам и прямым движемся из одной точки в другую. Вроде маршрут строиться. Но не всегда оптимальный.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимальное соединения двух точек по заданным
СообщениеДобавлено: 12 фев 2016, 14:33 
Не в сети
Любитель математики
Аватара пользователя
Зарегистрирован:
16 июл 2011, 08:33
Сообщений: 22268
Откуда: Беларусь, Минск
Cпасибо сказано: 2096
Спасибо получено:
4958 раз в 4631 сообщениях
Очков репутации: 845

Добавить очки репутацииУменьшить очки репутации
Какими числами являются координаты заданных на сетке точек?

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Andy "Спасибо" сказали:
Emelya
 Заголовок сообщения: Re: Оптимальное соединения двух точек по заданным
СообщениеДобавлено: 12 фев 2016, 15:03 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Emelya писал(а):
К сожалению, ребра графа разной длины, а точки лежат не всегда на вершинах

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2  След.  Страница 1 из 2 [ Сообщений: 16 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Количество способов соединения двух и более кубов

в форуме Дискретная математика, Теория множеств и Логика

Andrulik

0

124

19 сен 2021, 15:46

Оптимальное расположение точек на прямой

в форуме Исследование операций и Задачи оптимизации

HappyRomio

3

399

09 авг 2017, 16:55

Перебор крайних точек с заданным шагом

в форуме Линейная и Абстрактная алгебра

Brook_m

7

483

28 окт 2015, 16:35

Нарисовать множество точек, удовлетворяющую заданным условия

в форуме Начала анализа и Другие разделы школьной математики

1996

3

268

02 фев 2021, 11:47

Совпадение двух точек

в форуме Геометрия

Anon 31

14

905

03 авг 2018, 15:50

Вероятность встречи двух точек.

в форуме Комбинаторика и Теория вероятностей

VaSSis

3

306

04 мар 2017, 17:57

Построить луч, удаленный от двух точек как 3:1

в форуме Интересные задачи участников форума MHP

ferma-T

13

625

16 сен 2022, 10:28

Фу-ия двух переменных с нужным количеством точек экстремума

в форуме Дифференциальное исчисление

Sammi2186

0

261

29 май 2014, 21:09

Результат произведения координат двух точек на графике

в форуме Алгебра

McMurphy

3

192

02 янв 2023, 19:28

Два тела движутся навстречу друг другу из двух точек

в форуме Школьная физика

Pavel_Kotoff

13

390

06 ноя 2022, 17:59


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 32


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved