111111111111

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



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

ก า ร ค้ น ห า แ บ บ ไ บ ล์ ด(BLIND SEARCH)กา ร ค้ นหา แบ บ ไ บ ล์ ด (BL IN D S E A R C H) เ ป็ นการค้ นหาแบบที่เดินทางจากโหนด หน่ึงไปยั งอีกโหนดหน่ึง โดยอาศัยทิศทางเป็ นตัวกาหนด การค้ นหา ไม่ต้ องมีข้ อมูลอะไรมาช่วยเสริ มก ารตัดสินใจว่าจะเดินทางต่อไปอย่างไร หรื อก ล่าวอย่างง่าย ๆ คือการจะหยิบข้ อมูลใดมาช่วย ในการค้ นหาต่อไปไม่ต้ องอาศัยข้ อมูลใด ๆ ทั้งสิน้นอกจากทิศทางซ่ึงเป็ นรู ปแบบตายตัว การค้ นหาแบบไบล์ดสามารถ แบ่งย่อยได้ ดังนี ้ คือการค้ นหา ทัง้ หมด และการค้ นหาบางส่วน-ก า ร ค้ น ห า ทัง้ ห ม ด ( E X H AU S T I V E S E A R C H )คือ การค้ นหาทัง้ หมดของปริ ภูมิสถานะ-ก า ร ค้ น ห า บ า ง ส่ว น ( 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 S E A R C H ) ม า ร ว ม กั น เ ป็ น วิ ธี ก า ร เ ดี ย ว โ ด ย ท่ี แ ต่ ล ะ ขั้น ข อ ง ก า ร ค้ น ห า ใ น โ ห น ด ลู ก นั้น • ก า ร ค้ น ห า แ บ บ ดี ท่ี ดี ก่ อ น จ ะ เ ลื อ ก เ อ า โ ห น ด ท่ี ดี ท่ี สุ ด ( M O S T P R O M I S I N G ) แ ล ะ ก า ร ท่ี จ ะ ท ร า บ ว่ า โ ห น ด ใ ด ดี ท่ี สุ ด นี้ส า ม า ร ถ ท า ไ ด้ โ ด ย อ า ศั ย ฮิ ว ริ ส ติ ก ฟั ง ก์ ชั น ซ่ึ ง ฮิ ว ริ ส ติ ก ฟั ง ก์ ชั น นี้จ ะ ท า ห น้ า ท่ี เ ห มื อ น ตั ว วั ด ผ ล แ ล ะ ใ ห้ ผ ล ข อ ง ก า ร วั ด นี้อ อ ก ม า เ ป็ น คะแนน

