搜索對象與策略的重要性

1、.：.；第 PAGE 4 頁 共 NUMPAGES 4 頁由“汽車問題淺談深度搜索的一個(gè)方面搜索對象與戰(zhàn)略的重要性問 題 描 述有一個(gè)人在某個(gè)公共汽車站上，從12:00到12:59察看公共汽車到達(dá)本站的情況，該站被多條公共汽車線路所公用，他依次記下公共汽車到達(dá)本站的時(shí)辰。在12:0012:59期間，同一條線路上的公共汽車以一樣的時(shí)間間隔到站。時(shí)間單位用“分表示，從0 到59 。每條公共汽車線路至少有兩輛車到達(dá)本站。公共汽車線路數(shù)K一定17，汽車數(shù)目N一定小于300。不同線路的公共汽車能夠在同一時(shí)辰到達(dá)本站。不同公共汽車線路的車初次到站時(shí)間和到站的時(shí)間間隔都有能夠一樣。請為公共汽車線路編一個(gè)調(diào)度

2、表，目的是：公共汽車線路數(shù)目最少的情況下，使公共汽車到達(dá)本站的時(shí)辰滿足輸入數(shù)據(jù)的要求。例如：汽車編號12345678到達(dá)時(shí)間0351314142125 0143142551321線路一線路二線路三0351314142125間隔為14間隔為11間隔為8那就能夠存在這樣一個(gè)解，由以下3條汽車線路組成：解 析經(jīng)過一系列的分析，我們決議用深度搜索由于通篇討論的是深度搜索，以下就一致簡稱搜索解這道標(biāo)題。對這樣一個(gè)問題，首先提取出三個(gè)關(guān)鍵要素：時(shí)間、車、道路。車輛的特征是時(shí)間，道路的特征是“首發(fā)車時(shí)間和“間隔時(shí)間，這等效于“第一輛車和“第二輛車。面對這三個(gè)關(guān)鍵要素，下面就要從中確定搜索對象和搜索戰(zhàn)略?？梢?/p>

3、看出，標(biāo)題要求的是車和線路的關(guān)系，而時(shí)間在其中起的是描畫作用和條件制約作用，因此，此題的搜索對象應(yīng)該是車或線路這兩個(gè)關(guān)鍵要素。分析搜索對象及戰(zhàn)略1對象 車由此對象而產(chǎn)生的搜索戰(zhàn)略是：按到站時(shí)間順序，依次枚舉每輛車屬于哪條道路。留意道路的特征，假設(shè)一道路的第一輛車和第二輛車確定了，那該道路也就確定了。大致搜索方案為：按到達(dá)時(shí)間順序，依次對于那些沒有確定屬于哪條線路的車進(jìn)展枚舉，該車屬于某新線路的第一輛車或?qū)儆谀骋延芯€路的第二輛車，假設(shè)為后一種選擇，那么可確定道路上其他一切的車輛。0?3?5?13?0?3?5130?3135?不成立0133?5?不成立053? 不成立0?3?5?0?3?03不成立

4、0?0?35不成立014留意： 表示 的是一條線路。 0為第一輛車到 達(dá)時(shí)間，14為第二 輛車到達(dá)時(shí)間。汽車編號12345678到達(dá)時(shí)間0351314142125還是看先前給的那個(gè)簡單例子來構(gòu)造搜索樹大致如下：察看該搜索樹，發(fā)現(xiàn)：隨著搜索樹層數(shù)的遞增，每層節(jié)點(diǎn)所擴(kuò)展出的樹叉數(shù)目逐漸增大。從直觀上說：該搜索樹從根開場，“分叉越來越多，“枝葉越來越茂盛。這就是搜索對象為車的搜索樹的典型特點(diǎn)。2對象線路由此對象而產(chǎn)生的搜索戰(zhàn)略是：枚舉每條道路包含哪些車，確定該道路。實(shí)踐上，對每條道路，我們只需枚舉其特征：第一輛車和第二輛車。再根據(jù)“有序化思想，固定一切道路是按照第一輛車的到達(dá)時(shí)間為關(guān)鍵字排序的。大致

5、搜索方案為：汽車編號12345678到達(dá)時(shí)間 0 3 513141421250?014313不成立03不成立0143?0143145?0143255?0253?01435不成立搜索每層都要確定一條道路：將未確定歸屬道路的到達(dá)時(shí)間最小的車固定為新道路的第一輛車，其后枚舉這條道路的第二輛車，從而確定該道路。同樣，根據(jù)先前給的那個(gè)簡單例子我們也構(gòu)造出了方法二的搜索樹見前頁。察看這個(gè)搜索樹，和方法一的搜索樹對比，我們發(fā)現(xiàn)，兩者特性截然相反，該搜索樹從根開場，“分叉越來越少。兩種搜索對象及戰(zhàn)略是完全不同的，搜索樹特性又截然相反。從宏觀上，搜索樹上節(jié)點(diǎn)多少，兩者相差無幾。如何抉擇呢？這時(shí)就要從微觀上比較：

6、 比較哪個(gè)搜索對象和戰(zhàn)略更優(yōu)既然是比較，就要有比較的規(guī)范。這里，確定了兩個(gè)規(guī)范：誰易于優(yōu)化剪枝 ； 誰的操作量小 關(guān)于誰易于優(yōu)化剪枝的比較：此題的主要剪枝有三種，如下逐一分析?？尚行约糁Ξ?dāng)?shù)缆返奶卣鞔_定了，就可以判別該道路能否成立。方法一，搜索中，每層枚舉當(dāng)前車是哪條道路的第二輛車，都要用到該判別；方法二，每層是確定一條道路，也用到該判別。關(guān)鍵是，根據(jù)兩者搜索樹，方法一一旦剪枝，將剪去的是一大片“茂盛的樹枝，顯然，相比之下，方法二剪枝的效果就差了許多。故在此剪枝運(yùn)用上，方法二比如法一遜色許多。與知最優(yōu)解比較剪枝這就要看誰能很快找到解了。顯然，由于方法一可行性剪枝的優(yōu)點(diǎn)，每次剪枝都能刪去很多的不

