عمق أول أساسيات البحث

Question

أحاول تحسين الخوارزمية الحالية لمشكلة 8 كوينز ، وهذه هي المرة الأولى التي أتعامل فيها حقًا مع خوارزميات/خوارزميات الخوارزمية. أرغب في تنفيذ بحث عمق أول مع التقليب لقيم Y المختلفة الموضحة هنا:http://en.wikipedia.org/wiki/eight_queens_puzzle#the_eight_queens_puzzle_as_an_exercise_in_algorithm_design

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

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

هل هناك أي موارد يمكن أن تساعدني في أساسيات عمليات البحث في العمق أو إنشاء التباديب lexigraphic في شكل شجرة؟

Answer 1

بشكل عام ، نعم ، فكرة البحث في العمق الأول هي أنك لن تضطر إلى إنشاء (أو "زيارة" أو "توسيع") كل عقدة.

في حالة مشكلة كوينز الثمانية ، إذا وضعت ملكة بحيث يمكنها مهاجمة ملكة أخرى ، فيمكنك إحباط هذا الفرع ؛ لا يمكن أن يؤدي إلى حل.

إذا كنت تحل متغيرًا من ثمانية ملكات ، كان هدفك هو العثور عليه واحد الحل ، وليس كل 92 ، ثم يمكنك الإقلاع بمجرد العثور على واحد.

بشكل عام ، إذا كنت تحل مشكلة أقل منفصلة ، مثل العثور على ترتيب "أفضل" للملكات وفقًا لبعض التدبير ، فيمكنك إحباط فرع بمجرد أن تعرف أنه لا يمكن أن يؤدي إلى حالة نهائية أفضل من حالة نهائية كنت قد وجدت بالفعل في فرع آخر. هذا مرتبط بـ خوارزمية البحث*.

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

Answer 2

خوارزمية DFS نفسها لا تولد الشجرة/الرسم البياني. إذا كنت ترغب في إنشاء الشجرة والرسوم البيانية ، فسيكون ذلك بسيطًا في بنائه كما تقوم بالبحث. إذا كنت ترغب فقط في العثور على Soution واحد ، فإن بنية بيانات LIFO المسطحة مثل القائمة المرتبطة ستكفي لهذا: عند زيارة عقدة جديدة ، قم بإلحاقها بالقائمة. عندما تترك عقدة للتراجع في البحث ، قم ببث العقدة.

Answer 3

كتاب بعنوان "مقدمة إلى الخوارزميات" من قبل Anany Levitan لديه تفسير مناسب لفهمك. كما قدم الحل لمشكلة 8 كوينز بالطريقة التي تنطلق بها. سوف يساعدك بالتأكيد.

كما أفهم ، لإيجاد حل واحد لا تحتاج إلى أي تقليب كل ما تحتاجه