next up previous
Next: ¼ÓÈ¨ÍøÂç Up: ÍøÂçÉϵľ²Ì¬¼¸ºÎÁ¿ Previous: ÎÞÏòÍøÂç

ÓÐÏòÍøÂç

ĿǰÒѵõ½Ñо¿µÄµäÐÍÓÐÏòÍøÂç°üÀ¨£ºWWWÍøÂ磬ϸ°ûÄÚ»¯Ñ§·´Ó¦ÍøÂ磬ʳÎïÁ´ÍøÂ磬ÒýÎÄÍøÂ磬µçÁ¦ÍøÂ磬Éñ¾­ÍøÂç¡£

µ±ÎÒÃǺöÂԱߵķ½ÏòµÄʱºò£¬»òÕß·´¹ýÀ´¿´ÈÏΪÈκÎÒ»Ìõ±ß¶¼ÊÇË«ÏòµÄʱºò£¬ÓÐÏòÍøÂç¾Í³ÉΪÎÞÏòÍøÂç¡£Òò´Ë£¬¹ØÓÚÎÞÏòÍøÂçµÄËùÓм¸ ºÎÁ¿¶¼¿ÉÒÔÔÚÓÐÏòÍøÂçÖÐÑо¿¡£ÓÐÏòÍøÂçµÄÌØÊ⾲̬¼¸ºÎÁ¿°üÀ¨£ºIn¶ÈºÍOut¶ÈµÄ·Ö²¼ÌØÕ÷£¬»ùÓÚ¶¥µãµÄIn-Out¶È ¹ØÁªÐÔ£¬»ùÓÚ±ßµÄ $ \left(\vphantom{In-Out, In-In, Out-In, Out-Out}\right.$In - Out, In - In, Out - In, Out - Out$ \left.\vphantom{In-Out, In-In, Out-In, Out-Out}\right)$¶È¹ØÁªÐÔ£¬Ë«Ïò±È£¬In¼¯ÍźÍOut¼¯Íŵļ¯¾Û³Ì¶È¡£

°ÑÎÞÏòÍøÂçµÄ¶ÈÍÆ¹ãΪIn¶ÈºÍOut¶È£¬

doutu = $\displaystyle \sum_{{v\in V}}^{}$$\displaystyle \delta^{{uv}}_{}$ (6)
ÒÔ¼°

dinu = $\displaystyle \sum_{{v\in V}}^{}$$\displaystyle \delta^{{vu}}_{}$, (7)
¿É·Ö±ðÑо¿In¶ÈºÍOut¶ÈµÄ·Ö²¼ÌØÕ÷¡£ÊµÖ¤Ñо¿±íÃ÷£¬ÓÐÏòÍøÂçÖдæÔÚIn¶ÈºÍOut¶ÈµÄË«ÏòÃÝÂÊ·Ö²¼£¬ÈçWWWÍøÂç[26,50,27]£¬Ï¸°û ÄÚ»¯Ñ§·´Ó¦ÍøÂç[51,52]£»µ«ÊÇÒ²´æÔÚÖ»ÓÐIn¶ÈÃÝÂÊ·Ö²¼µÄÍøÂ磬ÈçÒýÎÄÍøÂç[65]£»ÒÔ¼°·ûºÏÖ¸ÊýË¥¼õµÄÍøÂ磬ÈçµçÁ¦ÍøÂç[7] ÓëÉñ¾­ÍøÂç[46]£»´ËÍ⣬ÓÉÓÚÊܶ¥µãÊý¹æÄ£ÏÞÖÆ£¬Ê³ÎïÁ´ÍøÂçµÄ¶È·Ö²¼ÌØÕ÷ÈÔȻûÓÐÈ·¶¨[53,54,55,56]¡£

ÓÉÓÚÿһ¸öÓÐÏòÍøÂçµÄ¶¥µã¶¼´æÔÚInÓëOutÁ½¸ö¶ÈÖµ£¬Ñо¿ÕâÁ½¸ö¶ÈÖµÖ®¼äµÄ¹ØÁª½«ÊÇÓÐÏòÍøÂçµÄÁíÒ»¸öÖØÒªÌØÕ÷¡£ÓëÎÞÏòÍøÂçµÄ¶È Ïà¹ØÀàËÆ£¬ÎÒÃÇ¿ÉÒÔÑо¿ÓÐÏòÍøÂç»ùÓڱߵĶÈÏà¹Ø¡£ÈÎÒâѡȡһÌõ±ß£¬ÔڱߵÄÁ½¶Ë´æÔÚ4¸ö¶ÈÖµ£¬ÆðµãµÄIn¶ÈºÍOut¶È£¬ ÖÕµãµÄIn¶ÈºÍOut¶È£¬ËùÒÔ´æÔÚ4ÖÖ¹ØÁªÐÔ£¬·Ö±ðÊÇIn-In£¬In-Out£¬Out-In£¬Out-Out ¹ØÁª¡£¾¡¹Ü¹ØÁªÐÔ¸´ÔÓÁË£¬¿ÉÊÇͬʱȥµôÁËÉÏһС½ÚËùÌáµ½µÄÎÞÏòÍøÂç¶ÈÏà¹Ø·ÖÎöµÄÈÎÒâÐÔ¡£ÄÇôÕâÑùµÄ¶È¶ÈÏà¹ØµÄÑо¿ÊÇ·ñ½ö½öÊÇÎÞ ÏòÍøÂçÖÐ¶È¹Ø ÁªÐÔ·ÖÎöµÄÆ½Ó¹ÍÆ¹ãÄØ£¿²»ÊÇ¡£ÎÒÃÇÌáµ½£¬ËùÓÐÐÂÌá³öµÄ¼¸ºÎÁ¿¶¼ÊÇΪÁËÍøÂç»úÖÆÄ£ÐÍ·þÎñµÄ£¬ÔÚÏÂÒ»½ÚÖдó¼Ò¿ÉÒÔ¿´¼ûÔÚ»úÖÆÄ£ÐÍÖУ¬ ·´À¡»úÖÆÊÇÒ»¸öÖØÒªµÄÒòËØ£¬¶øÓÐÏòÍøÂçµÄ¶ÈÏà¹ØÐÔÕýÊǽ¨Á¢·´À¡»úÖÆµÄÖØÒª²Î¿¼¡£

±ßµÄË«Ïò±È£¬¼´Ë«ÏòµÄ±ßÕ¼ËùÓбߵıÈÀý£¬Ò²ÊÇÒ»¸öÖØÒªµÄ¸ÅÄ¿ÉÒÔΪÉè¼ÆË«ÏòÃÝÂÊ·Ö²¼µÄ»úÖÆÄ£ÐÍÌṩ²Î¿¼¡£



wwwwjs 2004-01-04