`
trydofor
  • 浏览: 149945 次
  • 性别: 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
分享到:
评论

相关推荐

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

    《国密算法工具SmartTool:助力国密算法测试与应用》 国密算法工具SmartTool是一款专门用于国密算法辅助测试的专业软件,它涵盖了对称和非对称算法的全面测试,是确保我国信息安全领域中关键算法正确性和安全性的...

    Hello 算法.pdf

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

    群智能算法matlab测试函数.zip

    "群智能算法matlab测试函数.zip"这个压缩包集合了一些在这些算法中常用的标准测试函数,为研究者和工程师提供了一个方便的测试平台,以验证和比较不同算法的性能。 首先,我们来详细了解下这些算法: 1. **粒子群...

    place测试算法.rar_PLACE评估测试_算法测试

    在IT领域,"PLACE测试算法"是一个特定的术语,它主要涉及到集成电路设计自动化(EDA)中的布局布线问题。在集成电路设计中,PLACE算法是关键的一环,它的目的是在芯片的二维空间内合理地安排各个逻辑门的位置,以...

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

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

    测试函数的智能算法使用.zip

    "测试函数的智能算法使用.zip"这个压缩包文件很可能包含了用于自动化测试的一些工具、脚本或者源代码,这些内容可以帮助我们更有效地执行测试用例,提高测试效率。下面我们将详细探讨测试函数和智能算法在测试用例中...

    OTB100测试算法.zip

    OTB100测试算法.zip是一个包含针对计算机视觉领域中视频目标跟踪技术的测试资源的压缩文件。这个压缩包特别关注了三种著名的相关滤波算法:KCF(Kernelized Correlation Filter)、DSST(Discriminative Scale-Space...

    常见经典算法测试重点知识点总结.docx

    算法 章节目录 一、算法基本概念与原理 二、算法设计与分析 三、常用经典算法 四、算法复杂度与优化 五、高级算法专题 一、算法基本概念与原理 重点详细内容知识点总结 1.算法定义:算法是一组解决特定问题的规则或...

    2 - 自动空调构架及控制算法.pdf

    在汽车自动空调系统中,构架与控制算法是确保舒适驾驶环境的关键技术。该文档主要涵盖了以下几个方面: 1. **自动空调软件构架(应用层)**:这是空调系统的顶层设计,包括各种模块的集成与交互,如输入信号处理、...

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

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

    matlab AP聚类算法.zip

    在IT领域,特别是数据分析和机器学习中,聚类算法是一种常用的技术,用于将数据无监督地分组到不同的类别中。AP(Affinity Propagation)聚类算法是其中的一种,由Scott D.浚和Michael I. Jordan在2007年提出。...

    Python-算法.zip

    Python是一种广泛应用于各种领域的编程语言,特别是在数据处理、科学计算和人工智能方面。它以其简洁的语法和丰富的...此外,熟悉Python的算法实现还有助于准备面试,因为许多公司会在技术面试中测试候选人的算法能力。

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

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

    MPPT算法.rar

    此外,它还可能提到了如何将该算法集成到光伏充电器的控制电路中,以及如何进行性能测试和优化。 “资料说明.txt”文件可能是对整个压缩包内容的简要说明,列出所有文件的作用和相互关系,为用户提供一个整体的视图...

    ACM 算法模板集

    ACM 算法模板集 Contents 一. 常用函数与STL 二. 重要公式与定理 1. Fibonacci Number 2. Lucas Number 3. Catalan Number 4. Stirling Number(Second Kind) 5. Bell Number 6. Stirling's Approximation 7. Sum of ...

    rrt算法、偏向rrt算法、平滑rrt算法.zip

    `map.png`则提供了一个地图图像,可以用作测试这些算法的环境模型。 在实际应用中,你可以根据具体需求调整这些算法的参数,比如树的扩展步长、目标区域的偏置因子等,以适应不同场景。同时,由于这些代码带有中文...

    传统超声成像算法.rar_传统超声_超声 matlab_超声 算法_超声成像_超声成像MATLAB

    2. 实验验证:通过仿真可以对新算法进行预测试,减少实际硬件实验的需求。 3. 教学工具:对于学生和初学者,MATLAB仿真是学习超声成像算法的良好平台。 总之,这些MATLAB脚本为研究者和学习者提供了一个探索和改进...

Global site tag (gtag.js) - Google Analytics