| ²é¿´: 1237 | »Ø¸´: 15 | ||
zhangwzh½ð³æ (ÕýʽдÊÖ)
|
[ÇóÖú]
ÍòÄܵÄСľ³æ£¬°ï°ïÎÒ°É£¬ Ò»¸öÀàËÆ terminal Steiner tree problemÎÊÌâ
|
|
ÓÐÒ»¸öÎÞÏòͼG(v,e),¼ÙÉèÓÐVÓÐ100¸ö¶¥µã¡£ ÎÒÏÖÔÚ¸ø¶¨Ò»¸ön,±ÈÈç10£¬ ÄÇô£¬ÒÔÒ¶×ӽڵ㽨Á¢Ò»¸ö×Óͼ£¬×ÓͼÊÇÒÔVÖÐÈÎÒân¸öÒ¶×ÓÁ¬½Ó½¨Á¢µÄ×îСÉú³ÉÊ÷¡£ ÇëÎʽ¨Á¢Õâ¸ö×îСÉú³ÉÊ÷ÎÊÌâÊDz»ÊÇÒ»¸öNP hardÎÊÌ⣬ÓÐûÓÐÏà¹ØµÄNPÎÊÌ⣬ÓÃÒÔÖ¤Ã÷¡£ ²éÁËЩÎÄÏ×£¬ËƺõÊÇÒ»¸ö terminal Steiner tree problem£¬µ«Çø±ðÊÇÄǸö¶¥µãµÄ×Ó¼¯ÊǸø¶¨µÄ£¬¶øÎÒÕâ¸öÎÊÌâÖ»ÊÇÈ·¶¨ÊýÁ¿¡£Õâ¸ö¸ü²»Ò»¶¨£¬ÊDz»ÊÇ¿ÉÒÔÕâÑù˵£¬ËûÄǸöÊÇnp, ÎÒÕâ¸ö¾Í¸üÊÇnpÁË£¬¼ÙÈçÒ¶×ÓÓÐm¸öµã£¬¾ÍÊǶàÁËCm,n±¶¶øÒÑ¡£ [ Last edited by zhangwzh on 2012-7-25 at 10:54 ] |
» ²ÂÄãϲ»¶
µ÷¼Á
ÒѾÓÐ6È˻ظ´
Ò»Ö¾Ô¸ ½ÄÏ´óѧ 085602 »¯¹¤×¨Ë¶ 338·ÖÇóµ÷¼Á
ÒѾÓÐ12È˻ظ´
²ÄÁÏר˶(0856) 339·ÖÇóµ÷¼Á
ÒѾÓÐ8È˻ظ´
377Çóµ÷¼Á
ÒѾÓÐ5È˻ظ´
0703µ÷¼Á£¬Ò»Ö¾Ô¸Ìì½ò´óѧ319·Ö
ÒѾÓÐ6È˻ظ´
Ò»Ö¾Ô¸Äϲý´óѧ£¬085600£¬344·ÖÇóµ÷¼Á
ÒѾÓÐ5È˻ظ´
308Çóµ÷¼Á
ÒѾÓÐ8È˻ظ´
ÕÒµ÷¼Á
ÒѾÓÐ9È˻ظ´
Ò»Ö¾Ô¸Ö£ÖÝ´óѧ085600Çóµ÷¼Á
ÒѾÓÐ12È˻ظ´
316Çóµ÷¼Á
ÒѾÓÐ3È˻ظ´

dybo
ľ³æ (ÕýʽдÊÖ)
- Ó¦Öú: 8 (Ó×¶ùÔ°)
- ½ð±Ò: 5500.2
- É¢½ð: 134
- ºì»¨: 43
- Ìû×Ó: 625
- ÔÚÏß: 239.9Сʱ
- ³æºÅ: 897154
- ×¢²á: 2009-11-08
- ÐÔ±ð: GG
- רҵ: ²ÝµØ¿ÆÑ§

