`
trydofor
  • 浏览: 150410 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

005.测验.情景之男女相亲算法

阅读更多


# 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 
0
4
分享到:
评论

相关推荐

    Hello 算法.pdf

    算法实现的细节很重要,包括编程语言的选择、代码风格、注释、测试等。这些细节能够影响算法的效率和可靠性。 知识点五:实践经验的价值 实践经验是学习算法的最好老师。作者通过分享自己的实践经验,提供了一份...

    国密算法工具smartTool软件,算法测试工具,可用于国密算法辅助测试.zip

    国密算法工具smartTool软件,算法测试工具,可用于国密算法辅助测试,包括对称及非对称算法。

    CEC 2013函数及相关测试算法.rar_Cec测试_algorithm_cec2013_算法测试函数

    该文件包含了一个CEC 2013测试函数定义文件和相关测试算法文献。

    优化算法测试函数.zip

    优化算法测试函数其中包括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...

    [麻省理工学院-算法导论].Introduction.to.Algorithms.-.Test 课程测试

    通过这些测试,学生不仅需要掌握算法的实现,还需要具备分析算法效率、解决问题的能力,以及在面对复杂问题时灵活应用所学知识的技巧。在准备这些测试时,除了阅读教材和完成习题,参加讨论和模拟考试也是十分有益的...

    51单片机循迹小车PID算法.zip

    5. **测试与调试**:记录了在不同环境和条件下的测试结果,以及如何根据测试反馈优化算法。 总的来说,51单片机循迹小车的PID算法实现是一项综合性的工程实践,它融合了硬件设计、嵌入式编程和控制理论等多个领域的...

    超分辨率的算法可测试-POCS算法.rar

    在"超分辨率的算法可测试-POCS算法.rar"压缩包中,可能包含了MATLAB实现POCS算法的相关代码,以及一个名为“新建文件夹 (2)”的子文件夹,里面可能包含示例图像和预处理或后处理脚本。通过运行这些代码,用户可以...

    leetcode初级算法.zip

    《LeetCode初级算法C++详解》 LeetCode作为全球知名的在线编程挑战平台,深受程序员喜爱,尤其是对于初学者,它提供了丰富的算法题目,是提升编程技能和算法理解的绝佳场所。本资料集“leetcode初级算法.zip”正是...

    无线传感器网络覆盖优化算法模拟测试平台源码.zip

    【资源说明】 1、该资源包括项目的全部源码,下载可以直接使用! 2、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大作业和毕设项目,作为参考资料...无线传感器网络覆盖优化算法模拟测试平台源码.zip

    人工蜂群算法以及测试函数

    人工蜂群算法(Artificial Bee Colony,ABC)是一种模拟自然界蜜蜂采蜜行为的全局优化算法,由Karaboga在2005年提出。该算法借鉴了蜜蜂社会中寻找蜜源的行为模式,包括工蜂、侦查蜂和食物源三个基本概念,用于解决多...

    操作系统课程设计磁盘调度算法.doc

    操作系统课程设计磁盘调度算法是计算机操作系统中的一种重要算法,用于确定磁盘读写操作的顺序,以提高磁盘的读写效率。本文将对磁盘调度算法的设计进行详细的介绍,并对其实现过程进行剖析。 1. 操作系统课程设计...

    几种能用于小ram单片机的压缩算法.7z

    在嵌入式系统和物联网设备中,有限的RAM资源对数据处理能力构成了严峻挑战。针对这类情况,开发者经常需要寻找适合小RAM单片机的...在实际应用中,可能需要进行性能测试和权衡,以找到最适合小RAM单片机的解决方案。

    论文研究-针对规则更新操作的测试数据包选取算法.pdf

    防火墙规则集中存在的配置错误主要来源于规则的添加、删除等更新...理论分析和仿真实验表明,与现有测试算法相比,在进行规则更新时,PCRU算法只需使用少量的测试数据包,即可检测出所有因规则冲突而导致的配置错误。

    国密SM9算法测试工具

    VS2015写的SM9算法测试工具,包括KGC密钥生成、签名验签、密钥封装解封、加密解密、密钥交换。另外还有SM2/3/4系列算法、SHA系列算法、几个分组算法、Base64编码和C++的随机数生成测试。

    软件测试总报告-实例(珍藏版)

    软件测试报告 珍藏版。好用记得回复推荐哦 目 录 1. 测试概述 3 1.1. 编写目的 3 1.2. 测试范围 3 1.3. 参考资料 3 2. 测试计划执行情况 3 2.1. 测试类型 3 2.2. 测试环境与配置 4 2.3. 测试人员 4 2.4. ...

Global site tag (gtag.js) - Google Analytics