heuristic suite

ชุดฮิวริสติก

หมายเหตุสำคัญ

โครงการไม่ได้อยู่ภายใต้การบำรุงรักษาอีกต่อไป กรุณาเยี่ยมชม LINQ ไปที่ A* สำหรับเวอร์ชันล่าสุด

ภาพรวม

Heuristic Suite เป็นการทดลองใช้อัลกอริธึมฮิวริสติกในการเขียนโปรแกรมทั่วไป โครงการมีวัตถุประสงค์เพื่อให้โครงสร้างพื้นฐานที่สามารถนำไปใช้กับปริศนาใด ๆ - ตราบใดที่ปริศนาสามารถแก้ไขได้ด้วยอัลกอริทึม

อัลกอริทึมที่ใช้งาน:

• A*
• ซ้ำลึกลงไป* (ida*)
• การค้นหาครั้งแรกที่ดีที่สุด
• การค้นหาครั้งแรกที่ดีที่สุด (RBF) ที่ดีที่สุด (RBF)

การใช้งานนั้นมุ่งเน้นวัตถุอย่างสมบูรณ์และใช้ประโยชน์จากกลไกการเปรียบเทียบเฟรมเวิร์กในตัวเช่น ICOMPARER (T) และ IEqualityComparer (T) เพื่อสร้างความเข้ากันได้ที่ยอดเยี่ยมกับ. NET มาตรฐานและระบบนิเวศ. NET ทั้งหมด ซอร์สโค้ดสามารถนำไปยังแพลตฟอร์มอื่น ๆ ได้อย่างง่ายดายเช่น Unity และ Xamarin

การแก้ปริศนาด้วยอัลกอริทึม

ในการใช้อัลกอริทึมกับปริศนาจำเป็นต้องมีการใช้งานต่อไปนี้:

1. คำจำกัดความขั้นตอน ประเภทที่กำหนดขั้นตอนของปริศนาจะต้องใช้อินเตอร์เฟส ISTEP (TKEY) คุณสมบัติ Key มีวัตถุประสงค์สองประการ:

   • เพื่อทดสอบว่าสองขั้นตอนเทียบเท่าหรือไม่ ตัวอย่างเช่น: ตำแหน่งเดียวกันบนกระดาน
   • เพื่อเปรียบเทียบสองขั้นตอนในการพิจารณาว่าคะแนนที่ดีกว่า ตัวอย่างเช่น: ระยะห่างระหว่างตำแหน่ง A และเป้าหมายและระยะห่างระหว่างตำแหน่ง B และเป้าหมายยิ่งได้คะแนนที่ดีกว่า

2. ขั้นตอนการเปรียบเทียบ ขั้นตอนจะถูกนำไปเปรียบเทียบซึ่งกันและกันตามคุณสมบัติ Key เพื่อพิจารณาว่าคะแนนใดดีกว่า การเปรียบเทียบสามารถทำได้ด้วยวิธีใดวิธีหนึ่งต่อไปนี้:

   • การใช้งาน iComparable (TKEY)
   • อินสแตนซ์ ICOMPARER (TKEY) ที่กำหนดเอง
   • ฟังก์ชั่น H (n) ที่ให้ไว้อย่างชัดเจนโดยที่พารามิเตอร์ n คือ Key

3. ขั้นตอนที่มีอยู่จากขั้นตอนขั้นตอนปัจจุบัน ข้อมูลขั้นตอนถัดไปสามารถให้ได้โดยการใช้อินเทอร์เฟซ INextStepFactory(TKey, TStep) หรือจัดหาตัวแทน NextStepFactory

หลังจากนั้นอัลกอริทึมสามารถเรียกใช้ได้โดยการเรียกใช้วิธี FindSolution ด้วยขั้นตอน from และขั้นตอน goal เป็นพารามิเตอร์ หากมีการแก้ปัญหาแต่ละขั้นตอนสามารถทำได้โดยการเรียกวิธี Enumerate ขั้นตอนสามารถ Reverse ก่อนที่การแจงนับจะเริ่มขึ้น

การเปรียบเทียบแบบฮิวริสติกและการเปรียบเทียบการแก้ปัญหาแบบไม่ต่อเนื่อง

โครงการจัดทำ HeuristicComparer และ DiscreteHeuristicComparer สำหรับสถานการณ์การเปรียบเทียบขั้นตอนที่แตกต่างกัน

• หากคุณสมบัติ Key สามารถเปรียบเทียบกันได้โดยตรงโดยไม่มีฟังก์ชั่น H (n) ที่ชัดเจนโดยค่าเริ่มต้น DiscreteHeuristicComparer จะถูกใช้สำหรับการเปรียบเทียบขั้นตอนที่เร็วขึ้น
• หากต้องการฟังก์ชั่น H (n) อย่างชัดเจนเพื่อเปรียบเทียบแต่ละขั้นตอน HeuristicComparer จะถูกใช้เพื่อดำเนินการประมาณการแบบดั้งเดิม F (N) = G (N) + H (N)

การตั้งค่าฟังก์ชันฮิวริสติก

การแจกแจง HeuristicFunctionPreference ช่วยให้ผู้ใช้สามารถเปลี่ยนยอดคงเหลือของการประมาณค่า f (n) = g (n) + h (n) เมื่อสองขั้นตอนได้รับการประเมินคะแนนเดียวกันการแจงนับจะตัดสินใจว่าฟังก์ชันใด G (n) หรือ H (n) จะได้รับการพิจารณาก่อน ความสมดุลที่เปลี่ยนแปลงสามารถส่งผลกระทบต่อพฤติกรรมของอัลกอริทึมฮิวริสติก

ตัวอย่าง

• การค้นหาเส้นทาง (Algorithmforce.example.Pathfinding)

  ตัวอย่างแสดงให้เห็นถึงปริศนาที่พบบ่อยที่สุดและแบบดั้งเดิมที่ใช้อัลกอริทึมฮิวริสติกเพื่อแก้ปัญหา

• 8-puzzle (Algorithmforce.example.eightPuzzle)

  ตัวอย่างแสดงให้เห็นถึงวิธีการแก้ปัญหา 8-puzzle ด้วยอัลกอริทึมฮิวริสติก ขั้นตอนเริ่มต้นและเป้าหมายของปริศนาแสดงด้านล่าง:

• Coins Flipping Puzzle (Algorithmforce.example.coinsflipping)

  ตัวอย่างนี้แสดงให้เห็นว่าเกม AI แก้ปริศนาการพลิกของเหรียญได้อย่างไร ในปริศนามีเพียงคู่ของเหรียญที่อยู่ติดกันเท่านั้นที่ได้รับอนุญาตให้พลิกในเวลาเดียวกัน ทั้งสิบเหรียญที่เป็นหัวหน้าคือเป้าหมาย ปริศนาได้รับแรงบันดาลใจจาก brially.org

ตัวอย่างเพิ่มเติมจะถูกเพิ่มในอนาคต

แพลตฟอร์ม

ปัจจุบันโครงการกำหนดเป้าหมาย. NET Core และ. NET Framework 4.5 หรือสูงกว่า