<ins id="ut1r0"></ins>

    1. <ins id="ut1r0"><option id="ut1r0"></option></ins>
      <ins id="ut1r0"><video id="ut1r0"><optgroup id="ut1r0"></optgroup></video></ins>
      1. 會員中心 |  會員注冊  |  兼職信息發布    瀏覽手機版!    精選9.9元!    人工翻譯    英語IT服務 貧困兒童資助 | 留言板 | 設為首頁 | 加入收藏  繁體中文
        當前位置:首頁 > 機翻技術 > 機器翻譯 > 正文

        搜索算法介紹

        發布時間: 2023-08-29 09:25:34   作者:etogether.net   來源: 網絡   瀏覽次數:
        摘要: 抽象地看,所有的搜索算法都是在探索一個具有不同的可能狀態的空間,以找到一些能夠滿足搜索目標的狀態。


        本質上所有的人工智能程序都使用某種形式的搜索來找到想要的結果。事實上,人工智能的一個領域專門研究不同的搜索算法。抽象地看,所有的搜索算法都是在探索一個具有不同的可能狀態的空間,以找到一些能夠滿足搜索目標的狀態。舉例來說,在一個下國際象棋的程序中,一個狀態就表示下棋過程中的第一個棋盤局面。而目標就是要找到一個狀態,使得下棋程序能夠將對手將死。要搜索一個贏的狀態,程序要使用一種轉換函數,根據輸入的一個狀態生成另一個狀態。在下棋的程序中,這個轉換函數可以定義為棋子的移動。給定一個狀態,程序根據一個可能的移動計算出一個新的狀態。典型地,程序需要根據所有可能的移動來考慮產生的狀態集合。這些狀態被稱為后繼狀態。


        國際象棋是一種非常復雜的游戲,會產生相當復雜的搜索空間。這里,我們先討論一個非常簡單的例子。假設你想找到一個朋友的密碼鎖的數字組合。你可以隨機地嘗試各種組合并且希望有好運氣,但是如果你想要系統地考慮所有的可能,則應該決定一種專門的搜索策略。我們可以按照下面的方式將這個問題形式化為一個狀態空間搜索問題。這里,“狀態”表示你已經處理過的數字的一個列表。當你撥另一個數字時,就完成了一次“移動”,并產生了一個新的狀態,表現為在原來的狀態尾部加入這個新的數字。假設我們并不知道需要撥多少數字。為了使這個例子保持在可控制的范圍內,我們還假設密碼鎖只有兩個數字1和2。圖B.1給出了涉及最多3個數字的狀態空間。從初始狀態()開始,我們撥數字1或者2,這樣就有了兩個后繼狀態(1)和(2),如圖所示。從這兩個狀態開始,我們可以撥第二個數字,這樣每個狀態又有兩個后繼狀態,這樣一直繼續下去。很多搜索策略的研究都可以在一個一般性的框架下進行,這個框架需要維護一個還需要嘗試的狀態列表。假設TODO就是一個你需要考慮的狀態列表。


        圖B.1.png

        圖B.1簡單密碼鎖的搜索空間


        1. 將TODO初始化為僅包含初始狀態的(())的列表;

        2. 重復下面的操作直至找到目標狀態:

           2.1 從TODO中移出一個狀態;

           2.2 檢查它是否是目標狀態(是否能開鎖?);

           2.3 如果不能,生成所有后繼狀態,并將其加入到TODO列表中。


        根據選擇下一個要處理的狀態的策略的不同,產生了不同的搜索策略。有兩種基本的策略。第一種是深度優先策略,使用一個棧作為TODO列表。這樣,它總是選擇最后一個加到棧中的狀態做進一步的處理??紤]在密碼鎖問題的處理中采用這種策略,假設實際的組合是(211)。一開始,TOD0中只有初始狀態()。兩個后繼狀態被加入到列表中,也就是(1)和(2)。加入這兩個狀態后,TOD0值為((1)(2))。下一步選擇狀態(1)。發現它不是目標狀態(也就是說,它不能開鎖),因此兩個后繼狀態,(11)和(12),產生并加到了TOD0列表中,這時TOD0列表變成了((11)(12)(2))。下面選擇狀態(11),發現鎖依然無法打開后,兩個后繼狀態(111)和(112)產生出來,并被加入到TOD0列表中,這時TOD0列表變成了((111)(112)(12)(2))。知道(111)不是密碼后,后繼狀態(1111)和(1112)被加入到TOD0列表中?,F在你也許注意到了,除非給這個算法規定一個需要產生的數字位數的上限,否則這個策略永遠不會找到答案。


        另外一種基本的策略稱為廣度優先搜索,將TOD0當做隊列而不是棧。這樣,后繼狀態被添加到TOD0列表的末尾。還是從狀態()開始,TOD0列表在算法運行過程中依次取下面這些值:


        ((1)(2))

        ((2)(1 1)(1 2))

        ((1 1)(1 2)(21)(2 2))

        ((12)(2 1)(22)(11 1)(1 12))

        ((21)(22)(111)(112)(121)(122))

        等等


        可以看到這兩種策略以很不一樣的順序探索這個空間。如果在圖B.1所示的表示這個搜索空間的樹中依據這兩種策略來跟蹤搜索到的狀態,會看到深度優先策略在這棵樹上快速向下移動,不斷地在更深的層次上探索狀態。另一方面,廣度優先策略總是系統地探索樹的某一個層次上所有可能的狀態,然后才考慮下一個層次的狀態。


        對于有限的搜索空間[舉例來說,我們可以指定密碼最多只有4位,因此類似(1111)的狀態就沒有后繼狀態],通常深度優先策略會更快地找到答案。不過,對于無限的搜索空間,就像對于不限長度的密碼鎖問題一樣,深度優先策略不能保證會找到答案,因為它可能會沿著一條具有無限后繼狀態但又不包含答案的鏈搜索下去。廣度優先策略可以保證如果存在一個答案就一定能夠找到。


        很多其他搜索策略也是可能的。一種稱為迭代深化的策略類似于深度優先策略,不過它在到達一個特定的深度后就會停下來。如果在特定的深度上沒有找到答案,它就增加深度并重復上述操作。雖然這會導致重復勞動,不過人們發現它總體上要好于純粹的深度優先或廣度優先策略。作為選擇,你也可以使用啟發式搜索,這種策略采用某種啟發式信息來選擇下一個狀態。舉例來說,如果你認為不包含相同數字反復出現的序列更有可能是密碼,你也許總是盡可能選擇一個不包含重復數字的狀態,只有在不存在這種狀態時才考慮其他的可能性。你可能將包含重復數字的狀態加入到TOD0列表的末尾,而將其他狀態加入到前面。


        ((1)(2))

        ((1 2)(2)(1 1))

        ((121)(2)(11)(122))

        等等


        啟發式搜索的一種一般化的形式描述稱為最佳優先搜索。這種策略使用一個函數,為每一個狀態返回一個啟發式的值。在搜索的每一步,你都選擇值最高的狀態。


        責任編輯:admin


        微信公眾號

        • 上一篇:邏輯程序設計
        • 下一篇:識別語內表現行為


        • 《譯聚網》倡導尊重與保護知識產權。如發現本站文章存在版權問題,煩請30天內提供版權疑問、身份證明、版權證明、聯系方式等發郵件至info@qiqee.net,我們將及時溝通與處理。


        我來說兩句
        評分: 1分 2分 3分 4分 5分
        評論內容:
        驗證碼:
        【網友評論僅供其表達個人看法,并不表明本站同意其觀點或證實其描述?!?
        評論列表
        已有 0 條評論(查看更多評論)

        天天AV天天翘,开心五月天|开心播播网,亚洲无码网站在现观看,快穿被c翻校园h

          <ins id="ut1r0"></ins>

          1. <ins id="ut1r0"><option id="ut1r0"></option></ins>
            <ins id="ut1r0"><video id="ut1r0"><optgroup id="ut1r0"></optgroup></video></ins>