¤w¦b²Ä¤@­¶¡@1¢x2¢x3¢x4¡@¦¸­¶

 


­º­¶ | ·j´M

¡D­ì¸ü©ó¼Æ¾Ç¶Ç¼½²Ä¤Q¤@¨÷²Ä¤T´Á
¡D§@ªÌ·í®É¥ô±Ð©ó³{¥Ò¤j¾Ç²Î­p¨t
 

®È¦æ·~°È­û°ÝÃD

¼B²[ªì

 
 

®È¦æ·~°È­û°ÝÃD (Traveling Salesman Problem) ¬O­Ó¦³¦WªºÃøÃD¡A®È¦æ·~°È­û­n¨ì n ­Ó«°¥«±À®i·~°È¡An ­Ó«°¥«¥H 1,2,¡K,n ªí¥Ü¡A ±q 1 ¥Xµo¡A¸g¹L¨C­Ó«°¥««ê¥u¤@¦¸¡A¦A¦^¨ì 1¡A¥O Cij ªí«°¥« i ¨ì«°¥« j ªº®È¦æ¦¨¥»¡A °ÝÃD¬°§ä¥X¤@­Ó³Ì¤p¦¨¥»ªº¸ô®|¡C¦b¤u¼tªº²Õ¦X½u¤W¡A¥H¾÷¾¹¤H¤WºòÁ³µ·´U¡A¾÷¾¹¤H±q°_©lªº¦ì¸m¥Xµo¡A °µ³sÄòªº²¾°Ê¡A¤Wºò¨C¤@­ÓÁ³µ·´U¡A¦A¦^¨ì°_©lªº¦ì¸m¡A¦p¦ó§ä¨ì¤@­Ó³Ìµuªº¸ô®|¡H³o¥ç¬O®È¦æ·~°È­û°ÝÃD¡C³o­Ó°ÝÃDÃø¦b­þùØ¡H§Ú­Ì¬Ý¥H¤Uªº¥|ºØ¸Ñªk¡C


(¤@)ÆZ¤Oªk(brute force method)

§Ú­Ì¥H³Ìª½Ä±ªº¤èªk¤@¤@­p¼Æ¨Ó¸Ñ¡A¥ç§Y§ä¥X©Ò¦³¥i¯àªº¸ô®|¡A­pºâ¨C±ø¸ô®|ªº¦¨¥»«á¡A§ä¥X¨ä³Ì¤pªÌ¡C ¨º»ò¦@¦³´X±ø¸ô®|¡H¦]¨C¤@±ø¸ô®|¥²§Î¦p $1\rightarrow \cdots \rightarrow 1$¡A¤¤¶¡»Ý¸g¹L n-1 ­Ó«°¥«¡A¬G¦³ (n-1)! ¸ô®|¡A ­Y n=26¡A«h¦³ 25! ±ø¤£¦P¸ô®|¡A25! ³o­Ó¼Æ¦r¼g¨Ó»´ÃP¡A¨s³º¦³¦h¤j¡H $25!\cong 1.55\times 10^{25}$¡A °²³]¹q¸£¨C¬í¥i­pºâ 106 ±ø¸ô®|ªº¦¨¥»(¥Ø«e¤]³\ÁÙ°µ¤£¨ì)¡A¤@¦~¦³ 3.15 x 107¬í¡A ¬G¤@¦~¥i­pºâ 3.15 x 1013±ø¸ô®|¡A¨D¥X©Ò¦³¸ô®|ªº¦¨¥»»Ý®É

\begin{displaymath}
\frac{1.55\times 10^{25}}{3.15\times 10^{13}}\cong 5\times 1...
...\mbox{({\fontfamily{cwM1}\fontseries{m}\selectfont \char 20})}
\end{displaymath}

§Y¨Ï¹ï¤£¤Ó¤jªº n=26¡A´N»Ý®É¤­¤d»õ¦~¡AÅãµM³oºØ¤èªk²@µL¥Î³B¡C

 
¹ï¥~·j´MÃöÁä¦r¡G
¡D®È¦æ·~°È­û°ÝÃD
¡DNP-Hard

¤w¦b²Ä¤@­¶¡@1¢x2¢x3¢x4¡@¦¸­¶

¦^­¶­º
 
¡]­Y¦³«ü¥¿¡BºÃ°Ý¡K¡K¡A¥i¥H¦b¦¹ ¯d¨¥ ©Î ¼g«H µ¹§Ú­Ì¡C¡^
EpisteMath

EpisteMath (c) 2000 ¤¤¥¡¬ã¨s°|¼Æ¾Ç©Ò¡B¥x¤j¼Æ¾Ç¨t
¦Uºô­¶¤å³¹¤º®e¤§µÛ§@Åv¬°­ìµÛ§@¤H©Ò¦³


½s¿è¡G§d©ú©M ¢A ®Õ¹ï¡G³¯¤å¬O ¢A ø¹Ï¡G²¥ßªY ³Ì«á­×§ï¤é´Á¡G5/2/2002