2Â¥2012-08-10 12:04:38
zhangwzh
½ð³æ (ÕýʽдÊÖ)
- Ó¦Öú: 3 (Ó×¶ùÔ°)
- ½ð±Ò: 278.5
- É¢½ð: 856
- ºì»¨: 3
- Ìû×Ó: 973
- ÔÚÏß: 335.1Сʱ
- ³æºÅ: 605802
- ×¢²á: 2008-09-18
- ÐÔ±ð: GG
- רҵ: ¼ÆËã»úÍøÂç

3Â¥2012-08-10 12:10:49
zhangwzh
½ð³æ (ÕýʽдÊÖ)
- Ó¦Öú: 3 (Ó×¶ùÔ°)
- ½ð±Ò: 278.5
- É¢½ð: 856
- ºì»¨: 3
- Ìû×Ó: 973
- ÔÚÏß: 335.1Сʱ
- ³æºÅ: 605802
- ×¢²á: 2008-09-18
- ÐÔ±ð: GG
- רҵ: ¼ÆËã»úÍøÂç

4Â¥2012-08-10 12:11:26
zhangwzh
½ð³æ (ÕýʽдÊÖ)
- Ó¦Öú: 3 (Ó×¶ùÔ°)
- ½ð±Ò: 278.5
- É¢½ð: 856
- ºì»¨: 3
- Ìû×Ó: 973
- ÔÚÏß: 335.1Сʱ
- ³æºÅ: 605802
- ×¢²á: 2008-09-18
- ÐÔ±ð: GG
- רҵ: ¼ÆËã»úÍøÂç

5Â¥2012-08-10 12:13:11
gen007gen
ľ³æ (ÕýʽдÊÖ)
- Ó¦Öú: 28 (СѧÉú)
- ½ð±Ò: 4954.7
- É¢½ð: 69
- ºì»¨: 3
- Ìû×Ó: 413
- ÔÚÏß: 262.9Сʱ
- ³æºÅ: 1161736
- ×¢²á: 2010-12-03
- ÐÔ±ð: GG
- רҵ: ¼ÆËã»ú¿ÆÑ§µÄ»ù´¡ÀíÂÛ

6Â¥2012-08-11 04:31:20
zhangwzh
½ð³æ (ÕýʽдÊÖ)
- Ó¦Öú: 3 (Ó×¶ùÔ°)
- ½ð±Ò: 278.5
- É¢½ð: 856
- ºì»¨: 3
- Ìû×Ó: 973
- ÔÚÏß: 335.1Сʱ
- ³æºÅ: 605802
- ×¢²á: 2008-09-18
- ÐÔ±ð: GG
- רҵ: ¼ÆËã»úÍøÂç
|
лл¹ØÐÄ¡£ Êýѧ²»ºÃ£¬ÎÒ´ó¸ÅÃèÊöÏ£º ¸ø¶¨Ò»¸öÎÞÏò´øÈ¨Ê÷G(V,E),¶ÔÓÚÿһÌõÏàÁڵıß(u,v)¡ÊE,ÆäȨֵw(u,v)Ϊ1£¬¶Ô²»ÏàÁÚµÄÁ½¸ö½Úµãm,n, Æäw(m,n)ΪÔÚGÉϵıßȫ֮ºÍ£¨µÈÓÚÌøÊý£©£»ÉèÓÐGÖÐÈ«²¿Ò¶×Ó½ÚµãµÄ¼¯ºÏVs£¨VsÖнáµã¸öÊý´óÓÚV¡¯£©£»Ò»¿Ã¸ø¶¨½á¹¹µÄÊ÷G¡¯(V¡¯,E¡¯)£¬³õʼ»¯E¡¯È¨Öµ¾ùΪ0£»ÊÇ·ñ´æÔÚÕâÑùµÄÒ»¸öÓ³Éäf£º¶ÔÓÚÿ¸öV¡¯ÖеĽڵãuÓ³Éäµ½×Ó¼¯Vs½Úµãus£¬¶ÔÓÚÊ÷G¡¯ÖÐE¡¯£¬Éè(u,v)¡ÊE¡¯,ÔòÓÃw(us,vs)±íʾÁ¬½Óu¡¢v½ÚµãµÄ´ú¼Û£¬Ê¹µÃÊ÷µÄ´ú¼Û×îС£¿ |

