Lexicographic Breadth-First Search เป็นวิธีการค้นหาข้อมูลแบบหนึ่งที่คล้ายกับ breadth-first search แต่เปลี่ยนจากการนำเส้นเข้าแถว เปลี่ยนเป็นนำ set ของจุดเข้าแถวแทน โดยที่ set ในแถวนั้นคือ set ที่เกิดจากการแบ่งกลุ่มจุด ที่ยังไม่ได้รวมเข้าด้วยกัน ในแต่ละขั้นตอน จะทำการดึง จุด v (จุดใดๆ ใน set)จาก set หน้าสุดของแถว ออกมาจากแถวและ ถ้าการดึงนั้นทำให้ทำให้ set นั้นว่างก็จะดึง set นั้นออกจากแถว หลังจากนั้น ทุกๆ set ในแถวจะถูกแทนที่ด้วย 2 subsets คือ set ที่มี v เชื่อม และ set ที่ไม่มี v เชื่อม โดย set ที่มี v เชื่อมจะถูกนำมาเข้าแถวก่อน อีกแบบหนึ่ง วิธีการทำงานดังนี้ :
- ให้แถวผลลัพธ์เป็นว่างเปล่า
- ถ้ายังมีset ในแถว :
- หาจุด v และ เอาจุด v ออกจาก set แรกในแถว - ถ้า set แรกในแถวว่างแล้ว ให้เอา set นั้นออกจากแถว - ใส่ v ลงไปแถวผลลัพธ์ - ในทุกๆ จุด w ที่จุดvเชื่อมได้ ซึ่งอยู่ใน set ในแถว : - ถ้า set นั้นๆ ยังไม่ได้ แทน w ด้วย v ให้สร้าง set ใหม่ แล้ว ใส่ set ใหม่ไว้หน้า set นั้นๆ ถ้าไม่ ให้ set ใหม่ไว้ด้านหนัง set นั้นๆ - ย้าย w ไปที่ set ใหม่ แล้วถ้า set ที่ถูกดึง w ออกนั้นว่างก็ให้ดึง set นั้นออกจากแถว
การที่เรียกว่า Lexicographic Breadth-First Search เพราะว่ากระบวนการนี้ได้สร้างการจัดเรียงที่สามารถนำไปใช้ในการเรียกคำศัพท์ทางพจนานุกรมได้
(เพิ่มเติม) Lexicographic breath-first-search ordering(Lex-BFS) เป็นการจัดเรียง จุด ของกราฟ โดยผ่านกระบวนการต่อไปนี้ 1. ทำเครื่องหมาย จุดไหนก็ได้บนกราฟให้เป็น 1 แล้วตั้งว่า ได้ผ่านกราฟไปแล้ว 2. ถ้ายังมีจุดที่ไม่ได้ผ่าน ให้เลือกจุดที่ยังไม่ได้ผ่านนั้นซึ่งต้องเป็นจุดที่ติดกับจุดที่ผ่านไปแล้วที่เล็กที่สุด(สุดแรก)โดยวิธีการ Lexicographic breath-first-search ordering ตั้งให้เป็นจุดที่ผ่านไปแล้ว และใส่ไว้ในลำดับต่อไป
ซึ่งการเปรียบเทียบ 2 ลิส นั้น สามารถเปรียบเทียบได้ดังนี้ จัด list ทั้ง 2 อันแบบลำดับเพิ่ม หาจุดที่เล็กที่สุดที่ทั้ง 2 ลิสต่างกัน ซึ่งจุดที่มีเลข น้อยกว่าจะถือว่าเล็กกว่า( อยู่ก่อน ) ทำให้ลิสนั้นอยุ่ก่อนด้วย
ทฤษฎี 1 กราฟใดๆ เป็น chordal graph ก็ต่อเมื่ออินเวิสของการจัดเรียงแบบ Lex-BFS ของกราฟนั้น เป็นการจัดเรียงแบบ perfect elimination ordering
ถ้าอินเวิส ของ Lex-BFS เป็น perfect elimination ordering แล้วกราฟนั้นเป็น chordal graph ถ้ากราฟ G เป็น chordal graph และ อินเวิสของ Lex-BFS ของ G ไม่เป็น perfect elimination ordering แล้วแสดงว่าจะต้องมี จุด ที่ n0 > n1 > n2 ซึ่ง n0 ติดกับ n1 n2 แต่ n1 ไม่ติดกับ n2 เราสามารถเขียน ลำดับของจุดโดยการเรียงแบบมากไปน้อย ว่า n0 > n1 > n2 > …. > nL-1 ผิดถ้า l >= 3 และกราฟย่อย ( L=3; n3-1 =>n2 => n2>n2 ผิด ) เราใช้ Lex-BFS ในลำดับอื่นๆแบบที่แสดงไปก่อนหน้านี้ แต่ยกเว้นว่าลำดับที่ ได้อยู่ในการจัดเรียงจากน้อยไปมากอยู่แล้ว ถ้าอินเวิสของการจัดเรียงแบบ Lex-BFS ไม่เป็น perfect elimination ordering แล้วแสดงว่าจุดที่มีลำดับไม่ดี จากการจำนวนลำดับนั้นจำกัด จะต้องมีลำดับที่ไม่ดีอยู่ซึ่ง n0 > n1 > n2 … > nL-1 ซึ่งจะถือว่ามาก่อนในการจัดเรียงแบบ Lex-BFS ซึ่งเราจะแสดงว่ามันขัดแย้งกัน พิจารณาในขณะที่ จุดnL-2 ถูกผ่านนไปแล้วใน Lex-BFS แล้วครั้งนี้ จุด nL-3 ยังไม่ได้ถูกผ่าน และมันติดกับจุดnL-1 ซึ่งถูกตั้งให้ผ่านแล้ว และไม่ได้ติดกับจุด nL-2 เพราะว่าจุด nL-2 ถูกเลือกให้เป็นจุดต่อไปในการเข้าถึง มันจะต้องมีจุด nL < nL-1 ที่ติดกับ nL-2 แต่ไม่ติดกับ nL-3 เราอ้างว่า nL ไม่สามารถติดกับ จุด ใดๆ โดยที่จุด nI โดย 0<= I < L-2 ถ้า nL ติดกับ จุด nL-3-2I เมื่อ I >=1 ; ให้ I เป็นตัวเลขที่น้อยที่สุดนั้น แล้วจะได้ nL-3-2I, nL-1-2I จะได้ nL เป็น Lex-BFS ที่มาก่อนซึ่งเป็นลำดับที่ผิด ซึ่งขัดแย้งกัน ถ้า nL ติดกับ nL-1 เราจะได้ กราฟที่ไม่มี chord ที่เป็น cycle ซึ่งยาวอย่างน้อย 4 ซึ่งขัดแย้งกับสมมุติฐานที่เราให้มันเป็น chordal graph แม้ว่า nL จะติดกับ nL-2 เท่านั้น ด้วยเหตุนี้ n0 > n1 > n2 …. > nL-2 > nL-1 > nL เป็นตัวเล็กที่สุด ตามการจัดเรียง Lex-BFS ซึ่งเป็นลำดับที่ผิด ซึ่งขัดแย้งกัน จึงการที่ไม่มีลำดับที่ผิดของ อินเวิสของการจัดเรียงแบบ Lex-BFS เป็น perfect elimination ordering
การค, นหาในแนวกว, างตามการเร, ยงลำด, บแบบพจนาน, กรม, บทความน, ได, บแจ, งให, ปร, บปร, งหลายข, กร, ณาช, วยปร, บปร, งบทความ, หร, ออภ, ปรายป, ญหาท, หน, าอภ, ปราย, บทความน, องการเก, บกวาด, โดยการตรวจสอบหร, อปร, บปร, งความถ, กต, อง, ตลอดจนแก, ไขร, ปแบบหร, อภาษาท, ใช. bthkhwamniidrbaecngihprbprunghlaykhx krunachwyprbprungbthkhwam hruxxphipraypyhathihnaxphipray bthkhwamnitxngkarekbkwad odykartrwcsxbhruxprbprungkhwamthuktxng tlxdcnaekikhrupaebbhruxphasathiich bthkhwamnitxngkarphisucnxksr xacepndankarichphasa karsakd iwyakrn rupaebbkarekhiyn hruxkaraeplcakphasaxun bthkhwamniyngkhadaehlngxangxingephuxphisucnkhwamthuktxngLexicographic Breadth First Search epnwithikarkhnhakhxmulaebbhnungthikhlaykb breadth first search aetepliyncakkarnaesnekhaaethw epliynepnna set khxngcudekhaaethwaethn odythi set inaethwnnkhux set thiekidcakkaraebngklumcud thiyngimidrwmekhadwykn inaetlakhntxn cathakardung cud v cudid in set cak set hnasudkhxngaethw xxkmacakaethwaela thakardungnnthaihthaih set nnwangkcadung set nnxxkcakaethw hlngcaknn thuk set inaethwcathukaethnthidwy 2 subsets khux set thimi v echuxm aela set thiimmi v echuxm ody set thimi v echuxmcathuknamaekhaaethwkxn xikaebbhnung withikarthangandngni erimisthuk set ekhaipin aethw odyaetlaset cami cud 1 cud ihaethwphllphthepnwangepla thayngmiset inaethw hacud v aela exacud v xxkcak set aerkinaethw tha set aerkinaethwwangaelw ihexa set nnxxkcakaethw is v lngipaethwphllphth inthuk cud w thicudvechuxmid sungxyuin set inaethw tha set nn yngimid aethn w dwy v ihsrang set ihm aelw is set ihmiwhna set nn thaim ih set ihmiwdanhnng set nn yay w ipthi set ihm aelwtha set thithukdung w xxknnwangkihdung set nnxxkcakaethw aetlacud cathukthangankhrngediyw aetlaesncathukichnganemux cud 2 cud thuknamakhanwn aela thakaryay set inaethwkhxymikhwamerwaebbkhngthi karwnsaaetlakhrngcamikarwnsaaebbkhngthiechnkn cungehmuxnkbkarich Breadth First Search krabwnkarniichewlaaebbkhngthikarthieriykwa Lexicographic Breadth First Search ephraawakrabwnkarniidsrangkarcderiyngthisamarthnaipichinkareriykkhasphththangphcnanukrmid ephimetim Lexicographic breath first search ordering Lex BFS epnkarcderiyng cud khxngkraf odyphankrabwnkartxipni 1 thaekhruxnghmay cudihnkidbnkrafihepn 1 aelwtngwa idphankrafipaelw 2 thayngmicudthiimidphan iheluxkcudthiyngimidphannnsungtxngepncudthitidkbcudthiphanipaelwthielkthisud sudaerk odywithikar Lexicographic breath first search ordering tngihepncudthiphanipaelw aelaisiwinladbtxipsungkarepriybethiyb 2 lis nn samarthepriybethiybiddngni cd list thng 2 xnaebbladbephim hacudthielkthisudthithng 2 listangkn sungcudthimielkh nxykwacathuxwaelkkwa xyukxn thaihlisnnxyukxndwythvsdi 1 krafid epn chordal graph ktxemuxxinewiskhxngkarcderiyngaebb Lex BFS khxngkrafnn epnkarcderiyngaebb perfect elimination orderingthaxinewis khxng Lex BFS epn perfect elimination ordering aelwkrafnnepn chordal graph thakraf G epn chordal graph aela xinewiskhxng Lex BFS khxng G imepn perfect elimination ordering aelwaesdngwacatxngmi cud thi n0 gt n1 gt n2 sung n0 tidkb n1 n2 aet n1 imtidkb n2 erasamarthekhiyn ladbkhxngcudodykareriyngaebbmakipnxy wa n0 gt n1 gt n2 gt gt nL 1 phidtha l gt 3 aelakrafyxy L 3 n3 1 gt n2 gt n2 gt n2 phid eraich Lex BFS inladbxunaebbthiaesdngipkxnhnani aetykewnwaladbthi idxyuinkarcderiyngcaknxyipmakxyuaelw thaxinewiskhxngkarcderiyngaebb Lex BFS imepn perfect elimination ordering aelwaesdngwacudthimiladbimdi cakkarcanwnladbnncakd catxngmiladbthiimdixyusung n0 gt n1 gt n2 gt nL 1 sungcathuxwamakxninkarcderiyngaebb Lex BFS sungeracaaesdngwamnkhdaeyngkn phicarnainkhnathi cudnL 2 thukphannipaelwin Lex BFS aelwkhrngni cud nL 3 yngimidthukphan aelamntidkbcudnL 1 sungthuktngihphanaelw aelaimidtidkbcud nL 2 ephraawacud nL 2 thukeluxkihepncudtxipinkarekhathung mncatxngmicud nL lt nL 1 thitidkb nL 2 aetimtidkb nL 3 eraxangwa nL imsamarthtidkb cud id odythicud nI ody 0 lt I lt L 2 tha nL tidkb cud nL 3 2I emux I gt 1 ih I epntwelkhthinxythisudnn aelwcaid nL 3 2I nL 1 2I caid nL epn Lex BFS thimakxnsungepnladbthiphid sungkhdaeyngkn tha nL tidkb nL 1 eracaid krafthiimmi chord thiepn cycle sungyawxyangnxy 4 sungkhdaeyngkbsmmutithanthieraihmnepn chordal graph aemwa nL catidkb nL 2 ethann dwyehtuni n0 gt n1 gt n2 gt nL 2 gt nL 1 gt nL epntwelkthisud tamkarcderiyng Lex BFS sungepnladbthiphid sungkhdaeyngkn cungkarthiimmiladbthiphidkhxng xinewiskhxngkarcderiyngaebb Lex BFS epn perfect elimination ordering ekhathungcak https th wikipedia org w index php title karkhnhainaenwkwangtamkareriyngladbaebbphcnanukrm amp oldid 4700735, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
บทความ , อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม