ทฤษฎีกราฟเชิงปฏิบัติใน Ruby

นี่เป็นงวดถัดไปในซีรีส์ “วิทยาการคอมพิวเตอร์เชิงปฏิบัติ” ที่คุณจะได้เรียนรู้วิธีใช้แนวคิดวิทยาการคอมพิวเตอร์แบบคลาสสิกเพื่อแก้ปัญหาจริงโดยใช้ Ruby

วันนี้เราจะมาพูดถึง ทฤษฎีกราฟ .

คุณอาจเคยได้ยินเกี่ยวกับไบนารีทรี พวกมันมีลักษณะดังนี้:

ประเด็นก็คือ ต้นไม้ไบนารีเป็นเพียงกราฟรุ่นพิเศษ ดังนั้นควรให้แนวคิดแก่คุณว่ากราฟมีความกว้างเพียงใด

มาเริ่มกันที่ภาพรวมของพื้นฐานทฤษฎีกราฟกันก่อน จากนั้นเราจะมาดูกันว่าการใช้งานจริงมีอะไรบ้างและจะใช้งานสิ่งนี้ใน Ruby ได้อย่างไร

กราฟพื้นฐาน

กราฟประกอบด้วยสององค์ประกอบ:

• โหนด (หรือจุดยอด)
• ขอบ

โหนดหนึ่งแสดงถึงองค์ประกอบหนึ่งในกราฟ เช่น เมืองหรือถนน ในกราฟที่แสดงแผนที่ ในขณะที่ขอบแสดงถึงการเชื่อมต่อระหว่างโหนด

หากคุณดูหนังสือวิทยาศาสตร์คอมพิวเตอร์หรือคณิตศาสตร์ คุณจะเห็นกราฟที่กำหนดโดยสูตรนี้:G(V, E) .

โดยที่ G หมายถึงกราฟ V คือเซตของจุดยอด &E คือเซตของขอบ

กราฟสามารถกำหนดทิศทางหรือไม่มีทิศทางได้ หมายความว่าคุณสามารถไปได้เพียงทิศทางเดียว (กราฟบอกทิศทาง) หรือทั้งสองทิศทาง (กราฟแบบไม่บอกทิศทาง)

กราฟที่ได้รับความนิยมมากที่สุดคือ กราฟ Acyclic แบบกำกับทิศทาง (DAG). Acyclic หมายถึง ไม่มีการวนซ้ำ ไม่มีทางย้อนรอยได้

ใช้สำหรับกราฟ

ตอนนี้เราได้เห็นภาพรวมของปัจจัยพื้นฐานแล้ว มาดูการใช้งานทั่วไปของกราฟกัน

คุณสามารถใช้กราฟเพื่อทำสิ่งต่างๆ เช่น:

• ค้นหาเส้นทางที่สั้นที่สุด (หรือยาวที่สุด) ระหว่างสองตำแหน่ง
• ตรวจสอบว่าสองสิ่งเกี่ยวข้องกันหรือไม่
• สร้างเครื่องมือแนะนำ
• วิเคราะห์การพึ่งพา

อีกตัวอย่างหนึ่งรวมถึงการหาเส้นทางที่ดีที่สุดไปยังจุดหมายปลายทาง (นึกถึงอุปกรณ์ GPS)

วิธีการใช้และใช้กราฟ

คุณสามารถเขียนการใช้งานกราฟของคุณเองได้ แต่สำหรับบทความนี้ เราจะใช้ RGL gem ที่ได้ติดตั้งไว้สำหรับเราแล้ว

ในการสร้างกราฟพื้นฐานโดยใช้ RGL:

require 'rgl/adjacency'

graph = RGL::DirectedAdjacencyGraph.new

graph.add_edge 1,2
graph.add_edge 3,4
graph.add_edge 1,4
graph.add_edge 4,3

รหัสนี้สร้างกราฟต่อไปนี้:

คุณสามารถแสดงกราฟของคุณได้ดังนี้:

require 'rgl/dot'

graph.print_dotted_on

จากนั้นคัดลอกผลลัพธ์ของวิธีการนั้นบนไซต์ที่สามารถประมวลผลภาษาดอทได้ ชอบอันนี้

หรือคุณสามารถติดตั้ง Graphviz บนเครื่องของคุณเพื่อสร้างภาพในเครื่อง

ตอนนี้เรามีกราฟแล้ว เราอาจต้องการสำรวจเพื่อหาข้อมูลเกี่ยวกับกราฟ

มีอัลกอริธึมพื้นฐานสองแบบสำหรับการค้นหากราฟของคุณ :

• การค้นหาแบบกว้างก่อน (BFS)
• ค้นหาความลึกครั้งแรก (DFS)

ใน BFS คุณจะได้รับโหนดที่ใกล้เคียงที่สุดก่อน และใน DFS คุณจะต้องให้ลึกที่สุดเท่าที่จะเป็นไปได้สำหรับทุกโหนด อัลกอริทึมเหล่านี้สามารถใช้งานได้โดยใช้โครงสร้างข้อมูลสแต็ก

