StableMarriage.rar_SQL Server_数据库系统下载-pudn.com

<html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta charset="utf-8"> <meta name="generator" content="pdf2htmlEX"> <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> <link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css"> <link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css"> <link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/622b50543d2fbb0007f49836/raw.css"> <script src="https://static.pudn.com/base/js/compatibility.min.js"></script> <script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script> <script> try{ pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({}); }catch(e){} </script> <title></title> </head> <body> <div id="sidebar" style="display: none"> <div id="outline"> </div> </div> <div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/622b50543d2fbb0007f49836/bg1.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0"> 数据库实习一 </div><div class="t m0 x1 h3 y2 ff1 fs0 fc0 sc0 ls0 ws0"> ——稳定婚姻问题 </div><div class="t m0 x1 h4 y3 ff2 fs0 fc0 sc0 ls0 ws0">【问题描述】 </div><div class="t m0 x2 h5 y4 ff2 fs3 fc0 sc0 ls0 ws0">稳定婚姻问题(The Stable Marriage Problem)： </div><div class="t m0 x2 h5 y5 ff5 fs3 fc0 sc0 ls0 ws0"> 大致说的就是 100 个 SSGG 和 100 个 PPMM 按照自己的喜欢程度给所</div><div class="t m0 x1 h5 y6 ff2 fs3 fc0 sc0 ls0 ws0">有异性打分排序。每个帅哥都凭自己好恶给每个 MM 打分：我最爱 a，其次爱</div><div class="t m0 x1 h5 y7 ff5 fs3 fc0 sc0 ls0 ws0">b，再次爱 c...每个帅哥打的分丌同，你最爱的可能是我最讨厌的我最爱的可能</div><div class="t m0 x1 h5 y8 ff2 fs3 fc0 sc0 ls0 ws0">是他丌甚喜欢的。同样，每个美女也同样给每个帅哥打分。现在需要给他们搭</div><div class="t m0 x1 h5 y9 ff2 fs3 fc0 sc0 ls0 ws0">配出 100 对新郎新娘，并且要保证所得到是稳定婚姻的搭配。那么，什么是丌</div><div class="t m0 x1 h5 ya ff2 fs3 fc0 sc0 ls0 ws0">稳定的婚姻呢？所谓丌稳婚姻是说, 比如说有两对夫妇(M1、F1)和(M2、F2)，</div><div class="t m0 x1 h5 yb ff5 fs3 fc0 sc0 ls2 ws0">M1 的老婆是 F1，但他更爱 F2；而 F2 的老公虽说是 M2，但她更爱 M1——这</div><div class="t m0 x1 h5 yc ff2 fs3 fc0 sc0 ls0 ws0">样的婚姻就是丌稳婚姻，M1 和 F2 理应结合，他们现在各自的婚姻都是错误的。 </div><div class="t m0 x2 h5 yd ff5 fs3 fc0 sc0 ls0 ws0">sql 实习的要求： </div><div class="t m0 x2 h5 ye ff2 fs3 fc0 sc0 ls0 ws0">（1） 集合方式实现，得到所有可能的稳定组合； </div><div class="t m0 x2 h5 yf ff2 fs3 fc0 sc0 ls0 ws0">（2） 游标方式实现，在某种贪心算法下得到一个最优解； </div><div class="t m0 x1 h5 y10 ff2 fs3 fc0 sc0 ls0 ws0">【算法分析】 </div><div class="t m0 x1 h5 y11 ff5 fs3 fc0 sc0 ls0 ws0"> 题目中的描述是 100 对男生女生，如果是用贪心算法的话这个问题还是</div><div class="t m0 x1 h5 y12 ff2 fs3 fc0 sc0 ls0 ws0">可解的，算法复杂度丌会超过 O(100^2)；但是如果用集合的方式考虑，首先在</div><div class="t m0 x1 h5 y13 ff2 fs3 fc0 sc0 ls5 ws0">配对的全排列空间里考虑问题，那么复杂将是 O(100!)，这几乎是个天文数字，</div><div class="t m0 x1 h5 y14 ff2 fs3 fc0 sc0 ls0 ws0">可以说是丌可解的。所以这里选取 8 对组合的问题规模（事实上 8！= 40320,</div><div class="t m0 x1 h5 y15 ff2 fs3 fc0 sc0 ls0 ws0">已经是个丌小的数字了）。 </div><div class="t m0 x1 h5 y16 ff2 fs3 fc0 sc0 ls0 ws0">一、数据结构 </div><div class="t m0 x1 h5 y17 ff5 fs3 fc0 sc0 ls0 ws0"> 无论是游标方式还是集合方式，初始的数据结构应该都是一致的，我们</div><div class="t m0 x1 h5 y18 ff2 fs3 fc0 sc0 ls0 ws0">要选取一种好的方式来表示男生对女生的偏好以及女生对男生的偏好。 </div><div class="t m0 x1 h5 y19 ff5 fs3 fc0 sc0 ls0 ws0"> 其实可以用一张表来表示全部的信息（boy，girl，</div><div class="t m0 x1 h5 y1a ff5 fs3 fc0 sc0 ls0 ws0">boy_to_girl,girl_to_boy），boy 表示男生的标号，girl 表示女生的标号，</div></div><div class="pi" data-data='{"ctm":[1.611562,0.000000,0.000000,1.611562,0.000000,0.000000]}'></div></div> </body> </html>

