µÚ¶þ½Ú ϵͳ½á¹¹Ä£ÐÍ»¯¼¼Êõ Ò»¡¢ÏµÍ³½á¹¹Ä£ÐÍ»¯»ù´¡
(Ò»)½á¹¹·ÖÎöµÄ¸ÅÄîºÍÒâÒå
ÈκÎϵͳ¶¼ÊÇÓÉÁ½¸öÒÔÉÏÓлúÁªÏµ¡¢Ï໥×÷ÓõÄÒªËØËù×é³ÉµÄ£¬¾ßÓÐÌض¨¹¦ÄÜÓë½á¹¹µÄÕûÌå¡£½á¹¹¼´×é³ÉϵͳÖîÒªËØÖ®¼äÏ໥¹ØÁªµÄ·½Ê½¡£°üÀ¨ÏÖ´úÆóÒµÔÚÄڵĴó¹æÄ£¸´ÔÓϵͳ¾ßÓÐÒªËؼ°Æä²ã´ÎÖڶࡢ½á¹¹¸´ÔÓºÍÉç»áÐÔÍ»³öµÈÌص㡣ÔÚÑо¿ºÍ½â¾öÕâÀàϵͳÎÊÌâʱ£¬ÍùÍùҪͨ¹ý½¨Á¢ÏµÍ³µÄ½á¹¹Ä£ÐÍ£¬½øÐÐϵͳµÄ½á¹¹·ÖÎö£¬ÒÔÇóµÃ¶ÔÎÊÌâÈ«ÃæºÍ±¾ÖʵÄÈÏʶ¡£
½á¹¹Ä£ÐÍÊǶ¨ÐÔ±íʾϵͳ¹¹³ÉÒªËØÒÔ¼°ËüÃÇÖ®¼ä´æÔÚ×ŵı¾ÖÊÉÏÏ໥ÒÀÀµ¡¢Ï໥ÖÆÔ¼ºÍ¹ØÁªÇé¿öµÄÄ£ÐÍ¡£½á¹¹Ä£ÐÍ»¯¼´½¨Á¢ÏµÍ³½á¹¹Ä£Ð͵Ĺý³Ì¡£¸Ã¹ý³Ì×¢ÖرíÏÖϵͳҪËØÖ®¼äÏ໥×÷ÓõÄÐÔÖÊ£¬ÊÇϵͳÈÏʶ¡¢×¼È·°ÑÎÕ¸´ÔÓÎÊÌ⣬²¢¶ÔÎÊÌ⽨Á¢ÊýѧģÐÍ¡¢½øÐж¨Á¿·ÖÎöµÄ»ù´¡¡£½×²ãÐÔÊÇ´ó¹æÄ£¸´ÔÓϵͳµÄ»ù±¾ÌØÐÔ£¬ÔڽṹģÐÍ»¯¹ý³ÌÖУ¬¶ÔµÝ½×½á¹¹µÄÑо¿ÊÇÒ»ÏîÖØÒª¹¤×÷¡£
½á¹¹·ÖÎöÊÇÒ»¸öʵÏÖϵͳ½á¹¹Ä£ÐÍ»¯²¢¼ÓÒÔ½âÊ͵Ĺý³Ì¡£Æä¾ßÌåÄÚÈÝ°üÀ¨£º¶ÔϵͳĿµÄ--¹¦ÄܵÄÈÏʶ£»ÏµÍ³¹¹³ÉÒªËصÄÑ¡È¡£»¶ÔÒªËؼäµÄÁªÏµ¼°Æä²ã´Î¹ØϵµÄ·ÖÎö£»ÏµÍ³ÕûÌå½á¹¹µÄÈ·¶¨¼°Æä½âÊÍ¡£ÏµÍ³½á¹¹Ä£ÐÍ»¯Êǽṹ·ÖÎöµÄ»ù±¾ÄÚÈÝ¡£
½á¹¹·ÖÎöÊÇϵͳ·ÖÎöµÄÖØÒªÄÚÈÝ£¬ÊÇϵͳÓÅ»¯·ÖÎö¡¢Éè¼ÆÓë¹ÜÀíµÄ»ù´¡¡£ÓÈÆäÊÇÔÚ·ÖÎöÓë½â¾öÉç»á¾¼ÃϵͳÎÊÌâʱ£¬¶Ôϵͳ½á¹¹µÄÕýÈ·ÈÏʶÓëÃèÊö¸ü¾ßÓÐÊýѧģÐͺͶ¨Á¿·ÖÎöËùÎÞ·¨Ìæ´úµÄ×÷Óá£
(¶þ)ϵͳ½á¹¹µÄ»ù±¾±í´ï·½Ê½
ϵͳµÄÒªËؼ°Æä¹ØϵÐγÉϵͳµÄÌض¨½á¹¹¡£ÔÚͨ³£Çé¿öÏ£¬¿É²ÉÓü¯ºÏ¡¢ÓÐÏòͼºÍ¾ØÕóµÈÈýÖÖÏ໥¶ÔÓ¦µÄ·½Ê½À´±í´ïϵͳµÄijÖֽṹ¡£ 1¡¢ÏµÍ³½á¹¹µÄ¼¯ºÏ±í´ï
ÉèϵͳÓÉn(n¡Ý2)¸öÒªËØ(S1£¬S2£¬?£¬Sn)Ëù×é³É£¬Æ伯ºÏΪS£¬ÔòÓУº S={S1£¬S2£¬?£¬Sn}
ϵͳµÄÖî¶àÒªËØÓлúµØÁªÏµÔÚÒ»Æ𣬲¢ÇÒÒ»°ã¶¼ÊÇÒÔÁ½¸öÒªËØÖ®¼äµÄ¶þÔª¹ØϵΪ»ù´¡µÄ¡£Ëùν¶þÔª¹ØϵÊǸù¾ÝϵͳµÄÐÔÖʺÍÑо¿µÄÄ¿µÄËùÔ¼¶¨µÄÒ»ÖÖÐèÒªÌÖÂ۵ġ¢´æÔÚÓÚϵͳÖеÄÁ½¸öÒªËØ(Si¡¢Sj)Ö®¼äµÄ¹ØϵRij(¼ò¼ÇΪR)¡£Í¨³£ÓÐÓ°Ïì¹Øϵ¡¢Òò¹û¹Øϵ¡¢°üº¬¹Øϵ¡¢Á¥Êô¹ØϵÒÔ¼°¸÷ÖÖ¿ÉÒԱȽϵĹØϵ(Èç´óС¡¢ÏȺó¡¢
ÇáÖØ¡¢ÓÅÁÓµÈ)¡£¶þÔª¹ØϵÊǽṹ·ÖÎöÖÐËùÒªÌÖÂÛµÄϵͳ¹¹³ÉÒªËؼäµÄ»ù±¾¹Øϵ£¬Ò»°ãÓÐÒÔÏÂÈýÖÖÇéÐΣº
SiÓëSj¼äÓÐijÖÖ¶þÔª¹ØϵR£¬¼´SiRSj£» SiÓëSj¼äÎÞijÖÖ¶þÔª¹ØϵR£¬¼´SiRSj£»
?Sj¡£ SiÓëSj¼äµÄijÖÖ¶þÔª¹ØϵR²»Ã÷£¬¼´SiRÔÚͨ³£Çé¿öÏ£¬¶þÔª¹Øϵ¾ßÓд«µÝÐÔ£¬¼´£ºÈôSiRSj¡¢SjRSk£¬ÔòÓÐSiRSk(Si¡¢Sj¡¢SkΪϵͳµÄÈÎÒâ¹¹³ÉÒªËØ)¡£´«µÝÐÔ¶þÔª¹Øϵ·´Ó³Á½¸öÒªËصļä½ÓÁªÏµ£¬¿É¼Ç×÷R (tΪ´«µÝ´ÎÊý)£¬ÈçºÎ½«SiRSk¼Ç×÷SiRSk¡£
ÓÐʱ£¬¶ÔϵͳµÄÈÎÒâ¹¹³ÉÒªËØSiºÍSjÀ´Ëµ£¬¼ÈÓÐSiRSj£¬ÓÖÓÐSjRSi£¬ÕâÖÖÏ໥¹ØÁªµÄ¶þÔª¹Øϵ½ÐÇ¿Á¬½Ó¹Øϵ¡£¾ßÓÐÇ¿Á¬½Ó¹ØϵµÄ¸÷ÒªËØÖ®¼ä´æÔÚÌæ»»ÐÔ¡£
ÒÔϵͳҪËؼ¯ºÏS¼°¶þÔª¹ØϵµÄ¸ÅÄîΪ»ù´¡£¬Îª±ãÓÚ±í´ïËùÓÐÒªËؼäµÄ¹ØÁª·½Ê½£¬ÎÒÃÇ°Ñϵͳ¹¹³ÉÒªËØÖÐÂú×ãÆäÖÖ¶þÔª¹ØϵRµÄÒªËØSi¡¢SjµÄÒªËضÔ(Si£¬Sj)µÄ¼¯ºÏ£¬³ÆΪSÉϵĶþÔª¹Øϵ¼¯ºÏ£¬¼Ç×÷Rb£¬¼´ÓУº Rb={(Si,Sj)|Si¡¢Sj¡ÊS,SiRSj,i¡¢j=1,2,?,n}
ÇÒÔÚÒ»°ãÇé¿öÏ£¬(Si,Sj)ºÍ(Sj,Si)±íʾ²»Í¬µÄÒªËضԡ£
ÕâÑù£¬¡°ÒªËØSiºÍSjÖ®¼äÊÇ·ñ¾ßÓÐijÖÖ¶þÔª¹ØϵR¡±£¬Ò²¾ÍµÈ¼ÛÓÚ¡°ÒªËضÔ(Si,Sj)ÊÇ·ñÊôÓÚSÉϵĶþÔª¹Øϵ¼¯ºÏRb¡±¡£
ÖÁ´Ë£¬ÎÒÃǾͿÉÒÔÓÃϵͳµÄ¹¹³ÉÒªËؼ¯ºÏSºÍÔÚSÉÏÈ·¶¨µÄijÖÖ¶þÔª¹Øϵ¼¯ºÏRbÀ´¹²Í¬±íʾϵͳµÄijÖÖ»ù±¾½á¹¹¡£
Àý4¡ª1ijϵͳÓÉÆ߸öÒªËØ(S1¡¢S2¡¢?S7)×é³É¡£¾¹ýÁ½Á½ÅжÏÈÏΪ£ºS2Ó°ÏìS1¡¢S3Ó°ÏìS4¡¢S4Ó°ÏìS5¡¢S7Ó°ÏìS2¡¢S4ºÍS6Ï໥ӰÏì¡£ÕâÑù£¬¸ÃϵͳµÄ»ù±¾½á¹¹¿ÉÓÃÒªËؼ¯ºÏSºÍ¶þÔª¹Øϵ¼¯ºÏRbÀ´±í´ï£¬ÆäÖУº S={S1,S2,S3,S4,S5,S6,S7}
Rb={(S2,S1),(S3,S4),(S4,S5),(S7,S2),(S4,S6),(S6,S4)}
2¡¢ÏµÍ³½á¹¹µÄÓÐÏòͼ±í´ï 5 7 6 t
2
4 3 2 1 ͼ4¡ª4 Àý4¡ª1ÓÐÏòͼ¡¼TS)¡½
ÓÐÏòͼ(D)ÓɽڵãºÍÁ¬½Ó¸÷½ÚµãµÄÓÐÏò»¡(¼ýÏß)×é³É£¬¿ÉÓÃÀ´±í´ïϵͳµÄ½á¹¹¡£¾ßÌå·½·¨ÊÇ£ºÓýڵã±íʾϵͳµÄ¸÷¹¹³ÉÒªËØ£¬ÓÃÓÐÏò»¡±íʾҪËØÖ®¼äµÄ¶þÔª¹Øϵ¡£´Ó½Úµãi(Si)µ½j(Sj)µÄ×îС(ÉÙ)µÄÓÐÏò»¡Êý³ÆΪDÖнڵã¼äͨ·³¤¶È(·³¤)£¬Ò²¼´ÒªËØSiÓëSj¼ä¶þÔª¹ØϵµÄ´«µÝ´ÎÊý¡£ÔÚÓÐÏòͼÖУ¬´Óij½Úµã³ö·¢£¬ÑØ×ÅÓÐÏò»¡Í¨¹ýÆäËüijЩ½Úµã¸÷Ò»´Î¿É»Øµ½¸Ã½Úµãʱ£¬ÔÚDÖÐÐγɻØ·¡£³ÊÇ¿Á¬½Ó¹ØϵµÄÒªËؽڵã¼ä¾ßÓÐË«Ïò»Ø·¡£
±í´ïÀý4¡ª1¸ø³öµÄϵͳҪËؼ°Æä¶þÔª¹ØϵµÄÓÐÏòͼÈçͼ4¡ª4Ëùʾ¡£ÆäÖÐS3µ½S5¡¢S3µ½S6ºÍS7µ½S1µÄ·³¤¾ùΪ2¡£ÁíÍ⣬S4ºÍS6¼ä¾ßÓÐÇ¿Á¬½Ó¹Øϵ£¬S4ºÍS6Ï໥µ½´ï£¬ÔÚÆä¼äÐγÉË«Ïò»Ø·¡£ 3¡¢ÏµÍ³½á¹¹µÄ¾ØÕó±í´ï
(1)ÁÚ½Ó¾ØÕó
ÁÚ½Ó¾ØÕó(A)ÊDZíʾϵͳҪËؼä»ù±¾¶þÔª¹Øϵ»òÖ±½ÓÁªÏµÇé¿öµÄ·½Õó¡£ÈôA=(aij)n¡Án£¬ÔòÆ䶨ÒåʽΪ£º
aij= 1,SiRSj»ò(Si,Sj)¡ÊRb(Si¶ÔSjÓÐijÖÖ¶þÔª¹Øϵ)
0,SiRSj»ò(Si,Sj)¡ÊRb(Si¶ÔSjûÓÐijÖÖ¶þÔª¹Øϵ)
ÓÐÁ˱í´ïϵͳ½á¹¹µÄ¼¯ºÏª«(S,Rª«b)»òÓÐÏòͼ(D)£¬¾Í¿ÉºÜÈÝÒ׵ؽ«Aд³ö£¬·´Ö®ÒàÈ»¡£ÓëÀý4¡ª1ºÍͼ4¡ª4¶ÔÓ¦µÄÁÚ½Ó¾ØÕóÈçÏ£º S1 S2 S3 S4 S5 S6 S7 S1 ?0?S2 ?1S3 ?0S4 ?0A= ?S5 ?0S6 ?0S7 ??0?000000?000000??001000??000110? 000000??001000?100000??ºÜÃ÷ÏÔ£¬AÖС°1¡±µÄ¸öÊýÓëÀý4¡ª1ÖÐRbËù°üº¬µÄÒªËضÔÊýÄ¿ºÍͼ4¡ª4ÖÐÓÐÏò»¡µÄÌõÊýÏàµÈ£¬¾ùΪ6¡£ÔÚÁÚ½Ó¾ØÕóÖУ¬ÈôÓÐÒ»ÁÐ(ÈçµÚjÁÐ)ÔªËØȫΪ0£¬ÔòSjÊÇϵͳµÄÊäÈëÒªËØ£¬Èçͼ4¡ª4ÖеÄS3ºÍS7£»ÈôÓÐÒ»ÐÐ(ÈçµÚiÐÐ)ÔªËØȫΪ0£¬ÔòSiÊÇϵͳµÄÊä³öÒªËØ£¬Èçͼ4¡ª4ÖеÄS1ºÍS5¡£ (2)¿É´ï¾ØÕó
ÈôÔÚÒªËØSiºÍSj¼ä´æÔÚ×ÅijÖÖ´«µÝÐÔ¶þÔª¹Øϵ£¬»òÔÚÓÐÏòͼÉÏ´æÔÚ×ÅÓɽڵãiÖÁjµÄÓÐÏòͨ·ʱ£¬³ÆSiÊÇ¿ÉÒÔµ½´ïSjµÄ£¬»òÕß˵SjÊÇSi¿ÉÒÔµ½´ïµÄ¡£Ëùν¿É´ï¾ØÕó(M)£¬¾ÍÊDZíʾϵͳҪËØÖ®¼äÈÎÒâ´Î´«µÝÐÔ¶þÔª¹Øϵ»òÓÐÏòͼÉÏÁ½¸ö½ÚµãÖ®¼äͨ¹ýÈÎÒⳤµÄ·¾¶¿ÉÒÔµ½´ïÇé¿öµÄ·½Õó¡£ÈôM=(mij)n¡Án£¬ÇÒÔÚÎ޻طÌõ¼þϵÄ×î´ó·³¤»ò´«µÝ´ÎÊýΪr£¬¼´ÓÐ0¡Üt¡Ür£¬Ôò¿É´ï¾ØÕóµÄ¶¨ÒåʽΪ£º
mij= 1£¬SiRtSj (´æÔÚ×ÅiÖÁjµÄ·³¤×î´óΪrµÄͨ·)
0,SiRtSj (²»´æÔÚiÖÁjµÄͨ·)
µ±t=1ʱ£¬±íʾ»ù±¾µÄ¶þÔª¹Øϵ£¬M¼´ÎªA£»µ±t=0ʱ£¬±íʾSi×ÔÉíµ½´ï£¬»òSiRSi£¬Ò²³Æ·´ÉäÐÔ¶þÔª¹Øϵ£»µ±t¡Ý2ʱ£¬±íʾ´«µÝÐÔ¶þÔª¹Øϵ¡£
¾ØÕóAºÍMµÄÔªËؾùΪ¡°1¡±»ò¡°0¡±£¬ÊÇn¡Án½×0¡ª1¾ØÕó£¬ÇÒ·ûºÏ²¼¶û´úÊýµÄÔËËã¹æÔò£¬¼´£º0+0=0,0+1=1,1+0=1,1+1=1,0¡Á0=0,0¡Á1=0,1¡Á0=0,1¡Á1=1¡£Í¨¹ý¶ÔÁÚ½Ó¾ØÕóAµÄÔËË㣬¿ÉÇó³öϵͳҪËصĿɴï¾ØÕóM£¬Æä¼ÆË㹫ʽΪ£º M=(A+I)r (4¡ª1)
ÆäÖÐIΪÓëAͬ½×´ÎµÄµ¥Î»¾ØÕó(¼´ÆäÖ÷¶Ô½ÇÏßÔªËØȫΪ¡°1¡±£¬ÆäÓàÔªËØΪ¡°0¡±)£¬·´Ó³ÒªËØ×ÔÉíµ½´ï£»×î´ó´«µÝ´ÎÊý(·³¤)r¸ù¾ÝÏÂʽȷ¶¨£º (A+I)¡Ù(A+I)¡Ù(A+I)¡Ù?¡Ù(A+I)¡Ù(A+I)=(A+I)=?=(A+I) (4¡ª2) ÒÔÓëÀý4¡ª1ºÍͼ4¡ª4¶ÔÓ¦µÄÁÚ½Ó¾ØÕóΪÀýÓУº S1 S2 S3 S4 S5 S6 S7
?1S1 ?1?S2 ?0S3 ? A+I= S4 ?0S5 ?0?S6 ?0S7 ??0000000?100001??011000??001110? 000100??001010?100001??2
3
r-1
r
r+1
n
ÆäÖÐÖ÷¶Ô½ÇÏßÉϵġ°1¡±±íʾÖîÒªËØͨ¹ýÁã²½(×ÔÉí)µ½´ïÇé¿ö(µ¥Î»¾ØÕóI)£¬ÆäÓà¡°1¡±±íʾҪËؼäͨ¹ýÒ»²½(Ö±½Ó)µ½´ïÇé¿ö(ÁÚ½Ó¾ØÕóA)¡£
S1 S2 S3 S4 S5 S6 S7
?1S1 ?1S2 ??0S3 ?(A+I)2=A2+A+I= S4 ?0S5 ?0?S6 ?0S7 ??????001001000000100000?0000??1`??????0??1110? 0100??1???10?0001???ÆäÖдøԲȦµÄ¡°1¡±±íʾҪËؼäͨ¹ýÁ½²½(¼ä½Ó)µ½´ïÇé¿ö(¾ØÕóA2)¡£°´ÕÕÇ°Êö²¼¶û´úÊýµÄÔËËã¹æÔò£¬ÔÚÔʽ(A+I)2µÄÕ¹¿ªÖÐÀûÓÃÁËA+A=AµÄ¹Øϵ¡£ ½øÒ»²½¼ÆËã·¢ÏÖ£º(A+I)3=(A+I)2¡£ÓÉ(4¡ª2)ʽ¼´ÓÐr=2¡£ ÕâÑù£¬¸ù¾Ý(4¡ª1)ʽ£¬ÓëÀý4¡ª1ºÍͼ4¡ª4¶ÔÓ¦µÄ¿É´ï¾ØÕóΪ£º S1 S2 S3 S4 S5 S6 S7
?1S1 ?1S2 ??0S3 ?M=(A+I)2= S4 ?0S5 ?0?S6 ?0S7 ??1000000?100000??011110??001110? 000100??001110?100001?? (3)ÆäËü¾ØÕó
ÔÚÁÚ½Ó¾ØÕóºÍ¿É´ï¾ØÕóµÄ»ù´¡ÉÏ£¬»¹ÓÐÆäËü±í´ïϵͳ½á¹¹²¢ÓÐÖúÓÚʵÏÖϵͳ½á¹¹Ä£ÐÍ»¯µÄ¾ØÕóÐÎʽ£¬ÈçËõ¼õ¾ØÕ󡢹ǼܾØÕóµÈ¡£
¢ÙËõ¼õ¾ØÕó
¸ù¾ÝÇ¿Á¬½ÓÒªËصĿÉÌæ»»ÐÔ£¬ÔÚÒÑÓеĿɴï¾ØÕóMÖУ¬½«¾ßÓÐÇ¿Á¬½Ó¹ØϵµÄÒ»×éÒªËØ¿´×÷Ò»¸öÒªËØ£¬±£ÁôÆäÖеÄij¸ö´ú±íÒªËØ£¬É¾³ýµôÆäÓàÒªËؼ°ÆäÔÚMÖеÄÐкÍÁУ¬¼´µÃµ½¸Ã¿É´ï¾ØÕóMµÄËõ¼õ¾ØÕóM¡ä¡£ÈçÔÀý¿É´ï¾ØÕóµÄËõ¼õ¾ØÕóΪ£º
S1 S2 S3 S4 S5 S7 S1 ?1?S2 ?1S3 ?0S4 ?0M¡ä= ?S5 ?0S7 ??1??0000010000001110110010000?????? ?????10001¢Ú¹Ç¼Ü¾ØÕó
¶ÔÓÚ¸ø¶¨ÏµÍ³£¬AµÄ¿É´ï¾ØÕóMÊÇΨһµÄ£¬µ«ÊµÏÖijһ¿É´ï¾ØÕóMµÄÁÚ½Ó¾ØÕóA¿ÉÒÔ¾ßÓжà¸ö¡£ÎÒÃÇ°ÑʵÏÖijһ¿É´ï¾ØÕóM¡¢¾ßÓÐ×îС¶þÔª¹Øϵ¸öÊý(¡°1¡±ÔªËØ×îÉÙ)µÄÁÚ½Ó¾ØÕó½ÐMµÄ×îСʵÏÖ¶þÔª¹Øϵ¾ØÕ󣬻ò³Æ֮Ϊ¹Ç¼Ü¾ØÕ󣬼Ç×÷A¡ä¡£
ϵͳ½á¹¹µÄÈýÖÖ»ù±¾±í´ï·½Ê½Ï໥¶ÔÓ¦£¬¸÷ÓÐÌØÉ«¡£Óü¯ºÏÀ´±í´ïϵͳ½á¹¹¸ÅÄîÇå³þ£¬ÔÚ¸÷ÖÖ±í´ï·½Ê½Öд¦ÓÚ»ù´¡µØλ£»ÓÐÏòͼÐÎʽ½ÏΪֱ¹Û¡¢Ò×ÓÚÀí½â£»¾ØÕóÐÎʽ±ãÓÚͨ¹ýÂß¼ÔËË㣬ÓÃÊýѧ·½·¨¶Ôϵͳ½á¹¹½øÐзÖÎö´¦Àí¡£ÒÔËüÃÇΪ»ù´¡ºÍ¹¤¾ß£¬Í¨¹ý²ÉÓø÷ÖÖ¼¼Êõ£¬¿ÉʵÏÖ¸´ÔÓϵͳ½á¹¹µÄÄ£ÐÍ»¯¡£ (Èý)³£ÓÃϵͳ½á¹¹Ä£ÐÍ»¯¼¼Êõ
ϵͳ½á¹¹Ä£ÐÍ»¯¼¼ÊõÊÇÒÔ¸÷ÖÖ´´ÔìÐÔ¼¼ÊõΪ»ù´¡µÄϵͳÕûÌå½á¹¹µÄ¾ö¶¨¼¼Êõ¡£ËüÃÇͨ¹ý̽Ѱϵͳ¹¹³ÉÒªËØ¡¢¶¨ÒåÒªËؼä¹ØÁªµÄÒâÒå¡¢¸ø³öÒªËؼäÒÔ¶þÔª¹ØϵΪ»ù´¡µÄ¾ßÌå¹Øϵ£¬²¢ÇÒ½«ÆäÕûÀí³Éͼ¡¢¾ØÕóµÈ½ÏΪֱ¹Û¡¢Ò×ÓÚÀí½âºÍ±ãÓÚ´¦ÀíµÄÐÎʽ£¬Öð²½½¨Á¢Æð¸´ÔÓϵͳµÄ½á¹¹Ä£ÐÍ¡£³£ÓõÄϵͳ½á¹¹Ä£ÐÍ»¯¼¼ÊõÓУº¹ØÁªÊ÷·¨¡¢½âÊͽṹģÐÍ»¯¼¼Êõ¡¢ÏµÍ³¶¯Á¦Ñ§½á¹¹Ä£ÐÍ»¯¼¼ÊõµÈ£¬ÆäÖнâÊͽṹģÐÍ»¯(ISM)¼¼ÊõÊÇ×î»ù±¾ºÍ×î¾ßÌØÉ«µÄϵͳ½á¹¹Ä£ÐÍ»¯¼¼Êõ¡£
ISM¼¼ÊõÊÇÃÀ¹úJ¡¤N¡¤ÎַƶûµÂ½ÌÊÚÓÚ1973Äê×÷Ϊ·ÖÎö¸´ÔÓµÄÉç»á¾¼Ãϵͳ½á¹¹ÎÊÌâµÄÒ»ÖÖ·½·¨¶ø¿ª·¢µÄ¡£Æä»ù±¾Ë¼ÏëÊÇ£ºÍ¨¹ý¸÷ÖÖ´´ÔìÐÔ¼¼Êõ£¬ÌáÈ¡ÎÊÌâµÄ¹¹³ÉÒªËØ£¬ÀûÓÃÓÐÏòͼ¡¢¾ØÕóµÈ¹¤¾ßºÍ¼ÆËã»ú¼¼Êõ£¬¶ÔÒªËؼ°ÆäÏ໥¹ØϵµÈÐÅÏ¢½øÐд¦Àí£¬×îºóÓÃÎÄ×Ö¼ÓÒÔ½âÊÍ˵Ã÷£¬Ã÷È·ÎÊÌâµÄ²ã´ÎºÍÕûÌå½á¹¹£¬Ìá¸ß¶ÔÎÊÌâµÄÈÏʶºÍÀí½â³Ì¶È¡£¸Ã¼¼ÊõÓÉÓÚ¾ßÓв»Ðè¸ßÉîµÄÊýѧ֪ʶ¡¢Ä£ÐÍÖ±¹ÛÇÒÓÐÆô·¢ÐÔ¡¢¿ÉÎüÊÕ¸÷ÖÖÓйØÈËÔ±²Î¼ÓµÈÌص㣬Òò¶ø¹ã·ºÊÊÓÃÓÚÈÏʶºÍ´¦Àí¸÷ÀàÉç»á¾¼Ã
ϵͳµÄÎÊÌâ¡£ISMµÄ»ù±¾¹¤×÷ÔÀíÈçͼ4¡ª5Ëùʾ¡£ Òâʶ SjRSj? ÒªËؼ°Æä¹Øϵ¼¯ºÏ ÍÆ¶Ï ¿É´ï¾ØÕó ·Ö¼ì ¹Ç¼Ü¾ØÕó ×÷ͼ Ä£ÐÍ ÐÞÕý ½âÊͽṹ£¨ÈË£© Ëã»ú ¼Æ½âÊÍ µÝ½×½á¹¹Ä£ÐÍ £¨¶à¼¶µÝ½×ÓÐÏòͼ£© ·ÖÎö±¨¸æ Ä£ÐÍ Í¼4¡ª5 ISM¹¤×÷ÔÀíͼ
ÓÉͼ4¡ª5¿ÉÖª£¬ÊµÊ©ISM¼¼Êõ£¬Ê×ÏÈÊÇÌá³öÎÊÌ⣬×齨ISMʵʩС×飻½Ó×ŲÉÓü¯Ìå´´ÔìÐÔ¼¼Êõ£¬ËѼ¯ºÍ³õ²½ÕûÀíÎÊÌâµÄ¹¹³ÉÒªËØ£¬²¢É趨ijÖÖ±ØÐ뿼ÂǵĶþÔª¹Øϵ(ÈçÒò¹û¹Øϵ)£¬¾Ð¡×é³ÉÔ±¼°ÓëÆäËûÓйØÈËÔ±µÄÌÖÂÛ£¬ÐγɶÔÎÊÌâ³õ²½ÈÏʶµÄÒâʶ(¹¹Ë¼)Ä£ÐÍ¡£ÔÚ´Ë»ù´¡ÉÏ£¬ÊµÏÖÒâʶģÐ͵ľßÌ廯¡¢¹æ·¶»¯¡¢ÏµÍ³»¯ºÍ½á¹¹Ä£ÐÍ»¯£¬¼´½øÒ»²½Ã÷È·¶¨Òå¸÷ÒªËØ£¬Í¨¹ýÈË»ú¶Ô»°£¬Åжϸ÷ÒªËØÖ®¼äµÄ¶þÔª¹ØϵÇé¿ö(¼´SiRSj?)£¬ÐγÉijÖÖÐÎʽµÄ¡°ÐÅÏ¢¿â¡±£»¸ù¾ÝÒªËؼä¹ØϵµÄ´«µÝÐÔ£¬Í¨¹ý¶ÔÁÚ½Ó¾ØÕóµÄ¼ÆËã»òÂß¼Íƶϣ¬µÃµ½¿É´ï¾ØÕó£»½«¿É´ï¾ØÕó½øÐзֽ⡢ËõÔ¼ºÍ¼ò»¯´¦Àí£¬µÃµ½·´Ó³ÏµÍ³µÝ½×½á¹¹µÄ¹Ç¼Ü¾ØÕ󣬾ݴ˻æÖÆÒªËؼä¶à¼¶µÝ½×ÓÐÏòͼ£¬Ðγɵݽ׽ṹģÐÍ£»Í¨¹ý¶ÔÒªËصĽâÊÍ˵Ã÷£¬½¨Á¢Æð·´Ó³ÏµÍ³ÎÊÌâijÖÖ¶þÔª¹ØϵµÄ½âÊͽṹģÐÍ¡£×îºó£¬½«½âÊͽṹģÐÍÓëÈËÃÇÒÑÓеÄÒâʶģÐͽøÐбȽϣ¬Èç²»Ïà·ûºÏ£¬Ò»·½Ãæ¿É¶ÔÓйØÒªËؼ°Æä¶þÔª¹ØϵºÍ½âÊͽṹģÐ͵Ľ¨Á¢½øÐÐÐÞÕý£»¸üÖØÒªµÄÊÇ£¬ÈËÃÇͨ¹ý¶Ô½âÊͽṹģÐ͵ÄÑо¿ºÍѧϰ£¬¿É¶ÔÔÓеÄÒâʶģÐÍÓÐËùÆô·¢ºÍÐÞÕý¡£¾¹ý·´À¡¡¢±È½Ï¡¢ÐÞÕý¡¢Ñ§Ï°£¬×îÖյõ½Ò»¸öÁîÈËÂúÒâ¡¢¾ßÓÐÆô·¢ÐÔºÍÖ¸µ¼ÒâÒåµÄ½á¹¹·ÖÎö½á¹û¡£
ͨ¹ý¶Ô¿É´ï¾ØÕóµÄ´¦Àí£¬½¨Á¢ÏµÍ³ÎÊÌâµÄµÝ½á¹¹Ä£ÐÍ£¬ÕâÊÇISM¼¼ÊõµÄºËÐÄ
ÄÚÈÝ¡£¸ù¾ÝÎÊÌâ¹æÄ£ºÍ·ÖÎöÌõ¼þ£¬¿ÉÔÚÕÆÎÕ»ù±¾ÔÀí¼°Æä¹æ·¶·½·¨µÄ»ù´¡ÉÏ£¬²ÉÓöàÖÖÊֶΡ¢Ñ¡Ôñ²»Í¬·½·¨À´Íê³É´ËÏ×÷¡£ ¶þ¡¢½¨Á¢µÝ½×½á¹¹Ä£Ð͵Ĺ淶·½·¨
½¨Á¢·´Ó³ÏµÍ³ÎÊÌâÒªËؼä²ã´Î¹ØϵµÄµÝ½×½á¹¹Ä£ÐÍ£¬¿ÉÔÚ¿É´ï¾ØÕóMµÄ»ù´¡ÉϽøÐУ¬ÇÒÒ»°ãÒª¾¹ýÇøÓò»®·Ö¡¢¼¶Î»»®·Ö¡¢¹Ç¼Ü¾ØÕóÌáÈ¡ºÍ¶à¼¶µÝ½×ÓÐÏòͼ»æÖƵÈËĸö½×¶Î¡£ÕâÊǽ¨Á¢µÝ½×½á¹¹Ä£Ð͵Ļù±¾·½·¨¡£ÏÖÒÔÀý4¡ª1ËùʾÎÊÌâΪÀý˵Ã÷¡£Óëͼ4¡ª4¶ÔÓ¦µÄ¿É´ï¾ØÕó(ÆäÖн«Si¼ò¼ÇΪi)Ϊ£º 1 2 3 4 5 6 7
?11 ?12 ??03 ?M= 4 ?05 ?0?6 ?07 ??1000000?100000??011110??001110? 000100??001110?100001??
1¡¢ÇøÓò»®·Ö
ÇøÓò»®·Ö¼´½«ÏµÍ³µÄ¹¹³ÉÒªËؼ¯ºÏS£¬·Ö¸î³É¹ØÓÚ¸ø¶¨¶þÔª¹ØϵRµÄÏ໥¶ÀÁ¢µÄÇøÓòµÄ¹ý³Ì¡£
Ϊ´Ë£¬ÐèÒªÊ×ÏÈÒÔ¿É´ï¾ØÕóMΪ»ù´¡£¬»®·ÖÓëÒªËØSi(i=1,2,?,n)Ïà¹ØÁªµÄϵͳҪËصÄÀàÐÍ£¬²¢ÕÒ³öÔÚÕû¸öϵͳ(ËùÓÐÒªËؼ¯ºÏS)ÖÐÓÐÃ÷ÏÔÌØÕ÷µÄÒªËØ¡£ÓйØÒªËؼ¯ºÏµÄ¶¨ÒåÈçÏ£º (1)¿É´ï¼¯R(Si)
ϵͳҪËØSiµÄ¿É´ï¼¯ÊÇÔÚ¿É´ï¾ØÕó»òÓÐÏòͼÖÐÓÉSi¿Éµ½´ïµÄÖîÒªËØËù¹¹³ÉµÄ¼¯ºÏ£¬¼ÇΪR(Si)¡£Æ䶨ÒåʽΪ£º
R(Si)={Sj|Sj¡ÊS,mij=1,j=1,2,?,n} i=1,2,?,n
ÈçÔÚ¸ø³öµÄ¿É´ï¾ØÕóÖÐÓУºR(S1)={S1},R(S2)={S1,S2}£¬R(S3)={S3,S4,S5,S6},R(S4)=R(S6)={S4,S5,S6},R(S5)={S5},R(S7)={S1,S2,S7}¡£
(2)ÏÈÐм¯A(Si)
ϵͳҪËØSiµÄÏÈÐм¯ÊÇÔÚ¿É´ï¾ØÕó»òÓÐÏòͼÖпɵ½´ïSiµÄÖîϵͳҪËØËù¹¹³ÉµÄ¼¯ºÏ£¬¼ÇΪA(Si)¡£Æ䶨ÒåʽΪ£º
A(Si)={Sj|Sj¡ÊS,mji=1,j=1,2,?,n}i=1,2,?,n
Èç
ÔÚ
¸ø
³ö
µÄ
¿É
´ï
¾Ø
Õó
ÖÐ
ÓÐ
£º
A(S1)={S1,S2,S7},A(S2)={(S2,S7),A(S3)}={S3},A(S4)=A(S6)={S3,S4,S6},A(S5)={S3,S4,S5,S6},A(S7)={S7}¡£ (3)¹²Í¬¼¯C(Si)
ϵͳҪËØSiµÄ¹²Í¬¼¯ÊÇSiÔڿɴOºÍÏÈÐм¯µÄ¹²Í¬²¿·Ö£¬¼´½»¼¯£¬¼ÇΪC(Sª«i)¡£Æ䶨ÒåʽΪ£º
C(£Ói)={Sj|£Ój¡ÊS,mij=1, mij =1,j=1,2,,n} i=1,2£¬¡ ,nÈ磺
C(S1)={S1},C(S2)={S2},C(S3)={S3},C(S4)=C(S6)={S4,S6},C(S5)={S5},C(S7)={S7}¡£
ϵͳҪËØSiµÄ¿É´ï¼¯R(Si)¡¢ÏÈÐм¯A(Si)¡¢¹²Í¬¼¯C(Si)Ö®¼äµÄ¹ØϵÈçͼ4¡ª6Ëùʾ¡£
(4)Æðʼ¼¯B(S)ºÍÖÕÖ¹¼¯E(S)
ͼ4¡ª6 ¿É´ï¼¯¡¢ÏÈÐм¯¡¢¹²Í¬¼¯¹ØϵʾÒâͼ
ϵͳҪËؼ¯ºÏSµÄÆðʼ¼¯ÊÇÔÚSÖÐÖ»Ó°Ïì(µ½´ï)ÆäËûÒªËضø²»ÊÜÆäËûÒªËØÓ°Ïì(²»±»ÆäËûÒªËص½´ï)µÄÒªËØËù¹¹³ÉµÄ¼¯ºÏ£¬¼ÇΪB(S)¡£B(S)ÖеÄÒªËØÔÚÓÐÏòͼÖÐÖ»ÓмýÏßÁ÷³ö£¬¶øÎÞ¼ýÏßÁ÷È룬ÊÇϵͳµÄÊäÈëÒªËØ¡£Æ䶨ÒåʽΪ£ºB(S)={Si|Si¡ÊS,C(Si)=A(Si),i=1,2,?,n}¡£
ÈçÔÚÓëͼ4¡ª4Ëù¶ÔÓ¦µÄ¿É´ï¾ØÕóÖУ¬B(S)={S3,S7}¡£
R(Si) A(Sj) C(Sj) Sj µ±SiΪSµÄÆðʼ¼¯(ÖÕÖ¹¼¯)ÒªËØʱ£¬Ï൱ÓÚʹͼ4¡ª6ÖеÄÒõÓ°²¿·ÖC(Si)¸²¸Çµ½ÁËÕû¸öA(Si)(R(Si))ÇøÓò¡£
ÕâÑù£¬ÒªÇø·ÖϵͳҪËؼ¯ºÏSÊÇ·ñ¿É·Ö¸î£¬Ö»ÒªÑо¿ÏµÍ³Æðʼ¼¯B(S)ÖеÄÒªËؼ°Æä¿É´ï¼¯ÒªËØ(»òϵͳÖÕÖ¹¼¯E(S)ÖеÄÒªËؼ°ÆäÏÈÐм¯ÒªËØ)ÄÜ·ñ·Ö¸î(ÊÇ·ñÏà¶Ô¶ÀÁ¢)¾ÍÐÐÁË¡£ÀûÓÃÆðʼ¼¯B(S)ÅжÏÇøÓòÄÜ·ñ»®·ÖµÄ¹æÔòÈçÏ£º ÔÚB(S)ÖÐÈÎÈ¡Á½¸öÒªËØbu¡¢bv£º
¢ÙÈç¹ûR(bu)¡ÉR(bv)¡Ù¦µ(¦µÎª¿Õ¼¯)£¬Ôòbu¡¢bv¼°R(bu)¡¢R(bv)ÖеÄÒªËØÊôͬһÇøÓò¡£Èô¶ÔËùÓÐuºÍv¾ùÓд˽á¹û(¾ù²»Îª¿Õ¼¯)£¬ÔòÇøÓò²»¿É·Ö£»
¢ÚÈç¹ûR(bu)¡ÉR(bv)=¦µ£¬Ôòbu¡¢bv¼°R(bu)¡¢R(bv)ÖеÄÒªËز»ÊôͬһÇøÓò£¬ÏµÍ³ÒªËؼ¯ºÏSÖÁÉٿɱ»»®·ÖΪÁ½¸öÏà¶Ô¶ÀÁ¢µÄÇøÓò¡£
ÀûÓÃÖÕÖ¹¼¯E(S)À´ÅжÏÇøÓòÄÜ·ñ»®·Ö£¬Ö»ÒªÅж¨¡°A(eu)¡ÉA(ev)¡±(eu¡¢evΪE(S)ÖеÄÈÎÁ½¸öÒªËØ)ÊÇ·ñΪ¿Õ¼¯¼´¿É¡£
ÇøÓò»®·ÖµÄ½á¹û¿É¼ÇΪ£º¡Ç(S)=P1,P2,?,Pk,?,Pm(ÆäÖÐPkΪµÚk¸öÏà¶Ô¶ÀÁ¢ÇøÓòµÄÒªËؼ¯ºÏ)¡£¾¹ýÇøÓò»®·ÖºóµÄ¿É´ï¾ØÕóΪ¿é¶Ô½Ç¾ØÕó(¼Ç×÷M(P))¡£ Ϊ¶Ô¸ø³öµÄÓëͼ4¡ª4Ëù¶ÔÓ¦µÄ¿É´ï¾ØÕó½øÐÐÇøÓò»®·Ö£¬¿ÉÁгöÈÎÒ»ÒªËØSi(¼ò¼Ç×÷i,i=1,2,?£¬7)µÄ¿É´ï¼¯R(Si)¡¢ÏÈÐм¯A(Si)ºÍ¹²Í¬¼¯C(Si)£¬²¢¾Ý´Ëд³öϵͳҪËؼ¯ºÏµÄÆðʼ¼¯B(S)£¬Èç±í4¡ª1Ëùʾ¡£ Si 1 2 3 4 5 6 7 R(Si) 1 1,2 3,4,5,6 4,5,6 5 4,5,6 1,2,7 A(Si) 1,2,7 2,7 3 3,4,6 3,4,5,6 3,4,6 7 C(Si) 1 2 3 4,6 5 4,6 7 B(S) 3 7 ±í4¡ª1¿É´ï¼¯¡¢ÏÈÐм¯¡¢¹²Í¬¼¯ºÍÆðʼ¼¯Àý±í ÒòB(S)={S3,S7}
ÇÒÓÐR(S3)¡ÉR(S7)={S3,S4,S5,S6}¡É{S1,S2,S7}=¦µ
ËùÒÔ£¬S3¼°S4¡¢S5¡¢S6ºÍS7¼°S1¡¢S2·ÖÊôÁ½¸öÏà¶Ô¶ÀÁ¢µÄÇøÓò£¬¼´ÓУº¡Ç(S
)=P1,P2={S3,S4,S5,S6},{S1,S2,S7}¡£ ÕâʱµÄ¿É´ï¾ØÕóM±äΪÈçϵĿé¶Ô½Ç¾ØÕó£º 3 4 5 6 1 2 7
3 ?1?4 ?0P1
5 ?06 ?0M(P)= P2
11111101011100?1 ??2 ?7 ??101111?????? 0??0?1??2¡¢¼¶Î»»®·Öª«
ÇøÓòÄڵļ¶Î»»®·Ö£¬¼´È·¶¨Ä³ÇøÓòÄÚ¸÷ÒªËØËù´¦²ã´ÎµØλµÄ¹ý³Ì¡£ÕâÊǽ¨Á¢¶à¼¶µÝ½×½á¹¹Ä£Ð͵Ĺؼü¹¤×÷¡£
ÉèPÊÇÓÉÇøÓò»®·ÖµÃµ½µÄijÇøÓòÒªËؼ¯ºÏ£¬ÈôÓÃL1¡¢L2¡¢?Ll±íʾ´Ó¸ßµ½µÍµÄ¸÷¼¶ÒªËؼ¯ºÏ(ÆäÖÐlΪ×î´ó¼¶Î»Êý)£¬Ôò¼¶Î»»®·ÖµÄ½á¹û¿Éд³É£º¡Ç(P)=L1,L2,?,Ll¡£
ijϵͳҪËؼ¯ºÏµÄ×î¸ß¼¶ÒªËؼ´¸ÃϵͳµÄÖÕÖ¹¼¯ÒªËØ¡£¼¶Î»»®·ÖµÄ»ù±¾×÷·¨ÊÇ£ºÕÒ³öÕû¸öϵͳҪËؼ¯ºÏµÄ×î¸ß¼¶ÒªËØ(ÖÕÖ¹¼¯ÒªËØ)ºó£¬¿É½«ËüÃÇÈ¥µô£¬ÔÙÇóÊ£ÓàÒªËؼ¯ºÏ(Ðγɲ¿·Öͼ)µÄ×î¸ß¼¶ÒªËØ£¬ÒÀ´ÎÀàÍÆ£¬Ö±µ½È·¶¨³ö×îµÍÒ»¼¶ÒªËؼ¯ºÏ(¼´Ll)¡£
Ϊ´Ë£¬ÁîL0=¦µ(×î¸ß¼¶ÒªËؼ¯ºÏΪL1£¬Ã»ÓÐÁ㼶ҪËØ)£¬ÔòÓУº
L1={Si|Si¡ÊP-L0,C0(Si)=R0(Si),i=1,2,?,n} L2={Si|Si¡ÊP-L0-L1,C1(Si)=R1(Si),i£¼n£½
Lk={Si|Si¡ÊP-L0-L1-?-Lk-1,Ck-1(Si)=Rk-1(Si),i£¼n£½ (4¡ª3) ʽ(4¡ª3)ÖеÄCk-1(Si)ºÍRk-1(£Ói)ÊÇÓɼ¯ºÏP-L0-L1-?-Lk-1ÖеÄÒªËØÐγɵÄ×Ó¾ØÕó(²¿·Öͼ)ÇóµÃµÄ¹²Í¬¼¯ºÍ¿É´ï¼¯¡£
¾¹ý¼¶Î»»®·ÖºóµÄ¿É´ï¾ØÕó±äΪÇøÓò¿éÈý½Ç¾ØÕ󣬼ÇΪM(L)¡£ Èç¶ÔÔÀýÖÐP1={S3,S4,S5,S6}½øÐм¶Î»»®·ÖµÄ¹ý³ÌʾÓÚ±í4¡ª2¡£ ¶Ô¸ÃÇøÓò½øÐм¶Î»»®·ÖµÄ½á¹ûΪ£º
¦°(P1)=L1,L2,L3={S5},{S4,S6},{S3}
ͬÀí¿ÉµÃ¶ÔP2={S1,S2,S7}½øÐм¶Î»»®·ÖµÄ½á¹ûΪ£º ¦°(P2)=L1,L2,L3={S1},{S2},{S7} ±í4¡ª2 ¼¶Î»»®·Ö¹ý³ÌÀý±í
ÒªËؼ¯ºÏ Si R(S) A(S) C(S) C(S)= R(S) P1-L0 3 4 5 6 P1-L0-L1 3,4 6 3,4,5,6 4,5,6 5 4,5,6 3,4,6 4,6 4,6 P1-L0-L1- L2 3 3 3 3,4,6 3,4,5,6 3,4,6 3 3,4,6 3,4,6 3 3 4,6 5 4,6 3 4,6 4,6 3 L3={S3} L2={S4,S6} L1 ={S5} ¦°(P1) ÕâʱµÄ¿É´ï¾ØÕóΪ£º
5 4 6 3 1 2 7
?1?15 L1 ?4 ?1L2 ?6 M(L)= L3 ?1?3 ?L1 ?1 L2 ?2
?L3
7
00011011011100101111?????? 0??0?1??3¡¢ÌáÈ¡¹Ç¼Ü¾ØÕó
ÌáÈ¡¹Ç¼Ü¾ØÕó£¬ÊÇͨ¹ý¶Ô¿É´ï¾ØÕóM(L)µÄËõÔ¼ºÍ¼ì³ö£¬½¨Á¢ÆðM(L)µÄ×îСʵÏÖ¾ØÕ󣬼´¹Ç¼Ü¾ØÕóA¡ä¡£ÕâÀïµÄ¹Ç¼Ü¾ØÕó£¬Ò²¼´ÎªMµÄ×îСʵÏֶ༶µÝ½×½á¹¹¾ØÕ󡣶Ծ¹ýÇøÓòºÍ¼¶Î»»®·ÖºóµÄ¿É´ï¾ØÕóM(L)µÄËõ¼ì¹²·ÖÈý²½£¬¼´£º
µÚÒ»²½£º¼ì²é¸÷²ã´ÎÖеÄÇ¿Á¬½ÓÒªËØ£¬½¨Á¢¿É´ï¾ØÕóM(L)µÄËõ¼õ¾ØÕóM¡ä(L)¡£ Èç¶ÔÔÀýM(L)ÖеÄÇ¿Á¬½ÓÒªËؼ¯ºÏ{S4£¬S6}×÷Ëõ¼õ´¦Àí(°ÑS4×÷Ϊ´ú±íÒªËØ£¬È¥µôS6)ºóµÄеľØÕóΪ£º
5 4 3 1 2 7
?1?1??0M¡ä(L)= ??L1 1 ?L2 2 ??L3 7 ?L1
L2 L3
5 4 3
00101110011010????? 0?0??1??
µÚ¶þ²½£ºÈ¥µôM¡ä(L)ÖÐÒѾßÓÐÁÚ½Ó¶þÔª¹ØϵµÄÒªËؼäµÄÔ½¼¶¶þÔª¹Øϵ£¬µÃµ½¾½øÒ»²½¼ò»¯ºóµÄеľØÕóM¡å(L)¡£
ÈçÔÚÔÀýµÄM¡ä(L)ÖУ¬ÒÑÓеڶþ¼¶ÒªËØ(S4£¬S2)µ½µÚÒ»¼¶ÒªËØ(S5£¬S1)ºÍµÚÈý¼¶ÒªËØ(S3£¬S7)µ½µÚ¶þ¼¶ÒªËصÄÁÚ½Ó¶þÔª¹Øϵ£¬¼´S4RS5¡¢S2RS1ºÍS3RS4¡¢S7RS2£¬¹Ê¿ÉÈ¥µôµÚÈý¼¶ÒªËص½µÚÒ»¼¶ÒªËصÄÔ½¼¶¶þÔª¹Øϵ¡°S3R2S5¡±ºÍ¡°S7 R2S1¡±£¬¼´½«M¡ä(L)ÖÐ3¡ú5ºÍ7¡ú1µÄ¡°1¡±¸ÄΪ¡°0¡±£¬µÃ£º 5 4 3 1 2 7
?0?1??0M¡å(L)= ?? 1 ? 2 ?? 7 ?
5 4 3
00001000010010????? 0?0??0??µÚÈý²½£º½øÒ»²½È¥µôM¡å(L)ÖÐ×ÔÉíµ½´ïµÄ¶þÔª¹Øϵ£¬¼´¼õÈ¥µ¥Î»¾ØÕ󣬽«M¡å(L)Ö÷¶Ô½ÇÏßÉϵġ°1¡±È«±äΪ¡°0¡±£¬µÃµ½¾¼ò»¯ºó¾ßÓÐ×îÉÙ¶þÔª¹Øϵ¸öÊýµÄ¹Ç¼Ü¾ØÕóA¡ä¡£Èç¶ÔÔÀýÓУº
5 4 3 1 2 7
?0?1??0A¡ä=M¡å(L)-I= ?? 1 ? 2 ?? 7 ?
5 4 3
00001000010010????? 0?0??0??
4¡¢»æÖƶ༶µÝ½×ÓÐÏòͼD(A¡ä)
¸ù¾Ý¹Ç¼Ü¾ØÕóA¡ä£¬»æÖƳö¶à¼¶µÝ½×ÓÐÏòͼD(A¡ä)£¬¼´½¨Á¢ÆðÁËϵͳҪËصĵݽ׽ṹģÐÍ¡£»æͼһ°ã·ÖΪÈçÏÂÈý²½£º µÚÒ»²½£º·ÖÇøÓò´ÓÉϵ½ÏÂÖð¼¶ÅÅÁÐϵͳ¹¹³ÉÒªËØ£» S7 S3 ͼ4¡ª7 µÝ½×½á¹¹Ä£ÐÍÀýͼ
µÚ¶þ²½£ºÍ¬¼¶¼ÓÈ뱻ɾµôµÄÓëijҪËØ(ÈçÔÀýÖÐS4)ÓÐÇ¿Á¬½Ó¹ØϵµÄÒªËØ(ÈçS6)£¬¼°±íÕ÷ËüÃÇÏ໥¹ØϵµÄÓÐÏò»¡£»
µÚÈý²½£º°´A¡äËùʾµÄÁÚ½Ó¶þÔª¹Øϵ£¬Óü¶¼äÓÐÏò»¡Á¬½Ó³ÉÓÐÏòͼD(A¡ä)¡£ ¾Ý´Ë£¬½¨Á¢ÆðÔÀýµÄµÝ½×½á¹¹Ä£ÐÍ£¬Èçͼ4¡ª7Ëùʾ¡£
×ÛÉÏËùÊö£¬ÒÔ¿É´ï¾ØÕóMΪ»ù´¡£¬ÒÔ¾ØÕó±ä»»ÎªÖ÷Ïߵĵݽ׽ṹģÐ͵Ľ¨Á¢¹ý³ÌÈçͼ4¡ª8Ëùʾ¡£ ÇøÓò
S2 S4 S6 S1 S5 µÚÒ»¼¶ µÚ¶þ¼¶ µÚÈý¼¶ ¼¶Î» »®·Ö
M(L) Ç¿Á¬½ÓÒªËØËõ¼õ
ÌÞ³ýÔ½ È¥µô×Ô
»®·Ö M
M(P)
¼¶¹Øϵ Éí¹Øϵ »æͼ
M¡¯(L) M¡±(L) A¡¯ D(A¡¯)
£¨¿é¶Ô½Ç£© £¨ÇøÓò¿éÈý½Ç£©
£¨ÇøÓòÏÂÈý½Ç£©
ͼ4¡ª8µÝ½×½á¹¹Ä£Ðͽ¨Á¢¹ý³ÌʾÒâͼ Èý¡¢½¨Á¢µÝ½×½á¹¹Ä£Ð͵ÄʵÓ÷½·¨
°´Õչ淶·½·¨ËùÏÔʾµÄµÝ½×½á¹¹Ä£ÐÍ»¯»ù±¾ÔÀí£¬ÔÚϵͳ½á¹¹²¢²»Ê®·Ö¸´ÔÓµÄÇé¿öÏ£¬½¨Ä£¹¤×÷¿É²ÉÓýÏΪ¼ò±ãµÄ·½·¨À´Íê³É¡£ÆäÖ÷Òª¹ý³ÌÈçÏ£º 1¡¢Åж¨¶þÔª¹Øϵ£¬½¨Á¢¿É´ï¾ØÕó¼°ÆäËõ¼õ¾ØÕó
ÔÚÎÊÌâÉ趨֮ºó£¬Ê×ÏÈÓÉ·ÖÎöС×é»ò·ÖÎöÈËÔ±¸öÈËÑ°ÕÒÓëÎÊÌâÓÐijÖÖ¹ØϵµÄÒªËØ£¬¾¼¯Öк󣬸ù¾ÝÒªËظöÊý»æÖÆÈçͼ4¡ª9ËùʾµÄ·½¸ñͼ£¬²¢ÔÚÿÐÐÓÒ¶ËÒÀ´Î×¢Éϸ÷ÒªËصÄÃû³Æ¡£ÔÚ´Ë»ù´¡ÉÏ£¬Í¨¹ýÁ½Á½±È½Ï£¬Ö±¹ÛÈ·¶¨¸÷ÒªËØÖ®¼äµÄ¶þÔª¹Øϵ£¬²¢ÔÚÁ½ÒªËؽ»»ã´¦µÄ·½¸ñÄÚÓ÷ûºÅV¡¢AºÍX¼ÓÒÔ±êʶ¡£ÆäÖÐV±íʾ·½¸ñͼÖеÄÐÐ(»òÉÏλ)ÒªËØÖ±½ÓÓ°Ïìµ½ÁÐ(»òÏÂλ)ÒªËØ£¬A±íʾÁÐÒªËضÔÐÐÒªËØÓÐÖ±½ÓÓ°Ï죬X±íʾÐÐÁÐÁ½ÒªËØÏ໥ӰÏì(³Æ֮ΪǿÁ¬½Ó¹Øϵ)¡£½ø¶ø¸ù¾ÝÒªËؼä¶þÔª¹ØϵµÄ´«µÝÐÔ£¬Âß¼ÍƶϳöÒªËؼä¸÷´ÎµÝÍƵĶþÔª¹Øϵ£¬²¢ÓüÓÀ¨ºÅµÄ±êʶ·û±íʾ¡£×îºó£¬ÔÙ¼ÓÈë·´Ó³×ÔÉíµ½´ï¹ØϵµÄµ¥Î»¾ØÕ󣬽¨Á¢ÆðϵͳҪËصĿɴï¾ØÕó¡£ (A) A S7
ͼ4¡ª9 Åж¨ÒªËؼä¹ØϵÓ÷½¸ñͼ
×÷Ϊ·½·¨¾ÙÀý£¬ÏÖ¸ù¾ÝÀý4¡ª1¸ø³öµÄϵͳ½á¹¹·ÖÎöÎÊÌ⣬»æÖƳö°ïÖú½¨Á¢¿É´ï¾ØÕóµÄ·½¸ñͼÈçͼ4¡ª9Ëùʾ¡£
¸ù¾Ýͼ4¡ª9£¬²¢¼ÓÈ뵥λ¾ØÕ󣬿Éд³öÈçÏ¿ɴï¾ØÕó(ÆäÖн«Si¼ò¼ÇΪi)£º 1 2 3 4 5 6 7
1 ?12 ?3 ?0?M= 4 ?05 ?06 ?0?7 ? (V) X (A) S6 (V) V S5 V S4 S3 A S2 S1
?10100000000?00000??11110??01110? 00100??001110???1100001?2¡¢¶Ô¿É´ï¾ØÕóµÄËõ¼õ¾ØÕó½øÐвã´Î»¯´¦Àí
¸ù¾ÝÒªËؼ¶Î»»®·ÖµÄ˼Ï룬ÔÚ¾ßÓÐÇ¿Á¬½Ó¹ØϵµÄÒªËØ(S4ÓëS6)ÖУ¬È¥³ýS6(¼´
È¥³ý¿É´ï¾ØÕóÖС°6¡±Ëù¶ÔÓ¦µÄÐкÍÁÐ)£¬¿ÉµÃµ½Ëõ¼õ(¿É´ï)¾ØÕóM¡ä¡£ÔÚM¡äÖа´Ã¿ÐС°1¡±ÔªËصĶàÉÙ£¬ÓÉÉÙµ½¶à˳´ÎÅÅÁУ¬µ÷ÕûM¡äµÄÐкÍÁУ¬µÃµ½M¡äL£»×îºóÔÚM¡äLÖУ¬´Ó×óÉϽǵ½ÓÒϽǣ¬ÒÀ´Î·Ö½â³ö×î´ó½×ÊýµÄµ¥Î»¾ØÕ󣬲¢¼Ó×¢·½¿ò¡£Ã¿¸ö·½¿ò±íʾһ¸ö²ã´Î¡£
¶ÔÔÀý¿É´ï¾ØÕóµÄËõ¼õ¾ØÕó½ø´Î²ã´Î»¯´¦ÀíµÄ½á¹ûΪ£º 1 5 2 4 7 3
1 ?1?2 0?3 ?1A= 4 ?0?5 ?16 ??0 ?00000?10000??01000??
10100?01010??10101??¿É¼û£¬¸ÃÀýÖеÄÒªËØ·ÖΪÈý¸ö²ã´Î¡£S1ºÍS5ÊôµÚÒ»²ã´Î£¬S2¡¢S4¼°S6ÊôµÚ¶þ²ã´Î£¬S7¡¢S3ΪµÚÈý²ã´Î¡£
ÊÂʵÉÏ£¬Ö»ÒªÕÆÎÕÁËÒªËؼ¶Î»»®·ÖµÄ»ù±¾ÔÀí£¬¾Í¿ÉÒÔ¹é½á³ö¸÷ÖÖ¶Ô¿É´ï¾ØÕó»òÆäËõ¼õ¾ØÕó½øÐвã´Î»¯´¦ÀíµÄ¼òÒ×·½·¨¡£ 3¡¢¸ù¾ÝM¡äL»æÖƶ༶µÝ½×ÓÐÏòͼ
Ê×ÏÈ°ÑËùÓÐÒªËØ°´ÒÑÓвã´ÎÅÅÁУ¬È»ºó°´ÕÕM¡äLÖÐÁ½·½¿ò(µ¥Î»¾ØÕó)½»»ã´¦µÄ¡°1¡±ÔªËØ£¬»³ö±íÕ÷²»Í¬²ã´ÎÒªËؼäÖ±½ÓÁªÏµµÄÓÐÏò»¡£¬Ðγɶ༶µÝ½×ÓÐÏòͼ¡£ Èç¸ù¾ÝÉÏÀýÖеڶþ²ãµ½µÚÒ»²ã¼äµÄS2RS1¡¢S4RS5ºÍµÚÈý²ãµ½µÚ¶þ²ã¼äµÄS7RS2¡¢S3RS4£¬²¢²¹³ä½ø±»ËõÔ¼µÄS6£¬¼´¿É»æÖƳöÓëͼ4¡ª7ÏàͬµÄ¶à¼¶µÝ½×ÓÐÏòͼ¡£
×îºó£¬¿É¸ù¾Ý¸÷ÒªËصÄʵ¼ÊÒâÒ壬½«¶à¼¶µÝ½×ÓÐÏòͼֱ½Óת»¯Îª½âÊͽṹģÐÍ¡£ ÕâÖÖ½¨Á¢½×½á¹¹Ä£Ð͵ķ½·¨ÒԹ淶·½·¨Îª»ù´¡£¬¼ò±ã¡¢ÊµÓã¬ÓÐÖúÓÚÈËÃÇʵÏÖ¶Ô¶àÒªËØÎÊÌâÈÏʶÓë·ÖÎöµÄ²ã´Î»¯¡¢ÌõÀí»¯ºÍϵͳ»¯¡£
˼¿¼ÓëÁ·Ï°Ìâ
1¡¢Çë¼òÊö½á¹¹·ÖÎöÔÚϵͳ·ÖÎöÖеĵØλºÍ×÷Óᣠ2¡¢Çë˵Ã÷ϵͳ½á¹¹ÈýÖÖ±í´ï·½Ê½µÄÌص㲢¼ÓÒԱȽϡ£ 3¡¢ÎªÊ²Ã´Ëµ¼¶Î»»®·ÖÊǽ¨Á¢¶à¼¶µÝ½×½á¹¹Ä£Ð͵Ĺؼü¹¤×÷? 4¡¢ÊÔ̽Ë÷Ò»ÖÖ½¨Á¢µÝ½×½á¹¹Ä£Ð͵ļò±ã·½·¨¡£
5¡¢¸ø¶¨ÃèÊöϵͳ»ù±¾½á¹¹µÄÓÐÏòͼÈç(a)¡¢(b)Ëùʾ¡£ÒªÇó£º (1)д³öϵͳҪËؼ¯ºÏS¼°SÉϵĶþÔª¹Øϵ¼¯ºÏRb£»
(2)½¨Á¢ÁÚ½Ó¾ØÕóA¡¢¿É´ï¾ØÕóM¼°Ëõ¼õ¾ØÕóM¡ä¡£ S1 S2
6
S5
1 5 2 3
S3
(a)
4 S4
(b)
6¡¢ÒÑÖªÏÂÃæµÄϵͳ¿É´ï¾ØÕ󣬷ֱðÓù淶·½·¨ÓëʵÓ÷½·¨½¨Á¢ÆäµÝ½×½á¹¹Ä£ÐÍ£º (1)
¢Ù ¢Ú ¢Û ¢Ü ¢Ý ¢Þ ¢ß
1¢Ù?ª«
?0¢Ú?ª«¢Û?ª«0¢Ü?ª«?0¢Ý?ª«0¢Þ?ª«
0¢ß ??0?000101?100000??010110??101000? 000100??010110?000101??(2)
¢Ù ¢Ú ¢Û ¢Ü ¢Ý ¢Þ ¢ß ¢à
?1ª«?0ª«??1ª«?ª«?0ª«?0?ª«?0?0¢à ???0¢Ù¢Ú¢Û¢Ü¢Ý¢Þ¢ß
1111111000100000101111100000111000000100000001100?0??0??0? ?0?1?1??1??7¡¢ÊÔÓÃISM¼¼ÊõÑо¿±¾×¨Òµ¸÷ÃÅÖ÷Òª¿Î³ÌÖ®¼äµÄ¹Øϵ(¼Ù¶¨¶þÔª¹ØϵΪ¡°Ö§³Ö¡±¹Øϵ)£¬½¨Á¢ÄãÈÏΪ±È½ÏºÏÀíµÄ¿Î³ÌÌåϵ½á¹¹¡£