ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgenij Masherov                     2:5020/175.2   16 Jul 2003  14:33:04
 To : Soldatenkov Mitea
 Subject : <none>
 -------------------------------------------------------------------------------- 
 

 Tue Jul 15 2003 22:45, Soldatenkov Mitea wrote to All:
 
  SM> Возник такой вопрос: есть точки A1, A2, A3, ... An. Есть точки B1, B2,
  SM> B3... Bx.
  SM> Известны их координаты в двух-мерном пространстве. n<=x. Каждую точку
  SM> A*, можно связать прямой с точкой B*, при-чем только с одной. Точно
  SM> так-же, любая точка B*, неможет быть связана более чем с одной точкой A*.
  SM> Hеобходимо чтоб все точки A*, были связаны с какой-то точкой B*. Как
  SM> подобрать связи так, чтоб их сумарная длинна, была миннимальна, при
  SM> n<=x<=32? Естественно интересует подбор в разумные сроки, а не к
  SM> следующему пришествию христа.
 
 Распадается на две подзадачи:
 1. Построить матрицу расстояний всех на все, в выбранной метрике.
 2. Решать задачу о назначении (обычно венгерским методом, но есть и другие)
 
 Евгений Машеров АКА СанитарЖеня
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    <без заголовка>   Soldatenkov Mitea   15 Jul 2003 22:45:04   <none>   Evgenij Masherov   16 Jul 2003 14:33:04