السلام عليكم و رحمة الله و بركاته

انا بصدد كتابة خوارزمية للبحث عن كل المسارات التي بين نقطتين في graph
اي ندخل ال graph على شكل مصفوفة من ثم ندخل النقطتين اللتين نريد معرفة
جميع المسارات التي بينها

في البداية بدا لي الامر سهلا لاني نفذت خوارزميات اكثر تعقيدا

لكني عندما بدات الحل لم اعرف كيف احتفظ بالمسار مثلا الاول و ابحث عن مسار اخر

و كيف ارجع الى نقطة بها اكثر من مسار عندما امشي في مسار الاول كيف ارجع و ارى المسارات الاخرى

ارجو ان تفيدوني

هذا شرح صغير للخوارزمية

العثور على جميع المسارات الممكنة بين 2 بيانات مختلفة في سلسلة تحتوي

بيانn

اريد ان اسالكم الان عن البحث عن كل المسارات


لقد فكرت كما قلت بمصفوفة اذا كان هناك مسار من حالة الى اخرى نضع 1 و العكس نضع -1

و باضافة جدول لجدول اي كل خانة من جدول هي بحد ذاتها جدول اخر

مثال

اذا كانت لدينا مصفوفة

mat[1.1]=1,mat[1.2]=1,mat[1.3]=-1,mat[1.4]=-1,mat[1.5]=-1

mat[2.1]=-1,mat[2.2]=1,mat[2.3]=1,mat[2.4]=-1,mat[2.5]=-1

mat[3.1]=-1,mat[3.2]=-1,mat[3.3]=1,mat[3.4]=1,mat[3.5]=1

mat[4.1]=-1,mat[4.2]=1,mat[4.3]=-1,mat[4.4]=1,mat[4.5]=-1

mat[5.1]=-1,mat[5.2]=1,mat[5.3]=-1,mat[5.4]=-1,mat[5.5]=1

ذا اردنا ان نعرف كل المسارات التي تؤدي من 1 الى الحالة 2 نظريا نرى

المسار1 : 1->2

المسار2 :1->3->4->2

المسار3: 1->3->5->2

هذا من الملاحظة


لكن خوارزميا مشكلة

function recherche_path(first,last,arrivel) begin

if last=arrivel then print (first-path) else

