Notice: Function _load_textdomain_just_in_time was called incorrectly. Translation loading for the ad-inserter domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /www/wwwroot/hdd-vatly/re_mysql.top1index-top1list.com/wp-includes/functions.php on line 6131
Notice: Function _load_textdomain_just_in_time was called incorrectly. Translation loading for the rehub-framework domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /www/wwwroot/hdd-vatly/re_mysql.top1index-top1list.com/wp-includes/functions.php on line 6131
Notice: Trying to get property 'post_type' of non-object in /www/wwwroot/hdd-vatly/re_mysql.top1index-top1list.com/wp-content/mu-plugins/post-media-only.php on line 74 [👨💻🇻🇳] Cải tiến dùng Index Priority Queue - top1brand Notice: Trying to get property 'post_type' of non-object in /www/wwwroot/hdd-vatly/re_mysql.top1index-top1list.com/wp-content/mu-plugins/post-media-only.php on line 74
Notice: Trying to get property 'post_type' of non-object in /www/wwwroot/hdd-vatly/re_mysql.top1index-top1list.com/wp-content/mu-plugins/post-media-only.php on line 74
Notice: Trying to get property 'post_type' of non-object in /www/wwwroot/hdd-vatly/re_mysql.top1index-top1list.com/wp-content/mu-plugins/post-media-only.php on line 74
Notice: Trying to get property 'post_type' of non-object in /www/wwwroot/hdd-vatly/re_mysql.top1index-top1list.com/wp-content/mu-plugins/post-media-only.php on line 74
SaveSavedRemoved0
Notice: Trying to get property 'post_type' of non-object in /www/wwwroot/hdd-vatly/re_mysql.top1index-top1list.com/wp-content/mu-plugins/post-media-only.php on line 74
Notice: Trying to get property 'post_type' of non-object in /www/wwwroot/hdd-vatly/re_mysql.top1index-top1list.com/wp-content/mu-plugins/post-media-only.php on line 74
class="post-inner post post-301488 type-post status-publish format-standard has-post-thumbnail hentry category-top1dev-no1dev category-top1index-top1list-top1world category-top1labs-no1labs category-top1vietnam-no1vietnam tag-no1dev tag-no1labs tag-top1dev tag-top1labs tag-cai tag-dung tag-index tag-no1vietnam tag-priority tag-queue tag-tien tag-top1index tag-top1list tag-top1vietnam" id="post-301488">
Ở phần trước Thuật toán Prim: Cài đặt thuật toán chúng ta đã tìm hiểu qua cách cài đặt thuật toán Prim dựa vào Priority Queue. Tuy nhiên, có một nhược điểm là phải duyệt các cạnh không hợp lệ trong queue. Do vậy, trong bài này chúng ta sẽ tối ưu cách cài đặt thuật toán Prim ở bài trước bằng cách sử dụng Index Priority Queue.
Ở phiên bản trước, chúng ta lấy ra cạnh nhỏ nhất bằng Min Priority Queue. Tất cả các cạnh được đẩy vào Priority Queue để rồi sau đó sẽ phải xử lý những cạnh thừa. Trong bước tối ưu này, Index Priority Queue sẽ chỉ chứa cạnh tối ưu nhất ở đỉnh đích, nếu có cạnh nào tối ưu hơn cạnh đó thì cập nhật trực tiếp vào queue. Do đó sẽ không phải xử lý cạnh thừa nữa.
Các bước của thuật toán như sau:
Bước 1: Chọn một đỉnh v bất kỳ làm đỉnh bắt đầu và đưa đỉnh v vào cây khung.
Bước 2: Thêm tất cả các cạnh nối với v vào danh sách cạnh đang xét .
Bước 3: Xét các cạnh trong danh sách đến khi hết:
Bước 3.1: Lấy ra cạnh có trọng số nhỏ nhất nối từ v1 đến một đỉnh v2 chưa nằm trong cây khung. Đưa cạnh này và đỉnh v2 vào cây khung.
Bước 3.2: Trong các đỉnh kề của v2, nếu có đỉnh nào đã nằm trong danh sách đang xét mà có trọng số nhỏ hơn thì thay thế cạnh tương ứng đỉnh đó trong danh sách đang xét bằng cạnh này. Nếu chưa nằm trong cây khung thì đưa vào danh sách cạnh đang xét.
Ở bước lấy ra cạnh có trọng số nhỏ nhất trong số các cạnh đang xét, chúng ta sử dụng Index Min-PriorityQueue để lấy ra cạnh có trọng số nhỏ nhất và thay thế cạnh ở bước 3.2.
Cùng chạy thuật toán với đồ thị $G$ bên dưới:
Đồ thị $G$
Chọn đỉnh $0$ làm đỉnh bắt đầu, đưa đỉnh này vào cây khung (màu xanh). Đưa các cạnh 0-1, 0-2, 0-3 vào danh sách cạnh đang xét (màu cam). Ta thấy cạnh 0-2 là cạnh có trọng số nhỏ nhất.
Đưa cạnh 0-2 và đỉnh $2$ vào cây khung. Đưa các cạnh 2-4 và 2-5 vào danh sách đang xét. Lúc này ta thấy cạnh 2-4 có trọng số nhỏ nhất.
Đưa cạnh 2-4 và đỉnh $4$ vào cây khung. Đưa các cạnh 4-1 và 4-6 vào danh sách đang xét. Cạnh 4-1 có trọng số nhỏ hơn cạnh 0-1 nên sẽ thay thế cạnh này. Lúc này ta thấy cạnh 4-1 có trọng số nhỏ nhất.
Đưa cạnh 4-1 và đỉnh $1$ vào cây khung. Các đỉnh nối từ $1$ là $0$ và $4$ đều đã nằm trong cây khung nên chúng ta sẽ không đưa các cạnh nối các đỉnh này vào danh sách đang xét. Lúc này, ta xét các cạnh còn lại và thấy cạnh 2-5 có trọng số nhỏ nhất.
Đưa cạnh 2-5 và đỉnh $5$ vào cây khung. Tiếp tục xét ba cạnh 5-3, 5-6 và 5-7. Cạnh 5-3 có trọng số lớn hơn cạnh 0-3 trong danh sách đang xét nên sẽ không được đưa vào. Cạnh 5-6 có trọng số nhỏ hơn cạnh 4-6 trong danh sách nên sẽ thay thế cho cạnh này. Cạnh 5-7 có đỉnh $7$ chưa có trong danh sách nên sẽ được đưa vào danh sách đang xét. Trong danh sách đang xét lúc này, cạnh 5-6 có trọng số nhỏ nhất.
Đưa cạnh 5-6 và đỉnh $6$ vào cây khung. Tiếp tục xét cạnh 6-4, 6-7 và 6-8, không đưa cạnh 6-4 vì đỉnh $4$ đã nằm trong cây khung. Cạnh 6-7 có trọng số nhỏ hơn cạnh 5-7 trong danh sách đang xét nên sẽ thay thế cho cạnh này. Cạnh 6-8 với đỉnh $8$ chưa nằm trong danh sách đang xét nên sẽ được đưa vào danh sách đang xét. Cạnh 6-8 lúc này có trọng số nhỏ nhất.
Đưa cạnh 6-8 và đỉnh $8$ vào cây khung. Cạnh 8-7 có trọng số lớn hơn cạnh 6-7 nên sẽ không được đưa vào danh sách đang xét. Lúc này danh sách có cạnh 6-7 có trọng số nhỏ nhất.
Đưa cạnh 6-7 và đỉnh $7$ vào cây khung. Không có cạnh nào được đưa tiếp vào danh sách đang xét vì các đỉnh kề của $7$ đều đã nằm trong cây khung. Chỉ còn cạnh 0-3 là cạnh có trọng số nhỏ nhất.
Đưa cạnh 0-3 vào cây khung. Các đỉnh kề của đỉnh $3$ đều nằm trong cây khung.
Danh sách lúc này rỗng. Thuật toán kết thúc.
Để hiện thực thuật toán Prim, chúng ta sẽ sử dụng cấu trúc đồ thị vô hướng có trọng số EdgeWeightedGraph ở bài viết Tổng quan về đồ thị. Interface PrimMST ở bài viết Thuật toán Prim: Cài đặt thuật toán và cấu trúc IndexPQ ở bài viết Index Priority Queue.
Trước hết chúng ta tạo class EagerPrimMST hiện thực interface PrimMST và cài đặt một hàm constructor nhận EdgeWeightedGraph làm tham số đầu vào.
public class EagerPrimMST implements PrimMST {
public EagerPrimMST(EdgeWeightedGraph G) {
// to be implemented
}
@Override
public Iterable<Edge> edges() {
// to be implemented
}
@Override
public double weight() {
// to be implemented
}
}
Bên trong EagerPrimMST là các field sử dụng để tìm cây khung nhỏ nhất.
marked: Mảng boolean đánh dấu một đỉnh đã được đưa vào cây khung hay chưa.
edgeTo: Tham chiếu của cạnh tối ưu nhất đến một đỉnh.
distTo: Khoảng cách tối ưu nhất đến một đỉnh.
pq: Danh sách các cạnh dùng để xét sau mỗi bước chạy thuật toán. Sử dụng IndexPQ cho thao tác lấy ra cạnh nhỏ nhất và thay thế cạnh.
Thuật toán được hiện thực ở contructor như sau:
public EagerPrimMST(EdgeWeightedGraph G) {
// initialization
edgeTo = new Edge[G.V()];
distTo = new double[G.V()];
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
pq = new IndexPQ<Double>(G.V(), Comparator.naturalOrder());
// init pq with 0 to start at vertex 0
distTo[0] = 0.0;
pq.insert(0, 0.0);
while (!pq.isEmpty())
visit(G, pq.removePeek());
}
private void visit(EdgeWeightedGraph G, int v) {
marked[v] = true;
for (Edge e : G.adj(v)) {
int w = e.other(v);
if (marked[w]) continue;
if (e.weight() < distTo[w]) { // Edge e is new best connection from tree to w.
edgeTo[w] = e;
distTo[w] = e.weight();
if (pq.contains(w))
pq.change(w, distTo[w]);
else
pq.insert(w, distTo[w]);
}
}
}
Cài đặt các phương thức còn lại.
@Override
public Iterable<Edge> edges() {
ArrayList<Edge> mst = new ArrayList<>();
for (int i = 1; i < edgeTo.length; i++) {
mst.add(edgeTo[i]);
}
return mst;
}
@Override
public double weight() {
return Arrays.stream(distTo).sum();
}
Notice: Trying to get property 'post_type' of non-object in /www/wwwroot/hdd-vatly/re_mysql.top1index-top1list.com/wp-content/mu-plugins/post-media-only.php on line 74