jv 17 (056)

SEAR โครงสร้ างข้ อมูลC ( JV 17)H การค้นหาข้อมูลING นชุ นาฏ ธรรมวงศ์ 60123468056

วัตถุประสงค์• หนงั สือเลม่ นี ้จดั ทาขนึ ้ เพ่ือให้ผ้ศู กึ ษาเร่ืองนีม้ ี ความเข้าใจในความหมาย การใช้งาน เพื่อให้ ผ้อู า่ นได้ความรู้ ความเข้าใจในเรื่องนีม้ ากย่ิงขนึ ้

สารบัญ

การค้ นหาข้ อมูล ( SEARCHING )การค้นหาข้อมลู ในทางคอมพวิ เตอร์มกั จะกระทาบนโครงสร้างข้อมลู แบบต้นไม้และกราฟ เพราะโครงสร้างข้อมลู ในลกั ษณะนีส้ ามารถทาให้การค้นหาทาได้สะดวกและสามารถพลกิ แพลงการค้นหาได้งา่ ยในความเป็ นจริงแล้วการค้นหาข้อมลู บางครัง้ สามารถทาบนโครงสร้างข้อมลู ชนิดอื่นก็ได้ เช่น อาเรย์ แสตก และควิ แตก่ ารจดั ข้อมลู ในโครงสร้างเชน่ นี ้มีข้อจากดั ในการค้นหาข้อมลู มาก การค้นหาทาได้แบบเรียงลาดบั(Sequential Search) เทา่ นนั้

การค้ นหาแบบไบล์ ด( BLIND SEARCH )การค้นหาแบบไบล์ด(Blind search) เป็ นการค้นหาแบบที่เดนิ ทางจากโหนด หนงึ่ ไปยงั อีกโหนดหนงึ่กลา่ วอยา่ งง่าย ๆ คือการจะหยิบข้อมลู ใดมาช่วยในการค้นหาตอ่ ไปไมต่ ้องอาศยั ข้อมลู ใด ๆ ทงั้ สนิ ้นอกจากทศิ ทางซงึ่ เป็ นรูปแบบตายตวั การค้นหาแบบไบล์ดสามารถ แบง่ ยอ่ ยได้ดงั นี ้คอื การค้นหาทงั้ หมด และการค้นหาบางสว่ น-การค้นหาทงั ้ หมด (exhaustive search) คือ การ ค้นหาทงั้ หมดของปริภมู สิ ถานะ- การค้นหาบางสว่ น (partial search) คือ การค้นหา เพยี งบางสว่ นของปริภมู สิ ถานะ การค้นหาแบบนีส้ ามารถแบง่ ได้เป็ น 2 ประเภท

การค้ นหาแบบลึกก่ อน( DEPTH FIRST SEARCH ) • การค้นหาแบบลกึ ก่อนเป็ นการค้นหาท่ี กาหนดทศิ ทางจากรูปของ โครงสร้าง ต้นไม้ ที่เริ่มต้นจากโหนด ราก (Root node) ท่ีอยบู่ นสดุ แล้วเดินลงมาให้ลกึ ที่สดุ เมื่อถงึ โหนดลา่ งสดุ (Terminal node) ให้ย้อนขนึ ้ มา ท่ีจดุ สงู สดุ ของก่ิงเดย่ี วกนั ท่ีมีก่ิงแยกและ ยงั ไมไ่ ด้เดนิ ผ่าน แล้วเร่ิม เดนิ ลงจนถงึ โหนดลกึ สดุ อีก ทาเช่นนี ้ สลบั ไปเรื่อย จนพบโหนดท่ีต้องการหา หรือสารวจครบทกุ โหนดแล้ว

การค้ นหาแบบกว้ างก่ อน(BREADTH FIRST SEARCH) • การค้นหาแบบกว้างก่อนเป็ นการ กาหนดทศิ ทางการค้นหาแบบที่ละ ระดบั ของโครงสร้างต้นไม้โดยเริ่ม จากโหนดราก(ระดบั ท่ี 0) แล้วลงมา ระดบั ท่ี 1 จากซ้ายไปขวา เม่ือเสร็จ ระดบั ที่ 1 ไประดบั ท่ี 2 จากซ้ายไป ขวา เชน่ กนั ทาเชน่ นีเ้ร่ือยๆ จนพบ โหนดที่ต้องการตามรูปท่ี 3 ลาดบั การเดนิ ทางของโหนด เป็ นไปตาม หมายเลข ที่กากบั ไว้บนโหนด

