2014 dxdy logo

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

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




 
 Триангуляция многоугольника!
Сообщение24.05.2010, 15:45 
Помогите решить задачу из кормен "Алгоритмы. Построение и анализ".
Найти оптимальную триангуляцию правильного многоугольника на евклидовой плоскости для случая если весом треугольника считается периметр.

P.S. вот ссылка на скачивание книги если когото заинтересовало http://samouchka.net/2007/07/02/algo..._i_analiz.html)

 
 
 
 Re: Триангуляция многоугольника!
Сообщение24.05.2010, 17:15 
Может быть, у Кормена другое решение, но это типичная задача на применение метода динамического программирования.
Оптимальный вес всего многоугольника - минимум суммы оптимальных весов двух многоугольников после разрезания исходного его диагональю.

 
 
 
 Re: Триангуляция многоугольника!
Сообщение24.05.2010, 19:49 
Тоесть миниму сумы периметров этих многоугольников.(Просто я впервые сталкиваюсь вообще с триангуляцией и немогу никак разобратся поэтому и задаю такие простые на ваш взгляд вопросы. ) Немогли бы вы описать подробнее пожалуйста оч прошу.

 
 
 
 Re: Триангуляция многоугольника!
Сообщение24.05.2010, 19:52 
Vuktorr в сообщении #323539 писал(а):
Тоесть миниму сумы периметров этих многоугольников.
Нет. Минимум суммы весов триангуляций этих многоугольников.

 
 
 
 Re: Триангуляция многоугольника!
Сообщение24.05.2010, 19:55 
Но весом треугольника считается периметр. Ничего немогу понять извините канечно за тупость

 
 
 
 Re: Триангуляция многоугольника!
Сообщение24.05.2010, 20:35 
Vuktorr в сообщении #323542 писал(а):
Но весом треугольника считается периметр. Ничего немогу понять извините канечно за тупость
Вес треугольника - периметр, а вес четырёх- и более- угольника - не периметр, а сумма периметров треугольников.

 
 
 [ Сообщений: 6 ] 


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