heuristic suite

جناح مجريات الأمور

ملاحظة مهمة

لم يعد المشروع قيد الصيانة. يرجى زيارة LINQ إلى A* للحصول على أحدث إصدار.

ملخص

جناح الإرشادات هو تطبيق تجريبي لسلسلة من الخوارزميات الإرشادية في البرمجة العامة. يهدف المشروع إلى توفير بنية تحتية يمكن تطبيقها على أي لغز - طالما يمكن حل اللغز باستخدام الخوارزمية.

الخوارزميات المنفذة:

• أ*
• تعميق التكراري A* (IDA*)
• أفضل بحث أول
• أفضل بحث عن العودية الأولى (RBFS)

التنفيذ موجه نحو الكائنات بالكامل ويأخذ مزايا آلية مقارنة إطار العمل المدمجة مثل icomparer (t) و iequalitycomparer (t) لخلق توافق كبير مع .NET Standard و .NET Ecosystem. يمكن تقديم رمز المصدر بسهولة إلى منصات أخرى مثل 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 D قبل بدء التعداد.

المقارنة الإرشادية والمقارنات الإرشادية المنفصلة

يوفر المشروع 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) ، سيتم اعتبارها أولاً. يمكن أن يؤثر التوازن المتغير على سلوك الخوارزمية الإرشادية.

أمثلة

• العثور على المسار (خوارثمفورس

  يوضح المثال اللغز الأكثر شيوعًا والتقليدي الذي يستخدم الخوارزميات الإرشادية التي يجب حلها.

• 8-puzzle (خوارثمفورس. مثال.

  يوضح المثال كيفية حل الخوارزمية الثابتة. وترد الخطوات الأولية والهدف من اللغز أدناه:

• Coins Flipping Puzzle (GANTITHMForce.example.coinsflipping)

  يوضح هذا المثال كيف تحل لعبة AI اللغز المعدني. في اللغز ، يُسمح فقط بانقلب زوج من العملات المعدنية المجاورة في نفس الوقت. جميع العملات المعدنية العشرة التي هي الرأس هي الهدف. اللغز مستوحى من Brilliant.org.

سيتم إضافة المزيد من الأمثلة في المستقبل.

منصة

يستهدف المشروع حاليًا .NET Core و .NET Framework 4.5 أو أعلى.