แพ็คเกจ Python เพื่อค้นหาเส้นทางที่สั้นที่สุดในกราฟโดยใช้ Ant Colony Optimization (ACO)
➡️ ตรวจสอบบทความขนาดกลางของฉันเพื่อดูคำแนะนำแบบละเอียด
อัลกอริธึมการเพิ่มประสิทธิภาพอาณานิคมมดเป็นเทคนิคความน่าจะเป็นสำหรับการแก้ปัญหาทางการคำนวณซึ่งสามารถลดเหลือเพียงการค้นหาเส้นทางที่ดีผ่านกราฟ (ที่มา)
การใช้อัลกอริทึม ACO นี้ใช้สภาพแวดล้อมกราฟ NetworkX
$ pip install aco_routing
ตรวจสอบ: example.py
นำเข้าการอ้างอิงทั้งหมด:
จาก aco_routing นำเข้า ACOimport networkx เป็น nx
สร้างวัตถุ NetworkX.Graph
ที่มีโหนดและขอบ:
G = nx.DiGraph()G.add_edge("A", "B", ราคา=2)G.add_edge("B", "C", ราคา=2)G.add_edge("A", "H" , ต้นทุน=2)G.add_edge("H", "G", ต้นทุน=2)G.add_edge("C", "F", ต้นทุน=1)G.add_edge("F", "G", ราคา=1)G.add_edge("G", "F", ราคา=1)G.add_edge("F", "C", ราคา=1)G.add_edge("C", "D", ราคา= 10)G.add_edge("E", "D", ราคา=2)G.add_edge("G", "E", ราคา=2)
ใช้ ACO เพื่อค้นหาเส้นทางที่สั้นที่สุดและต้นทุนระหว่าง source
และ destination
:
aco = ACO(G, ant_max_steps=100, num_iterations=100, ant_random_spawn=True)aco_path, aco_cost = aco.find_shortest_path(source="A",destination="D",num_ants=100, -
เอาท์พุท:
ACO path: A -> H -> G -> E -> D ACO path cost: 8.0
aco_routing.Ant
Ant
ที่เคลื่อนที่ผ่านกราฟ
aco_routing.ACO
อัลกอริธึมการเพิ่มประสิทธิภาพ Ant Colony แบบดั้งเดิมที่วางไข่มดที่โหนดต่างๆ ในกราฟ และค้นหาเส้นทางที่สั้นที่สุดระหว่างต้นทางและปลายทางที่ระบุ (รหัสเทียม)
โพสต์ปัญหาและข้อเสนอแนะในหน้าปัญหา GitHub
หากต้องการมีส่วนร่วม ให้แยกโปรเจ็กต์แล้วสร้างคำขอดึงกลับไปยังต้นแบบ