การค้นหาแบบฮิวริสติก

               การค้นหาประเภทฮิวริสติกนี้จะใช้กับความรู้แบบหนึ่งที่เรียกว่า ฮิวริสติกมาช่วยในการค้นหาให้มีประสิทธิภาพมากขึ้น โดยฮิวริสติกตัวนี้จะช่วยชี้แนะว่ากระบวนการค้นหาควรจะเลือกเส้นทางใดเพื่อค้นหาต่อไปให้ได้คำตอบอย่างมีประสิทธิภาพ พิจารณาปัญหาการเดินทางของพนักงานขาย (Traveling salesman problem)

            ในตัวอย่างปัญหานี้ มีเมือง 7 เมือง พนักงานขายต้องการเดินทางไปให้ได้ครบทั้ง 7 เมืองและกลับมายังจุดเริ่มต้นโดยให้ระยะทางโดยรวมสั้นที่สุด วิธีหนึ่งที่ทำได้คือ หาเส้นทางทั้งหมดที่เป็นไปได้ซึ่งจะมีด้วยกันทั้งสิ้น (7-1)!/2 = 360 วิธี จากนั้นวัดแต่ละเส้นทางว่าใช้ระยะทางเท่าไร แล้วก็เลือกเส้นทางที่สั้นที่สุด วิธีการนี้ไม่สามารถคำนวญได้อย่างมีประสิทธิภาพในทางปฎิบัติ เมื่อจำนวนเมืองมีมากขึ้น เช่นถ้ามีเมือง 100 เมือง จะมีเส้นทางที่เป็นไปได้ทั้งสิ้น 4.67 x 10^155

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

                การค้นหาแบบฮิวริสติกคือ การค้นหาที่นำความรู้ประเภทนี้มาใช้ช่วยชี้แนะเส้นทางในการค้นหาคำตอบ โดยมีลักษณะเด่นดังนี้

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

ตัวอย่างฟังก์ชันฮิวริสติก เช่น
3. เกม TicTacToe
เกม TicTacToe เป็นเกมที่มีผู้เล่น 2 คน ผลัดกันกาเครื่องหมายบนกระดานขนาด 3x 3 ฝ่ายหนึ่งกาเครื่องหมาย X และอีกฝ่ายหนึ่งกาเครื่องหมาย O ฝ่ายที่สามารถกาเครื่องหมายของตนติดต่อกันเป็นแนวเส้นตรงในทิศทางใดก็ได้ (ตั้ง, นอน, ทะแยงมุม) จะเป็นฝ่ายชนะ

ฟังก์ชันฮิวริสติกของสถานะ n อาจนิยามเป็น

f(n) = (จำนวนแนวเส้นตรงตามแนวนอน แนวตั้งและแนวทแยงที่ฝ่าย X ยังมีโอกาสชนะได้)
– (จำนวนแนวเส้นตรงตามแนวนอน แนวตั้งและแนวทแยงที่ฝ่าย O ยังมีโอกาสชนะได้)