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à