java — поиск по подмножествам, алгоритм (оптимальный или эвристический)
Я ищу помощь с алгоритмом поиска проблемы. Проблема может быть упрощена до следующего.
У нас есть объект, который может принимать определенные атрибуты — X1, X2 … XN. N имеет порядок 5000. Однако конкретный объект принимает подмножество этих атрибутов, скажем, Xi .. Xj (около 50).
Конфигурация — это определенное подмножество атрибутов. Существуют определенные конфигурации с нумерацией Z (порядка 0,1 миллиона), которые являются оптимальными.
Входные данные:
Configuration 1: X1, X2, X3.. Xf
Configuration 2: X4, X6, X7, .. Xz
:
:
Configuration Z: X10, X200… XN
Проблема: Для определенного объекта, ALPHA с подмножеством атрибутов {Xi… Xj}, цель состоит в том, чтобы найти конфигурацию, наиболее близкую к этому объекту. Конфигурация может быть надмножеством конфигурации объекта ALPHA. Также может быть так, что ни одна конфигурация не имеет всех атрибутов ALPHA. Ближайший определяется как конфигурация, которая имеет наибольшее число атрибутов ALPHA.
Наивное решение, которое я имею, в основном делает следующее
1. Take each configuration
2. Loop through each attribute of ALPHA
3. Keep track of the configuration with maximum number of matches to ALPHA
4. Pop out the configuration maximum matches.
Я думаю, что наивное решение верное, но оно слишком медленное. Есть ли эффективный способ поиска по конфигурациям? Даже приблизительная эвристика хороша, если она очень быстрая.
Добавление C ++, тегов Java, чтобы увидеть, есть ли программное обеспечение, которое делает это.
Благодарю.
Решение
Вот лучший неэвристический подход. Сохраните ваши оптимальные конфигурации в обратном порядке. т.е. сопоставление каждого атрибута с конфигурациями, в которых он появляется. например (не имеет отношения к вашему примеру)
X1 : C1 C4 C5 C99999
X2 : C1 C2
X3 : C1
X4 : C1 C2
...
XN : C100 C200 C300
Теперь вы делаете массив длины Z хранить, сколько совпадений вы нашли. Вы перебираете ALPHA, и для каждого атрибута вы проходите через связанные конфигурации. Для каждой конфигурации вы добавляете одну в соответствующую позицию в вашем массиве.
Наконец, вы запускаете массив и выбираете конфигурацию с наибольшим количеством. Вместо этого вы можете сохранить рабочий максимум, но это будет более эффективно, если вы рассчитываете сделать меньше всего Z сравнений (количество элементов в ALPHA, умноженное на среднее количество связанных конфигураций).
Это найдет наилучшее совпадение, и должно быть примерно в 50 раз быстрее, чем ваше наивное решение.
Другие решения
Других решений пока нет …