อัญมณี RGL ได้ใช้อัลกอริทึมเหล่านั้นสำหรับคุณแล้ว:

require 'rgl/traversal'

graph.bfs_iterator.to_a
# [1, 2, 4, 3]

graph.dfs_iterator.to_a
# [1, 4, 3, 2]

ดูกราฟอีกครั้งและทำตามเส้นทางที่อัลกอริธึมเหล่านี้ใช้เพียงแค่ตาของคุณ (หรือคุณจะใช้นิ้วก็ได้หากต้องการ) ที่จะช่วยให้คุณเข้าใจสิ่งที่เกิดขึ้น

กราฟแสดงน้ำหนัก

เราสามารถเพิ่มข้อมูลเพิ่มเติมลงในกราฟในรูปแบบของน้ำหนักเพื่อให้มีประโยชน์มากขึ้น

น้ำหนักถูกกำหนดให้กับขอบ ซึ่งเป็น เส้นทางระหว่างสองโหนด (เรียกอีกอย่างว่า “จุดยอด”) ตุ้มน้ำหนักเหล่านี้แสดงถึงค่าใช้จ่ายในการเดินทางจากจุดหนึ่งไปยังอีกจุดหนึ่ง

ตัวอย่างเช่น หากเรามีแผนที่ของประเทศในรูปของกราฟ &เราต้องการไปให้ถึงจุดหมายในเวลาที่สั้นที่สุดเท่าที่จะเป็นไปได้ น้ำหนักจะแสดงระยะทางระหว่างสองเมือง

หรือถ้าเรามีเครือข่ายคอมพิวเตอร์ น้ำหนักอาจแสดงถึงจำนวนฮ็อปที่ต้องใช้ในการเข้าถึงเครือข่ายใดเครือข่ายหนึ่ง

“ในระบบเครือข่ายคอมพิวเตอร์ การกระโดดเป็นส่วนหนึ่งของเส้นทางระหว่างต้นทางและปลายทาง แพ็กเก็ตข้อมูลจะผ่านบริดจ์ เราเตอร์ และเกตเวย์ขณะที่เดินทางระหว่างต้นทางและปลายทาง ทุกครั้งที่ส่งแพ็กเก็ตไปยังอุปกรณ์เครือข่ายเครื่องถัดไป จะเกิดการกระโดดขึ้น” – วิกิพีเดีย

นี่คือตัวอย่างโค้ดสำหรับกราฟแบบถ่วงน้ำหนัก:

graph = RGL::DirectedAdjacencyGraph.new
graph.add_vertices "Los Angeles", "New York", "Chicago", "Houston", "Seattle"

edge_weights =
{
  ["New York", "Los Angeles"] => 2445,
  ["Los Angeles", "Chicago"] => 2015,
  ["Los Angeles", "Houston"] => 1547,
  ["Chicago", "Houston"] => 939,
  ["Seattle", "Los Angeles"] => 1548
}

edge_weights.each { |(city1, city2), w| graph.add_edge(city1, city2) }

ขณะนี้เราสามารถค้นหาเส้นทางที่สั้นที่สุดจากจุดหนึ่งไปยังอีกจุดหนึ่งได้ และนั่นคือหัวข้อของหัวข้อถัดไป!

ค้นหาเส้นทางที่สั้นที่สุด

อัลกอริทึมยอดนิยมสำหรับการค้นหาเส้นทางที่สั้นที่สุดในกราฟคืออัลกอริธึม "เส้นทางที่สั้นที่สุดของ Dijkstra"

จากกราฟถ่วงน้ำหนัก เราสามารถใช้อัลกอริทึมของ Dijkstra เพื่อแก้ปัญหานี้:

“วิธีที่เร็วที่สุดในการเดินทางจากจุด A ไปยังจุด B คืออะไร”

นี่คือตัวอย่างโค้ดโดยใช้ RGL gem:

p graph.dijkstra_shortest_path(edge_weights, "New York", "Houston")
# ["New York", "Los Angeles", "Houston"]

ซึ่งจะบอกเราถึงเส้นทางที่สั้นที่สุดจากนิวยอร์กไปยังฮูสตัน โดยใช้ข้อมูลที่มีอยู่ในกราฟ

สรุป

คุณได้เรียนรู้ว่าโครงสร้างข้อมูลกราฟคืออะไร &ใช้งานอย่างไรกับอัญมณี RGL

คุณยังได้เรียนรู้เกี่ยวกับอัลกอริทึมทั่วไปสำหรับการทำงานกับกราฟ เช่น DFS, BFS &Dijkstra

อย่าลืมแชร์โพสต์นี้ หากคุณพบว่ามีประโยชน์เพื่อให้คนอื่น ๆ สามารถเพลิดเพลินได้ 🙂