ข้ามไปเนื้อหา

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

จากวิกิพีเดีย สารานุกรมเสรี

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

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

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

อ้างอิง

[แก้]
  1. "ศัพท์บัญญัติ ๔๐ สาขาวิชา สำนักงานราชบัณฑิตยสภา".{{cite web}}: CS1 maint: url-status (ลิงก์) หมวดคอมพิวเตอร์และเทคโนโลยีสารสนเทศ