hhhhhhhhhhhhhhhh

SEARC การค้นหาข้อมูลHING



ก า ร ค้ น ห า ข้ อ มูล(SEARCHING)การค้ นหาข้ อมูลในทางคอมพิวเตอร์มักจะกระทาบนโครงสร้ างข้ อมูล แบบต้ นไม้ และกราฟ เพราะโครงสร้ างข้ อมูลในลักษณะนีส้ ามารถทาให้ การค้ นหาทาได้ สะดวกและสามารถพลิกแพลง การค้ นหาได้ ง่าย ในความเป็ นจริ งแล้ วการค้ นหาข้ อมูลบางครัง้สามารถกทาาบน โครงสร้ างข้ อมูลชนิดอ่ืนก็ได้ เช่น อาเรย์ แสตก และคิว แต่การจัด ข้ อมูลในโครงสร้ างเช่นนี ้ มีข้ อจากัดในการค้ นหาข้ อมูลมาก การค้ นหาทาได้ แบบเรี ยงลาดับ( S E Q U E NT I A L S E A R C H) เ ท่า นัน้

ก า ร ค้ น ห า แ บ บ ไ บ ล์ ด(BLIND SEARCH)กา รค้ นหา แบบไ บ ล์ ด (B LI N D S E A R C H ) เป็ นการค้ นหาแบบที่เดินทางจากโหนด หนึ่งไปยังอีกโหนดหน่ึง โดยอาศัยทิศทางเป็ นตัวกาหนดการค้ นหา ไม่ต้ องมีข้ อมูลอะไรมาช่วยเสริ มการตัดสินใจว่าจะเดินทางต่อไปอย่างไร หรื อกล่าวอย่างง่าย ๆ คือการจะหยิบข้ อมูลใดมาช่วยในการค้ นหาต่อไปไม่ต้ องอาศัยข้ อมูลใด ๆ ทัง้ สิน้นอกจากทิศทางซึ่งเป็ นรู ปแบบตายตัว การค้ นหาแบบไบล์ดสามารถ แบ่งย่อยได้ ดังนี ้ คือการค้ นหา ทัง้ หมด และการค้ นหาบางส่วน-ก า รค้ น ห า ทัง้ ห ม ด (E X H A U S T IV ESEARCH) คือ การค้ นหาทัง้ หมดของปริ ภูมิสถานะ-ก า ร ค้ น ห า บ า งส่ว น ( PA RT I A L S E A R C H)คือ การค้ นหาเพียงบางส่วนของปริ ภูมิสถานะการค้ นหาแบบนีส้ ามารถแบ่งได้ เป็ น 2 ประเภท

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

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

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

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



ก า ร ค้ น ห า ดี สุ ด ก่ อ น (BEST-FIRST SEARCH) • ขั้น ต อ น วิ ธี ใ น ก า ร ค้ น ห า ใ น ก ร า ฟ เ ป็ น ก า ร น า ข้ อ ดี ข อ ง ก า ร ค้ น ห า ต า ม แ น ว ก ว้ า ง แ ล ะ ก า ร ค้ น ห า ต า ม แ น ว ลึ ก ม า ร ว ม กั น โ ด ย ก า ร ค้ น ห า แ บ บ ดี ท่ี สุ ด จ ะ เ ลื อ ก จุ ด ย อ ด ท่ี มี ค่ า ดี สุ ด ซ่ึ ง อ า ศั ย ฮิ ว ริ ส ติ ก ฟั ง ก์ ชั น ใ น ก า ร ค้ น ห า • เ ป็ น ก ร ะ บ ว น ก า ร ค้ น ห า ข้ อ มู ล ท่ี ไ ด้ น า เ อ า ข้ อ ดี ข อ ง ทั้ง ก า ร ค้ น ห า แ บ บ ลึ ก ก่ อ น (DEPTH FIRST SEARCH) แ ล ะ ก า ร ค้ น ห า แ บ บ ก ว้ า ง ก่ อ น (BREADTH FIRST SEARCH) ม า ร ว ม กั น เ ป็ น วิ ธี ก า ร เ ดี ย ว โ ด ย ท่ี แ ต่ ล ะ ขั้น ข อ ง ก า ร ค้ น ห า ใ น โ ห น ด ลู ก นั้น • ก า ร ค้ น ห า แ บ บ ดี ท่ี ดี ก่ อ น จ ะ เ ลื อ ก เ อ า โ ห น ด ท่ี ดี ท่ี สุ ด ( M O S T P R O M I S I N G ) แ ล ะ ก า ร ท่ี จ ะ ท ร า บ ว่ า โ ห น ด ใ ด ดี ท่ี สุ ด นี้ส า ม า ร ถ ท า ไ ด้ โ ด ย อ า ศั ย ฮิ ว ริ ส ติ ก ฟั ง ก์ ชั น ซ่ึ ง ฮิ ว ริ ส ติ ก ฟั ง ก์ ชั น นี้จ ะ ท า ห น้ า ท่ี เ ห มื อ น ตั ว วั ด ผ ล แ ล ะ ใ ห้ ผ ล ข อ ง ก า ร วั ด นี้อ อ ก ม า เ ป็ น คะแนน