启发式搜索








Ambox wikify.svg
 本条目部分链接不符合格式手冊規範。跨語言链接及章節標題等處的链接可能需要清理。（2015年12月11日）
請協助改善此條目。參見WP:LINKSTYLE、WP:MOSIW以了解細節。突出显示跨语言链接可以便于检查。

计算机科学中所謂的heuristic，除了有經驗法則的意思外（見啟發式），它還有另外兩個技術上的意義。




目录






  • 1 啟發式演算法


  • 2 啟發式演算法與最短路徑問題


    • 2.1 啟發式演算法對運算效能的影響


    • 2.2 找尋新的啟發式演算法




  • 3 參閱





啟發式演算法


電腦科學的兩大基礎目標，就是發現可證明其執行效率良好且可得最佳解或次佳解的演算法。而啟發式演算法則試圖一次提供一个或全部目標。例如它常能發現很不錯的解，但也沒辦法證明它不會得到較壞的解；它通常可在合理時間解出答案，但也沒辦法知道它是否每次都可以這樣的速度求解。


有時候人們會發現在某些特殊情況下，啟發式演算法會得到很壞的答案或效率極差，然而造成那些特殊情況的資料結構，也許永遠不會在現實世界出現。因此現實世界中啟發式演算法很常用來解決問題。啟發式演算法處理許多實際問題時通常可以在合理時間內得到不錯的答案。


有一類的通用啟發式策略稱為元啟發式演算法（metaheuristic），通常使用亂數搜尋技巧。他們可以應用在非常廣泛的問題上，但不能保證效率。



啟發式演算法與最短路徑問題


所謂的最短路径問題有很多種意思，在這裡啟發式指的是一個在一個搜尋樹的節點上定義的函数h(n){displaystyle h(n)}h(n)，用於評估從此節點到目標節點最便宜的路徑。啟發式通常用於資訊充份的搜尋演算法，例如最好优先貪婪演算法與A*。最好优先貪婪演算法會為啟發式函數選擇最低代價的節點；A*則會為g(n)+h(n){displaystyle g(n)+h(n)}g(n)+h(n)選擇最低代價的節點，此g(n){displaystyle g(n)}g(n)是從起始節點到目前節點的路徑的確實代價。如果h(n){displaystyle h(n)}h(n)是可接受的（admissible）意即h(n){displaystyle h(n)}h(n)未曾付出超過達到目標的代價，則A*一定會找出最佳解。


最能感受到啟發式演算法好處的經典問題是n-puzzle。此問題在計算錯誤的拼圖圖形，與計算任兩塊拼圖的曼哈頓距離的總和以及它距離目的有多遠時，使用了本演算法。注意，上述兩條件都必須在可接受的範圍內。



啟發式演算法對運算效能的影響


