Это не так просто, вам нужно создать служебную функцию, которая позволит вам узнать, какое из них лучше подходит. Например, что будет лучше:
(1) одна пара с отличным совпадением, другая ужасно плохая.
(2) две пары со средним совпадением.
Я предлагаю использовать некоторые проверенные средства искусственного интеллекта для решения этой проблемы.
сначала несколько определений:
P={all persons} S={all possibilities to match all people}- пусть
u:PxP->R будет функцией подсчета очков для пары: u(p1,p2)=their
score as a match [конечно, зависит от ваших данных]
- пусть
U:S->R будет функцией оценки для всего соответствия: U(aMatch)
= Sigma(u(p1,p2)) for each paired couple.
- пусть
next:S->2^S будет: next(S)={all possible matchings which are
different from S by swapping two people only}
Теперь с приведенным выше определением вы можете использовать крутое восхождение на гору или генетический алгоритм , которые являются проверенными инструментами искусственного интеллекта для получения хорошего результата.
Крутое восхождение на гору [SAHC] прост, начните с случайного соответствия и вносите небольшие изменения, пока не дойдете до точки, где вы не сможете сделать локальное улучшение. Эта точка является локальным максимумом, и кандидат является лучшим решением. перезапустите процесс с другим начальным состоянием.
псевдокод:
1. best<- -INFINITY
2. while there is more time
3. choose a random matching
4. NEXT <- next(s)
5. if max{ U(v) | for each v in NEXT} < U(s): //s is a local maximum
5.1. if u(s) > best: best <- u(s) //if s is better then the previous result - store it.
5.2. go to 2. //restart the hill climbing from a different random point.
6. else:
6.1. s <- max { NEXT }
6.2. goto 4.
7. return best //when out of time, return the best solution found so far.
Примечание1: , что этот алгоритм в любое время , что означает, что он даст лучшие результаты, если вы дадите ему больше времени. и если ваше время -> бесконечность, алгоритм в конечном итоге найдет оптимальное решение.
Примечание 2: функция полезности U - это просто совет, вы также можете использовать max{u(p1,p2) | for each pair in the match} или любую другую полезную функцию, которая вам подойдет.
EDIT:
Даже более простая проблема, а именно: два человека могут просто «соответствовать» или «не соответствовать» [u(p1,p2)=0 или u(p1,p2)=1], на самом деле является проблемой максимального соответствия , которая равна NP-Hard , таким образом, не существует известного полиномиального решения этой проблемы, и, вероятно, следует использовать эвристическое решение, такое как предложенное выше.
Обратите внимание, что если ваш график двудольный [т.е. Вы не можете сопоставить мужчину с мужчиной / женщину с женщиной], эта проблема разрешима за полиномиальное время. Дополнительная информация: совпадение в двудольных графах