หลักสูตร/ปี พ.ศ. วิศวกรรมศาสตรมหาบัณฑิต สาขาวิชาวิศวกรรมคอมพิวเตอร์ ปี พ.ศ. 2565
ภาคและปีการศึกษาที่สำเร็จการศึกษา ภาคต้น ปีการศึกษา 2564
ประเภทโครงงาน
วิทยานิพนธ์
ชื่อโครงงานภาษาไทย
การปรับปรุงขั้นตอนวิธีแบบประมาณสำหรับปัญหาการติดตามวิถี
ชื่อโครงงานภาษาอังกฤษ
AN IMPROVED APPROXIMATION ALGORITHM FOR TRACKING PATHS
ผู้พัฒนา
6314500982 คุณานนต์ บุรเทพ
อาจารย์ที่ปรึกษาหลัก
จิตร์ทัศน์ ฝักเจริญผล
อาจารย์ที่ปรึกษาร่วม
ธนาวินท์ รักธรรมานนท์
บทคัดย่อ
วิทยานิพนธ์ฉบับนี้จัดทำขึ้นเพื่อนำเสนอขั้นตอนวิธีสำหรับปัญหาสองปัญหาปัญหาแรกคือปัญหา Vertex Multicut บนต้นไม้ที่ต้องการหาเซตของจุดยอดที่มีค่าถ่วงน้ำหนักน้อยที่สุดที่เมื่อตัดออกแล้วทำให้ทุกคู่จุดยอดที่ได้ถูกกำหนดมาให้ไม่มีวิถีถึงกัน วิทยานิพนธ์นี้ได้นำเสนอขั้นตอนวิธีแบบประมาณที่อัตราส่วนการประมาณเท่ากับ 2 ปัญหาที่สองได้แก่ปัญหา Tracking Paths ที่ต้องการหาเซตของจุดยอด T ที่ทำให้สามารถจำแนกวิถีในเซต T สำหรับปัญหาดังกล่าว งานวิจัยล่าสุดในปัจจุบันซึ่งเสนอโดย Václav Blažej, Pratibha Choudhary, Dušan Knop, Jan Matyáš Křišťan, Ondrej Suchy and Tomáš Valla [WAOA'21] เป็นขั้นตอนวิธีแบบประมาณที่อัตราส่วนการประมาณเท่ากับ 66 โดยใช้ขั้นตอนวิธีแบบประมาณสำหรับปัญหา Vertex Multicut บนต้นไม้ เมื่อนำขั้นตอนวิธีแบบประมาณสำหรับปัญหา Vertex Multicut ที่เราได้เสนอขึ้นทำให้สามารถลดค่าอัตราส่วนการประมาณจาก 66 เป็น 6 ได้สำหรับปัญหาดังกล่าว
Abstract
This thesis considers two related path problems in graphs. The first problem is the Vertex Multicut on Trees whose goal is to find the cheapest set of vertices that cut every given pair of vertices. We present a 2-approximation algorithm for this problem. Another problem is the Tracking Paths whose goal is to find the cheapest set of vertices such that every distinct path from source s to target t can be uniquely identified by an intersection pattern with those set of vertices. The 2-approximation algorithm for the Vertex Multicut on Trees can be used as a subroutine in the recent approximation algorithm presented by Václav Blažej, Pratibha Choudhary, Dušan Knop, Jan Matyáš Křišťan, Ondrej Suchy and Tomáš Valla [WAOA'21], improving approximation ratio from 66 to 6 for the Tracking Paths problem.
คำสำคัญ (Keywords)
-
เว็บไซต์โครงงาน
-
วีดีโอคลิปของโครงงาน
-
ที่เก็บเวอร์ชันซอร์สโค้ด
-
ผู้นำเข้าข้อมูลครั้งแรก
คุณานนต์
บุรเทพ
(g6314500982)
แก้ไขครั้งสุดท้าย
เมื่อ Sept. 1, 2022, 3:37 p.m. โดย
คุณานนต์
บุรเทพ
(g6314500982)
สถานะการอนุมัติ
รออนุมัติ