Thuật toán tìm kiếm TABU giải bài toán cây khung với chi phí định tuyến nhỏ nhất

  • Phan Tấn Quốc Khoa Công nghệ Thông tin, Trường Đại học Sài Gòn.
  • Nguyễn Đức Nghĩa Viện Công nghệ Thông tin và Truyền thông, Trường Đại học Bách khoa Hà Nội.

Abstract

Minimum Routing Cost Spanning Tree (MRCST)  is  one  of  spanning  tree  optimization problems  having  several  applications  in  network design. In general cases, the problem is proved as NP (Non-deterministic  Polynomial)  -  hard.  This  paper proposes  an  algorithm  for  solving  MRCST  problem based  on  the  schema  of  TABU  search  algorithm. Experimental  results  show  that  our  proposal algorithm  is  better  than  Wong  algorithm,  many population-based  meta-heuristics  like  Max-Min  Ant System  (MMAS),  Genetic  Algorithm  (GA)  and outperforms  recently  proposed  Artificial  Bee  Colonyalgorithm  (ABC)  both  in  terms  of  solution  quality  as well as running time.

Author Biographies

Phan Tấn Quốc, Khoa Công nghệ Thông tin, Trường Đại học Sài Gòn.

Sinh ngày 12 tháng 10 năm 1971.

Nhận bằng thạc sỹ Tin học, chuyên ngành Khoa học Máy tính tại Trường Đại học Khoa học Tự nhiên – Đại học Quốc gia TP.HCM năm 2002, NCS tiến sỹ tại trường Đại học Bách Khoa Hà Nội từ tháng 3/2010 - chuyên ngành Khoa học Máy tính.

Hiện công tác tại Bộ môn Khoa học Máy tính, Khoa Công nghệ Thông tin, Trường Đại học Sài Gòn.

Lĩnh vực nghiên cứu: Thuật toán gần đúng.

Điện thoại: 0918 178 052

E-mail:quocpt@sgu.edu.vn

Nguyễn Đức Nghĩa, Viện Công nghệ Thông tin và Truyền thông, Trường Đại học Bách khoa Hà Nội.

Sinh ngày: 02 tháng 06 năm 1954.

Nhận bằng Tiến sỹ tại Trường Đại học Tổng hợp Quốc gia Bạch Nga. Hiện là Phó Giáo Sư, giảng viên cao cấp tại Bộ môn Khoa học Máy tính, Viện Công nghệ Thông tin và Truyền thông, Trường Đại học Bách khoa Hà Nội.

Lĩnh vực nghiên cứu: Tối ưu hóa tổ hợp và toàn cục, đồ thị, thiết kế và phân tích thuật toán, các thuật toán gần đúng, tính toán song song.

E-mail: nghiand@soict. hut.edu.vn

Published
2014-09-12
Section
Bài báo