1 ) ก า ร ค้ น ห า แ บ บ G R E E DY ( G R E E DYA L G O R I T H M ) ก รี ดี อั ล ก อ ริ ธึ ม เ ป็ น ก า รค้ น ห า แ บ บ ดี ท่ี สุ ด ก่ อ น ( B E S T F I R S TS E A R C H ) ท่ี ง่ า ย ท่ี สุ ด ห ลั ก ก า ร ข อ ง ก า รค้ น ห า แ บ บ นี้คื อ ก า ร เ ลื อ ก โ ห น ด ท่ี ดี ท่ี สุ ดต ล อ ด เ ว ล า อั ล ก อ ริ ธึ ม ก รี ดี 1 . เ ลื อ ก โ ห น ด เ ร่ิ ม ต้ นม า ห น่ึ ง โ ห น ด 2 . ใ ห้ โ ห น ด ท่ี เ ลื อ ก ม า นี้เ ป็ นส ถ า น ะ ปั จ จุ บั น 3 . ใ ห้ ทํ า ต า ม ข บ ว น ก า ร ข้ า ง ล่ า ง นี้จ น ก ว่ า จ ะ ไ ม่ ส า ม า ร ถ ส ร้ า ง โ ห น ด ลู ก ไ ด้ อี ก 3 . 1ส ร้ า ง ส ถ า น ะ ใ ห ม่ ท่ี เ ป็ น โ ห น ด ลู ก ท่ี เ ป็ น ไ ป ไ ด้ทั้ง ห ม ด จ า ก ส ถ า น ะ ปั จ จุ บั น 3 . 2 จ า ก ส ถ า น ะ ใ ห ม่ท่ี ส ร้ า ง ขึ้น ม า ทั้ง ห ม ด ใ ห้ เ ลื อ ก ส ถ า น ะ ห รื อโ ห น ด ลู ก ท่ี ดี ท่ี สุ ด อ อ ก ม า เ พี ย ง โ ห น ด เ ดี ย วตั ว อ ย่ า ง จ า ก เ ร่ื อ ง ก า ร เ ดิ น ท า ง ข อ ง เ ซ ล แ ม น ท่ีจ ะ ต้ อ ง เ ดิ น ท า ง ไ ป ยั ง เ มื อ ง A B C D ซ่ึ ง มีร ะ ย ะ ท า ง ต า ม ต า ร า ง ท่ี 3 เ ร า จ ะ แ ก้ ปั ญ ห า นี้ด้ ว ยวิ ธี ก า ร ข อ ง ก รี ดี บ้ า ง ก า ร แ ก้ ปั ญ ห า ก า ร เ ดิ น ท า งข อ ง เ ซ ล แ ม น ด้ ว ย ก รี ดี อั ล ก อ ริ ธึ ม ก า ร แ ก้ ปั ญ ห าเ ร่ิ ม จ า ก ก า ร เ ลื อ ก A เ ป็ น เ มื อ ง เ ร่ิ ม แ ร กจ า ก นั้น ทํ า ก า ร ส ร้ า ง โ ห น ด ลู ก B C แ ล ะ D ห า รร ะ ย ะ ท า ง ร ะ ห ว่ า ง A ถึ ง เ มื อ ง เ ห ล่ า นี้ไ ด้ 2 0 3 0แ ล ะ 5 0 ต า ม ลํ า ดั บ เ ลื อ ก B เ ป็ น เ มื อ ง ท่ี จ ะเ ดิ น ท า ง ต่ อ ม า จ า ก นั้น ส ร้ า ง โ ห น ด ลู ก ข อ ง B ไ ด้C แ ล ะ D แ ล ะ ไ ด้ ร ะ ย ะ ท า ง เ ท่ า กั บ 1 5 แ ล ะ2 0 ต า ม ลํ า ดั บ เ ลื อ ก C เ ป็ น เ มื อ ง ท่ี จ ะ เ ดิ น ท า งต่ อ ไ ป จ า ก นั้น ส ร้ า ง โ ห น ด ลู ก ใ ห้ C ไ ด้ D มี ค่ าเ ท่ า กั บ 1 0 เ ลื อ ก เ ดิ น ม า ท่ี D เ ป็ น เ มื อ ง สุ ด ท้ า ยก่ อ น ก ลั บ ไ ป A ร ว ม ร ะ ย ะ ท า ง เ ท่ า กั บ 2 0 + 1 5+ 10 + 50 = 95

