Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
การค้นแบบกองซ้อนบีม (อังกฤษ: Beam stack search) เป็นการขั้นตอนวิธีการค้นหาที่รวมการย้อนรอย (backtracking) เข้ากับการใช้การค้นแบบบีม(beam search) โดยขั้นตอนวิธีการค้นหานี้เป็นขั้นตอนวิธีที่หาคำตอบที่ดีที่สุดได้โดยการหาผลเฉลยด้วยวิธีที่หาผลเฉลยได้เร็ว เช่น การค้นแบบบีม จากนั้นจึงใช้การย้อนรอยเพื่อหาผลเฉลยที่ดีกว่าจนกว่าจะไม่สามารถหาได้อีก
แนวคิด
เนื่องจากการค้นแบบบีมสามารถใช้เป็นขั้นตอนวิธีในการค้นหาที่หาผลเฉลยได้ภายในเวลาและหน่วยความจำที่น้อย แม้ในการค้นหาปริภูมิสถานะ (stage space search) ที่ใหญ่ แต่การค้นแบบบีมก็มีข้อเสียที่สำคัญคือ ความไม่สมบูรณ์ เพราะในการค้นแบบบีมนั้นมีความเป็นไปได้ที่ผลเฉลยที่ต้องการจะถูกตัดออกไปในระหว่างการค้นหา ผลเฉลยที่ได้จากการค้นแบบบีมนั้นจึงไม่สามารถรับรองได้ว่าเป็นผลเฉลยที่ดีที่สุด ดังนั้นจึงมีการใช้ กองซ้อน เพื่อช่วยในการย้อนรอยเพื่อให้ได้คำตอบที่สมบูรณ์
การใช้งาน
การค้นหาแบบกองซ้อนบีมสามารถมองเป็นเหมือน การค้นตามแนวกว้างแบบขยายและจำกัดเขต (breadth first search branch-and-bound) ที่ปรับปรุงให้ไม่มีการเก็บปมไว้มากกว่าความกว้างบีม (beam width)
โดยการค้นหาจะทำโดยขยายตามแนวกว้าง(breadth first) และใช้ค่าในการตัดสินใจเพื่อจะตัดปมออกจากการค้นหาเป็น
- f(n)=g(n)+h(n)
- เมื่อ f(n) เป็นค่าที่พิจารณาของปม n
- g(n) เป็นค่าที่ดีที่สุดจากจุดเริ่มจนถึงปม n
- h(n) เป็นค่าประมาณที่ใช้จากจุด n ไปจนถึงเป้าหมาย
- เพื่อที่จะทำการย้อนรอยได้ จะต้องเก็บค่าของแต่ละชั้นที่ทำการค้นหา โดยจะเก็บปมที่ผ่านการค้นหาลงในกองซ้อน และต้องมีการจำด้วยว่าปมลูกของปมนั้นๆ มีปมใดผ่านการค้นหาแล้ว และปมใดที่ยังไม่ผ่านการค้นหา
โดยทำได้โดยในการขยายจะมีการกำหนดขอบเขตค่า f ของปมลูกที่จะพิจารณา และเมื่อมีการย้อนรอยกลับมาถึงปมก็จะทำการขยายปมนั้นโดยเปลี่ยนขอบเขตค่า f ปมลูก โดยการเปลี่ยนขอบบนใหม่ให้มากกว่าขอบบนเก่า และให้ขอบล่างใหม่มีค่าเท่ากับขอบบนเก่า ไปเรื่อยๆจนกว่าขอบบนใหม่จะมีค่ามากกว่าผลเฉลยที่ดีที่สุดที่เคยหาได้
- เมื่อมีการค้นหาไปแล้วมีการเก็บปมมากกว่าความกว้างบีม จะทำการตัดปมที่เก็บออกเพื่อให้สามารถทำงานต่อได้โดยไม่ต้องเก็บปมไว้มากกว่าความกว้างบีม โดยจะเริ่มตัดจากปมที่มีค่า f สูงที่สุด และไปแก้ขอบเขตการหาของปมแม่ของปมนั้น เมื่อมีการย้อนรอยขึ้นไป ปมที่ถูกตัดจะได้ถูกค้นหาอีกรอบ
วิเคราะห์การทำงาน
ความสมบูรณ์ของขั้นตอนวิธี (Completeness)
การค้นหาแบบกองซ้อนบีม มีความสมบูรณ์ กล่าวคือหากมีผลเฉลย การค้นหาแบบกองซ้อนบีมจะหาเจอ และจะหาเจอคำตอบที่ดีที่สุดเท่าที่จะมีเมื่อการค้นหาเสร็จ
การทำงานเชิงหน่วยความจำ (Space Complexity)
การค้นหาแบบกองซ้อนบีม จะใช้หน่วยความจำในการค้นหาขึ้นอยู่กับความกว้างบีม และความสูงของต้นไม้ที่ทำการค้น โดยให้ต้นไม้ที่ค้นสูง d และมีความกว้างบีม w จะใช้พื้นที่หน่วยความจำเป็น O(wd)
เปรียบเทียบการทำงาน
การทำงานของการค้นหาแบบกองซ้อน จะขึ้นอยู่กับการกำหนด ความกว้างบีม โดยเมื่อกำหนดให้เท่ากับ 1 จะทำงานเหมือนกับ การค้นตามแนวลึก และเมื่อกำหนดความกว้างบีมให้ไม่จำกัด จะทำงานเหมือนกับการค้นตามแนวกว้าง
อ้างอิง
- Zhou, Rong. Hansen, Eric. "Beam-Stack Search: Integrating Backtracking with Beam Search". 2005.
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
karkhnaebbkxngsxnbim xngkvs Beam stack search epnkarkhntxnwithikarkhnhathirwmkaryxnrxy backtracking ekhakbkarichkarkhnaebbbim beam search odykhntxnwithikarkhnhaniepnkhntxnwithithihakhatxbthidithisudidodykarhaphlechlydwywithithihaphlechlyiderw echn karkhnaebbbim caknncungichkaryxnrxyephuxhaphlechlythidikwacnkwacaimsamarthhaidxikaenwkhidenuxngcakkarkhnaebbbimsamarthichepnkhntxnwithiinkarkhnhathihaphlechlyidphayinewlaaelahnwykhwamcathinxy aeminkarkhnhapriphumisthana stage space search thiihy aetkarkhnaebbbimkmikhxesiythisakhykhux khwamimsmburn ephraainkarkhnaebbbimnnmikhwamepnipidthiphlechlythitxngkarcathuktdxxkipinrahwangkarkhnha phlechlythiidcakkarkhnaebbbimnncungimsamarthrbrxngidwaepnphlechlythidithisud dngnncungmikarich kxngsxn ephuxchwyinkaryxnrxyephuxihidkhatxbthismburnkarichngankarkhnhaaebbkxngsxnbimsamarthmxngepnehmuxn karkhntamaenwkwangaebbkhyayaelacakdekht breadth first search branch and bound thiprbprungihimmikarekbpmiwmakkwakhwamkwangbim beam width odykarkhnhacathaodykhyaytamaenwkwang breadth first aelaichkhainkartdsinicephuxcatdpmxxkcakkarkhnhaepn f n g n h n emux f n epnkhathiphicarnakhxngpm n g n epnkhathidithisudcakcuderimcnthungpm n h n epnkhapramanthiichcakcud n ipcnthungepahmayephuxthicathakaryxnrxyid catxngekbkhakhxngaetlachnthithakarkhnha odycaekbpmthiphankarkhnhalnginkxngsxn aelatxngmikarcadwywapmlukkhxngpmnn mipmidphankarkhnhaaelw aelapmidthiyngimphankarkhnha odythaidodyinkarkhyaycamikarkahndkhxbekhtkha f khxngpmlukthicaphicarna aelaemuxmikaryxnrxyklbmathungpmkcathakarkhyaypmnnodyepliynkhxbekhtkha f pmluk odykarepliynkhxbbnihmihmakkwakhxbbneka aelaihkhxblangihmmikhaethakbkhxbbneka iperuxycnkwakhxbbnihmcamikhamakkwaphlechlythidithisudthiekhyhaid emuxmikarkhnhaipaelwmikarekbpmmakkwakhwamkwangbim cathakartdpmthiekbxxkephuxihsamarththangantxidodyimtxngekbpmiwmakkwakhwamkwangbim odycaerimtdcakpmthimikha f sungthisud aelaipaekkhxbekhtkarhakhxngpmaemkhxngpmnn emuxmikaryxnrxykhunip pmthithuktdcaidthukkhnhaxikrxbwiekhraahkarthangankhwamsmburnkhxngkhntxnwithi Completeness karkhnhaaebbkxngsxnbim mikhwamsmburn klawkhuxhakmiphlechly karkhnhaaebbkxngsxnbimcahaecx aelacahaecxkhatxbthidithisudethathicamiemuxkarkhnhaesrc karthanganechinghnwykhwamca Space Complexity karkhnhaaebbkxngsxnbim caichhnwykhwamcainkarkhnhakhunxyukbkhwamkwangbim aelakhwamsungkhxngtnimthithakarkhn odyihtnimthikhnsung d aelamikhwamkwangbim w caichphunthihnwykhwamcaepn O wd epriybethiybkarthangan karthangankhxngkarkhnhaaebbkxngsxn cakhunxyukbkarkahnd khwamkwangbim odyemuxkahndihethakb 1 cathanganehmuxnkb karkhntamaenwluk aelaemuxkahndkhwamkwangbimihimcakd cathanganehmuxnkbkarkhntamaenwkwangxangxingZhou Rong Hansen Eric Beam Stack Search Integrating Backtracking with Beam Search 2005