2014 dxdy logo

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

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




 
 Распределение множества точек на 2 подмножества.
Сообщение13.05.2007, 23:34 
Итак, друзья, помогите решить такую задачу.
На плоскости расположено N<=1000 точек и заданы растаяния между любыми двумя.
Нужно разбить эти точки на два подмножества. При этом в этих подмножествах будут максимальные расстаяния между какими-то точками их длины: max1 и max2. Дефектом разбиения назовём |max1-max2|.
Нужно найти такое разбиение, чтобы дефект был минимальным.

Если у Вас есть предложения, решения, или хотя бы мысли по теме - поделитесь пожалуйста. Очень надо, лаба горит.

Добавлено спустя 2 часа 37 минут 37 секунд:

Спасибо тем, кто думал. Кому интересно смотрите
Задача про сад и деревья.
http://uoi.kiev.ua/Download.aspx?name=UOI\2007\article.zip
Сори за проблемы с линком, но как я понимаю просто надо копироватьстроку адреса, так как "\" не входят в стандарты URL, а спецификация ASP. Я не спец могу ошибаться.

 
 
 
 
Сообщение13.05.2007, 23:45 
1. Отсортируй по убыванию этот массив на 1 млн расстояний.
2. Возьми два максимальных расстояния сверху, но так, чтобы эти пары точек были различными.
3. Добавь оставшиеся точки к любой из этих родительских пар.

Все что не так прошу отнести к неясной постановке задачи :)

PS Твой линк не работает.

 
 
 
 
Сообщение14.05.2007, 00:42 
Твой вариант может не дать результатов, так как имеет место ситуаия, когда от одной точки выходит очень много расстаяний большой длинны, близких к максимальному, и тогда не ясно куда их девать.

 
 
 
 
Сообщение14.05.2007, 00:48 
Аватара пользователя
Эта тема имеет непосредственное отношение к вашей работе, но там задача немножко сложнее

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


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