2014 dxdy logo

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

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




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

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

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

Спасибо!

 
 
 
 Re: Задача на построение ломаной
Сообщение19.07.2014, 13:01 
Не представляю, что вы хотите найти в источниках, разве что готове решение. Задача достаточно проста и достаточно интересна, чтобы заслуживать того, чтобы вы сами придумали алгоритм, безо всяких источников.

-- 19.07.2014, 14:57 --

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

 
 
 
 Re: Задача на построение ломаной
Сообщение28.07.2014, 17:06 
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 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group