for all neoud E(succ(last) & noeud<> first_path

recherche(first_path+noeud,last,arrivel) end

بحيث

first_path هو مسار

first بداية المسار

arrivel النقطة التي مود الوصول اليها


لقد اعطتني نتيجة لكنني لم افلح في احويلها الى كود
لان هذا سؤال فقط من موضوع على سلاسل ماركوف

أوه أحب الأسئلة غن الخوارزميات 😄

أرى أنك قطعت شوطاً كبيراً والباقي (ترجمة الخوارزمية إلى كود) بسيط جداً. لكن بملاحظة الخوارزمية يبدو أنها منقولة بشكل مغلوط إذا تحوي على كثير من الأخطاء المنطقية. أظن الخوارزمية الصحيحة هي كالتالي:

1. function recherche_path(first-path,last,arrivel)
2. begin
3. if last=arrivel then
4.     print (first-path)
5. else
6. for all neoud E(succ(last) & noeud <> first_path
7.    recherche_path(first_path+noeud,noeud,arrivel)
8. end

أترك لك اكتشاف الفرق. ولنعمل معاً على تحوبل هذه الخوارزمية إلى كود يعمل (على لغة C++ مثلاُ)
أولا لتمثيل المصفوفة التي تكلمت عنها في لغات البرمجة نستطيع استخدام مصفوفة ثنائية البعد. من الشكل:

char Graph[NodesCount][NodesCount];

(لم استخدم std::vector هنا للتبسيط). ثم لحفظ سلسلة من الـ Nodes نستطيع تعريف نوع يعبر عن الـ node بحفظ احداثياتها داخل مصفوفة الـ graph واستخدام list ديناميكية تحوي مجموعة من الـ nodes كالتالي:

struct node_t
{
     node_t(int _i, int _j) : i(_i), j(_j) {}
     int i,j;
};
typedef std::list node_list_t;

الآن نحن جاهزون لتحويل الخوارزمية إلى كود.
لنبداً بالسطر الأول. هذا هو تعريف الإجراء وهو يأخذ ثلاث معاملات: المسار الذي وجد حتى الآن (سلسلة من الـ nodes)، آخر node من هذا المسار وأخيراً الهدف (من نوع Node). أولا دعنا نستغني عن المعامل last حيث أنه موجود في نهاية المسار (path) فيصبح تعريف الإجراء كالتالي:

void find_path(node_list_t& path, const node_t& target)
{
    const node_t &last = path.back();

السطر الثالث يقوم ببساطة بالتحقق ما إذا كان المسار قد وصل بالفعل في نهاية المطاف إلى الهدف وطباعة المسار في هذه الحالة. ونستطيع تحويله ببساطة إلى:

if (last == target)
      path_found(path);

لاحظ أنه بدلاً من طباعة المسار نقوم هنا بنداء إجراء آخر يأخذ المسار نفسه ويفعل به ما يشاء (طباعة، حفظ إلخ)

في خال لم يكن المسار قد وصل إلى الهدف فإنه يتم البحث عن الـ nodes المتصلة بالـ node الأخيرة وتصبح المشكلة البحث عن الهدف بدئاً من كل node متصلة بالـ node الأخيرة. مع الانتباه إلى تفادي الوقوغ قي حلقة مفرغة (يتم ذلك بالتأكد بأن الـ nodes المتصلة لم يتم زيارتها في المسار الحالي).

بالمحصلة يصبح الإجراء كالتالي:

void find_path(node_list_t& path, const node_t& target) {
    const node_t &last = path.back();
    if (last == target)   // هل وصلنا إلى الهدف؟
      path_found(path);
      else {
          const node_list_t &neighbors = get_neighbors(last);
          for (node_list_t::const_iterator itr=neighbors.begin();itr!=neighbors.end();itr++)
          {    // من أجل كل node مجاورة
	    if (path.find(*itr) != path.end())  // هل توجد قي المسار؟
	          continue;      // تم زيارة هذه الـ node سابقاً
            path.push_back(*itr);     // أضفها إلى المسار
	    find_path(path, target);   // ابحث عن الهدف بدئاً منها
            path.pop_back();       // أزلها من المسار
          }
      }
}

وبهذا نكوت قد انتهينا.
.
.
حسناً ليس حقيقة. بقي لك النقاط التالية:
1. الكود السابق لم يتم تجريبه وهو غالباً يحوي بعذ الأخطاء الإملائية هنا وهناك أترك لك تصحيحها
2. كتابة الإجرائين get_neighors() و path_found()
3. هل تستطيع اكتشاف النداء الصحيحة لهذا الإجراء لمعرفة المسار بين node و أخرى؟
4. هذه الحل يقوم بتجربة جميغ الحلول. أنصحك بالبحث عن خوارزمية بحث أقضل من هذه إن كانت السرعة تهمك.

إن كان لديك أي استفسار أرجو ألا تتردد في طرحه

لقد غيرت في هذا السطر لكن لماذا غيرت
 في مكان last وضعت noeud  انا اقصد ب last  اخر noeud  موجود في first_path
لقد جربته يدويا و عمل
هل جربته عندما اجريت التبديل

سوف اقوم بتجريبه ان شاء الله

كما قلت لم أجرب الكود لكن منطقياً هذا هو الحل الصحيح.
الحل الذي وضعته يفقتد أحد العناصر الهامة في كتابة إي إجراء عودي وهي:
1. شرط التوقف: هذا هو الشرط الذي يختبر ما إذا كانت آخر node هي الـ node الهدف
2. التقدم في فضاء المسألة: هذا ما تفتقده الخوارزمية التي وضعتها إذ أنها تغير فقط في المتغير first_path والذي يستخدم للإظهار فقط وليس في سير الخوارزمية.
3. نداء الإجراء نفسه
تخيل معي لو أننا نفذنا الخوارزمية. بداية من الـ node التي يشير لها last وكانت ليست هي الهدف ما سيحدث هو أنه سيتم نداء الإجراء مرة أخرى بنفس الـ node (التي يشير لها last) ليتبين أنها ليست الهدف مرة أخرى. ثم سيتم مرة أخرى نداء الإجراء بنفس الـ node وهكذا
لا أدري ما الخطأ التي تترتكبه في تجربتك للخوارزمية. لكن بإمكانك وضع سير التجربة لكي يتم التأكد منها



حسناً هذا يغير بعض الأمور. لكن تذكر أخي أن الخوارزمية التي كتبتها لا تحوي أي إيحاء بهذا القصد. ولم تعطي أنت أي شرح عن هذه النقطة (أعرف معلماً أو اثنين مستعدين لترسيب أي طالب لم يكتب الخوارزمية بشكل صحيح مهما كان قصده شريفاً ☺ )

السلام عليكم
 هل لك اخي عبد اللطيف ان تغير لي الكود بلغة c فقط لانني لم استطع التحصل على برنامج c++
ساتحصل عليه بعد ايام لكن يكون قد فات الاوان فان لم يكن يتعبك  ان تعطيه لي ب c  او حتى بالباسكال
اكون جد شاكرة

مف مف مف... أنفي لا يخطئ... أشم رائحة وظيفة... 😄
أختي الكريمة، ليس هدفنا تقديم حلول جاهزة للوظائف أو غيرها من الأعمال الواجبة بل هدفنا هو توجيه الطلاب والتقنيين عموماً ليجدوا الحلول بأنفسهم. هذا سوف يجعلهم قادرين على إيجاد حلول لمشاكل أخرى دون سؤال أحد (أو عندما لا يستطيعون ذلك، في الفحص مثلاً)

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


على كلٍ وحتى لا أكون قد أضفت مشكلة أخرى لمشاكلك. إليك بعض النقاط التي ترشدك لتغيير الكود:
1. الكود يستخدم المرجع (&) أحد مميزات C++. استبدليه بـ (*) المدعومة في C
2. الكود يستخدم std::list أحد مكتبات C++. يمكنك استبداله بـ static array مع خسارة في الديناميكية، أو البحث في الانترنت عن حل بديل لمصفوفة ديناميكية في C
3. يجب أن تكتبين المقابلات لـ push_back، pop_back و find على بنية البيانات التي اخترتيها كبديل لـ std::list


هذه هي أهم النقاط. أتمنى أن تحاولين القيام بعملية التحويل. ولا تترددي بالسؤال عن أي مشكلة تواجهك. كما أتمنى منك أن تضعين الحل الذي توصلتي إليه ليتسنى للأعضاء التأكد من صحته والاستفادة منه كذلك.