Tài liệu Toán Học

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: 585 | 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: 409 | 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: 610 | 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: 708 | 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: 531 | 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: 494 | Lượt tải: 0

Hàm nhận biết ứng cử viên int UCVh(int j, int k) { // UCVh nhận giá trị 1 // khi và chỉ khi j  Sk int i; for (i=1; i

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

Cỏc số Ramsey Xét một cách tô màu (tuỳ ý) các cạnh của K7. Rõ ràng hoặc là tìm đợc ít nhất một cạnh của K7 đợc tô màu đỏ, hoặc là tất cả các cạnh của nó đều đợc tô bởi màu xanh. Nếu có cạnh tô màu đỏ thì rõ ràng ta có K2 đỏ. Còn nếu tất cả các cạnh đều tô bởi màu xanh thì ta có K7 xanh. Vậy số 7 có tính chất (2,7)-Ramsey, và vì thế R(2,7) ? 7. Nh...

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

Cỏc số Ramsey Từ phân tích ở trên ta thấy 6 có tính chất (3,3)-Ramsey, và mọi số n<6 đều không có tính chất này. Vậy 6 là số nhỏ nhất có tính chất (3,3)-Ramsey. Định nghĩa 3. Số Ramsey R(i,j) là số nguyên dơng nhỏ nhất có tính chất (i,j)-Ramsey. Chẳng hạn, từ kết quả vừa trình bày ở trên, ta có R(3,3) = 6. Ví dụ. Tìm R(2,7) - số nguyên dơng n...

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

LiNoReCoCo Example Find all solutions to an = 3an−1+2n. Which solution has a1 = 3? Notice this is a 1-LiNoReCoCo. Its associated 1-LiHoReCoCo is an = 3an−1, whose solutions are all of the form an = α3n. Thus the solutions to the original problem are all of the form an = p(n) + α3n. So, all we need to do is find one p(n) that works. If the extr...

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