ทฤษฎีกราฟกับ Ingress

By: neizod
Writer
on Wed, 13/03/2013 - 21:02

หัวใจสำคัญของ Ingress คือการสร้าง control field ปกคลุมพื้นที่เพื่อเพิ่มคะแนนโดยรวมให้กับทีมตัวเอง ซึ่งการจะสร้างมันได้ ต้องอาศัย portal จำนวน 3 เสา และ key ของ portal ปลายทางไว้สำหรับ link portal เข้าด้วยกัน

เมื่อเทียบกับวิชาทฤษฎีกราฟแล้ว portal ก็คือ vertex, link คือ edge และ control field คือ face นั่นเอง สำหรับบทความนี้ จะเรียกสิ่งต่างๆ ตามแบบ Ingress เพื่อความเป็นมิตรครับ :D

กราฟเชิงระนาบ

ข้อจำกัดอีกอย่างของการ link portal เข้าด้วยกัน (ที่เว็บส่วนใหญ่ไม่ค่อยเขียนบอก) คือ link ที่จะสร้างนั้น ต้องไม่ไปทับกับ link เส้นอื่นที่มีอยู่ก่อนแล้ว

เราเรียกกราฟในลักษณะนี้ว่ากราฟเชิงระนาบ (planar graph) ซึ่งมีสมบัติดังนี้

ถ้าให้ p แทนจำนวน portal, l แทนจำนวน link และ f แทนจำนวนพื้นที่ของ control field รวมกับพื้นที่ว่าง แล้ว

    p - l + f = 2

สมการนี้บ่งบอกความสัมพันธ์ระหว่างจำนวน key กับ control field ได้

นอกจากนี้ จากการที่ control field 1 พื้นที่ต้องการ link ล้อมรอบ 3 เส้น เมื่อคิดรวมทั้งหมด จะส่งผลให้นับ link เส้นหนึ่งๆ ซ้ำอย่างอย่างมาก 2 ครั้ง หรือเขียนได้ว่า 3f ≤ 2l จึงทำให้ได้

    l ≤ 3p - 6

จำนวน key ทั้งหมดที่ต้องการ เพื่อรับประกันว่าจะสามารถสร้าง control field ได้มากที่สุด

    f ≤ 2p - 4

จำนวน control field ที่สามารถเกิดขึ้นได้มากที่สุด ภายใต้จำนวน portal ที่มี

ส่วนจำนวน control field ที่สามารถเกิดขึ้นได้จริงในเกมนั้น มักจะน้อยกว่าที่อสมการข้างบนนี้บอกไว้อยู่จำนวนหนึ่ง เพราะเราไม่สามารถลาก link เป็นเส้นโค้งได้

ถึงกระนั้น การหาจำนวน control field ทั้งหมดก็สามารถทำได้โดยวาด link portal ที่อยู่ตามขอบเข้าด้วยกันทั้งหมดก่อน แล้วจึงสมมติสร้าง control field จาก link ที่เป็นเส้นโค้ง เช่นนี้

เสาสีเทาคือ portal ที่อยู่ในตำแหน่งขอบ พื้นที่สีส้มคือ control field ที่เป็นไปไม่ได้ (เพราะใช้เส้นโค้งช่วยสร้าง link) พื้นที่สีม่วงคือ control field ที่สามารถสร้างได้

จากตัวอย่างนี้ เมื่อหาค่า f ด้วยอสมการข้างต้นได้แล้ว ให้นำไปลบออกอีก 2 (จำนวน control field ที่เป็นไปไม่ได้) ก็จะได้ control field ที่เป็นไปได้ทั้งหมดครับ

กราฟสม่ำเสมอ

พิจารณา

