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

{{เกี่ยวกับ|[[วิทยาการคอมพิวเตอร์]]||ฮิวริสติก (แก้ความกำกวม)}}
{{ลิงก์ไปภาษาอื่น}}

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

'''การแก้ปัญหาแบบศึกษาสำนึก'''<ref>{{Cite web|url=https://coined-word.orst.go.th/index.php |title=ศัพท์บัญญัติ ๔๐ สาขาวิชา สำนักงานราชบัณฑิตยสภา|url-status=live}} หมวดคอมพิวเตอร์และเทคโนโลยีสารสนเทศ</ref> (heuristic approach) เปรียบเทียบได้กับ [[ขั้นตอนวิธี]]หรือขั้นตอนวิธีแก้ปัญหาที่ไม่สามารถรับประกันถึงคุณสมบัติทั้งสองประการข้างต้นได้ อาจจะมีเพียงประการใดประการหนึ่ง หรือ อาจจะไม่มีเลยก็ได้ ตัวอย่างความหมายของความไม่สามารถรับประกันได้ เช่น ถ้าเรามีวิธีในการหาคำตอบของปัญหาประเภทหนึ่ง ซึ่งโดยปกติวิธีนี้จะให้คำตอบที่มีคุณภาพดี แต่ในบางครั้งคำตอบที่ได้อาจจะไม่ดี, หรือ เราไม่สามารถจะพิสูจน์ได้ว่า วิธีการหาคำตอบหนึ่งจะสามารถหาคำตอบได้เร็วตลอดเวลา ถึงแม้ว่าโดยทั่วไปแล้วจะเร็วก็ตาม

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

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

สำหรับ[[ปัญหาเส้นทางสั้นที่สุด]] ([[:en:shortest path problem|shortest path problem]]s) นั้น วิธีแบบศึกษาสำนึกจะกำหนดให้ ''การศึกษาสำนึก'' เป็น [[ฟังก์ชัน]]ศึกษาสำนึก , <math>h(n)</math> อยู่บน[[ปม]] ([[:en:node|node]]s) ของ[[ต้นไม้สำหรับค้น]] ([[:en:search tree|search tree]]), ซึ่งทำงานโดยการประมาณค่าของวิถี([[:en:path|path]]) สั้นที่สุดหรือมีค่าน้อยสุด จากปมปัจจุบันไปยังปมเป้าหมาย ([[:en:goal|goal]]) วิธีการศึกษาสำนึกใช้ใน [[:en:informed search algorithm|informed search algorithm]] เช่น การค้นหาของที่ดีที่สุดเชิงละโมบ หรือ[[:en:Greedy best-first search|Greedy best-first search]] และ การค้นหาเอสตาร์[[:en:A-star search algorithm|A*]] สำหรับเป็นผู้เลือกหรือตัวตัดสินใจเลือกปมที่ดีที่สุดก่อนการค้นหาปมต่อไป. การค้นหาของที่ดีที่สุดเชิงละโมบ (Greedy best-first search) จะเลือกปมที่มีค่าน้อยที่สุดสำหรับฟังก์ชันศึกษาสำนึก ส่วน เอสตาร์ (A*) จะค้นหาปมที่มีค่าน้อยที่สุดจากสมการ <math> g(n)+h(n) </math>, โดยที่ฟังก์ชัน <math>g(n)</math> คือ ค่าที่แท้จริง (exact cost) สำหรับเส้นทางจาก '''สถานะกำหนดเริ่มต้น''' (initial state) มายังสถานะปัจจุบัน. และโดยที่ฟังก์ชัน <math>h(n)</math> จะส่งค่าประมาณการศึกษาสำนึกที่ยอมรับได้ นั่นคือ ถ้าฟังก์ชัน <math>h(n)</math> เป็นค่าประมาณที่ไม่เคยประมาณมากกว่าค่าจริงจนถึงเป้าหมาย (goal) — สำหรับกรณีนี้เอสตาร์ (A*) ได้มีการพิสูจน์แล้วว่าได้ผลเฉลยที่เหมาะที่สุดเสมอ ([[:en:optimal|optimal]])

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

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

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

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

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

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

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

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

== อ้างอิง ==
{{รายการอ้างอิง}}

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