Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
การค้นแบบบีม (อังกฤษ: Beam Search) เป็นขั้นตอนวิธีในการค้นหาโดยใช้หลักการศึกษาสำนึก โดยแทนที่จะขยายทุกปมในกราฟ การค้นแบบบีมจะเลือกขยายเฉพาะปมจำนวนหนึ่งที่มีโอกาสนำไปสู่คำตอบมากที่สุด
ความแตกต่างระหว่างการค้นแบบบีมกับการค้นตามแนวกว้างคือ ถึงแม้ว่าการค้นตามแนวกว้าง รับรองว่าการค้นจะเจอเส้นวิธีที่สั้นที่สุด (shortest path) จากจุดเริ่มต้นไปยังจุดเป้าหมาย แต่การเลือกใช้การค้นตามแนวกว้างกับปริภูมิการค้น (search space) ที่ใหญ่นั้นไม่สะดวก เพราะว่า หน่วยความจำที่ใช้มีอัตราการเติบโดแบบ (exponential growth) ดังนั้นการค้นแบบแนวกว้างมักจะใช้หน่วยความจำจนหมดก่อนที่จะเจอคำตอบ ด้วยเหตุผลนี้การค้นแบบบีมจึงถูกสร้างขึ้นมาเพื่อพยายามหาคำตอบที่ดีที่สุดที่ได้จากการค้นตามแนวกว้างโดยไม่ใช้หน่วยความจำมากเกินไป
การค้นแบบบีมใช้การค้นตามแนวกว้างในการสร้างต้นไม้ค้นหา ในแต่ละสถานะของการค้น มันจะสร้างปมลูกของปมปัจจุบัน ซึ่งแทนที่จะเก็บทุกปมลูกที่พบ มันจะเรียงลำดับปมลูกจากน้อยไปมากตามจากค่าศึกษาสำนึก (heuristic cost) และเลือกเก็บเฉพาะปมลูกไว้จำนวนหนึ่งตามค่าที่กำหนดไว้ก่อนหน้า ที่เรียกว่าความกว้างของบีม (beam width) ยิ่งค่าความกว้างของบีมมากเท่าไหร่ ปมลูกหรือสถานะ (partial solution state) ก็จะถูกตัดทิ้งน้อยลงเท่านั้น หากค่าความกว้างของบีมมีไม่จำกัด การค้นมีลักษณะเหมือนกับการค้นตามแนวกว้าง กล่าวคือความกว้างของบีมเป็นตัวกำหนดขอบเขตของหน่วยความจำที่ใช้ในการค้นหานั่นเอง
อย่างไรก็ตามสถานะเป้าหมาย (goal state) อาจถูกตัดทิ้งไปขณะที่ทำการค้นเพราะค่าความกว้างของบีมน้อยเกินไป โดยการค้นแบบบีมแลกความสมบูรณ์ (การรับรองว่าขั้นตอนวิธีจะพบคำตอบ ถ้าสามารถหาคำตอบได้) และคำตอบที่ดีที่สุด (การรับรองว่าขั้นตอนวิธีจะเจอคำตอบที่ดีที่สุด) กับความสามารถในการประหยัดหน่วยความจำ
ชื่อ
คำว่า "การค้นแบบบีม" ถูกตั้งโดย แห่งมหาวิทยาลัยคาร์เนกี้เมลอนในปี 1976 เนื่องจากคำว่า บีม (beam) ในภาษาอังกฤษแปลว่าคานซึ่งคือโครงสร้างตามแนวกว้างที่ใช้ในการรับน้ำหนัก จึงใช้แทนคำว่าช่วงกว้าง โดยแตกต่างจากการค้นตามแนวกว้าง ตรงที่การค้นตามแนวกว้างจะขยายปมลูกในแต่ละสถานะการค้นทุกปม แต่การค้นแบบบีมจะขยายปมลูกเพียงบางส่วนเท่านั้น
การใช้งาน
การใช้งาน การค้นแบบบีมถูกใช้ระบบขนาดใหญ่ที่ต้องการความสามารถในการจัดการ โดยมีหน่วยความจำหลักไม่พอที่จะเก็บต้นไม้ค้นหาทั้งต้น เช่น การใช้การค้นหาแบบบีมใน เพื่อที่จะเลือกแปลให้ดีที่สุด ขณะที่ประมวลผลแต่ละส่วน ก็จะมีคำแปลหลายๆแบบเกิดขึ้นมา คำแปลที่ดีที่สุดจะถูกเก็บไปใช้และทิ้งส่วนที่เหลือไป หลังจากนั้นตัวแปลจะทำการวิเคราะห์ประโยคที่เหลือโดยคิดคะแนนตามข้อกำหนด และเลือกคำแปลที่ดีที่สุดไว้
รหัสเทียม
ขั้นตอนวิธี การค้นแบบบีม ข้อมูลรับเข้า: กราฟ G, โหนด s คือ โหนดที่ต้องการเริ่มต้นการค้น, โหนด g คือ โหนดเป้าหลายที่ต้องการค้น, ค่าความกว้างของบีม 'w' สร้างแถวคอย Q โดยเริ่มต้นให้แถวคอยว่าง สร้างรายการ Visited สำหรับบอกว่าปมไหนเคยเจอแล้ว โดยเริ่มค้นให้รายการ Visited ว่าง เพิ่มปมเริ่มต้น s เข้าที่ Q จนกว่า Q จะว่าง หรือ เจอ g ให้ u เป็น ปมหน้าสุดในแถวคอย เอาปม u ออกจากแถวคอย ถ้า v เป็นปมที่ไม่อยู่ในรายการ Visited สำหรับทุกปม v ที่เชื่อมกับ u ให้เลือกเพิ่มปม v ที่มีค่าศึกษาสำนึกดีที่สุดจำนวน w ปมต่อที่แถวคอย Q เพิ่ม u เข้าในรายการ Visited ถ้า เจอปม g การค้นหาสำเร็จ ถ้า ไม่เจอปม g ค้นหาไม่สำเร็จ
ตัวอย่างการทำงาน
แบบที่ 1
ให้หาปม H โดยเริ่มจาก A และกำหนดให้ค่าความกว้างของบีม = 2
| รอบที่ | ปมหน้าสุดของแถวคอย(u) | ปมที่มีเส้นเชื่อมต่อกับ u เรียงตามค่าศึกษาสำนึก | ปมที่ในแถวคอย Q หลังจากเพิ่มปมลูกใหม่เข้าไปแล้ว | ปมในรายการ Visited | หมายเหตุ |
|---|---|---|---|---|---|
| 0 | - | - | {A} | {} | - |
| 1 | A | C,D,B | {C,D} | {A} | ปม B ถูกตัดออกเนื่องจากค่าความกว้างของบีม = 2 จึงเลือกเก็บได้ 2 ปมคือปม C,D |
| 2 | C | G | {D,G} | {A,C} | - |
| 3 | D | H | {G,H} | {A,C,D} | - |
| 4 | G | I | {G,H,I} | {A,C,D,G} | - |
| 5 | H | เจอปมเป้าหมายจบการทำงาน | เจอปมเป้าหมายจบการทำงาน | เจอปมเป้าหมายจบการทำงาน | - |
คำตอบ คือ เจอปม H
แบบที่ 2
ให้หาปม H โดยเริ่มจาก A และกำหนดให้ค่าความกว้างของบีม = 1
| รอบที่ | ปมหน้าสุดของแถวคอย(u) | ปมที่มีเส้นเชื่อมต่อกับ u เรียงตามค่าศึกษาสำนึก | ปมที่ในแถวคอย Q หลังจากเพิ่มปมลูกใหม่เข้าไปแล้ว | ปมในรายการ Visited | หมายเหตุ |
|---|---|---|---|---|---|
| 0 | - | - | {A} | {} | - |
| 1 | A | C,D,B | {C} | {A} | ปม D,B ถูกตัดออกเพราะค่าความกว้างของบีม = 1 ซึ่งเลือกเก็บได้ปมเดียวซึ่งก็คือ C |
| 2 | C | G | {G} | {A,C} | - |
| 3 | G | I | {} | {A,C,G} | - |
| 4 | ไม่มีปมเหลือใน Q จบการทำงาน | ไม่มีปมเหลือใน Q จบการทำงาน | ไม่มีปมเหลือใน Q จบการทำงาน | ไม่มีปมเหลือใน Q จบการทำงาน | - |
คำตอบ คือ ไม่เจอปมเป้าหมาย H ดังนั้นจะเห็นว่าการค้นแบบบีมไม่มีความสมบูรณ์ของขั้นตอนวิธีถึงแม้ว่าจะมีปมเป้าหมาย (H) ในปริภูมิการค้นหา เนื่องจากค่าความกว้างของบีมที่น้อยเกินไปทำให้ปม D ซึ่งเป็นวิถีย่อยเดียวที่นำไปสู่ปมเป้าหมาย (H) ถูกตัดออกไป
วิเคราะห์การทำงาน
(Completeness)
- โดยทั่วไปการค้นแบบบีมจะไม่มีความสมบูรณ์ คือ ขั้นตอนวิธีนี้มีจะไม่เจอปมที่ค้นหาถึงแม้ว่าจะมีวิธี(path)จากปมเริ่มต้นไปยังปมทีต้องการค้นหาก็ตาม เพราะปมที่นำไปสู่ปมเป้าหมายอาจโดนตัดทิ้งระหว่างการค้นเนื่องจากค่าความกว้างของบีมน้อยเกินไป การขาดความสมบูรณ์ของขั้นตอนวิธีเป็นข้อเสียหนึ่งของการค้นแบบบีม
ซึ่งเราสามารถเพิ่มโอกาสให้เจอปมเป้าหมายได้โดยการ ขยายความกว้างของบีมหรือปรับฟังก์ชันศึกษาสำนึกให้แม่นยำมากขึ้น ซึ่งทั่วไปที่นิยมทำกันคือเวลาค้นจะไม่จำหนดความกว้างของบีมตายตัวแต่กำหนดเป็นช่วงแทน โดยจะกำหนดค่าเริ่มค้นให้ เมื่อการค้นครั้งแรกไม่สำเร็จก็จะขยายความกว้างให้มากขึ้น
(Optimality)
- เนื่องจากการค้นไม่มีความสมบูรณ์ของขั้นตอนวิธี จึงไม่ยืนยันว่าจะได้คำตอบที่ดีที่สุด เนื่องจากวิถีย่อยของวิถีที่ดีที่สุดอาจโดนตัดออกไปจากการค้นเนื่องจากค่าความกว้างของบีมน้อยเกินไปเช่นกัน
(Time Complexity)
- ถ้าต้นไม้มีความสูงมากสุดไม่เกิน h หน่วย การทำงานเชิงเวลาจะเป็น O(wh) เนื่องจากในแต่ละชั้นของต้นไม้ค้นหามีปมไม่เกิน w ปม ดังนั้นจะมีปมให้ค้นทั้งหมดไม่เกิน wh ปม ทำให้การค้นแบบบีมมีการทำงานเชิงเวลาเป็นแบบเชิงเส้น ซึ่งเป็นจุดเด่นของการค้นแบบบีมที่ขั้นตอนวิธีแบบอื่นที่มีอัตราการเติบโดแบบแบบอัตราก้าวหน้า (exponential growth) ไม่สามารถทำได้ในปริภูมิการค้นหาขนาดใหญ่ได้
(Space Complexity)
- ถ้าต้นไม้มีความสูงมากสุดไม่เกิน h หน่วย การทำงานเชิงเวลาจะเป็น O(wh) เนื่องจากในแต่ละชั้นของต้นไม้ค้นหามีปมไม่เกิน w ปม ดังนั้นจะมีปมให้ค้นทั้งหมดไม่เกิน wh ปม ทำให้การค้นแบบบีมมีการทำงานเชิงเวลาเป็นแบบเชิงหน่วยความจำ ซึ่งเป็นจุดเด่นของการค้นแบบบีมที่ขั้นตอนวิธีแบบอื่นที่มีอัตราการเติบโดแบบแบบอัตราก้าวหน้า (exponential growth) ไม่สามารถทำได้ในปริภูมิการค้นหาขนาดใหญ่ได้
อ้างอิง
ศึกษาเพิ่มเติม
- โครงสร้างข้อมูล (ฉบับวาจาจาวา) โดยสมชาย ประสิทธิ์จูตระกูล
- การออกแบบอัลกอริทึม (Algorithm Design) โดยสมชาย ประสิทธิ์จูตระกูล
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
karkhnaebbbim xngkvs Beam Search epnkhntxnwithiinkarkhnhaodyichhlkkarsuksasanuk odyaethnthicakhyaythukpminkraf karkhnaebbbimcaeluxkkhyayechphaapmcanwnhnungthimioxkasnaipsukhatxbmakthisud khwamaetktangrahwangkarkhnaebbbimkbkarkhntamaenwkwangkhux thungaemwakarkhntamaenwkwang rbrxngwakarkhncaecxesnwithithisnthisud shortest path cakcuderimtnipyngcudepahmay aetkareluxkichkarkhntamaenwkwangkbpriphumikarkhn search space thiihynnimsadwk ephraawa hnwykhwamcathiichmixtrakaretibodaebb exponential growth dngnnkarkhnaebbaenwkwangmkcaichhnwykhwamcacnhmdkxnthicaecxkhatxb dwyehtuphlnikarkhnaebbbimcungthuksrangkhunmaephuxphyayamhakhatxbthidithisudthiidcakkarkhntamaenwkwangodyimichhnwykhwamcamakekinip karkhnaebbbimichkarkhntamaenwkwanginkarsrangtnimkhnha inaetlasthanakhxngkarkhn mncasrangpmlukkhxngpmpccubn sungaethnthicaekbthukpmlukthiphb mncaeriyngladbpmlukcaknxyipmaktamcakkhasuksasanuk heuristic cost aelaeluxkekbechphaapmlukiwcanwnhnungtamkhathikahndiwkxnhna thieriykwakhwamkwangkhxngbim beam width yingkhakhwamkwangkhxngbimmakethaihr pmlukhruxsthana partial solution state kcathuktdthingnxylngethann hakkhakhwamkwangkhxngbimmiimcakd karkhnmilksnaehmuxnkbkarkhntamaenwkwang klawkhuxkhwamkwangkhxngbimepntwkahndkhxbekhtkhxnghnwykhwamcathiichinkarkhnhannexng xyangirktamsthanaepahmay goal state xacthuktdthingipkhnathithakarkhnephraakhakhwamkwangkhxngbimnxyekinip odykarkhnaebbbimaelkkhwamsmburn karrbrxngwakhntxnwithicaphbkhatxb thasamarthhakhatxbid aelakhatxbthidithisud karrbrxngwakhntxnwithicaecxkhatxbthidithisud kbkhwamsamarthinkarprahydhnwykhwamcachuxkhawa karkhnaebbbim thuktngody aehngmhawithyalykharenkiemlxninpi 1976 enuxngcakkhawa bim beam inphasaxngkvsaeplwakhansungkhuxokhrngsrangtamaenwkwangthiichinkarrbnahnk cungichaethnkhawachwngkwang odyaetktangcakkarkhntamaenwkwang trngthikarkhntamaenwkwangcakhyaypmlukinaetlasthanakarkhnthukpm aetkarkhnaebbbimcakhyaypmlukephiyngbangswnethannkarichngankarichngan karkhnaebbbimthukichrabbkhnadihythitxngkarkhwamsamarthinkarcdkar odymihnwykhwamcahlkimphxthicaekbtnimkhnhathngtn echn karichkarkhnhaaebbbimin ephuxthicaeluxkaeplihdithisud khnathipramwlphlaetlaswn kcamikhaaeplhlayaebbekidkhunma khaaeplthidithisudcathukekbipichaelathingswnthiehluxip hlngcaknntwaeplcathakarwiekhraahpraoykhthiehluxodykhidkhaaenntamkhxkahnd aelaeluxkkhaaeplthidithisudiwrhsethiymkhntxnwithi karkhnaebbbim khxmulrbekha kraf G ohnd s khux ohndthitxngkarerimtnkarkhn ohnd g khux ohndepahlaythitxngkarkhn khakhwamkwangkhxngbim w srangaethwkhxy Q odyerimtnihaethwkhxywang srangraykar Visited sahrbbxkwapmihnekhyecxaelw odyerimkhnihraykar Visited wang ephimpmerimtn s ekhathi Q cnkwa Q cawang hrux ecx g ih u epn pmhnasudinaethwkhxy exapm u xxkcakaethwkhxy tha v epnpmthiimxyuinraykar Visited sahrbthukpm v thiechuxmkb u iheluxkephimpm v thimikhasuksasanukdithisudcanwn w pmtxthiaethwkhxy Q ephim u ekhainraykar Visited tha ecxpm g karkhnhasaerc tha imecxpm g khnhaimsaerc twxyangkarthangan aebbthi 1 ihhapm H odyerimcak A aelakahndihkhakhwamkwangkhxngbim 2 rxbthi pmhnasudkhxngaethwkhxy u pmthimiesnechuxmtxkb u eriyngtamkhasuksasanuk pmthiinaethwkhxy Q hlngcakephimpmlukihmekhaipaelw pminraykar Visited hmayehtu0 A 1 A C D B C D A pm B thuktdxxkenuxngcakkhakhwamkwangkhxngbim 2 cungeluxkekbid 2 pmkhuxpm C D2 C G D G A C 3 D H G H A C D 4 G I G H I A C D G 5 H ecxpmepahmaycbkarthangan ecxpmepahmaycbkarthangan ecxpmepahmaycbkarthangan khatxb khux ecxpm H aebbthi 2 ihhapm H odyerimcak A aelakahndihkhakhwamkwangkhxngbim 1 rxbthi pmhnasudkhxngaethwkhxy u pmthimiesnechuxmtxkb u eriyngtamkhasuksasanuk pmthiinaethwkhxy Q hlngcakephimpmlukihmekhaipaelw pminraykar Visited hmayehtu0 A 1 A C D B C A pm D B thuktdxxkephraakhakhwamkwangkhxngbim 1 sungeluxkekbidpmediywsungkkhux C2 C G G A C 3 G I A C G 4 immipmehluxin Q cbkarthangan immipmehluxin Q cbkarthangan immipmehluxin Q cbkarthangan immipmehluxin Q cbkarthangan khatxb khux imecxpmepahmay H dngnncaehnwakarkhnaebbbimimmikhwamsmburnkhxngkhntxnwithithungaemwacamipmepahmay H inpriphumikarkhnha enuxngcakkhakhwamkwangkhxngbimthinxyekinipthaihpm D sungepnwithiyxyediywthinaipsupmepahmay H thuktdxxkipwiekhraahkarthangan Completeness odythwipkarkhnaebbbimcaimmikhwamsmburn khux khntxnwithinimicaimecxpmthikhnhathungaemwacamiwithi path cakpmerimtnipyngpmthitxngkarkhnhaktam ephraapmthinaipsupmepahmayxacodntdthingrahwangkarkhnenuxngcakkhakhwamkwangkhxngbimnxyekinip karkhadkhwamsmburnkhxngkhntxnwithiepnkhxesiyhnungkhxngkarkhnaebbbim sungerasamarthephimoxkasihecxpmepahmayidodykar khyaykhwamkwangkhxngbimhruxprbfngkchnsuksasanukihaemnyamakkhun sungthwipthiniymthaknkhuxewlakhncaimcahndkhwamkwangkhxngbimtaytwaetkahndepnchwngaethn odycakahndkhaerimkhnih emuxkarkhnkhrngaerkimsaerckcakhyaykhwamkwangihmakkhun Optimality enuxngcakkarkhnimmikhwamsmburnkhxngkhntxnwithi cungimyunynwacaidkhatxbthidithisud enuxngcakwithiyxykhxngwithithidithisudxacodntdxxkipcakkarkhnenuxngcakkhakhwamkwangkhxngbimnxyekinipechnkn Time Complexity thatnimmikhwamsungmaksudimekin h hnwy karthanganechingewlacaepn O wh enuxngcakinaetlachnkhxngtnimkhnhamipmimekin w pm dngnncamipmihkhnthnghmdimekin wh pm thaihkarkhnaebbbimmikarthanganechingewlaepnaebbechingesn sungepncudednkhxngkarkhnaebbbimthikhntxnwithiaebbxunthimixtrakaretibodaebbaebbxtrakawhna exponential growth imsamarththaidinpriphumikarkhnhakhnadihyid Space Complexity thatnimmikhwamsungmaksudimekin h hnwy karthanganechingewlacaepn O wh enuxngcakinaetlachnkhxngtnimkhnhamipmimekin w pm dngnncamipmihkhnthnghmdimekin wh pm thaihkarkhnaebbbimmikarthanganechingewlaepnaebbechinghnwykhwamca sungepncudednkhxngkarkhnaebbbimthikhntxnwithiaebbxunthimixtrakaretibodaebbaebbxtrakawhna exponential growth imsamarththaidinpriphumikarkhnhakhnadihyidxangxinghttp jhave org algorithms graphs beamsearch beamsearch shtml 2012 01 31 thi ewyaebkaemchchin http ai depot com Tutorial PathFinding Heuristics html 2012 08 12 thi ewyaebkaemchchinsuksaephimetimokhrngsrangkhxmul chbbwacacawa odysmchay prasiththicutrakul karxxkaebbxlkxrithum Algorithm Design odysmchay prasiththicutrakul