搜索對(duì)象與策略的重要性.docx

由“汽車問題”淺談深度搜索的一個(gè)方面搜索對(duì)象與策略的重要性問 題 描 述有一個(gè)人在某個(gè)公共汽車站上，從12:00到12:59觀察公共汽車到達(dá)本站的情況，該站被多條公共汽車線路所公用，他依次記下公共汽車到達(dá)本站的時(shí)刻。l 在12:0012:59期間，同一條線路上的公共汽車以相同的時(shí)間間隔到站。l 時(shí)間單位用“分”表示，從0 到59 。l 每條公共汽車線路至少有兩輛車到達(dá)本站。l 公共汽車線路數(shù)K一定17，汽車數(shù)目N一定小于300。l 來自不同線路的公共汽車可能在同一時(shí)刻到達(dá)本站。l 不同公共汽車線路的車首次到站時(shí)間和到站的時(shí)間間隔都有可能相同。請(qǐng)為公共汽車線路編一個(gè)調(diào)度表，目標(biāo)是：公共汽車線路數(shù)目最少的情況下，使公共汽車到達(dá)本站的時(shí)刻滿足輸入數(shù)據(jù)的要求。例如：汽車編號(hào)12345678到達(dá)時(shí)間0351314142125 0143142551321線路一線路二線路三0351314142125間隔為14間隔為11間隔為8那就可能存在這樣一個(gè)解，由以下3條汽車線路組成：解 析經(jīng)過一系列的分析，我們決定用深度搜索（由于通篇討論的是深度搜索，以下就統(tǒng)一簡(jiǎn)稱搜索）解這道題目。對(duì)這樣一個(gè)問題，首先提取出三個(gè)關(guān)鍵要素：時(shí)間、車、路線。車輛的特征是時(shí)間，路線的特征是“首發(fā)車時(shí)間”和“間隔時(shí)間”，這等效于“第一輛車”和“第二輛車”。面對(duì)這三個(gè)關(guān)鍵要素，下面就要從中確定搜索對(duì)象和搜索策略?？梢钥闯觯}目要求的是車和線路的關(guān)系，而時(shí)間在其中起的是描述作用和條件制約作用，因此，本題的搜索對(duì)象應(yīng)該是車或線路這兩個(gè)關(guān)鍵要素。 分析搜索對(duì)象及策略1對(duì)象 車由此對(duì)象而產(chǎn)生的搜索策略是：按到站時(shí)間順序，依次枚舉每輛車屬于哪條路線。注意路線的特征，若一路線的第一輛車和第二輛車確定了，那該路線也就確定了。大致搜索方案為：按到達(dá)時(shí)間順序，依次對(duì)于那些沒有確定屬于哪條線路的車進(jìn)行枚舉，該車屬于某新線路的第一輛車或?qū)儆谀骋延芯€路的第二輛車，若為后一種選擇，則可確定路線上其他所有的車輛。0?3?5?13?0?3?5130?3135?不成立0133?5?不成立053? 不成立0?3?5?0?3?03不成立0?0?35不成立014注意： 表示 的是一條線路。 0為第一輛車到 達(dá)時(shí)間，14為第二 輛車到達(dá)時(shí)間。汽車編號(hào)12345678到達(dá)時(shí)間0351314142125還是看先前給的那個(gè)簡(jiǎn)單例子來構(gòu)造搜索樹大致如下：觀察該搜索樹，發(fā)現(xiàn)：隨著搜索樹層數(shù)的遞增，每層節(jié)點(diǎn)所擴(kuò)展出的樹叉數(shù)目逐漸增大。從直觀上說：該搜索樹從根開始，“分叉”越來越多，“枝葉”越來越茂盛。這就是搜索對(duì)象為車的搜索樹的典型特點(diǎn)。2對(duì)象線路由此對(duì)象而產(chǎn)生的搜索策略是：枚舉每條路線包含哪些車，確定該路線。實(shí)際上，對(duì)每條路線，我們只要枚舉其特征：第一輛車和第二輛車。再根據(jù)“有序化”思想，固定所有路線是按照第一輛車的到達(dá)時(shí)間為關(guān)鍵字排序的。大致搜索方案為：汽車編號(hào)12345678到達(dá)時(shí)間 0 3 513141421250?014313不成立03不成立0143?0143145?0143255?0253?01435不成立搜索每層都要確定一條路線：將未確定歸屬路線的到達(dá)時(shí)間最小的車固定為新路線的第一輛車，其后枚舉這條路線的第二輛車，從而確定該路線。同樣，根據(jù)先前給的那個(gè)簡(jiǎn)單例子我們也構(gòu)造出了方法二的搜索樹（見前頁(yè)）。觀察這個(gè)搜索樹，和方法一的搜索樹對(duì)比，我們發(fā)現(xiàn)，兩者特性截然相反，該搜索樹從根開始，“分叉”越來越少。兩種搜索對(duì)象及策略是完全不同的，搜索樹特性又截然相反。從宏觀上，搜索樹上節(jié)點(diǎn)多少，兩者相差無幾。如何抉擇呢？這時(shí)就要從微觀上比較： 比較哪個(gè)搜索對(duì)象和策略更優(yōu)既然是比較，就要有比較的標(biāo)準(zhǔn)。這里，確定了兩個(gè)標(biāo)準(zhǔn)：誰易于優(yōu)化剪枝 ； 誰的操作量小 關(guān)于誰易于優(yōu)化剪枝的比較：本題的主要剪枝有三種，如下逐一分析。 可行性剪枝當(dāng)路線的特征確定了，就可以判斷該路線是否成立。方法一，搜索中，每層枚舉當(dāng)前車是哪條路線的第二輛車，都要用到該判斷；方法二，每層是確定一條路線，也用到該判斷。關(guān)鍵是，根據(jù)兩者搜索樹，方法一一旦剪枝，將剪去的是一大片“茂盛”的樹枝，顯然，相比之下，方法二剪枝的效果就差了許多。故在此剪枝應(yīng)用上，方法二比方法一遜色許多。 與已知最優(yōu)解比較剪枝這就要看誰能很快找到解了。顯然，由于方法一可行性剪枝的優(yōu)點(diǎn)，每次剪枝都能刪去很多的不可行的節(jié)點(diǎn)，找到解的速度就不比方法二慢了。此剪枝，方法二不比方法一要好。 排除重復(fù)剪枝注意到題目中時(shí)間這個(gè)關(guān)鍵要素的范圍為059，而車輛數(shù)目可達(dá)300，說明，在同一時(shí)間到達(dá)的車輛數(shù)目很多！前面那個(gè)簡(jiǎn)單例子中，就出現(xiàn)了兩個(gè)14，而到達(dá)時(shí)間為14的兩輛車各屬于那條路線是等效的，這就有重復(fù)。方法一對(duì)于同時(shí)到達(dá)的且未確定歸屬的車，若編號(hào)小的車為某路線的第一輛車，則編號(hào)大的車為也必為一條路線的第一輛車。方法二，對(duì)到達(dá)時(shí)間相同的且未確定歸屬的車，固定只選編號(hào)最小的車為第二輛車。兩者剪去的都是重復(fù)的枝，所以，效果是一樣的，故此剪枝上，雙方平分秋色。結(jié)論：由于方法一搜索樹的良好特性，使得方法一在剪枝優(yōu)化方面前景更廣闊。 關(guān)于誰的操作量小的比較：操作量是“主遞歸程序操作量”的簡(jiǎn)稱，由主遞歸程序的枚舉循環(huán)和剪枝函數(shù)決定的。主遞歸程序的枚舉循環(huán)方法一，每層利用循環(huán)來枚舉一輛車是屬于新路線的第一輛車還是已知路線的第二輛車，而且搜索樹上這個(gè)循環(huán)枚舉量是由未確定“第二輛車”的線路數(shù)目決定的，最大為17。方法二，每層枚舉哪輛車是第二輛車。由于用了排除重復(fù)剪枝，這個(gè)循環(huán)量最大為60。直觀上看兩者的最大界限就已知道，方法二不比方法一好。剪枝函數(shù)消耗時(shí)間由于本題特殊性，主要剪枝函數(shù)基本上差異不大，消耗時(shí)間也差不多。結(jié)論：操作量大小方面，方法二不比方法一好。最終結(jié)論：通過以上微觀理論分析，對(duì)兩種方法進(jìn)行了比較，得出最終結(jié)論是：方法一比方法二好！選定了搜索對(duì)象和策略，剛才又分析了實(shí)現(xiàn)中的主要問題：如何剪枝，編寫程序自然就得心應(yīng)手了。事實(shí)也證明了我們的結(jié)論。兩種程序運(yù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è)方面為標(biāo)準(zhǔn)呢？我們知道：深度搜索消耗時(shí)間 每個(gè)節(jié)點(diǎn)操作系數(shù) 節(jié)點(diǎn)個(gè)數(shù)從上面一個(gè)公式，我們很顯然地能從微觀上看出，要減少消耗時(shí)間，一是減少節(jié)點(diǎn)個(gè)數(shù)這就是我們所說地剪枝優(yōu)化；二是減少每個(gè)節(jié)點(diǎn)的操作系數(shù)即剛才分析的程序操作量。為了提高搜索效率，根據(jù)這個(gè)公式，我們往往在以上兩方面反復(fù)進(jìn)行改進(jìn)。殊不知，從宏觀前提上，如何才能使我們“可以、充分、有效”剪枝，如何才能使我們“可以、充分、有效”降低程序操作量也都是很重要的！于是，搜索對(duì)象和策略為剪枝，降低操作系數(shù)創(chuàng)造前提條件的好壞就成了我們的標(biāo)準(zhǔn)！剪枝后的節(jié)點(diǎn)個(gè)數(shù)每個(gè)節(jié)點(diǎn)的操作系數(shù)深度搜索消耗時(shí)間平衡點(diǎn)但是，在以這兩方面為標(biāo)準(zhǔn)比較的時(shí)候，我們要注意到：這兩個(gè)標(biāo)準(zhǔn)緊密關(guān)聯(lián)，要剪枝多，就要有好的復(fù)雜的剪枝函數(shù)，但這就增大了每個(gè)節(jié)點(diǎn)操作系數(shù)。如圖所示：兩者在目的上是統(tǒng)一的，效果上卻是對(duì)立的。在以這兩者為標(biāo)準(zhǔn)的時(shí)候，要把握好“如何協(xié)調(diào)，找準(zhǔn)兩者平衡點(diǎn)”。總的來說，對(duì)深度搜索題目，一個(gè)好的搜索對(duì)象和策略是十分重要的。本文通過對(duì)