任何的搜尋問題中，每個節點都有b{displaystyle b}b個選擇以及到達目標的深度d{displaystyle d}d，一個毫無技巧的演算法通常都要搜尋bd{displaystyle b^{d}}b^{d}個節點才能找到答案。啟發式演算法藉由使用某種切割機制降低了分叉率（branching factor）以改進搜尋效率，由bd{displaystyle b^{d}}b^{d}降到較低的b′{displaystyle b'}b'。分叉率可以用來定義啟發式演算法的偏序关系，例如：若在一個n{displaystyle n}n節點的搜尋樹上，h1(n){displaystyle h_{1}(n)}h_{1}(n)的分叉率較h2(n){displaystyle h_{2}(n)}h_{2}(n)低，則h1(n)<h2(n){displaystyle h_{1}(n)<h_{2}(n)}h_{1}(n)<h_{2}(n)。啟發式為每個要解決特定問題的搜尋樹的每個節點提供了較低的分叉率，因此它們擁有較佳效率的計算能力。



找尋新的啟發式演算法


如何找到一個分叉率較少又通用的合理啟發式演算法，已被人工智慧社群深入探究過。他們使用幾種常見技術：


  • 部分問題的解答的代價通常可以評估解決整個問題的代價，通常很合理。例如一個10-puzzle拼盤，解題的代價應該與將1到5的方塊移回正確位置的代價差不多。通常解題者會先建立一個儲存部份問題所需代價的模式資料庫（pattern database）以評估問題。

  • 解決較易的近似問題通常可以拿來合理評估原先問題。例如曼哈頓距離是一個簡單版本的n-puzzle問題，因為我們假設可以獨立移動一個方塊到我們想要的位置，而暫不考慮會移到其他方塊的問題。

  • 給我們一群合理的啟發式函式h1(n),h2(n),...,hi(n){displaystyle h_{1}(n),h_{2}(n),...,h_{i}(n)}h_{1}(n),h_{2}(n),...,h_{i}(n)，而函式h(n)=max{h1(n),h2(n),...,hi(n)}{displaystyle h(n)=max{h_{1}(n),h_{2}(n),...,h_{i}(n)}}h(n)=max{h_{1}(n),h_{2}(n),...,h_{i}(n)}則是個可預測這些函式的啟發式函式。

一個在1993年由A.E. Prieditis寫出的程式ABSOLVER就運用了這些技術，這程式可以自動為問題產生啟發式演算法。ABSOLVER為8-puzzle產生的啟發式演算法優於任何先前存在的！而且它也發現了第一個有用的解魔術方塊的啟發式程式。



參閱



  • 人工智慧

  • 專家系統

  • Heuristic evaluation（英语：Heuristic evaluation）

  • 推理機

  • Inquiry（英语：Inquiry）

  • 解决问题

  • 爬山算法

  • 模拟退火算法

  • 遗传算法

  • Tabu算法

  • 最好优先

  • 通用图

  • A*搜寻算法




Comments

Post a Comment

Popular posts from this blog

Information security

Image
This article is part of a series on Information security Related security categories Internet security Cyberwarfare Computer security Mobile security Network security Threats Computer crime Vulnerability Eavesdropping Malware Spyware Ransomware Trojans Viruses Worms Rootkits Bootkits Keyloggers Screen scrapers Exploits Backdoors Logic bombs Payloads Denial of service Defenses Computer access control Application security Antivirus software Secure coding Secure by default Secure by design Secure operating systems Authentication Multi-factor authentication Authorization Data-centric security Encryption Firewall Intrusion detection system Mobile secure gateway Runtime application self-protection (RASP) v t e Information security , sometimes shortened to InfoSec , is the practice of preventing unauthorized access, use, disclosure, disruption, modification, inspection, recording or destruction of information. Th...
Read more

Volkswagen Group MQB platform

Image
The Volkswagen Group MQB platform is the company's strategy for shared modular design construction of its transverse, front-engine, front-wheel-drive layout (optional front-engine, four-wheel-drive layout) automobiles. Volkswagen spent roughly $60bn [1] developing this new platform and the cars employing it. The platform underpins a wide range of cars from the supermini class to the mid size SUV class. MQB allows Volkswagen to assemble any of its cars based on this platform across all of its MQB ready factories. This allows the Volkswagen group flexibility to shift production as needed between its different factories. Beginning in 2012, Volkswagen Group marketed the strategy under the code name MQB , which stands for Modularer Querbaukasten , translating from German to "Modular Transversal Toolkit" or "Modular Transverse Matrix". [2] [3] MQB is one strategy within VW's overall MB (Modularer Baukasten or modular matrix) program which also includes th...
Read more

刘萌萌

Image
body.skin-minerva .mw-parser-output table.infobox caption{text-align:center} 刘萌萌 女演员 罗马拼音 Liu Meng Meng 英文名 Cya 国籍   中国 民族 汉族 出生 ( 1989-10-16 ) 1989年10月16日 （ 29歲）   中国辽宁省大连市 职业 演员、艺人 语言 汉语 教育程度 沈阳音乐学院 北京电影学院表演系进修班 活跃年代 2011年至今 唱片公司 浙江永乐影视制作有限公司 经纪公司 浙江永乐影视制作有限公司 网站 刘萌萌 官方微博 刘萌萌 （1989年10月16日 － ），汉族，中国演员，2010年参加湖南卫视《芒果训练营》而出道至今，凭借电视剧《爱情公寓》“诺澜”一角走红。北京电影学院10级表演系（进修班）毕业。 目录 1 主要经历 2 影视作品 2.1 电视剧 2.2 电影 2.3 综艺节目 3 参考文献 4 外部链接 主要经历 1989年，出生于辽宁省大连市一个工人家庭； 2006年，考入沈阳音乐学院舞蹈系本科班学习； 2010年，参加湖南卫视《芒果训练营》演艺新秀比赛而出道 [1] ；進入北京电影学院表演系进修班 2011年，出演电视剧《隋唐演义》“琼花公主”一角色； 2012年，担任电视剧《爱情公寓》“诺澜”一角并开始走红 [2] ； 2013年，担任电视剧《利箭纵横》《利剑行动》 [3] 女主角“林筱雨” 2014年，参加江苏卫视真人秀栏目《花样年华》 [4] 备受瞩目 [5] 。 影视作品 电视剧 首播年份 剧名 角色 备注 2012 《爱情公寓3》 诺澜 2012 《利箭行动》 林筱雨 2013 《隋唐演义》 琼花公主 2013 《决战燕子门》 马晓婉 2014 《利箭纵横》 林筱雨 2014 《屌丝日记》 林洛霏 網絡劇 2014 《爱情公寓4》 诺澜 ...
Read more