Ira Pohlคือบุคคลแรกที่ออกแบบและนำเอาการค้นหาแบบสองทิศทางมาใช้ในปีค.ศ.1971 เริ่มแรกนั้นขั้นตอนวิธีดังกล่าวไม่มีประสิทธิภาพมากนักคือการค้นหาจากสองทางมักจะพลาดไม่ได้มาบรรจบกันทำให้ได้ผลลัพธ์ที่ผิดพลาด ต่อมาในปีค.ศ.1983 Des Champeaux ได้ออกแบบขั้นตอนวิธีใหม่เพื่อเข้ามาใช้แก้ปัญหาดังกล่าวด้วยวิธีแบบBHFFA(Bidirectional heuristic front to front algorithm)แต่ก็ทำให้เกิดปัญหาในเรื่องพื้นที่หน่วยความจำ ต่อมาในปีค.ศ.1984 PohlและPolitowiskyได้นำเสนอทางออกอีกแบบที่เขาเรียกว่า D-node retargetingขึ้นมาซึ่งสามารถช่วยแก้ปัญหาที่มีมาแต่เดิมรวมถึงเรื่องของหน่วยความจำได้อย่างมีประสิทธิภาพกว่าเก่า
Pohl, Ira (1971), "Bi-directional Search", ใน Meltzer, Bernard; Michie, Donald (บ.ก.), Machine Intelligence, 6, Edinburgh University Press, pp. 127–140.
Russell, Stuart J.; Norvig, Peter (2002), "3.4 Uninformed search strategies", Artificial Intelligence: A Modern Approach (2nd ed.), Prentice Hall.
Davis, Henry W.; Pollack, Randy B.; Sudkamp, Thomas (1984), "Towards a better understanding of Bidirectional search", AAAI'84: 68–72.
Pijls, Wim; Post, Henk (2009), "A new bidirectional search algorithm with shortened postprocessing", European Journal of Operational Research: 363–369.
ตุลาคม 11, 2021
การค, นหาแบบสองท, ศทาง, งก, ามภาษา, ในบทความน, ไว, ให, านและผ, วมแก, ไขบทความศ, กษาเพ, มเต, มโดยสะดวก, เน, องจากว, เด, ยภาษาไทยย, งไม, บทความด, งกล, าว, กระน, ควรร, บสร, างเป, นบทความโดยเร, วท, งกฤษ, bidirectional, search, อว, หน, งท, ใช, สำหร, บการค, นหาข, อม. lingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisudkarkhnhaaebbsxngthisthang xngkvs Bidirectional Search khuxwithihnungthiichsahrbkarkhnhakhxmulphayinkrafrabuthisthang odymicudprasngkhepnkarhawithisnsudcakcuderimtnipyngcudsinsudbnkraf hlkkarkhnhathiepnexklksnkhxngwithikarnikkhuxeracathakarkhnhacakcuderimipyngcudsinsudaelacakcudsinsudklbmayngcuderimtnipphrxmkn aelaemuxkarkhnhamabrrcbphrxmknthicudhnungrahwangklangkcathuxepnxnsinsud nxkcaknikarkhnhaaebbsxngthisthangniyngsamarthnaexaipprayuktrwmekhakbkarkhnhaaebbxunephuxihidprasiththiphaphthidiyingkhunid twxyangkhxngwithikarkhnhathisamarthnaexamaprayuktkbkarkhnhaaebbsxngthisthangechn karkhntamaenwkwang karkhnaebbdithisud khntxnwithiexstarepntn thngnikephuxthicaephimprasiththiphaphinkarkhnhaihdithisudnnexngkarkhnhaaebbsxngthisthangphsmkbkarkhnhaaebbkracaytamaenwkhwang enuxha 1 niyam 2 prawti 3 karthangan 4 rhsethiym 5 xangxingniyam aekikhkarkhnhaaebbsxngthisthangnnodyniyamaelwkkhuxkhntxnwithithiichhlkkarsungkhlaykbkhntxnwithiaebngaeykephuxexachna xngkvs Divide and conquer inkrnithierathrabtaaehnngkhxngepahmaythicakhnhaaelw aethnthicakhxyerimcakcuderimtnipyngcudplayeracathakarkhnhacakcudplayyxnklbmahacuderimtnipphrxmknaethn dwywithinikhwamerwinkarkhnhakhxngaetlaesnthangcaxyuthi O bd 2 emux b displaystyle b khuxcanwnkaraetkkingkan Branching factor aela d displaystyle d khuxrayathangthnghmdcakcuderimtnipyngcudsinsud sungemuxnarayaewlakarkhnhamarwmknaelwkyngthuxwaidldewlainkarkhnhalngipxyangmakhakethiybkbkarkhnhaaebbpkti O bd xyangirktamaemwawithikarnicaduehmuxnwasamarththicaldewlakarkhnhaipidxyangmakktam khxesiykhxngmnkyngmixyuhlaykhxdwyknkhux withikarkhnhaaebbsxngthisthangmilksnathiepnsuksasanukhruxkkhuximsamarthbxkidxyangaennxnwaesnthangthihaidepnesnthangthidithisudhruxim inkarxxkaebbkhntxnwithicaepnthicatxngkhidhawithikarthicathaihsamarthkhnhacakcudplayihyxnklbmayngcuderimtnid txngxxkaebbwithikarhacudechuxmtxthimacakkarkhnkhxngthngsxngthisthang txngmikarkahndepahmaywaxyuthiidbnkrafdwysaehtuthngpwngthiklawmathaihkarnaexawithikarkhnhaaebbsxngthisthangipichngancringnncungyungyakphxsmkhwrprawti aekikhIra Pohlkhuxbukhkhlaerkthixxkaebbaelanaexakarkhnhaaebbsxngthisthangmaichinpikh s 1971 erimaerknnkhntxnwithidngklawimmiprasiththiphaphmaknkkhuxkarkhnhacaksxngthangmkcaphladimidmabrrcbknthaihidphllphththiphidphlad txmainpikh s 1983 Des Champeaux idxxkaebbkhntxnwithiihmephuxekhamaichaekpyhadngklawdwywithiaebbBHFFA Bidirectional heuristic front to front algorithm aetkthaihekidpyhaineruxngphunthihnwykhwamca txmainpikh s 1984 PohlaelaPolitowiskyidnaesnxthangxxkxikaebbthiekhaeriykwa D node retargetingkhunmasungsamarthchwyaekpyhathimimaaetedimrwmthungeruxngkhxnghnwykhwamcaidxyangmiprasiththiphaphkwaekahlngcaknnwithikarkhnhaaebbsxngthisthangkidphankarprbprungeruxymaxikhlaykhrngcnthunglasudkhuxpikh s 2009odyWimaelaHenk sungidkhidkhnxxkaebbkarkhnhaaebbsxngthisthangkhxngexstarthiidrbkarprngprungihkhnhaidxyangmiprasiththiphaphyingkhunkarthangan aekikh phaphtwxyangkhxngkarkhnhaaebbsxngthisthang cakkrafdanbneracasamarthmxngehnkarthangankhrawidody hakerasmmtiih wngklmaetlawngkhuxpmkhxngkrafodythiaetlapmcaekbkhataaehnngkhxngpmnnexaiw esnechuxmthihnacahmaythungkhaichcaythimakkwainkaredinthangphan swnpmthithukthadwysifacahmaythungepnpmthithukeluxkaelapmsiaedngkhuxcudthikhadwakarkhnhacaksxngthisthangmabrrcbkn esnpraichaesdngkhxbekhtkhxngkarkhnhaaeykaetlafngexaiw inaengkhxngkarnaexaipichngancringnn karkhnhaaebbsxngthisthangmkcathuknaiprwmekhakbkhntxnwithiaebbxunesiymakkwa thngnikephuxthicaihidphllphthxxkmatamaetthitxngkarrhsethiym aekikhkhntxnwithisamarthaesdngodysngekhpdwyrhsethiymiddngni function BiderectionalSearch xs xg define Qs Qg as priority queue kahndaethwkhxyaebbladbkhwamsakhy ihQskhuxaethwkhxythiichekberimcakpmerimtn aelaQgkhuxaethwkhxythiichekberimcakpmepahmay Qs insert xs and mark xs as visited napmerimtn xsislnginQs aelaepliynsthanakhxngxsihepnpmthithukphicarnaaelw Qg insert xg and mark xg as visited napmepahmay xgislnginQg aelaepliynsthanakhxngxgihepnpmthithukphicarnaaelw while Qs not empty and Qg not empty if Qs not empty x Qs getFirst if x xg or x ɛ Qg thahakwapmthikalngduepnpmepahmayhruxwaepnpmthixyuinaethwkhxykhxngepahmayaelwkihaesdngxxkipwahaphbaelaeliktha return SUCCESS for each v ɛ adj x sahrbthukpmthimiesnechuxmtxxxkx hakpmnnyngimekhythukphicarnakihexaekhaaethwkhxyip if v is not visited Mark v status as visited Qs insert v if Qg not empty xr Qg getFirst if xr xs or xr ɛ Qs thahakwapmthikalngduepnpmerimtnhruxwaepnpmthixyuinaethwkhxykhxngpmerimtnaelwkihaesdngxxkipwahaphbaelaeliktha return SUCCESS for each vr ɛ inversed adj xr sahrbthukpmthimiesnechuxmmayngxr hakpmnnyngimekhythukphicarnakihexaekhaaethwkhxyip if vr is not visited Mark vr status as visited Qs insert vr return FAILURE thathacnhmdaelwyngechuxmesnknimidkkhuximmiesnechuxmrahwangxskbxgxangxing aekikhde Champeaux Dennis Sint Lenie 1977 An improved bidirectional heuristic search algorithm Journal of the ACM 24 2 177 191 doi 10 1145 322003 322004 de Champeaux Dennis 1983 Bidirectional heuristic search again Journal of the ACM 30 1 22 32 doi 10 1145 322358 322360 Ghosh Subrata Mahanti Ambuj 1991 Bidirectional Heuristic Search with Limited Resources Inf Process Lett 335 340 Pohl Ira 1971 Bi directional Search in Meltzer Bernard Michie Donald b k Machine Intelligence 6 Edinburgh University Press pp 127 140 Russell Stuart J Norvig Peter 2002 3 4 Uninformed search strategies Artificial Intelligence A Modern Approach 2nd ed Prentice Hall Davis Henry W Pollack Randy B Sudkamp Thomas 1984 Towards a better understanding of Bidirectional search AAAI 84 68 72 Pijls Wim Post Henk 2009 A new bidirectional search algorithm with shortened postprocessing European Journal of Operational Research 363 369 ekhathungcak https th wikipedia org w index php title karkhnhaaebbsxngthisthang amp oldid 4700731, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,