7、可行的節(jié)點(diǎn)，找到解的速度就不比如法二慢了。此剪枝，方法二不比如法一要好。排除反復(fù)剪枝留意到標(biāo)題中時(shí)間這個(gè)關(guān)鍵要素的范圍為059，而車輛數(shù)目可達(dá)300，闡明，在同一時(shí)間到達(dá)的車輛數(shù)目很多！前面那個(gè)簡單例子中，就出現(xiàn)了兩個(gè)14，而到達(dá)時(shí)間為14的兩輛車各屬于那條道路是等效的，這就有反復(fù)。方法一對于同時(shí)到達(dá)的且未確定歸屬的車，假設(shè)編號小的車為某道路的第一輛車，那么編號大的車為也必為一條道路的第一輛車。方法二，對到達(dá)時(shí)間一樣的且未確定歸屬的車，固定只選編號最小的車為第二輛車。兩者剪去的都是反復(fù)的枝，所以，效果是一樣的，故此剪枝上，雙方平分秋色。結(jié)論：由于方法一搜索樹的良好特性，使得方法一在剪枝優(yōu)化方面

8、前景更寬廣。 關(guān)于誰的操作量小的比較：操作量是“主遞歸程序操作量的簡稱，由主遞歸程序的枚舉循環(huán)和剪枝函數(shù)決議的。主遞歸程序的枚舉循環(huán)方法一，每層利用循環(huán)來枚舉一輛車是屬于新道路的第一輛車還是知道路的第二輛車，而且搜索樹上這個(gè)循環(huán)枚舉量是由未確定“第二輛車的線路數(shù)目決議的，最大為17。方法二，每層枚舉哪輛車是第二輛車。由于用了排除反復(fù)剪枝，這個(gè)循環(huán)量最大為60。直觀上看兩者的最大界限就知道，方法二不比如法一好。剪枝函數(shù)耗費(fèi)時(shí)間由于此題特殊性，主要剪枝函數(shù)根本上差別不大，耗費(fèi)時(shí)間也差不多。結(jié)論：操作量大小方面，方法二不比如法一好。最終結(jié)論：經(jīng)過以上微觀實(shí)際分析，對兩種方法進(jìn)展了比較，得出最終結(jié)論是

9、：方法一比如法二好！選定了搜索對象和戰(zhàn)略，剛剛又分析了實(shí)現(xiàn)中的主要問題：如何剪枝，編寫程序自然就得心應(yīng)手了。現(xiàn)實(shí)也證明了我們的結(jié)論。兩種程序運(yùn)轉(zhuǎn)比較如下，可以發(fā)現(xiàn)兩者優(yōu)劣差別宏大。car.in1K=3 car.in2K=5car.in3K=8car.in4K=10car.in5K=15car.in6K=17方法一用時(shí)0.01s0.01s0.05s0.11s1.48s1.76s方法二用時(shí)0.01s0.01s9.07s100s100s100s總 結(jié)就此題而言，從宏觀上看，很難知道兩種方法效率的差別，為什么方法一更好呢？關(guān)鍵緣由在于：它適宜程序上的剪枝優(yōu)化，且操作量小。那為什么選擇這兩個(gè)方面為規(guī)范呢

10、？我們知道：深度搜索耗費(fèi)時(shí)間 每個(gè)節(jié)點(diǎn)操作系數(shù) 節(jié)點(diǎn)個(gè)數(shù)從上面一個(gè)公式，我們很顯然地能從微觀上看出，要減少耗費(fèi)時(shí)間，一是減少節(jié)點(diǎn)個(gè)數(shù)這就是我們所說地剪枝優(yōu)化；二是減少每個(gè)節(jié)點(diǎn)的操作系數(shù)即剛剛分析的程序操作量。為了提高搜索效率，根據(jù)這個(gè)公式，我們往往在以上兩方面反復(fù)進(jìn)展改良。殊不知，從宏觀前提上，如何才干使我們“可以、充分、有效剪枝，如何才干使我們“可以、充分、有效降低程序操作量也都是很重要的！于是，搜索對象和戰(zhàn)略為剪枝，降低操作系數(shù)發(fā)明前提條件的好壞就成了我們的規(guī)范！剪枝后的節(jié)點(diǎn)個(gè)數(shù)每個(gè)節(jié)點(diǎn)的操作系數(shù)深度搜索耗費(fèi)時(shí)間平衡點(diǎn)但是，在以這兩方面為規(guī)范比較的時(shí)候，我們要留意到：這兩個(gè)規(guī)范嚴(yán)密關(guān)聯(lián)，要剪枝多，就要有好的復(fù)雜的剪枝函數(shù)，但這就增大了每個(gè)節(jié)點(diǎn)操作系數(shù)。如下圖：兩者在目的上是一致的，效果上卻是對立的。在以這兩者為規(guī)范的時(shí)候，要把握好“如何協(xié)調(diào)，找準(zhǔn)兩者平衡點(diǎn)?？偟膩碚f，對深度搜索標(biāo)題，一個(gè)好的搜索對象和戰(zhàn)略是非常重要的。本文經(jīng)過