min_span_tree_visualizer
1.0.0
مشروع C ++ لتصور كيف يعمل اثنتان من خوارزميات شجرة الامتداد الأكثر شيوعًا (MST) - بشكل أساسي Kruskal's و Prim's. يسمح التطبيق للمستخدم بإنشاء بنية شجرة بشكل عشوائي أو استيراد واحد من ملف ، ثم حدد الخوارزمية التي يجب استخدامها للعثور على MST. يتم تنفيذ وظائف التشغيل المفيدة حتى يتمكن المستخدم من رؤية بصريًا خطوة بخطوة كيفية وصول الخوارزميات إلى الحل النهائي. يتمتع المستخدم بالقدرة على التنقل عبر عملية حل الخوارزمية خطوة بخطوة ، أو تحديد سرعة تشغيل ومشاهدتها تعمل إنها سحرية.
تم إلهام المشروع من مقاطع فيديو youtube التالية ، والتي اعتقدت أنها ستكون ممتعة لمحاولة تنفيذ نفسي في C ++:
الرسوم المتحركة خوارزمية بريم
الرسوم المتحركة خوارزمية كروسكال
في علوم الكمبيوتر ، الرسم البياني عبارة عن مجموعة من العقد متصلة معًا بواسطة الحواف ، والتي لها بعض الترجيح المرتبطة. من الناحية العملية ، قد يعطي الوزن الحافة بين العقدتين بعض المعنى المادي مثل المسافة بالأمتار أو الوقت في ساعات أو تكلفة بالدولار. الشجرة هي رسم بياني بدون دورات. أي) شيدت بطريقة لا يوجد طريق من الحواف التي يمكن اتباعها والتي ستسمح لك بالوصول إلى نفس العقدة التي تركتها منها. وبالتالي فإن شجرة الامتداد هي خريطة فرعية لبعض الرسم البياني الذي "يمتد" ، أو يتصل ، جميع رؤوس الرسم البياني. يمكن أن تكون شجرة الامتداد هذه أيضًا شجرة تمتد "الحد الأدنى" (MST) عند تحديدها بطريقة تختار الحواف التي لها وزن أدنى عند تلخيصها. اتضح أن MSTs مفيدة للغاية في العديد من مشاكل التحسين ، وفي الواقع تم اكتشاف خوارزمية MST الأولى أثناء تصميم شبكة كهرباء لمدينة مورافيا. 1
في حين تم اختراع أول خوارزمية يتم اكتشافها لحل هذه المشكلة من قبل عالم الرياضيات التشيكي أوتاكار بورفكا ، فإن الخوارزميتين الأكثر شعبية اليوم هما Prim's و Kruskal ، وهما أمثلة على الخوارزميات الجشع التي تعمل بطرق مختلفة قليلاً.
خوارزمية Prim's هي عبارة عن قفص جشع تقوم ببناء MST One Edge في وقت واحد من خلال فحص جميع الحواف الصادرة من بعض عقدة البداية ، وإضافة الحافة بأقل وزن إلى MST. وبهذه الطريقة ، تم بناء MST على التوالي حتى يتم استكشاف جميع الحواف.
بنفس الطريقة التي تقوم بها خوارزمية بريم ببناء حافة MST One في وقت واحد ، فإن خوارزمية Kruskal تفعل ذلك أيضًا ، ومع ذلك فهي تفعل ذلك من خلال البدء بعدد من مجموعات مفككة من الحواف بين العقد والانضمام إلى المجموعات على التوالي مع الحواف الأقل وزنًا حتى تكون هناك مجموعة واحدة متبقية من الحواف التي هي MST.
خوارزمية Chazelle هي خوارزمية زمنية خطية تقريبًا للعثور على MST.
git clone المستودع إلى جهازك المحلي.
من الدليل الجذري لركض المستودع:
git clone https://github.com/Microsoft/vcpkg.git
بمجرد الانتهاء ، cd إلى مجلد VCPKG وتشغيله:
./bootstrap-vcpkg.sh
أخيرًا ، قم بالتشغيل:
./vcpkg integrate install
قم بتشغيل cd .. cd build ثم قم بتشغيل cmake .. -DCMAKE_TOOLCHAIN_FILE=vcpkg/scripts/buildsystems/vcpkg.cmake . إذا سارت الأمور على ما يرام ، فستشاهد رسالة "إنشاء ملفات إلى ...". يمكنك الآن فتح مشروع "Minimum_Spanning_Tree_Visualizer" الذي تم إنشاؤه.
لتشغيل الاختبارات ، انقر بزر الماوس الأيمن و "SELECT as as startup project":
لتشغيل الاختبارات ، انقر بزر الماوس الأيمن و "SELECT as as startup project":
يا jistém problému minimálním (حول مشكلة الحد الأدنى) ↩
