ما هي المشاكل التي يمكن حلها أو معالجتها بسهولة أكبر باستخدام الرسوم البيانية والأشجار؟[مغلق]

Question

ما هي المشاكل الأكثر شيوعًا التي يمكن حلها باستخدام بنيات البيانات هذه؟

سيكون من الجيد بالنسبة لي أن أحصل أيضًا على توصيات بشأن الكتب التي:

• تنفيذ الهياكل
• تنفيذ وشرح أسباب الخوارزميات التي تستخدمها

Answer 1

أول شيء أفكر فيه عندما أقرأ هذا السؤال هو: ما هي أنواع الأشياء التي تستخدم الرسوم البيانية/الأشجار؟ ثم أفكر بشكل عكسي في كيفية استخدامها.

على سبيل المثال، خذ استخدامين شائعين للشجرة:

• دوم
• أنظمة الملفات

يشبه DOM وXML في هذا الصدد الهياكل الشجرية.

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

يجب أن تسأل نفسك أيضًا:هل تقع البيانات في هذا النوع من البنية؟قم بإنشاء هياكل بيانات منطقية للمشكلة وسيتبع الباقي.

وبقدر ما يكون الأمر أسهل، أعتقد أن هذا أمر نسبي.هل أنت جيد في الوظائف العودية لاجتياز شجرة/رسم بياني؟ماذا لو كنت بحاجة إلى موازنة الشجرة؟

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

آمل أن يساعدك ذلك على التفكير في هذه الهياكل.أما بالنسبة لتوصية الكتاب، يجب أن أوافق عليه مقدمة في الخوارزميات.

Answer 2

مخططات الدائرة.

التجميع (الرسوم البيانية غير الحلقية الموجهة)

خرائط.مدمجة للغاية مثل الرسوم البيانية.

مشاكل تدفق الشبكة.

قرار الأشجار للأنظمة الخبيرة (كذا)

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

Answer 3

يمكن إعادة كتابة كل مشكلة تقريبًا من حيث نظرية الرسم البياني.أنا لا أمزح، انظر إلى أي كتاب عن مشاكل NP الكاملة، هناك بعض المشاكل الغريبة التي تتحول إلى نظرية الرسم البياني لأن لدينا أدوات جيدة للعمل مع الرسوم البيانية...

Answer 4

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

Answer 5

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

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

Answer 6

خوارزميات جافا:الجزء 5 روبرت سيدجويك يدور حول خوارزميات الرسم البياني وهياكل البيانات.سيكون هذا أول كتاب جيد للعمل عليه إذا كنت تريد تنفيذ بعض خوارزميات الرسم البياني.

Answer 7

تستخدم الرسوم البيانية للمشهد لرسم الرسومات في الألعاب وتطبيقات الوسائط المتعددة الأشجار والرسوم البيانية بشكل كبير.تمثل العقد الكائنات التي سيتم تقديمها، والتحويلات، وعناصر التحكم، والمجموعات، ...

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

Answer 8

@DavidJoiner/الكل:

FWIW:نسخة جديدة من دليل تصميم الخوارزمية ومن المقرر أن يخرج في أي يوم الآن.

الدورة التدريبية الكاملة التي قام الأستاذ سكيينا بتطوير هذا الكتاب لها متاحة أيضًا على الويب:

http://www.cs.sunysb.edu/~algorith/video-lectures/2007-1.html

Answer 9

تُستخدم الأشجار كثيرًا في لغات البرمجة الوظيفية نظرًا لطبيعتها التكرارية.

تعد الرسوم البيانية والأشجار أيضًا طريقة جيدة لنمذجة الكثير من مشكلات الذكاء الاصطناعي.

Answer 10

تستخدم الألعاب غالبًا الرسوم البيانية لتسهيل العثور على المسارات عبر عالم اللعبة.يمكن أن يحتوي التمثيل البياني للعالم على خوارزميات مثل بحث العرض أولاً أو A* من أجل العثور على طريق عبره.

كما أنهم غالبًا ما يستخدمون الأشجار لتمثيل الكيانات داخل العالم.إذا كان لديك الآلاف من الكيانات وتحتاج إلى العثور على واحدة في موضع معين، فإن التكرار الخطي عبر القائمة قد يكون غير فعال، خاصة إذا كنت بحاجة إلى القيام بذلك كثيرًا.ولذلك يمكن تقسيم المنطقة إلى شجرة للسماح بالبحث فيها بسرعة أكبر.مثلما يمكن البحث في الفضاء الخطي بكفاءة باستخدام البحث الثنائي (وبالتالي تقسيمه إلى شجرة ثنائية)، يمكن تقسيم الفضاء ثنائي الأبعاد إلى quadtree ومساحة ثلاثية الأبعاد في ملف octree.