|
|
|||||||
| สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
  |
|
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
|
#1
16 กันยายน 2016, 04:32
|
||||
|
||||
รบกวนแนะนำทฤษฎีกราฟข้อนี้นิดนึงครับ
ถ้าทำแบบคิดต้นไม้แผ่ทั่วน้อยสุด ยังพอเก็ทนะครับ
 แต่ถ้าเจอแบบนี้ มีพี่ๆท่านไหนพอแนะนำได้บ้างไหมครับ  ขอบคุณล่วงหน้าครับ  ปล.ถ้าคิดว่าเดินซ้ำedgeเดินได้ไม่จำกัดจำนวนครั้ง 16 กันยายน 2016 05:55 : ข้อความนี้ถูกแก้ไขแล้ว 3 ครั้ง, ครั้งล่าสุดโดยคุณ ~VesCuLaR~ เหตุผล: เพิ่มเติม ปล. 
|
|
#2
18 กันยายน 2016, 22:05
|
||||
|
||||
|
ถ้าดีกรีของทุกจุดยอดเป็นเลขคู่ เราจะสามารถเดินจากจุด A กลับไปที่เดิมโดยผ่านทุกเส้นเชื่อมหนึ่งครั้งพอดีได้ครับ อันนี้เรียกว่า Eulerian circuit
ดังนั้นระยาทางที่สั้นที่สุดก็คือผลรวมของทุกเส้น เมื่อมีจุดที่มีดีครีเป็นคี่มาด้วย เราสามารถมองแบบนี้ได้ครับ สมมติว่าเราเดินจากจุด A แล้วกลับไปที่เดิมตามข้อ1 เมื่อไหร่ที่เราเดินซ้ำบนเส้นเชื่อมเดิม ให้เราวาดเส้นเชื่อมนั้นเพิ่มขึ้นมา เช่นเราเริ่มเดินด้วย AB แล้วในอนาคตเรากลับมาใช้เส้น AB อีก ให้เราเติมเส้นเชื่อมระหว่าง A กับ B เข้าไปอีกเส้น จะเห็นว่าในกราฟที่ได้มาใหม่ เราเดินบนเส้นเชื่อมแต่ละเส้นหนึ่งครั้งพอดีครับ และระยะทางที่เราเดินก็คือผลรวมของเส้นเชื่อมในกราฟใหม่ครับ ดังนั้นสิ่งที่เราต้องทำก็คือ หาว่าจะเติมเส้นเชื่อมยังไง เพื่อให้กราฟใหม่มีดีกรีของทุกจุดยอดเป็นคู่ โดยใช้ระยะเพิ่มน้อยที่สุด กราฟในโจทย์มีจุดยอดที่มีดีกรีคี่คือ A B C H ในข้อ1 การที่จะให้กราฟใหม่มีดีกรีของทุกจุดยอดเป็นคู่ เส้นเชื่อมที่เราเติมเข้าไปจะต้องรวมกันได้กราฟที่มี A B C H มีดีกรีเป็นคี่และจุดยอดที่เหลือมีดีกรีเป็นคู่ ข้อ2 น่าจะง่ายกว่า มาดูข้อ2กันก่อน เราต้องการเดินจาก A ไป H ใช้หลักการเดียวกันครับ ข้อแตกต่างก็คือเราต้องเติมเส้นเชื่อมเข้าไปเพื่อให้ดีกรีของทุกจุดยอดเป็นคู่ยกเว้น A กับ H นั่นก็คือ เส้นเชื่อมที่เราเติมเข้าไปจะต้องรวมกันได้กราฟที่มี B C มีดีกรีเป็นคี่และจุดยอดที่เหลือมีดีกรีเป็นคู่ กราฟดังกล่าวก็ต้องเป็น path จาก B ไป C ที่มีระยะทางสั้นที่สุดครับ นั่นก็คือ path BAC แปลว่าเมื่อเราเติมเส้นเชื่อม BA กับ AC เข้าไป เราจะได้กราฟที่มีดีกรีของทุกจุดยอดเป็นคู่ยกเว้น A กับ H คำตอบคือ ผลรวมของระยะทางทั้งหมดในรูป บวกด้วย BA กับ AC ครับ ซึ่งคือ +6+6 กลับมาที่ข้อ1 เราต้องการให้เส้นเชื่อมที่เราเติมเข้าไปจะต้องรวมกันได้กราฟที่มี A B C H มีดีกรีเป็นคี่และจุดยอดที่เหลือมีดีกรีเป็นคู่ สิ่งที่เราต้องทำคือ path สองอันโดยที่ปลายของ path สองอันนี้คือจุดยอด A B C H ครับ โดยที่ผลรวมของระยะทางบน path สั้นที่สุด เราทำได้โดยหา path ที่สั้นที่สุดนะหว่างทุกๆคู่ใน A B C H ครับ ไล่เอา Path ที่สั้นที่สุดระหว่าง A B ยาว 6 Path ที่สั้นที่สุดระหว่าง C H ยาว 16 รวมกันได้ 22 Path ที่สั้นที่สุดระหว่าง A C ยาว 6 Path ที่สั้นที่สุดระหว่าง B H ยาว 17 รวมกันได้ 23 Path ที่สั้นที่สุดระหว่าง A H ยาว 20 Path ที่สั้นที่สุดระหว่าง B C ยาว 12 รวมกันได้ 32 ดังนั้นเราควรเลือกแบบแรกครับ คือ path AB กับ path CFH นั่นคือเราเติมเส้นเชื่อ AB CF FH เข้าไปครับ กราฟที่ได้มาใหม่จะมีดีกรีคี่แค่ที่ A กับ H และมีระยะทางที่ต้องเดินคือ ผลรวมของระยะทางทั้งหมดในรูป รวมกับระยะทางที่เราเติมเข้าไป ซื่งคือ +22 ครับ งงตรงไหนถามได้ครับ อ่านเพิ่มเติมที่ได้ที่ https://en.m.wikipedia.org/wiki/Rout...ection_problem
|
|
#3
22 กันยายน 2016, 04:32
|
||||
|
||||
|
อ้างอิง:
ที่คิดออกคือต้องหาเส้นเดิมทั้งหมด แล้วหาเส้นใหม่ที่สั้นที่สุด แต่พอดูกรณีแล้วงงๆอะครับตอนแรก แต่ตอนนี้เก็ทหมดแล้ว ขอบคุณมากนะครับ
|
| |
|
|
