การแก้ปัญหาแบบศึกษาสำนึก

บทความนี้เกี่ยวกับวิทยาการคอมพิวเตอร์ สำหรับความหมายอื่น ดูที่ ฮิวริสติก (แก้ความกำกวม)

โดยปกติการออกแบบหรือค้นหาขั้นตอนวิธี หรือขั้นตอนวิธี ที่ดีเพื่อการหาผลลัพธ์หรือแก้ปัญหาด้วยคอมพิวเตอร์นั้นมีเป้าหมายพื้นฐานอยู่ 2 ประการ คือ

1. สามารถรับประกันคุณภาพของคำตอบได้ คือ สามารถพิสูจน์ถึงความเหมาะที่สุด (optimality) หรือ ระบุขอบข่ายคุณภาพ ของคำตอบได้
2. สามารถรับประกันช่วงเวลา หรือ ความเร็ว ที่ใช้ในการคำนวณ เพื่อหาคำตอบนั้นได้

การแก้ปัญหาแบบศึกษาสำนึก (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)จะใช้การค้นหาประมาณ $b^{d}$ ปม ถึงจะพบคำตอบ

การนำวิธีศึกษาสำนึกมาใช้ช่วยเพิ่มประสิทธิภาพเชิงเวลาของการค้นคำตอบได้โดยจะช่วยลด จำนวนการแตกกิ่งก้านbranching factor จากจำนวน $b$ ไปยังค่าคงที่ b*

แม้ว่าการประมาณโดยใช้วิธีศึกษาสำนึกจะให้ผลเฉลยที่เหมาะสม (optimal answer) แต่การใช้วิธีศึกษาสำนึกที่ให้การประมาณค่าในจำนวนการแตกกิ่งก้าน (branching factor) ที่ต่ำกว่าจะช่วยเพิ่มประสิทธิภาพของการคำนวณได้ดียิ่งขึ้น สำหรับในปัญหาทั่วๆ ไป เราสามารถแสดงได้ว่า วิธีศึกษาสำนึก $h_{2}(n)$ ดีกว่า วิธีศึกษาสำนึก $h_{1}(n)$ ในเงื่อนไขถ้า $h_{2}(n)$ มากกว่าdominate $h_{1}(n)$ หรือ $h_{1}(n)<h_{2}(n)$ สำหรับ $n$ ทุกๆ ค่า

วิธีศึกษาสำนึกในระบบปัญญาประดิษฐ์

มีขั้นตอนวิธีหลายอย่างในระบบปัญญาประดิษฐ์ ที่ใช้วิธีศึกษาสำนึกโดยธรรมชาติ หรือใช้กฎเกณฑ์แบบศึกษาสำนึกได้

ตัวอย่างเช่น ระบบตรวจจับการส่งข่าวขยะสแปม (SpamAssassin) ใช้วิธีศึกษาสำนึกในการตัดสินว่า อีเมลแบบใดเป็นข่าวขยะหรือไม่เป็น สำหรับกฎการตรวจจับที่ได้วางไว้ ถ้าใช้เพียงกฎเดียวก็จะไม่สามารถตรวจสอบได้อย่างถูกต้อง แต่เมื่อใช้วิธีศึกษาสำนึกเข้าช่วยประกอบรวมกฎการตรวจจับหลายๆ กฎเข้าไว้ด้วยกัน ก็จะได้ระบบที่ได้ผลที่ดีกว่า และน่าเชื่อถือยิ่งขึ้น