tailieunhanh - 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 48 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 78 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 114 0

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

9 83 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 461980 55

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

14 23314 67

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 11026 533

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

14 10231 452

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 9587 106

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

249 8451 1139

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

16 8308 423

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

8 7902 2239

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

17 6886 257

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 6287 1521

TỪ KHÓA LIÊN QUAN

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

Giáo án mầm non chương trình đổi mới: Đề tài: Ôn xác định vị trí trên – dưới, trước- sau của đối tượng khác.

8 388 3 31-05-2024

Đánh giá hao mòn và độ tin cậy của chi tiết và kết cấu trên đầu máy diezel part 3

12 329 0 31-05-2024

extremetech Hacking BlackBerry phần 9

31 266 0 31-05-2024

Trading Strategies Profit Making Techniques For Stock_3

23 205 1 31-05-2024

Data Structures and Algorithms - Chapter 8: Heaps

41 135 0 31-05-2024

CHƯƠNG 2: RỦI RO THÂM HỤT TÀI KHÓA

28 120 0 31-05-2024

Sử dụng mô hình ARCH và GARCH để phân tích và dự báo về giá cổ phiếu trên thị trường chứng khoán

24 1030 0 31-05-2024

Báo cáo y học: "Regulation and localization of endogenous human tristetraprolin"

12 93 0 31-05-2024

Báo cáo y học: "Effectiveness of injectable risperidone long-acting therapy for schizophrenia: data from the US, Spain, Australia, and Belgium"

7 89 0 31-05-2024

AN TOÀN TRONG PHÒNG HỒI TỈNH

15 113 0 31-05-2024

TÀI LIỆU HOT

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

8 7902 2239

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 6287 1521

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

112 3871 1276

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

62 5483 1142

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

249 8451 1139

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

561 3578 658

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

122 3778 568

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 11026 533

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

274 4219 527

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

35 4221 483