min_span_tree_visualizer

อัลกอริทึมต้นไม้ที่ครอบคลุมขั้นต่ำ?

โครงการ C ++ เพื่อแสดงให้เห็นว่าอัลกอริทึม Tree (MST) ขั้นต่ำสุดที่พบบ่อยที่สุดสองวิธีทำงานอย่างไร - ส่วนใหญ่คือ Kruskal's และ Prim's แอปพลิเคชันช่วยให้ผู้ใช้สามารถสร้างโครงสร้างต้นไม้แบบสุ่มหรือนำเข้าหนึ่งจากไฟล์จากนั้นเลือกอัลกอริทึมที่จะใช้เพื่อค้นหา MST ฟังก์ชั่นการเล่นที่เป็นประโยชน์ถูกนำไปใช้เพื่อให้ผู้ใช้สามารถมองเห็นทีละขั้นตอนว่าอัลกอริทึมมาถึงโซลูชันสุดท้ายได้อย่างไร ผู้ใช้มีความสามารถในการก้าวผ่านขั้นตอนการแก้อัลกอริทึมแบบทีละขั้นตอนหรือเลือกความเร็วในการเล่นและดูว่ามันเป็นเวทมนตร์

โครงการได้รับแรงบันดาลใจจากวิดีโอ YouTube สองรายการต่อไปนี้ซึ่งฉันคิดว่าน่าจะสนุกที่จะลองใช้ตัวเองใน C ++:

ภาพเคลื่อนไหวอัลกอริทึมของ Prim

ภาพเคลื่อนไหวอัลกอริทึมของ Kruskal

เทคโนโลยี

• C ++
• cmake
• เรียน Imgui
• catch2

เกี่ยวกับต้นไม้ที่ทอดน้อยที่สุด

ในวิทยาศาสตร์คอมพิวเตอร์กราฟเป็นคอลเลกชันของโหนดที่เชื่อมต่อเข้าด้วยกันด้วยขอบซึ่งมีน้ำหนักที่เกี่ยวข้อง ในแง่การปฏิบัติน้ำหนักอาจให้ขอบระหว่างสองโหนดความหมายทางกายภาพบางอย่างเช่นระยะทางเป็นเมตรเวลาเป็นชั่วโมงหรือค่าใช้จ่ายเป็นดอลลาร์ ต้นไม้เป็นกราฟที่ไม่มีวัฏจักร เช่น) สร้างขึ้นในลักษณะที่ไม่มีเส้นทางของขอบที่สามารถติดตามได้ซึ่งจะช่วยให้คุณกลับมาที่โหนดเดียวกับที่คุณเหลือ แผนผังที่ทอดนั้นจึงเป็นกราฟย่อยของกราฟบางส่วนที่ "ครอบคลุม" หรือเชื่อมต่อจุดยอดทั้งหมดของกราฟ ต้นไม้ที่ทอดนี้ยังสามารถเป็น 'ทรี' ต่ำสุด '(MST) เมื่อเลือกในลักษณะที่จะเลือกขอบที่มีน้ำหนักต่ำสุดเมื่อรวม ปรากฎว่า MSTs มีประโยชน์ในการปรับให้เหมาะสมหลายอย่างและในความเป็นจริงแล้วอัลกอริทึม MST แรกถูกค้นพบในขณะที่ออกแบบเครือข่ายไฟฟ้าสำหรับเมือง Moravia ¹

ในขณะที่อัลกอริทึมแรกที่ค้นพบสำหรับการแก้ปัญหานี้ถูกคิดค้นโดยนักคณิตศาสตร์ชาวเช็ก Otakar Borůvkaซึ่งเป็นอัลกอริธึมที่ได้รับความนิยมมากที่สุดในวันนี้คือ Prim's และ Kruskal ซึ่งเป็นตัวอย่างของอัลกอริธึมโลภที่ทำงานในรูปแบบที่แตกต่างกันเล็กน้อย

- อัลกอริทึมของ Prim

อัลกอริทึมของ Prim เป็นอัลกอริทึมโลภซึ่งสร้าง MST ทีละขอบโดยการตรวจสอบขอบขาออกทั้งหมดจากโหนดเริ่มต้นและเพิ่มขอบที่มีน้ำหนักต่ำที่สุดใน MST ด้วยวิธีนี้ MST ถูกสร้างขึ้นอย่างต่อเนื่องจนกว่าจะมีการสำรวจขอบทั้งหมด

- อัลกอริทึมของ Kruskal

ในทำนองเดียวกับที่อัลกอริทึมของ Prim สร้าง MST ทีละครั้งอัลกอริทึมของ Kruskal ก็ทำเช่นนั้นอย่างไรก็ตามมันก็เริ่มต้นด้วยการเริ่มต้นด้วยชุดที่แยกออกมาระหว่างโหนดและเข้าร่วมการตั้งค่าเข้าด้วยกันอย่างต่อเนื่อง

- อัลกอริทึมของ Chazelle (เร็ว ๆ นี้)

อัลกอริทึมของ Chazelle เป็นอัลกอริทึมเวลาเกือบเชิงเส้นสำหรับการค้นหา MST

คู่มือการพัฒนาท้องถิ่น Windows

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' ที่สร้างขึ้น

ในการเรียกใช้การทดสอบคลิกขวาและ "เลือกเป็นโครงการเริ่มต้น":

ในการเรียกใช้การทดสอบคลิกขวาและ "เลือกเป็นโครงการเริ่มต้น":

เชิงอรรถ

1. o jistémproblémuminimálním (ในปัญหาน้อยที่สุด) ↩