Thư viện tài liệu, ebook tham khảo dành cho học sinh, sinh viên

Algorithm 1: Thuật toán Gale-Shapley Khởi tạo mọi chàng trai m 2 M và mọi cô gái w 2 W là độc thân; while có một chàng trai m độc thân và vẫn chưa đính hôn với cô gái nào do Chọn chàng trai m này; Xét w là cô gái m thích nhất trong danh sách những cô mà m chưa đề nghị cưới; if w là độc thân then (m; w) đính hôn; else /* w hiện tại đang đính ...

3 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 895 | Lượt tải: 0

Input: • Dòng đầu tiên là số đỉnh n < 100 và số cạnh m của đồ thị G. • m dòng tiếp theo mỗi dòng gồm 3 số x y w thể hiện: Đồ thị G có cạnh fx, yg với trọng số w. • dòng tiếp theo chứa bốn số a b c d là đỉnh bắt đầu và kết thúc của hai robot. • dòng cuối cùng là số r > 0. Output: Bao gồm nhiều dòng, mỗi dòng là hai số u v thể hiện các đỉnh mà ...

6 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 1020 | Lượt tải: 0

B. Vẫn từ tập dữ liệu sgb-words, ta xây dựng đồ thị có hướng D với tập đỉnh là “ mọi từ trong sgb-words”, và một từ u có cung nối với một từ v khác nếu bốn chữ cuối của u xuất hiện trong v (tính cả số lần xuất hiện). Đồ thị có hướng D có 94, 084 cung và 5757 đỉnh. Đường đi có hướng ngắn nhất từ words tới graph là words ! dross ! soars ! orcas ...

1 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 872 | Lượt tải: 0

Ví dụ: Dữ liệu vào Dữ liệu ra 4 5 1 2 2 3 3 4 4 1 1 5 graph dothi { 5 [fillcolor=red, style=filled]; 4 [fillcolor=red, style=filled]; 1 [fillcolor=green, style=filled]; 3 [fillcolor=green, style=filled]; 2 [fillcolor=red, style=filled]; 1 -- 2; 2 -- 3; 3 -- 4; 4 -- 1; 1 -- 5; } Với dữ liệu ra dothitomau.dot, ta biên dịch với ch...

2 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 1015 | Lượt tải: 0

Dòng đầu tiên thể hiện số cạnh của cây; mỗi dòng tiếp theo thể hiện một cạnh của cây. Với dữ liệu này, chương trình nên output ra mã Prufer: 6 0 2 6 2 9 9 2 Test chương trình: Để test chương trình của mình, bạn có thể sử dụng mã nguồn sinh cây gán nhãn ngẫu nhiên từ mã Prufer (trong thư mục PruferCodes); và sử dụng cây này như Input của chương...

1 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 1282 | Lượt tải: 0

Tìm đường tăng function FoundIncPath: boolean; var dq, cq, v, w: integer; begin fillchar(q,sizeof(q),0); dq:=1; cq:=1; queue[dq]:=u; q[u]:=u; while dq<=cq do begin v:=queue[dq]; inc(dq); if v<=n then begin for w:=n+1 to n2 do if (f[v]+f[w]=c(v,w-n)) and (q[w]=0) then begin inc(cq); queue[cq]:=w; q[w]:=v; end; end else if...

43 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 690 | Lượt tải: 0

Đường tăng ngắn nhất: Các kết quả Bổ đề 1. Trong suốt thuật toán, độ dài đường tăng ngắn nhất không khi nào bị giảm. Bổ đề 2. Sau nhiều nhất m đường tăng ngắn nhất, độ dài đường tăng ngắn nhất sẽ tăng ngặt. Định lý. Thuật toán đường tăng luồng ngắn nhất đòi hỏi thời gian tính O(m2n). O(m+n) thời gian để tìm đường ngắn nhất nhờ sử dụng BFS. O(...

83 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 971 | Lượt tải: 0

Bài toán Cho đồ thị G = (V, E), với trọng số trên cạnh e là w(e), đối với mỗi cặp đỉnh u, v trong V, tìm đường đi ngắn nhất từ u đến v. Đầu vào: ma trận trọng số. Đầu ra ma trận: phần tử ở dòng u cột v là độ dài đường đi ngắn nhất từ u đến v. Cho phép có trọng số âm Giả thiết: Đồ thị không có chu trình âm.

78 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 1087 | Lượt tải: 0

Mô tả thuật toán Prim procedure Prim(G, c) begin Chọn đỉnh tuỳ ý r V; Khởi tạo cây T=(V(T), E(T)) với V(T)={ r }và E(T)=; while T có < n đỉnh do begin Gọi (u, v) là cạnh nhẹ nhất với u  V(T) và vV(G) – V(T) E(T)  E(T)  { (u, v) }; V(T)  V(T)  { v } end end; Tính đúng đắn suy từ hệ quả đã chứng minh: Giả sử A là tập co...

60 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 951 | Lượt tải: 0

Finding Sweden Tour The Concorde solver can accept as an input parameter the value of the best known tour for a TSP instance if one is available.  As a full (exact) TSP solver, Concorde is designed to find optimal solutions regardless of the quality of the estimate, but knowledge of a good tour allows for better tuning of parameters that are set i...

93 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 816 | Lượt tải: 0