ศึกษาสำนึก
จากวิกิพีเดีย สารานุกรมเสรี
- สำหรับความหมายอื่น ที่เป็นทฤษฎีทางคณิตศาสตร์ ดูที่ ฮิวริสติก
โดยปกติการออกแบบหรือค้นหาขั้นตอนวิธี หรืออัลกอริทึม ที่ดีเพื่อการหาผลลัพธ์หรือแก้ปัญหาด้วยคอมพิวเตอร์นั้นมีเป้าหมายพื้นฐานอยู่ 2 ประการ คือ
- สามารถรับประกันคุณภาพของคำตอบได้ คือ สามารถพิสูจน์ถึงความเหมาะที่สุด (optimality) หรือ ระบุขอบข่ายคุณภาพ ของคำตอบได้
- สามารถรับประกันช่วงเวลา หรือ ความเร็ว ที่ใช้ในการคำนวณ เพื่อหาคำตอบนั้นได้
การแก้ปัญหาแบบศึกษาสำนึก (heuristic approach) เปรียบเทียบได้กับ อัลกอริทึมหรือขั้นตอนวิธีแก้ปัญหาที่ไม่สามารถรับประกันถึงคุณสมบัติทั้งสองประการข้างต้นได้ อาจจะมีเพียงประการใดประการหนึ่ง หรือ อาจจะไม่มีเลยก็ได้ ตัวอย่างความหมายของความไม่สามารถรับประกันได้ เช่น ถ้าเรามีวิธีในการหาคำตอบของปัญหาประเภทหนึ่ง ซึ่งโดยปกติวิธีนี้จะให้คำตอบที่มีคุณภาพดี แต่ในบางครั้งคำตอบที่ได้อาจจะไม่ดี, หรือ เราไม่สามารถจะพิสูจน์ได้ว่า วิธีการหาคำตอบหนึ่งจะสามารถหาคำตอบได้เร็วตลอดเวลา ถึงแม้ว่าโดยทั่วไปแล้วจะเร็วก็ตาม
โดยส่วนใหญ่ เราสามารถสร้างและยกตัวอย่างปัญหาเป็นพิเศษให้กับวิธีแบบศึกษาสำนึก และเป็นกรณีที่ทำให้วิธีแบบศึกษาสำนึกให้คำตอบที่ผิด หรือทำงานอย่างเชื่องช้าได้ แต่อย่างไรก็ตาม เนื่องจากโครงสร้างของปัญหาตัวอย่างนั้นเป็นกรณีที่พิเศษมากๆ ซึ่งโดยทั่วไปแล้วมีโอกาสเกิดขึ้นได้น้อย หรือ อาจไม่เกิดขึ้นเลย ดังนั้นเราจึงพบเห็นการนำวิธีแบบศึกษาสำนึกไปใช้แก้ปัญหาในโลกจริงอยู่ทั่วไป
[แก้] วิธีแบบศึกษาสำนึกในปัญหาการหาเส้นทางสั้นที่สุด
สำหรับปัญหาเส้นทางสั้นที่สุด (shortest path problems) นั้น วิธีแบบศึกษาสำนึกจะกำหนดให้ การศึกษาสำนึก เป็น ฟังก์ชันศึกษาสำนึก , h(n) อยู่บนปม (nodes) ของต้นไม้สำหรับค้น (search tree), ซึ่งทำงานโดยการประมาณค่าของวิถี(path) สั้นที่สุดหรือมีค่าน้อยสุด จากปมปัจจุบันไปยังปมเป้าหมาย (goal) วิธีการศึกษาสำนึกใช้ใน informed search algorithm เช่น การค้นหาของที่ดีที่สุดเชิงละโมบ หรือGreedy best-first search และ การค้นหาเอสตาร์A* สำหรับเป็นผู้เลือกหรือตัวตัดสินใจเลือกปมที่ดีที่สุดก่อนการค้นหาปมต่อไป. การค้นหาของที่ดีที่สุดเชิงละโมบ (Greedy best-first search) จะเลือกปมที่มีค่าน้อยที่สุดสำหรับฟังก์ชันศึกษาสำนึก ส่วน เอสตาร์ (A*) จะค้นหาปมที่มีค่าน้อยที่สุดจากสมการ g(n) + h(n), โดยที่ฟังก์ชัน g(n) คือ ค่าที่แท้จริง (exact cost) สำหรับเส้นทางจาก สถานะกำหนดเริ่มต้น (initial state) มายังสถานะปัจจุบัน. และโดยที่ฟังก์ชัน h(n) จะส่งค่าประมาณการศึกษาสำนึกที่ยอมรับได้ นั่นคือ ถ้าฟังก์ชัน h(n) เป็นค่าประมาณที่ไม่เคยประมาณมากกว่าค่าจริงจนถึงเป้าหมาย (goal) — สำหรับกรณีนี้เอสตาร์ (A*) ได้มีการพิสูจน์แล้วว่าได้ผลเฉลยที่เหมาะที่สุดเสมอ (optimal)
ปัญหาเก่าแก่ที่เกี่ยวข้องกับวิธีศึกษาสำนึกคือปัญหา เอ็น-พัซเซิล (n-puzzle) โดยทั่วไปการใช้วิธีศึกษาสำนึก สำหรับปัญหานี้และการนับจำนวนครั้งของการขยับแผ่นที่สามารถขยับได้ ระหว่างตำแหน่งปัจุจบันไปยังเป้าหมาย เกี่ยวข้องกันกับการแก้ปัญหาลักษณะเดียวกับปัญหาระยะห่างแมนแฮทตัน (Manhattan distance)
[แก้] ผลกระทบของวิธีศึกษาสำนึกในด้านของประสิทธิภาพเชิงเวลา
ในการค้นหารูปแบบของการแก้ไขปัญหา เมื่อมีตัวเลือกจำนวน b ทุกๆ ปมและมีความลึก d จากตำแหน่งปัจจุบันไปยังปมเป้าหมาย การค้นหาแบบตรงไปตรงมา (naive)จะใช้การค้นหาประมาณ bd ปม ถึงจะพบคำตอบ
การนำวิธีศึกษาสำนึกมาใช้ช่วยเพิ่มประสิทธิภาพเชิงเวลาของการค้นคำตอบได้โดยจะช่วยลด จำนวนการแตกกิ่งก้านbranching factor จากจำนวน b ไปยังค่าคงที่ b*
แม้ว่าการประมาณโดยใช้วิธีศึกษาสำนึกจะให้ผลเฉลยที่เหมาะสม (optimal answer) แต่การใช้วิธีศึกษาสำนึกที่ให้การประมาณค่าในจำนวนการแตกกิ่งก้าน (branching factor) ที่ต่ำกว่าจะช่วยเพิ่มประสิทธิภาพของการคำนวณได้ดียิ่งขึ้น สำหรับในปัญหาทั่วๆ ไป เราสามารถแสดงได้ว่า วิธีศึกษาสำนึก h2(n) ดีกว่า วิธีศึกษาสำนึก h1(n) ในเงื่อนไขถ้า h2(n) มากกว่าdominate h1(n) หรือ h1(n) < h2(n) สำหรับ n ทุกๆ ค่า
[แก้] วิธีศึกษาสำนึกในระบบปัญญาประดิษฐ์
มีขั้นตอนวิธีหลายอย่างในระบบปัญญาประดิษฐ์ ที่ใช้วิธีศึกษาสำนึกโดยธรรมชาติ หรือใช้กฎเกณฑ์แบบศึกษาสำนึกได้
ตัวอย่างเช่น ระบบตรวจจับการส่งข่าวขยะสแปม (SpamAssassin) ใช้วิธีศึกษาสำนึกในการตัดสินว่า อีเมลแบบใดเป็นข่าวขยะหรือไม่เป็น สำหรับกฎการตรวจจับที่ได้วางไว้ ถ้าใช้เพียงกฎเดียวก็จะไม่สามารถตรวจสอบได้อย่างถูกต้อง แต่เมื่อใช้วิธีศึกษาสำนึกเข้าช่วยประกอบรวมกฎการตรวจจับหลายๆ กฎเข้าไว้ด้วยกัน ก็จะได้ระบบที่ได้ผลที่ดีกว่า และน่าเชื่อถือยิ่งขึ้น
