Это не так просто, вам нужно создать служебную функцию, которая позволит вам узнать, какое соответствие лучше. Например, что будет лучше:
(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, поэтому для этой задачи не существует известного полиномиального решения, и, вероятно, следует использовать эвристическое решение, подобное предложенному выше.
Обратите внимание, что если ваш график двудольный [т.е. вы не можете сопоставить мужчину с мужчиной/женщину с женщиной], эта проблема решается за полиномиальное время. Дополнительная информация: сопоставление в двудольных графах
person
amit
schedule
17.11.2011
