Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Định nghĩa bằng đệ qui Trong thực tế, chúng ta gặp rất nhiều đối tợng mà khó có thể định nghĩa nó một cách tờng minh, nhng lại dễ dàng định nghĩa đối tợng qua chính nó. | Mét trong nh÷ng ph¬ng ph¸p hiÓn nhiªn nhÊt ®Ó gi¶i bµi to¸n tèi u tæ hîp ®Æt ra lµ duyÖt toµn bé. Trªn c¬ së c¸c thuËt to¸n lÖt kª tæ hîp, ta tiÕn hµnh duyÖt tõng ph¬ng ¸n cña bµi to¸n. §èi víi mçi ph¬ng ¸n, ta ®Òu tÝnh gi¸ trÞ hµm môc tiªu t¹i nã, sau ®ã so s¸nh gi¸ trÞ cña hµm môc tiªu t¹i tÊt c¶ c¸c ph¬ng ¸n ®· ®îc liÖt kª ®Ó t×m ra ph¬ng ¸n tèi u. Ph¬ng ph¸p x©y dùng theo nguyªn t¾c nh vËy ®îc gäi lµ ph¬ng ph¸p duyÖt toµn bé. H¹n chÕ cña ph¬ng ph¸p duyÖt toµn bé lµ sù bïng næ cña c¸c cÊu h×nh tæ hîp. Ch¼ng h¹n, ®Ó duyÖt ®îc 15! = 1 307 674 368 000 cÊu h×nh, trªn m¸y cã tèc ®é 1 tû phÐp tÝnh gi©y, nÕu mçi ho¸n vÞ cÇn liÖt kª mÊt kho¶ng 100 phÐp tÝnh, ta cÇn kho¶ng thêi gian lµ 130767 gi©y ( lín h¬n 36 tiÕng ®ång hå). V× vËy, cÇn ph¶i cã biÖn ph¸p h¹n chÕ viÖc kiÓm tra hoÆc t×m kiÕm trªn c¸c cÊu h×nh tæ hîp th× míi cã hy väng gi¶i ®îc c¸c bµi to¸n tèi u tæ hîp thùc tÕ. TÊt nhiªn, ®Ó ®a ra ®îc mét thuËt to¸n, cÇn ph¶i nghiªn cøu kü tÝnh chÊt cña mçi bµi to¸n tæ hîp cô thÓ. ChÝnh nhê nh÷ng nghiªn cøu ®ã, trong mét sè trêng hîp ta cã thÓ x©y dùng ®îc thuËt to¸n hiÖu qu¶ ®Ó gi¶i quyÕt bµi to¸n ®Æt ra. Nhng còng cÇn ph¶i chó ý r»ng, trong nhiÒu trêng hîp ( bµi to¸n ngêi du lÞch, bµi to¸n c¸i tói, bµi to¸n cho thuª m¸y) chóng ta vÉn cha t×m ra ®îc mét ph¬ng ph¸p h÷u hiÖu nµo ngoµi ph¬ng ph¸p duyÖt toµn bé ®· ®îc ®Ò cËp ë trªn. VÝ dô sau ®©y lµ mét ®iÓn h×nh cho ph¬ng ph¸p duyÖt toµn bé.
