# 005.测验.情景之男女相亲算法
相亲算法,源于剩男剩女的相亲,解决男女速配问题。
过程大概是:根据相亲喜好,男女互相,按分值匹配。
@史荣久 / 2015-02-02 / CC-BY-SA-3.0
## 任务说明
事实上,爱美之心人皆有之,追求物质符合自然选择。
现状是,韩剧里高富帅棒子稀缺,白富美洗白的居多。
现在,我们搞一个相亲算法,让高富帅和白富美速配。
有三对单身男女,姓名,特点和心中的TA的特点如下:
人及属性 | 对TA的喜好及分值
1:高 富 | 富:10,白:20,美:30
2:白 富 | 富:10,高:20,帅:30
3:高 帅 | 富:30,白:10,美:20
4:白 美 | 富:30,高:10,帅:20
5:高富帅 | 富:10,白:30,美:20
6:白富美 | 富:10,高:30,帅:20
这样,以男1号"高富"为例,他对女选手喜好如下:
女2号:白+富 = 20+10 = 30
女4号:白+美 = 20+30 = 50
女6号:白+富+美 = 10+20+30 = 60
算法只对喜好值求和,对存在加,不存在的不加。
以此类推,为每个单身者计算出候选人列表。
男1:女2(30),女4(50),女6(60)
女2:男1(30),男3(50),男5(60)
男3:女2(40),女4(30),女6(60)
女4:男1(40),男3(30),男5(60)
男5:女2(40),女4(50),女6(60)
女6:男1(40),男3(50),男5(60)
可以看到,男5和女6最受欢迎,但这只是单方面的。
以女6为例,把男相女和女相男的分值求和,得总分。
女6+男1 = 40+60 = 100
女6+男3 = 50+60 = 110
女6+男5 = 60+60 = 120
这样,女6和男5分值最高,匹配成功。以此类推。
最后,牵手情况:男5+女6,男1+女4,男3+女2
## 数据存储
以下几张表,无事务,只读不写,因此使用MyISAM表引擎。
CREATE TABLE IF NOT EXISTS `USER` (
`UID` INT NOT NULL COMMENT '单身用户ID',
`GENDER` INT NOT NULL COMMENT '性别:0-女,1-男',
`NAME` VARCHAR(45) NOT NULL COMMENT '用户姓名',
PRIMARY KEY (`UID`))
ENGINE = MyISAM
DEFAULT CHARACTER SET = utf8
COLLATE = utf8_bin;
CREATE TABLE IF NOT EXISTS `LABEL` (
`LID` INT NOT NULL COMMENT '标签ID',
`NAME` VARCHAR(45) NOT NULL COMMENT '标签名字',
PRIMARY KEY (`LID`))
ENGINE = MyISAM
DEFAULT CHARACTER SET = utf8
COLLATE = utf8_bin;
CREATE TABLE IF NOT EXISTS `USER_LABEL` (
`UID` INT NOT NULL COMMENT '用户',
`LID` INT NOT NULL COMMENT '用户的标签',
PRIMARY KEY (`UID`, `LID`))
ENGINE = MyISAM
DEFAULT CHARACTER SET = utf8
COLLATE = utf8_bin;
CREATE TABLE IF NOT EXISTS `USER_LOVE` (
`UID` INT NOT NULL COMMENT '用户',
`LID` INT NOT NULL COMMENT '喜好的标签',
`SCORE` INT NULL COMMENT '喜好分值',
PRIMARY KEY (`UID`, `LID`))
ENGINE = MyISAM
DEFAULT CHARACTER SET = utf8
COLLATE = utf8_bin;
-- 插入记录
INSERT INTO `LABEL` (`LID`, `NAME`) VALUES
(0, '富'),(1, '高'),(2, '白'),(3, '帅'),(4, '美');
INSERT INTO `USER` (`UID`, `GENDER`, `NAME`) VALUES
(1, 1, '高富'),(3, 1, '高帅'),(5, 1, '高富帅'),
(2, 0, '白富'),(4, 0, '白美'),(6, 0, '白富美');
INSERT INTO `USER_LABEL` (`UID`, `LID`) VALUES
(1, 0),(1, 1),
(2, 0),(2, 2),
(3, 1),(3, 3),
(4, 2),(4, 4),
(5, 0),(5, 1),(5, 3),
(6, 0),(6, 2),(6, 4);
INSERT INTO `USER_LOVE`(`UID`,`LID`,`SCORE`) VALUES
(1, 0, 10),(1, 2, 20),(1, 4, 30),
(2, 0, 10),(2, 1, 20),(2, 3, 30),
(3, 0, 30),(3, 2, 10),(3, 4, 20),
(4, 0, 30),(4, 1, 10),(4, 3, 20),
(5, 0, 10),(5, 2, 30),(5, 4, 20),
(6, 0, 10),(6, 1, 30),(6, 3, 20);
-- 检查数据
SELECT U.NAME,
GROUP_CONCAT(L.NAME ORDER BY L.LID)
FROM USER_LABEL AS UL,USER AS U,LABEL AS L
WHERE UL.UID = U.UID AND UL.LID=L.LID
GROUP BY U.NAME ORDER BY U.UID;
SELECT U.NAME,
GROUP_CONCAT(L.NAME,':',UL.SCORE ORDER BY L.LID)
FROM USER_LOVE AS UL,USER AS U,LABEL AS L
WHERE UL.UID = U.UID AND UL.LID=L.LID
GROUP BY U.NAME ORDER BY U.UID;
## 问题来了
我们称以上算法为相亲算法(blindate),请尽情发挥。
(1)实现相亲算法,输入男,输出候选女的列表和分值。
即:输入男(UID),得到候选女的列表(UID,SCORE)
(2)用户量增到男女各5万,人均标签从3个增到10个。
要重构程序实现,要求候选女的列表按喜比例分配。
例如:男1的喜好值仍为:富:10,白:20,美:30,
则输出列表中,富占1/6,白占2/6,美占3/6。
列表需要去重(distinct),数量不足时需要补充。
优先满足每用户输出100个候选,然后考虑比例。
(3)假设,相亲算法在10万男x10万女时,有性能瓶颈。
请谈谈改善方法和依据。
----
题图:《非诚勿扰》是一档男女速配的相亲节目,很多人疑其真假,评其美丑,但这些真的那么重要么?
原文:
http://www.moilioncircle.com/actions/005.quiz.case-blind-date.html
分享到:
相关推荐
该文件包含了一个CEC 2013测试函数定义文件和相关测试算法文献。
国密算法工具smartTool软件,算法测试工具,可用于国密算法辅助测试,包括对称及非对称算法。
优化算法测试函数其中包括Rosenbrock.m,Schaffer.m,Schewel.m,Schwefel.m,shiftedRosenbrock.m,ShiftedSphere.m,Sphere.m,step.m,SumDifferent.m,SumSquares.m,Zakharov.m,rastrigin.m,sumpow.m,perm0...
超分辨率的算法可测试-POCS算法.rar 谁有MAP的算法啊 ,可以发给我一份
[麻省理工学院-算法导论].Introduction.to.Algorithms.-.Test 课程测试
芯片测试:蛮力测试和分治策略都有写到,算法按设计与分析课的笔记,博主自己写的,仅仅参考了讲义的伪代码,若有错误请指出,谢谢。 重要的假设:好芯片至少比坏芯片多一片。 测试结果:奇数个芯片√ 偶数个芯片...
place测试算法
测试数据和结果 10 4.1测试数据 10 4.2测试结果 11 4.3测试抓图 11 5.参考文献 14 6.总结 15 6.1设计体会 15 6.2结束语 15 7.程序使用说明书 15 8.程序源代码 15 1.课程设计目的 1.1编写目的 本课程设计的目的...
利用无约束和有约束两类具有多个全局最优解的非线性整数规划实例测试了植物多向生长模拟算法的性能,并与基本植物生长模拟算法、填充函数法、罚函数法以及基于遗传算法的混合算法进行了对比. 植物多向生长模拟算法...
【资源说明】 1、该资源包括项目的全部源码,下载可以直接使用! 2、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大作业和毕设项目,作为参考资料...无线传感器网络覆盖优化算法模拟测试平台源码.zip
论文研究-基于自适应学习群体搜索技术的集成进化算法.pdf, ... 在实验部分,首先定义了算法性能度量标准,然后在26个较新的测试函数上做了算法性能对比实验,实验结果表明所提出的算法具有较高的普适性和鲁棒性.
里面包含一些标准测试函数,在粒子群算法(PSO)、遗传算法(GA)、模拟退火算法等群智能算法中经常用到的标准测试函数。
测试新风车算法.zip
基本压缩解压功能大全.包括Huffuman算法,RLE算法,LZ算法,rice算法,shannon算 法.带有测试文件.
测试函数的智能算法使用.zip
论文研究-基于起讫点的均衡交通分配改进算法.pdf, AnthonyChen (2002)提出的... 在小型测试路网上改进算法较ODBFW算法达到收敛的时间减少近15%, 在大型测试路网上减少近5%.
论文研究-多目标置换流水车间调度的混沌杂草优化算法.pdf, 针对最小化最大完工时间,总...通过与NSGA-II算法进行OR-Library典型测试算例的对比实验,验证该算法的有效性.
针对人工鱼群算法局部搜索不精确、微粒群优化算法易发生过早收敛等问题,...最后,以五个标准函数和一个应用实例进行测试,测试结果表明,提出的算法在一定程度上避免了陷入局部极小,加快了收敛速度且提高了搜索精度。
论文研究-求解多星任务规划问题的演化学习型蚁群算法.pdf, ... 采用多星任务规划问题的21个测试实例进行实验, 结果表明演化学习型蚁群算法在优化性能方面优于其他两种方法.