Алгоритм наилучшего взаимного выбора

[Detech]

Мне кажется что у задачи есть какое то стандартное решение, но в тех книгах что есть по алгоритмизации у меня решения не встречал, а у самого ничего лучше чем алгоритм сложности N3 не получается - а это неприятно. В связи с тем что сложно понять как его правильно обозвать - непонятно что искать в поисковиках, поэтому прошу совета.

Собстно, задача звучит так. Есть два массива неких объектов. У каждого из объектов есть некое значение сопряжения с объектами другого массива. Таким образом, невозможно отсортировать объекты массивов так как значения у объектов существуют только в паре с обьектом из другого массива.

Т.е. например, объект А1 может иметь значение 13 в паре с объектом B1, 8 в паре с объектом B2 и 21 в паре с объектом B3. А объект А2 может иметь в то же время соответственно {15,18,12} с теми же объектами. Т.е. нельзя сказать какой из объектов, А1 или А2, показывает более высокое значение так как его значение зависит от его пары.

При этом, существуют условия. Каждый из объектов ВСЕГДА стремится выбрать себе пару получше. Т.е. каждый из объектов массива А стремится выбрать из всего массива Б того, с кем его сопряжение выше. А каждый из массива Б соответственно пытается выбрать по тем же условиям из массива А.

Нужно в итоге создать массив пар, учитывая тот факт что размерность массивов может быть разной (часть объектов из одного массива соответственно останутся без пары).

Подскажите алгоритм реализации (сложности ниже N3) или хотя бы намекните как он может официально называться.

Заранее спасибо.

[Detech]

Хотел бы еще добавить:

Естественно, собранные пары извлекаются из ситуации выбора и оставшиеся выбирают из оставшихся (чтобы не получилось ситуации когда некий Аn упорно хотит Бn, а тот уже себе нашел пару и ему на все пох).

При этом, существуют условия. Каждый из объектов ВСЕГДА стремится выбрать себе пару получше. Т.е. каждый из объектов массива А стремится выбрать из всего массива Б того, с кем его сопряжение выше. А каждый из массива Б соответственно пытается выбрать по тем же условиям из массива А.

Формальной постановки задачи не вижу. Какой функционал надо максимизировать?

"стремится выбрать себе пару получше" слишком слабый критерий. Ну будет у вас дохера и больше парето оптимальных решений, какое из них выбрать?

Если максимизируем сумму "сопряжений" бракосочетавшихся элементов, то это задача о взвешенном паросочетании a.k.a optimal assignment problem. Есть, например, венгерский алгоритм, работает за O(n^3).

Другая формализация - если надо найти паросочетания, такое, что в нем не было бы двух элментов a \in A, b \in B, таких что a предпочитает b своей текущей паре, и b предпочитает a своей паре, то така постановка называется http://en.wikipedia.org/wiki/Stable_marriage_problem
Классическое решение за O(n^2) работает.

[Detech]

Не требуется максимизировать сумму. Даже если итоговая сумма всех пар будет меньше оптимально максимальной - это приемлемо. Вернее даже не приемлемо - а является частью условия. Элементы - эгоисты. Каждый из них стремится получить максимум, даже если общество страдает. Интересы общества никак не представлены, никто из элементов не будет уступать своими интересами ради повышения общего сопряжения общества.

Условие я уже указал выше, может не совсем ясно написал. Попробую по другому.
Каждый из элементов массива А имеет собственный уровень сопряжения с любым элементом из массива Б. Таким образом, можно выстроить "очередь желаний" для этого элемента А. И элемент А всегда стремится получить в пару элемент из верхушки этой очереди. Желательно топовый. Но понятно что топовый элемент наверняка получить не удастся, так как существуют конкурирующие элементы, которые могут желать того же самого, а так же встречное желание элементов Б.

Если 2 или более элементов А желают один элемент Б (он находится в топе их "очереди желания") - то отдается предпочтение элементу что стоит выше в "очереди желания" элемента Б.

Т.е. нам не нужно создавать максимальную общую сумму сопряжений. Достаточно будет того что первая пара будет иметь максимально-возможное сопряжение из возможных, вторая пара будет иметь максимально-возможное сопряжение из оставшихся, третья - из оставшихся и т.д.

Ну собстно, как говорится вопрос практически отпал как в анекдоте, подымите руку, кровь прильет к голове и вопрос отпадет. Пока спал - решение сложности 3N2 сформировалось.

Но все равно большое спасибо, статью что вы дали обязательно прочитаю.

Так вы все равно здесь максимизируете сумму сопряжений. Хоть и неоптимально.

Совершенно не вижу как этот алгоритм вытекает из вашей постановки задачи.

Как я понимаю вашу постановку: рассмотрим два решения. Если в первом из них для каждого элемента сопряженность его пары больше чем сопряженность во втором, то первое решение лучше. Т.е. вы задали частичный порядок. Решений, лучше которых нет, - это и есть парето оптимальные решения. Вы ни слова не сказали какое из них вы хотите выбрать, когда их несколько (а их будет экспоненциально много). Ваш жадный алгоритм находит одно произвольное из них. Думайте сами, нужное ли решение он находит или нет. Потому что этого в вашей постановке задачи нет.

Да и кстати ваш алгоритм можно реализовать за O(n^2 log n)