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

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

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

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

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

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

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

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

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

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