Задача по нахождению оптимальных пар

[trarbish]

Добрый день!

Необходимо решить такую задачу.
Есть два множества объектов, каждому объекту соответствует набор числовых характеристик. Необходимо составить наиболее подходящие пары объектов (первый объект из первого множества, второй соответственно из второго).
Чтобы было более наглядно. Например, у нас есть два множества, состоящие из стран. В первом множестве страны Европы, во втором страны Азии. У каждой страны есть такие характеристики как численность населения, количество административных округов и т.д. Вот и необходимо наиболее оптимальным образом составить пары "страна из Европы - страна из Азии".

Я не сталкивался с такими задачами раньше. Небольшой поиск в интернете привел меня к таким понятиям как кластеризация и венгерский метод.
Я так понимаю, что сначала я составлю матрицу: столбцы пускай соответствуют странам из Азии, а строки странам из Европы. Элементами матрицы будут являться метрики (например, Евклидово расстояние) для всех возможных пар. А вот дальше я не очень понимаю, что нужно делать, для того чтобы составить весь набор оптимальных пар. Подходит ли тут использование венгерского метода? Или необходимо использовать другие техники?

[Евгений Машеров]

Задача о назначениях. И да, венгерский метод как раз для её решения и изобретён (есть и другие, но имеют больше теоретическое значение, венгерский очень эффективен)
При неравной мощности множеств надо вводить фиктивные страны, удалённые ото всех.

[trarbish]

Евгений Машеров в сообщении #1175089 писал(а):

Задача о назначениях. И да, венгерский метод как раз для её решения и изобретён (есть и другие, но имеют больше теоретическое значение, венгерский очень эффективен)
При неравной мощности множеств надо вводить фиктивные страны, удалённые ото всех.

Спасибо. Понятно, т.е. если у нас есть множество 1, в котором N элементов, и множество 2, в котором M элементов, то создается квадратная матрица с размером равным максимальной мощности двух множеств (получившиеся лишние строки/столбцы заполняются фиктивными большими числами, чтобы исключить их влияние при составлении пар).

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

[Евгений Машеров]

Да, фиктивные элементы для сравнения.
Нормировать данные можно по-разному. Часто применяемые "автоматические" это вычесть среднее по показателю и разделить на стандартное отклонение, или же вычесть минимум и разделить на разность максимум-минимум. Впрочем, если есть возможность использовать содержательную информацию - лучше брать её, скажем, вводя веса показателей применительно к их важности (а откуда их брать? от экспертов?).

[trarbish]

Евгений Машеров в сообщении #1175118 писал(а):

Нормировать данные можно по-разному. Часто применяемые "автоматические" это вычесть среднее по показателю и разделить на стандартное отклонение, или же вычесть минимум и разделить на разность максимум-минимум. Впрочем, если есть возможность использовать содержательную информацию - лучше брать её, скажем, вводя веса показателей применительно к их важности (а откуда их брать? от экспертов?).

Замечательно, спасибо. Я нашел информацию про " вычесть среднее по показателю и разделить на стандартное отклонение", буду пока использовать эту технику (все характеристики имеют одинаковую важность). Затем буду считать расстояния по Евклиду. План намечен, буду реализовывать

[Евгений Машеров]

Для фиктивных стран расстояния не обязаны быть большими. Можно даже нули. Принципиально важно, чтобы были одинаковы.