2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задача на построение ломаной
Сообщение19.07.2014, 07:25 


23/10/10
3
Здравствуйте!

Есть следующая задача. На плоскости есть точки A и B, а также набор прямоугольников, ребра которых параллельны осям координат. Точки A и B не принадлежат прямоугольникам. Необходимо создать алгоритм, который ломаную, соединяющую A и B, такую, что:
1) ломаная состоит только из отрезков, которые параллельны осям координат
2) ломаная не пересекает ни один прямоугольник
3) у ломаной минимальное количество изломов
4) у ломаной минимальная длина

Подскажите, пожалуйста, источники, которые могут помочь решить задачу.

Спасибо!

 Профиль  
                  
 
 Re: Задача на построение ломаной
Сообщение19.07.2014, 13:01 
Заслуженный участник


02/08/11
6874
Не представляю, что вы хотите найти в источниках, разве что готове решение. Задача достаточно проста и достаточно интересна, чтобы заслуживать того, чтобы вы сами придумали алгоритм, безо всяких источников.

-- 19.07.2014, 14:57 --

warlock66613 в сообщении #888706 писал(а):
Не представляю, что вы хотите найти в источниках, разве что готовое решение. Задача достаточно проста и достаточно интересна, чтобы заслуживать того, чтобы вы сами придумали алгоритм, безо всяких источников.

 Профиль  
                  
 
 Re: Задача на построение ломаной
Сообщение28.07.2014, 17:06 


30/06/14
47
RedMonk в сообщении #888656 писал(а):
Здравствуйте!

Есть следующая задача. На плоскости есть точки A и B, а также набор прямоугольников, ребра которых параллельны осям координат. Точки A и B не принадлежат прямоугольникам. Необходимо создать алгоритм, который ломаную, соединяющую A и B, такую, что:
1) ломаная состоит только из отрезков, которые параллельны осям координат
2) ломаная не пересекает ни один прямоугольник
3) у ломаной минимальное количество изломов
4) у ломаной минимальная длина

Подскажите, пожалуйста, источники, которые могут помочь решить задачу.

Спасибо!


Хм. Ну я понимаю все кроме последнего пункта, насчет минимальной длины.

Например есть у нас точки A(1,5) , B(10,5) и прямоугольник (2,7)-(9,0)

Очевидно что ломаная будет такой (1,5)-(1,7+dy)-(10,7+dy) - (10,5)
где dy ненулевая, но бесконечно малая величина. Как Вы собираетесь ее представлять ?

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

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group