การค้ นหาแบบฮิวริ สติก(HEURISTIC SEARCH)• การค้นหาข้อมลู ธรรมดาผ้ทู ี่ทาการค้นข้อมลู จะต้องตรวจสอบข้อมลู ทีละตวั ทกุ ตวั จนครบ• แตฮ่ ิวริสติกจะไมล่ งไปดขู ้อมลู ทกุ ตวั วิธีการนีจ้ ะเลือกได้คาตอบทีเ่ หมาะสมให้กบั การค้นหา• ข้อดีคอื สามารถทาการค้นหาคาตอบจากข้อมลู ท่ีมีขนาดใหญ่มากๆ ได้• ข้อเสียคือ คาตอบท่ีได้เป็นเพียงคาตอบทีด่ ี เทา่ นนั้ ไมแ่ น่วา่ จะดที ่ีสดุ• ปัญหาในบางลกั ษณะนนั้ ใหญ่มาก และเป็นไปไมไ่ ด้ท่ีจะ ทาการค้นหาด้วยวธิ ีธรรมดากระบวนการของฮิวริสติกจงึ เป็นส่งิ ท่ีจาเป็นในเร่ืองของฮิวริสติกนนั้• สง่ิ หนงึ่ ที่สาคญั คือ ฮิวริสติกฟังก์ชนั (heuristicfunction) ซึ่งหมายถงึ ฟังก์ชนั ที่ทาหน้าที่ในการวดั ขนาดของความเป็นไปได้ในการแก้ปัญหาซงึ่ จะแสดงด้วยตวั เลข

รูปภาพแสดง การค้นหาแบบฮิวริสติก(HEURISTIC SEARCH)

การค้นหาแบบปี นเขา(HILL CLIMBING)• การแก้ไขปัญหาทต่ี ้องการผลเฉลยท่ีเป็นที่สดุ คือ ดีท่ีสดุ หรือน้อยที่สดุ โดยมี หลกั การในการแก้ไขปัญหาคือการ เลือกแนวทางในการไปสคู่ าตอบของปัญหานบั จาก ตาแหน่งปัจจบุ นั ที่ดีท่ีสดุ อยา่ งสมุ่• แล้วจงึ ย้ายการหาแนวทางการไปสผู่ ลเฉลยที่เป็ นที่สดุ ไป ที่จดุ ลา่ สดุ ท่ีเลอื กไว้• แนวความคดิ ของสโตคาสติกเก่ียวกบั ขนั้ ตอนในการแก้ไข ปัญหาการปี นเขานีม้ ี ลกั ษณะคล้ายกนั กบั การแก้ไข ปัญหาการปี นเขาโดยทว่ั ๆ ไป• แตต่ า่ งกนั ตรงที่วิธีการของสโตคาสตกิ นนั้ อาศยั หลกั ใน การเลือกเส้นทางในการ ปี นเขาอยา่ งสมุ่• ขณะที่แบบทว่ั ๆ ไปนนั้ อาศยั หลกั ในการเลือกเส้นทางท่ีมี ความชนั มากที่สดุ เพื่อ มาประกอบกนั เป็นสว่ นหนง่ึ ของ คาตอบในการแก้ไขปัญหา

รูปภาพแสดงการค้นหาแบบปี นเขา(HILL CLIMBING)

การค้ นหาดีสุด ก่ อน(BEST-FIRST SEARCH)• ขนั้ ตอนวิธีในการค้นหาในกราฟ เป็นการนาข้อดีของการ ค้นหาตามแนว กว้าง และการค้นหาตามแนวลกึ มา รวมกนั โดยการค้นหาแบบดีท่ีสดุ จะเลือกจดุ ยอดท่ีมีคา่ ดี สดุ ซง่ึ อาศยั ฮิวริสติกฟังก์ชนั ในการค้นหา• เป็นกระบวนการค้นหาข้อมลู ท่ีได้นาเอาข้อดขี องทงั้ การ ค้นหาแบบลกึ ก่อน (Depth first search) และ การค้นหา แบบกว้างกอ่ น (Breadth first search) มารวมกนั เป็ น วธิ ีการเดียว โดยที่แตล่ ะขนั้ ของการค้นหาในโหนดลกู นนั้• การค้นหาแบบดีท่ีดีก่อนจะเลอื กเอาโหนดท่ีดีท่ีสดุ (most promising) และการที่จะทราบวา่ โหนดใดดีที่สดุ นี ้ สามารถทาได้โดยอาศยั ฮิวริสติกฟังก์ชนั ซงึ่ ฮิวริ สติก ฟังก์ชนั นีจ้ ะทาหน้าท่ีเหมือนตวั วดั ผล และให้ผลของการ วดั นีอ้ อกมาเป็นคะแนน

แบบทดสอบ• https://docs.google.com/form s/d/e/1FAIpQLSdeoD2MCuk SbtmlhzFNnECBXLvywpLCh 6V5jdWJhMizfYCSxQ/viewfor m

อ้ างอิง• http://www.teacher.ssru.ac.th/wi pada_ch/• http://lookgoodgood.blogspot.c om/2015/08/heuristic- search.html