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

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

การแก้ปัญหาแบบศึกษาสำนึก หมวดคอมพิวเตอร์และเทคโนโลยีสารสนเทศ (heuristic approach) เปรียบเทียบได้กับ ขั้นตอนวิธีหรือขั้นตอนวิธีแก้ปัญหาที่ไม่สามารถรับประกันถึงคุณสมบัติทั้งสองประการข้างต้นได้ อาจจะมีเพียงประการใดประการหนึ่ง หรือ อาจจะไม่มีเลยก็ได้ ตัวอย่างความหมายของความไม่สามารถรับประกันได้ เช่น ถ้าเรามีวิธีในการหาคำตอบของปัญหาประเภทหนึ่ง ซึ่งโดยปกติวิธีนี้จะให้คำตอบที่มีคุณภาพดี แต่ในบางครั้งคำตอบที่ได้อาจจะไม่ดี หรือ เราไม่สามารถจะพิสูจน์ได้ว่า วิธีการหาคำตอบหนึ่งจะสามารถหาคำตอบได้เร็วตลอดเวลา ถึงแม้ว่าโดยทั่วไปแล้วจะเร็วก็ตาม

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

 วิธีแบบศึกษาสำนึกในปัญหาการหาเส้นทางสั้นที่สุด 

สำหรับปัญหาเส้นทางสั้นที่สุด (shortest path problems) นั้น วิธีแบบศึกษาสำนึกจะกำหนดให้ การศึกษาสำนึก เป็น ฟังก์ชันศึกษาสำนึก  อยู่บนปม (nodes) ของต้นไม้สำหรับค้น (search tree) ซึ่งทำงานโดยการประมาณค่าของวิถี (path) สั้นที่สุดหรือมีค่าน้อยสุด จากปมปัจจุบันไปยังปมเป้าหมาย (goal) วิธีการศึกษาสำนึกใช้ใน informed search algorithm เช่น การค้นหาของที่ดีที่สุดเชิงละโมบ หรือ Greedy best-first search และ การค้นหาเอสตาร์ A* สำหรับเป็นผู้เลือกหรือตัวตัดสินใจเลือกปมที่ดีที่สุดก่อนการค้นหาปมต่อไป การค้นหาของที่ดีที่สุดเชิงละโมบ (Greedy best-first search) จะเลือกปมที่มีค่าน้อยที่สุดสำหรับฟังก์ชันศึกษาสำนึก ส่วน เอสตาร์ (A*) จะค้นหาปมที่มีค่าน้อยที่สุดจากสมการ  โดยที่ฟังก์ชัน  คือ ค่าที่แท้จริง (exact cost) สำหรับเส้นทางจาก สถานะกำหนดเริ่มต้น (initial state) มายังสถานะปัจจุบัน และโดยที่ฟังก์ชัน  จะส่งค่าประมาณการศึกษาสำนึกที่ยอมรับได้ นั่นคือ ถ้าฟังก์ชัน  เป็นค่าประมาณที่ไม่เคยประมาณมากกว่าค่าจริงจนถึงเป้าหมาย (goal) — สำหรับกรณีนี้เอสตาร์ (A*) ได้มีการพิสูจน์แล้วว่าได้ผลเฉลยที่เหมาะที่สุดเสมอ (optimal)

ปัญหาเก่าแก่ที่เกี่ยวข้องกับวิธีศึกษาสำนึกคือปัญหา เอ็น-พัซเซิล (n-puzzle) โดยทั่วไปการใช้วิธีศึกษาสำนึก สำหรับปัญหานี้และการนับจำนวนครั้งของการขยับแผ่นที่สามารถขยับได้ ระหว่างตำแหน่งปัจุจบันไปยังเป้าหมาย เกี่ยวข้องกันกับการแก้ปัญหาลักษณะเดียวกับปัญหาระยะห่างแมนแฮทตัน (Manhattan distance)

 ผลกระทบของวิธีศึกษาสำนึกในด้านของประสิทธิภาพเชิงเวลา 

ในการค้นหารูปแบบของการแก้ไขปัญหา เมื่อมีตัวเลือกจำนวน  ทุก ๆ ปมและมีความลึก d จากตำแหน่งปัจจุบันไปยังปมเป้าหมาย การค้นหาแบบตรงไปตรงมา (naive) จะใช้การค้นหาประมาณ  ปม ถึงจะพบคำตอบ

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

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

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

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

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

 อ้างอิง 

หมวดหมู่:การแก้ปัญหา
หมวดหมู่:ขั้นตอนวิธีแบบศึกษาสำนึก