Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 7 ] |
|
Автор | Сообщение | |
---|---|---|
denismix |
|
|
Задача. Есть множество отрезков (более 1000), которые являются хордами одной окружности. (Проще говоря, куча отрезков концы которых лежат на одной окружности.) Отрезки могут пересекаться, и иметь любую длину. Иногда концы разных отрезков совпадают, но в большинстве случаев это не так. Нужно пройти все отрезки, не важно в каком направлении идти по конкретному отрезку. Каждый отрезок можно проходить только один раз. Начальную и конечную точку обхода выбирает алгоритм. Путь между концами отрезков проходим по прямой. Требуется запрограммировать алгоритм, который оптимизирует расстояние которое потребуется пройти между концами отрезков. Т.е. минимизировать путь вне отрезков. Пример (пояснение). Если мы должны обойти все красные отрезки (каждый по одному разу), то нам нужно найти такой способ обхода, чтобы сумма длин зеленых пунктирных отрезков была минимальной. Буду признателен за любую помощь, хотя бы название более-менее подходящего алгоритма. Понятно, что это частный случай "Задачи коммивояжера", но не понятно как найти более-менее оптимальное решение. Если оптимальное решение находится методом полного перебора, нужен "быстрый" метод, который позволит найти "достаточно хорошее" решение. |
||
Вернуться к началу | ||
swan |
|
|
Киньте ссылку на задачу.
denismix писал(а): Если оптимальное решение находится методом полного перебора, нужен "быстрый" метод, который позволит найти "достаточно хорошее" решение. Жадный метод |
||
Вернуться к началу | ||
denismix |
|
|
Дык задачу я вроде сформулировал,
это прикладная задача, которую мне нужно решить, соответственно ссылки на нее нет =) |
||
Вернуться к началу | ||
denismix |
|
|
swan писал(а): Жадный метод "Жадными" обычно называют пути решения основанные на локальной оптимизации... и тут бы понять, что принять за параметр по которому "жадничать" - идти к "ближайшему" отрезку явно слишком не оптимально, особенно с учетом того, что отрезки можно проходить в удобном нам направлении и то, что они могут быть распределены какими то "группами" и пересекаться... |
||
Вернуться к началу | ||
swan |
|
|
denismix писал(а): Дык задачу я вроде сформулировал, это прикладная задача, которую мне нужно решить, соответственно ссылки на нее нет =) Я понял, в шпионов играем. Ок. Если держите нас здесь за наивных простачков, зачем обращаться? |
||
Вернуться к началу | ||
denismix |
|
|
swan писал(а): denismix писал(а): Дык задачу я вроде сформулировал, это прикладная задача, которую мне нужно решить, соответственно ссылки на нее нет =) Я понял, в шпионов играем. Ок. Если держите нас здесь за наивных простачков, зачем обращаться? э... вам для того,, чтобы подсказать алгоритм нужна конкретная задача? Ну есть у меня прикладная задача, ее объяснять долго и мало кому интересно, но сводится она к решению вышеизложенной. |
||
Вернуться к началу | ||
swan |
|
|
denismix, еще раз повторю. Либо мы открыты и делимся всем, что знаем, или играем в партизанов. Что выбрать - решать вам. Мне есть что сказать по этой задаче, но рассказывать просто так лень.
|
||
Вернуться к началу | ||
[ Сообщений: 7 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Оптимальное соединения двух точек по заданным | 15 |
719 |
11 фев 2016, 00:28 |
|
Количество способов соединения двух и более кубов | 0 |
124 |
19 сен 2021, 15:46 |
|
Отражение волн от концов отрезка | 4 |
276 |
12 ноя 2022, 17:25 |
|
Мера множества концов интервала?
в форуме Пределы числовых последовательностей и функций, Исследования функций |
10 |
358 |
13 авг 2020, 16:46 |
|
Координаты начал и концов равных дуг эллипса и углы нормалей | 60 |
1266 |
01 июл 2018, 01:23 |
|
Оптимизация | 0 |
337 |
08 дек 2016, 21:57 |
|
Условная оптимизация | 13 |
745 |
18 май 2017, 10:38 |
|
Оптимизация чисел | 4 |
665 |
18 июн 2016, 06:11 |
|
Оптимизация в производстве | 2 |
364 |
18 ноя 2020, 09:40 |
|
Оптимизация/задачa
в форуме Алгебра |
20 |
436 |
29 май 2020, 12:57 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 14 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |