1
THUẬT TOÁN SONG SONG
CHO MỘT SỐ BÀI TOÁN
TRÊN ĐỒ THỊ
2
Nội dung

Đại cương về tính toán song song

Một số thuật toán song song cơ bản trên đồ thị

Thuật toán song song giải bài toán K-Median

Thiết kế chương trình
3
Đại cương về tính toán song song

Một số khái niệm và thuật ngữ

Phân loại các kiến trúc song song

Đánh giá độ phức tạp của thuật toán song
song

Một số mẫu thiết kế thuật toán song song
4
Một số khái niệm và thuật ngữ

Tính toán song song hay xử lý song song : là quá trình xử lý
thông tin trong đó nhấn mạnh việc nhiều đơn vị dữ liệu được xử lý
đồng thời bởi một hay nhiều bộ xử lý để giải quyết một bài toán


MIMD (multiple instruction stream, multiple data stream)

Hệ đa xử lý với bộ nhớ phân tán

Hệ đa xử lý dùng chung bộ nhớ

Hệ đa xử lý với bộ nhớ dùng chung phân tán
6
Đánh giá độ phức tạp

Song song giới hạn và song song không
giới hạn

Các kỹ thuật cho việc nâng cao hiệu quả
của thuật toán song song

Giảm số lượng bộ xử lý

Giảm độ phức tạp thuật toán

Độ phức tạp của bài toán
7
Một số mẫu thiết kế thuật toán
song song

Mẫu cây nhị phân

Phát triển bởi nhân
đôi

Chỉ số ngăn cách :

Chỉ số lan truyền :

c là tâm của cây khi s(c) là tối
thiểu

m là median của cây khi t(m) là
tối thiểu

Ý tưởng : sử dụng thuật toán
song song tìm tổ tiên chung gần
nhất NCA(i, j).
d(i,j) = level(i) + level(j) - 2
×

level(NCA(i,j))
{ }
njjidis ,...2,1|),(max)(
==
∑
≤≤
=
nj
jidit
1
),()(
11
Tìm kiếm theo chiều rộng
12

14
Giới thiệu bài toán

Khởi nguồn từ thế kỷ 17, Fermat đưa ra một câu hỏi : Cho
một tam giác (với 3 đỉnh trên mặt phẳng), hãy tìm một điểm ( median)
trong mặt phẳng sao cho tối thiểu hóa tổng khoảng cách từ nó tới các
đỉnh.

Đầu thế kỷ 20, Alfred Weber tổng quát hóa : đưa thêm trọng
số vào đỉnh, số đỉnh n
≥
3, số median k
≥
1

Đầu năm 1960, Hakimi phát triển bài toán tìm k median trên
một đồ thị gồm n đỉnh. Phân ra làm 3 lớp bài toán : K-
median đơn thuần, UFLP , QAP.

Bài toán K-median trên đồ thị tổng quát là NP-khó.
15
Ví dụ minh họa

Có hai vị trí để đặt trạm
phục vụ. Trạm nào sẽ được
đặt :

Chúng ta muốn tối thiểu
hoá tổng khoảng cách từ
các trạm còn lại tới hai

ii
i
ij
nji
k
nj
ξ
ξξ
ξ
ξ
Với điều kiện
18
Các phương pháp đã giải quyết
19
Thuật toán nhánh cận
1. Khởi tạo : Tập hoạt động (tập các bài toán con chưa được duyệt) chứa bài toán ban
đầu, giá trị kỷ lục bằng ∞.
2. Lựa chọn : Lựa chọn và xoá một bài toán con khả thi từ tập hoạt động.
3. Phân nhánh :
i. Phân nhánh để sinh ra các bài toán con mới từ bài toán đang xét. Tính cận của các bài toán
con mới này.
ii. Kiểm tra các bài toán con vừa được sinh ra. Có hai trường hợp : (1) bài toán con đã được
giải quyết – đi tới bước 5, (2) bài toán con chưa được giải quyết – đi tới bước 4.
4. Cập nhật tập hoạt động : Đưa các bài toán con có cận nhỏ hơn kỷ lục tạm thời vào
tập hoạt động.
5. Cập nhật kỷ lục :
1. Nếu giá trị của bài toán con nhỏ hơn kỷ lục và khi đó nó sẽ thay thế kỷ lục. Ngược lại sẽ bị
xóa
2. Khi cập nhật kỷ lục mới (5i) thì tất cả các bài toán con trong tập hoạt động có cận dưới lớn
hơn hoặc bằng kỷ lục sẽ bị xóa