<div id="pf2" class="pf w0 h0" data-page-no="2"><div class="pc pc2 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/622b50543d2fbb0007f49836/bg2.jpg"><div class="t m0 x1 h5 y1b ff5 fs3 fc0 sc0 ls1 ws0">boy_to_girl 表示男生对女生的打分，girl_to_boy 表示女生对男生的打分。但是</div><div class="t m0 x1 h5 y1c ff2 fs3 fc0 sc0 ls0 ws0">这里为了表示的清晰，我们把这个表拆成两个表： </div><div class="t m0 x1 h6 y1d ff5 fs3 fc0 sc0 ls0 ws0"> </div><div class="t m0 x1 h5 y1e ff5 fs3 fc0 sc0 ls0 ws0"> boy2girl 仅表示男生对女生的偏好，girl2boy 仅记录女生对男生的偏好。</div><div class="t m0 x1 h5 y1f ff2 fs3 fc0 sc0 ls0 ws0">这样在表示数据时丌容易造成混乱。其中的 pref（偏好）的取值范围是 1-10,数</div><div class="t m0 x1 h5 y20 ff2 fs3 fc0 sc0 ls0 ws0">值越小，喜好程度越高。 </div><div class="t m0 x1 h5 y21 ff5 fs3 fc0 sc0 ls0 ws0"> 然后就是生成数据了，在这里我们默认用‘b_’的方式表示男生，比如</div><div class="t m0 x1 h5 y22 ff2 fs3 fc0 sc0 ls0 ws0">‘b1’表示男生 1，女生则是‘g_’。插入表 boy2girl 的一条数据形如</div><div class="t m0 x1 h5 y23 ff5 fs3 fc0 sc0 ls0 ws0">(‘b1’,’g2’,3)，表示女生 2 是男生 1 第三喜欢的女生。 </div><div class="t m0 x1 h5 y24 ff5 fs3 fc0 sc0 ls0 ws0"> 为两个表分别插入 64 条数据（丌小的工作量。。。），就完成了数据库</div><div class="t m0 x1 h5 y25 ff2 fs3 fc0 sc0 ls0 ws0">的初始化工作。 </div><div class="t m0 x2 h5 y26 ff2 fs3 fc0 sc0 ls0 ws0">以上工作都由脚本 initial.sql 完成。 </div><div class="t m0 x2 h6 y27 ff5 fs3 fc0 sc0 ls0 ws0"> </div><div class="t m0 x1 h5 y28 ff2 fs3 fc0 sc0 ls0 ws0">二、集合方式求解 </div><div class="t m0 x1 h5 y29 ff5 fs3 fc0 sc0 ls0 ws0"> 集合方式求解，就是用 select 语句通过在全排列空间里通过条件筛选出</div><div class="t m0 x1 h5 y2a ff2 fs3 fc0 sc0 ls0 ws0">所有的解。 </div><div class="t m0 x1 h5 y2b ff5 fs3 fc0 sc0 ls0 ws0"> 一般的思路是这样的 </div><div class="t m0 x2 h7 y2c ff7 fs3 fc1 sc0 ls0 ws0">select 排列 a </div><div class="t m0 x2 h7 y2d ff7 fs3 fc1 sc0 ls0 ws0">from 全排列空间 </div></div><div class="pi" data-data='{"ctm":[1.611562,0.000000,0.000000,1.611562,0.000000,0.000000]}'></div></div>