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

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

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

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




Начать новую тему Ответить на тему  [ Сообщений: 7 ] 
Автор Сообщение
 Заголовок сообщения: Оптимизация соединения концов отрезков
СообщениеДобавлено: 14 янв 2022, 10:18 
Не в сети
Начинающий
Зарегистрирован:
14 янв 2022, 09:50
Сообщений: 4
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Всем привет!

Задача.
Есть множество отрезков (более 1000), которые являются хордами одной окружности.
(Проще говоря, куча отрезков концы которых лежат на одной окружности.)
Отрезки могут пересекаться, и иметь любую длину.
Иногда концы разных отрезков совпадают, но в большинстве случаев это не так.

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

Требуется запрограммировать алгоритм, который оптимизирует расстояние которое потребуется пройти между концами отрезков.
Т.е. минимизировать путь вне отрезков.

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

Изображение

Буду признателен за любую помощь, хотя бы название более-менее подходящего алгоритма.
Понятно, что это частный случай "Задачи коммивояжера", но не понятно как найти более-менее оптимальное решение.
Если оптимальное решение находится методом полного перебора, нужен "быстрый" метод, который позволит найти "достаточно хорошее" решение.

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

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

Жадный метод

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимизация соединения концов отрезков
СообщениеДобавлено: 14 янв 2022, 13:21 
Не в сети
Начинающий
Зарегистрирован:
14 янв 2022, 09:50
Сообщений: 4
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Дык задачу я вроде сформулировал,
это прикладная задача, которую мне нужно решить, соответственно ссылки на нее нет =)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимизация соединения концов отрезков
СообщениеДобавлено: 14 янв 2022, 13:27 
Не в сети
Начинающий
Зарегистрирован:
14 янв 2022, 09:50
Сообщений: 4
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Жадный метод

"Жадными" обычно называют пути решения основанные на локальной оптимизации...
и тут бы понять, что принять за параметр по которому "жадничать" - идти к "ближайшему" отрезку явно слишком не оптимально, особенно с учетом того, что отрезки можно проходить в удобном нам направлении и то, что они могут быть распределены какими то "группами" и пересекаться...

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

Добавить очки репутацииУменьшить очки репутации
denismix писал(а):
Дык задачу я вроде сформулировал,
это прикладная задача, которую мне нужно решить, соответственно ссылки на нее нет =)

Я понял, в шпионов играем. Ок.
Если держите нас здесь за наивных простачков, зачем обращаться?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимизация соединения концов отрезков
СообщениеДобавлено: 14 янв 2022, 15:30 
Не в сети
Начинающий
Зарегистрирован:
14 янв 2022, 09:50
Сообщений: 4
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
denismix писал(а):
Дык задачу я вроде сформулировал,
это прикладная задача, которую мне нужно решить, соответственно ссылки на нее нет =)

Я понял, в шпионов играем. Ок.
Если держите нас здесь за наивных простачков, зачем обращаться?

э... вам для того,, чтобы подсказать алгоритм нужна конкретная задача?
Ну есть у меня прикладная задача, ее объяснять долго и мало кому интересно, но сводится она к решению вышеизложенной.

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

Добавить очки репутацииУменьшить очки репутации
denismix, еще раз повторю. Либо мы открыты и делимся всем, что знаем, или играем в партизанов. Что выбрать - решать вам. Мне есть что сказать по этой задаче, но рассказывать просто так лень.

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

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

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

Emelya

15

719

11 фев 2016, 00:28

Количество способов соединения двух и более кубов

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

Andrulik

0

124

19 сен 2021, 15:46

Отражение волн от концов отрезка

в форуме Дифференциальные и Интегральные уравнения

natural_gl

4

276

12 ноя 2022, 17:25

Мера множества концов интервала?

в форуме Пределы числовых последовательностей и функций, Исследования функций

rancid_rot

10

358

13 авг 2020, 16:46

Координаты начал и концов равных дуг эллипса и углы нормалей

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

iQWERTY13

60

1266

01 июл 2018, 01:23

Оптимизация

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

Frankilou007

0

337

08 дек 2016, 21:57

Условная оптимизация

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

maqueee

13

745

18 май 2017, 10:38

Оптимизация чисел

в форуме Литература и Онлайн-ресурсы по математике

Denis12345

4

665

18 июн 2016, 06:11

Оптимизация в производстве

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

DanF

2

364

18 ноя 2020, 09:40

Оптимизация/задачa

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

Sanna

20

436

29 май 2020, 12:57


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



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

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


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

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

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

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