TY - JOUR ID - TI - Developing Backtracking Algorithm to Find the Optimal Solution Path تطویر خوارزمیة الرجوع لإیجاد المسار الامثل للحل AU - Suhad M. Kadhum AU - Isra’a A. Abdul-Jabbar PY - 2010 VL - 28 IS - 24 SP - 6995 EP - 7003 JO - Engineering and Technology Journal مجلة الهندسة والتكنولوجيا SN - 16816900 24120758 AB - There are numerous search methods in A.I used to find the solution path to a subjected problem, but many of them return one solution path with no consider it is the optimal or not. The aim of this work is to find a direct path from the start state to the goal state such that it is the shortest path with minimum cost (the optimal solution path). We develop the backtracking algorithm in order to find the optimal solutionpath, such that all possible paths of the problem that expected to contain the optimal solution path can be checked, also we use a heuristic function depends on the actual cost of transition from one state to another. And in order to reduce the search time we discard any path that it is not useful in finding the optimal solution path.The proposed algorithm was implemented using visual prolog 5.1 and tested on tree diagram and the result was good in finding the optimal solution path (with efficient search time equivalent to O(bd/2) and space complexity O(bd) in worst cases).

هناك العديد من طرق البحث في الذكاء الاصطناعي المستخدمة لإيجاد مسار حل للمشكلة المطروحة، لكن العديد منها ترجع مسار حل واحد دون الاخذ بنظر الاعتبار هل ان هذا المسار يمثل الحل الامثل ام لا. الهدف من هذا البحث هو ايجاد مسار مباشر من الحالة الابتدائية الى الحالة الهدف باقل كلفةوباقصر طريق(المسار الامثل للحل). تم تطوير خوارزمية الرجوع للخلف لإيجاد المسار الأمثل للحل، بحيث ان كل المسارات الممكنة التي من المتوقع ان تحتوي على المسار الامثل للحل سوف يتم تدقيقها، وقد استخدمنا دالة موجهة تعتمد على الكلفة الحقيقية للانتقال من حالة الى اخرى. ولتقليل وقت البحث سنهمل أيمسار غير مفيد في ايجاد المسار الامثل للحل.تم تنفيذ الخوارزمية المقترحة باستخدام لغة برولوك المرئية 5.1 وتم اختبارها على مخطط شجري، وكانت النتائج جيدة في ايجاد المسار الامثل للحل في اسوء الحالات). O(bd) وتعقيد O(bd/ (مع كفاءة في وقت البحث تقارب ( ER -