TAILIEUCHUNG - Rút gọn đồ thị cho bài toán cây steiner nhỏ nhất

Bài viết này đề xuất một thuật toán rút gọn đồ thị cho bài toán SMT; đề xuất này đã được thực nghiệm trên một số bộ dữ liệu là đồ thị thưa trong hệ thống dữ liệu thực nghiệm chuẩn. Thuật toán rút gọn đồ thị đề xuất có hiệu quả rút gọn lên đến 98% đối với một số đồ thị lớn. | Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ IX Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin FAIR 9 Cần Thơ ngày 4-5 8 2016 DOI RÚT GỌN ĐỒ THỊ CHO BÀI TOÁN CÂY STEINER NHỎ NHẤT Phan Tấn Quốc Trường Đại học Sài Gòn quocpt@ TÓM TẮT Cây Steiner nhỏ nhất Steiner Minimal Tree - SMT là bài toán tối ưu tổ hợp có nhiều ứng dụng quan trọng trong khoa học và kỹ thuật đây là bài toán thuộc lớp NP-hard và hiện đang được nghiên cứu rộng rãi. Các tiếp cận giải bài toán SMT - dù là giải đúng hay giải gần đúng - thì công đoạn rút gọn đồ thị là rất quan trọng công đoạn này càng có ý nghĩa đối với các tiếp cận giải đúng bài toán SMT. Trong hàng chục năm qua đã có hàng loạt thuật toán rút gọn đồ thị cho bài toán SMT đã được công bố các kết quả này đã hỗ trợ tích cực cho việc giải bài toán SMT với kích thước lớn hơn. Bài báo này đề xuất thuật toán rút gọn đồ thị cho bài toán SMT và kết quả thực nghiệm là thông tin hữu ích cho việc nghiên cứu các thuật toán giải đúng cũng như các thuật toán giải gần đúng cho bài toán SMT. Từ khóa Steiner minimal tree graph reduction branch and bound algorithm exact algorithms for steiner minimal tree. I. GIỚI THIỆU A. Một số định nghĩa Cho n điểm P1 P2 Pn. Giả sử cần tìm một mạng giao thông nối k điểm trong số n điểm đã cho với nhau mạng giao thông này có thể sử dụng thêm một số điểm khác - cũng trong số n điểm đã cho và ngoài k điểm đã chọn - sao cho tổng độ dài của các đoạn thẳng nối các điểm là nhỏ nhất đây là bài toán cây Steiner nhỏ nhất. Mục này bài báo sẽ trình bày một số định nghĩa và tính chất liên quan. Định nghĩa 1. Cây Steiner 2 Cho G V G E G là một đơn đồ thị vô hướng liên thông và có trọng số không âm trên cạnh trong đó V G là tập gồm n đỉnh E G là tập gồm m cạnh w e là trọng số của cạnh e e E G . Cho Y là tập con các đỉnh của V G cây T đi qua tất cả các đỉnh trong Y được gọi là cây Steiner của Y. Tập Y được gọi là tập terminal các đỉnh thuộc tập Y được gọi là các đỉnh terminal các đỉnh thuộc cây T mà

Gia Hân 57 7 pdf

Upload

Bấm vào đây để xem trước nội dung

Tải xuống

TÀI LIỆU LIÊN QUAN

Rút gọn đồ thị cho bài toán cây steiner nhỏ nhất

7 39 1

Luận án Tiến sĩ Kỹ thuật: Nghiên cứu các thuật toán rút gọn đồ thị và ứng dụng để phát hiện cộng đồng trên mạng xã hội

130 30 1

Các dạng toán ôn tập vào lớp 10

32 62 0

Các dạng Toán ôn thi vào lớp 10

32 77 0

Đề kiểm tra HK 1 Toán 9 - Sở GD&ĐT Quảng Nam (2012-2013)

2 40 0

Đề thi tuyển lớp 10 môn Toán năm 2011 - Trường THCS Đáp Cầu (Đợt 2)

3 64 0

Đề KSCL đầu năm môn Toán lớp 11 năm 2018-2019 - THPT Thuận Thành Số 1

6 113 0

Thuật toán tìm kiếm Hill climbing giải bài toán Cây Steiner nhỏ nhất

9 82 2

Đề thi học sinh giỏi môn Toán lớp 9 cấp trường năm 2019-2020 có đáp án - Trường THCS Gia Hòa, Gia Viễn

5 48 1

Đề thi vào lớp 10 môn Toán năm 2021-2022 - Sở GD&ĐT Lai Châu

1 29 1

TÀI LIỆU XEM NHIỀU

Một Case Về Hematology (1)

8 462351 61

Giới thiệu :Lập trình mã nguồn mở

14 26673 79

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 11375 543

Câu hỏi và đáp án bài tập tình huống Quản trị học

14 10567 468

Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”

3 9855 108

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8906 1161

Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức

16 8518 426

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 8109 2279

Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)

152 7917 1821

Đề tài: Dự án kinh doanh thời trang quần áo nữ

17 7289 268

TỪ KHÓA LIÊN QUAN

TÀI LIỆU MỚI ĐĂNG

THE ANTHROPOLOGY OF ONLINE COMMUNITIES BY Samuel M.Wilson and Leighton C. Peterson

19 231 4 08-01-2025

B2B Content Marketing: 2012 Benchmarks, Budgets & Trends

17 241 3 08-01-2025

báo cáo hóa học:" Increased androgen receptor expression in serous carcinoma of the ovary is associated with an improved survival"

6 162 3 08-01-2025

báo cáo hóa học:" Perceptions of rewards among volunteer caregivers of people living with AIDS working in faith-based organizations in South Africa: a qualitative study"

10 162 1 08-01-2025

BÀI GIẢNG Biến Đổi Năng Lượng Điện Cơ - TS. Hồ Phạm Huy

137 166 1 08-01-2025

Báo cáo y học: "The Factors Influencing Depression Endpoints Research (FINDER) study: final results of Italian patients with depressio"

9 157 1 08-01-2025

Báo cáo " Thẩm quyền quản lí nhà nước đối với hoạt động quảng cáo thực trạng và hướng hoàn thiện "

7 217 7 08-01-2025

Valve Selection Handbook - Fourth Edition

337 150 2 08-01-2025

ĐỀ TÀI " ĐÁNH GIÁ HIỆU QUẢ HOẠT ĐỘNG KINH DOANH NGOẠI HỐI CỦA NGÂN HÀNG THƯƠNG MẠI CỔ PHẦN XUẤT NHẬP KHẨU VIỆT NAM "

51 159 3 08-01-2025

Bệnh sán lá gan trên gia súc và cách phòng trị

3 170 1 08-01-2025

TÀI LIỆU HOT

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 8109 2279

Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)

152 7917 1821

Ebook Chào con ba mẹ đã sẵn sàng

112 4436 1376

Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1

62 6353 1276

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8906 1161

Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu

561 3859 680

Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân

122 3930 610

Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm

274 4775 567

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 11375 543

Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe

35 4533 490