2 ) ก า ร ค้ น ห า แ บ บ A * ก า ร ค้ น ห า แ บ บ A * เ ป็ น อี ก แ บ บ ข อ งก า ร ค้ น ห า แ บ บ ดี ท่ี สุ ด ก่ อ น วิ ธี ก า ร เ ลื อ ก โ ห น ด ท่ี จ ะ ใ ช้ ใ น ก า รดํ า เ นิ น ก า ร ต่ อ จ ะ พิ จ า ร ณ า จ า ก โ ห น ด ท่ี ดี ท่ี สุ ด แ ต่ ใ น ก ร ณี ข อ งA * นี้ จ ะ มี ลั ก ษ ณ ะ พิ เ ศ ษ ก ว่ า คื อ ใ น ส่ ว น ข อ ง ฮิ ว ริ ส ติ ก ฟั ง ก์ ชั นใ น ก ร ณี ข อ ง ก า ร ค้ น ห า แ บ บ ดี ท่ี สุ ด ก่ อ น นั้ น ค่ า ท่ี ไ ด้ จ า ก ฮิ ว ริส ติ ก ฟั ง ก์ ชั น จ ะ เ ป็ น ค่ า ท่ี วั ด จ า ก โ ห น ด ปั จ จุ บั น แ ต่ ใ น ก ร ณีข อ ง A * ค่ า ข อ ง ฮิ ว ริ ส ติ ก ฟั ง ก์ ชั น จ ะ วั ด จ า ก ค่ า 2 ค่ า คื อค่ า ท่ี วั ด จ า ก โ ห น ด ปั จ จุ บั น ไ ป ยั ง โ ห น ด ร า ก แ ล ะ จ า ก โ ห น ดปั จ จุ บั น ไ ป ยั ง โ ห น ด เ ป้ า ห ม า ย ถ้ า เ ร า ใ ห้ ตั ว แ ป ร F แ ท น ค่ าข อ ง ฮิ ว ริ ส ติ ก ฟั ง ก์ ชั น G เ ป็ น ฟั ง ก์ ชั น ท่ี ใ ช้ วั ด ค่ า C O S Tจ า ก ส ถ า น ะ เ ร่ิ ม ต้ น จ น ถึ ง ส ถ า น ะ ปั จ จุ บั น H ' เ ป็ น ฟั ง ก์ ชั น ท่ี ใ ช้วั ด ค่ า C O S T จ า ก ส ถ า น ะ ปั จ จุ บั น ถึ ง ส ถ า น ะ เ ป้ า ห ม า ยดั ง นั้ น F = G + H ’ อั ล ก อ ริ ทึ ม A * ( A * S E A R C H )เ ป็ น ก า ร ข ย า ย อั ล ก อ ริ ทึ ม ดี สุ ด ก่ อ น โ ด ย พิ จ า ร ณ า เ พ่ิ ม เ ติ ม ถึ งต้ น ทุ น จ า ก ส ถ า น ะ เ ร่ิ ม ต้ น ม า ยั ง ส ถ า น ะ ปั จ จุ บั น เ พ่ื อ ใ ช้ คํ า น ว ณค่ า ฮิ ว ริ ส ติ ก ด้ ว ย ใ น ก ร ณี ข อ ง อั ล ก อ ริ ทึ ม A * เ ร า ต้ อ ง ก า ร ห าค่ า ตํ่ า สุ ด ข อ ง ฟั ง ก์ ชั น F ' ข อ ง ส ถ า น ะ S นิ ย า ม ดั ง นี้F ' ( S ) = G ( S ) + H ' ( S ) โ ด ย ท่ี G คื อ ฟั ง ก์ ชั น ท่ี คํ า น ว ณต้ น ทุ น จ า ก ส ถ า น ะ เ ร่ิ ม ต้ น ม า ยั ง ส ถ า น ะ ปั จ จุ บั น H ' คื อ ฟั ง ก์ ชั นท่ี ป ร ะ ม า ณ ต้ น ทุ น จ า ก ส ถ า น ะ ปั จ จุ บั น ไ ป ยั ง คํ า ต อ บ ดั ง นั้ นF ' จึ ง เ ป็ น ฟั ง ก์ ชั น ท่ี ป ร ะ ม า ณ ต้ น ทุ น จ า ก ส ถ า น ะ เ ร่ิ ม ต้ น ไ ป ยั งคํ า ต อ บ ( ย่ิ ง น้ อ ย ย่ิ ง ดี ) เ ร า ม อ ง ไ ด้ ว่ า ฟั ง ก์ ชั น H ' คื อฟั ง ก์ ชั น ฮิ ว ริ ส ติ ก ท่ี เ ร า เ ค ย ใ ช้ ใ น ก า ร ค้ น ห า อ่ื น ๆ ก่ อ น ห น้ า นี้เ ช่ น อั ล ก อ ริ ทึ ม ปี น เ ข า อั ล ก อ ริ ทึ ม ดี สุ ด ก่ อ น เ ป็ น ต้ น ใ น ท่ี นี้เ ร า ใ ส่ เ ค ร่ื อ ง ห ม า ย ' เ พ่ื อ แ ส ด ง ว่ า ฟั ง ก์ ชั น นี้ เ ป็ น ฟั ง ก์ ชั น 9ป ร ะ ม า ณ ข อ ง ฟั ง ก์ ชั น จ ริ ง ท่ี ไ ม่ รู้ ( เ ร า ทํ า ไ ด้ แ ค่ ป ร ะ ม า ณ ว่ า H 'คื อ ต้ น ทุ น จ า ก ส ถ า น ะ ปั จ จุ บั น ไ ป ยั ง คํ า ต อ บ เ ร า จ ะ รู้ ต้ น ทุ นจ ริ ง ก็ ต่ อ เ ม่ื อ เ ร า ไ ด้ ทํ า ก า ร ค้ น ห า จ ริ ง จ น ไ ป ถึ ง คํ า ต อ บ แ ล้ ว )ส่ ว น G เ ป็ น ฟั ง ก์ ชั น ท่ี คํ า น ว ณ ต้ น ทุ น จ ริ ง จ า ก ส ถ า น ะ เ ร่ิ ม ต้ นม า ยั ง ส ถ า น ะ ปั จ จุ บั น ( จึ ง ไ ม่ ไ ด้ ใ ส่ เ ค ร่ื อ ง ห ม า ย ' ) เ พ ร า ะ เ ร าส า ม า ร ถ ห า ต้ น ทุ น จ ริ ง ไ ด้ เ น่ื อ ง จ า ก ไ ด้ ค้ น ห า จ า ก ส ถ า น ะเ ร่ิ ม ต้ น จ น ม า ถึ ง ส ถ า น ะ ปั จ จุ บั น แ ล้ ว ส่ ว น F ' ก็ เ ป็ น เ พี ย ง แ ค่ฟั ง ก์ ชั น ป ร ะ ม า ณ โ ด ย ก า ร ร ว ม ต้ น ทุ น ทั้ ง ส อ ง คื อ H ' กั บ Gอั ล ก อ ริ ทึ ม A * จ ะ ทํ า ก า ร ค้ น ห า โ ด ย วิ ธี เ ดี ย ว กั น กั บ อั ล ก อ ริ ทึ มดี สุ ด ก่ อ น ทุ ก ป ร ะ ก า ร ย ก เ ว้ น ฟั ง ก์ ชั น ฮิ ว ริ ส ติ ก ท่ี ใ ช้ เ ป ล่ี ย น ม าเ ป็ น F ' ( ต่ า ง จ า ก อั ล ก อ ริ ทึ ม ดี สุ ด ก่ อ น ท่ี ใ ช้ H ' ) โ ด ย ก า ร ใ ช้F ' อั ล ก อ ริ ทึ ม A * จึ ง ใ ห้ ค ว า ม สํ า คั ญ กั บ ส ถ า น ะ ห น่ึ ง ๆ 2ป ร ะ ก า ร คื อ ( 1 ) ส ถ า น ะ ท่ี ดี ต้ อ ง มี H ' ดี คื อ ต้ น ทุ น เ พ่ื อ จ ะนํ า ไ ป สู่ คํ า ต อ บ ห ลั ง จ า ก นี้ ต้ อ ง น้ อ ย แ ล ะ ( 2 ) ต้ น ทุ น ท่ี จ่ า ย ไ ปแ ล้ ว ก ว่ า จ ะ ถึ ง ส ถ า น ะ นี้ ( G ) ต้ อ ง น้ อ ย ด้ ว ย เ ร า จึ ง ไ ด้ ว่ า A *จ ะ ค้ น ห า เ ส้ น ท า ง ท่ี ใ ห้ ต้ น ทุ น โ ด ย ร ว ม น้ อ ย ท่ี สุ ด ต า ม ค่ า F ' ซ่ึ งต่ า ง จ า ก อั ล ก อ ริ ทึ ม ดี สุ ด ก่ อ น ท่ี เ น้ น ค ว า ม สํ า คั ญ ข อ ง ส ถ า น ะ ท่ีต้ น ทุ น ห ลั ง จ า ก นี้ ท่ี จ ะ นํ า ไ ป สู่ คํ า ต อ บ ต้ อ ง น้ อ ย โ ด ย ไ ม่ ส น ใ จว่ า ต้ น ทุ น ท่ี จ่ า ย ไ ป แ ล้ ว ก ว่ า จ ะ นํ า ม า ถึ ง ส ถ า น ะ นี้ ต้ อ ง เ สี ย ไ ปเ ท่ า ไ ห ร่