7Â¥2012-08-12 15:37:37
zhangwzh
½ð³æ (ÕýʽдÊÖ)
- Ó¦Öú: 3 (Ó×¶ùÔ°)
- ½ð±Ò: 278.5
- É¢½ð: 856
- ºì»¨: 3
- Ìû×Ó: 973
- ÔÚÏß: 335.1Сʱ
- ³æºÅ: 605802
- ×¢²á: 2008-09-18
- ÐÔ±ð: GG
- רҵ: ¼ÆËã»úÍøÂç

8Â¥2012-08-21 15:34:33
gen007gen
ľ³æ (ÕýʽдÊÖ)
- Ó¦Öú: 28 (СѧÉú)
- ½ð±Ò: 4954.7
- É¢½ð: 69
- ºì»¨: 3
- Ìû×Ó: 413
- ÔÚÏß: 262.9Сʱ
- ³æºÅ: 1161736
- ×¢²á: 2010-12-03
- ÐÔ±ð: GG
- רҵ: ¼ÆËã»ú¿ÆÑ§µÄ»ù´¡ÀíÂÛ
¡¾´ð°¸¡¿Ó¦Öú»ØÌû
¡ï ¡ï ¡ï ¡ï ¡ï ¡ï ¡ï ¡ï ¡ï ¡ï ¡ï ¡ï ¡ï ¡ï ¡ï ¡ï ¡ï ¡ï ¡ï ¡ï
zhangwzh: ½ð±Ò+20, ¡ï¡ï¡ï¡ï¡ï×î¼Ñ´ð°¸, лл°¡£¬ÓпÕÒ»¶¨¿´¿´Í¼ÂÛ£¬¾ÍÊÇһֱûʱ¼ä°¡£¡ 2012-08-22 09:04:35
zhangwzh: ½ð±Ò+20, ¡ï¡ï¡ï¡ï¡ï×î¼Ñ´ð°¸, лл°¡£¬ÓпÕÒ»¶¨¿´¿´Í¼ÂÛ£¬¾ÍÊÇһֱûʱ¼ä°¡£¡ 2012-08-22 09:04:35
|
Õâ¸öÎÊÌâÏÔÈ»ÊÇNP-hardµÄ¡£ÒòΪmaxi leaf spanning treeÊÇÕâ¸öÎÊÌâµÄspecial case, ¶ømaxi leaf spanning treeÊÇNP-hardµÄ¡£µ«ÊÇÊÇNP-completeµÄ¿ÉÄÜÐв»´ó¡£ Äã¿ÉÒÔµ½google ËÑË÷maxi leaf spanning treeµÄ¶¨Òå¡£ ²»¹ýÎÒ¾õµÃÄãÒªÏëѧÕâЩ£¬ÒªÏȰÑͼÂۺúÿ´¿´¡£ÒòΪ¶¨ÒåÁËÈý´Î£¬¿ÉÊǵÚÈý´ÎµÄ¶¨ÒåÒ²²»ÊǺÜÑϽ÷¡£ÆäʵÄãµÄÎÊÌâ¿ÉÒÔÃèÊö³É£º¸ø¶¨Ò»¸ö±ß´øÈ¨Í¼£¬Çó½â¸ÃͼµÄº¬ÓÐM¸öÒ¶×Ó½ÚµãÇÒ×ÜȨֵ×îСµÄ×ÓÊ÷¡£ |

9Â¥2012-08-22 00:16:16
zhangwzh
½ð³æ (ÕýʽдÊÖ)
- Ó¦Öú: 3 (Ó×¶ùÔ°)
- ½ð±Ò: 278.5
- É¢½ð: 856
- ºì»¨: 3
- Ìû×Ó: 973
- ÔÚÏß: 335.1Сʱ
- ³æºÅ: 605802
- ×¢²á: 2008-09-18
- ÐÔ±ð: GG
- רҵ: ¼ÆËã»úÍøÂç

10Â¥2012-08-22 09:29:54














»Ø¸´´ËÂ¥
zhangwzh