การสร้าง control field แบบสีฟ้าจะมีจุดอ่อนอยู่ที่ portal (f) ฝ่ายตรงข้ามสามารถทำลาย portal นี้เพียงแห่งเดียวเพื่อตัด control field ได้ถึง 5 พื้นที่ แต่ถ้าสร้าง control field แบบสีเขียว การทำลาย portal (d), (e), (f) อันใดอันหนึ่งจะตัดได้แค่ 4 control field เท่านั้น

เรียกจำนวน link ทั้งหมดที่ออกจาก portal เสาหนึ่งๆ ว่า degree ทีนี้ลองกลับไปนับ degree ของแต่ละ portal

จะเห็นว่า control field แบบสีเขียว portal ทุกเสามี degree เท่ากัน เราจะเรียกกราฟที่มี degree เท่ากันหมดว่ากราฟสม่ำเสมอ (regular graph)

อย่างไรก็ตาม แม้กราฟสม่ำเสมอจะรับประกันว่าการโดนทำลาย portal เสาใดๆ จะส่งผลให้สูญเสีย control field เป็นจำนวนน้อยที่สุดเท่าที่จะเป็นไปได้ แต่การวาง link ให้ได้ออกมาเป็นกราฟสม่ำเสมอนั้นก็ไม่ใช่เรื่องง่าย (ส่วนใหญ่จะเป็นไปไม่ได้เลย) และบ่อยครั้งที่การสร้าง control field แบบสีฟ้ากลับเป็นทางเลือกที่ดีกว่า ถ้าหากว่าสามารถปกป้อง portal ที่มี degree สูงๆ ได้ดีกว่า portal อื่น

ปัญหาต่างๆ เกี่ยวกับการเลือกเส้นทาง

ในกรณีที่เรามี key เพียงพอและได้วางแผนว่าแล้วว่าจะสร้าง control field อย่างไร ขั้นต่อไปคือเดินทางไปสร้าง link ซึ่งเราไม่จำเป็นต้องไปทุก portal ก็ได้

จุดสีขาวในรูปแทน portal ที่ไม่จำเป็นต้องไป ถ้าหากว่าสามารถ link มาจากจุดสีเทาที่อยู่ติดกันได้

ปัญหานี้คือการหาจุดคลุมทั่ว (vertex cover) จัดเป็นปัญหาแบบ NP-hard

หลังจากตัด portal ที่ไม่จำเป็นออกจากลิสต์ของ portal ทั้งหมดด้วยวิธีข้างต้นแล้ว ก็ถึงขั้นตอนของการหาเวลาเดินทางระหว่าง portal พร้อมทั้งอาจเพิ่มสถานที่สำคัญเช่นบ้าน ที่ทำงาน หรือห้างที่จะไปฉลองหลังจากสร้าง control field ได้ครบตามเป้าหมายด้วย

ปัญหาเส้นทางที่สั้นที่สุด (shortest path) อาจช่วยหาเส้นทางจากที่ทำงานกลับบ้าน โดยที่ยังผ่านบาง portal ซึ่งสามารถใช้อัลกอริทึมของ Dijkstra ช่วยแก้ปัญหาได้

ส่วนถ้าเป็นวันหยุดที่มีเวลาเหลือเฟือและต้องการผ่านให้ครบทุก portal อาจเปลี่ยนไปพิจารณาปัญหาเดินทางของพนักงานขายตรง (travelling salesman) ที่จะตระเวนไปตาม portal ทุกเสาจนครบแล้วกลับมาที่เดิม ปัญหานี้เป็น NP-hard และมีความยุ่งยากที่ O(n!) สำหรับการแก้ปัญหาด้วยวิธี brute force หรือ O(n22n) เมื่อใช้ dynamic programming เข้าช่วยครับ

5 Comments

hisoft's picture

สมแล้ว ที่ท่านเป็นโสด เอ้ย ที่เป็นท่านเนยโสด

The Phantom Thief

-Rookies-'s picture

ไปลงบล็อคนัน มึนตึ๊บกันเป็นแถว มาลงที่นี่ มุกกันเป็นแถว ๕๕๕