Bài toán tìm bộ ghép cực đại trên đồ thị ứng dụng giải một số bài toán trong thực tế

Bài toán tìm bộ ghép cực đại trên đồ thị ứng dụng giải một số bài toán trong thực tế Bài toán tìm bộ ghép cực đại trên đồ thị ứng dụng giải một số bài toán trong thực tế Bài toán tìm bộ ghép cực đại trên đồ thị ứng dụng giải một số bài toán trong thực tế Bài toán tìm bộ ghép cực đại trên đồ thị ứng dụng giải một số bài toán trong thực tế

CƠ SỞ LÝ THUYẾT VỀ ĐỒ THỊ VÀ ĐỘ PHỨC TẠP THUẬT TOÁN

CÁC KHÁI NIỆM CƠ BẢN

Phần này được tham khảo trong các tài liệu [2], [3], [5], [9]

1.1.1 Khái niệm đồ thị Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó Đồ thị được ký hiệu là G = (V, E), trong đó V là tập đỉnh và E là tập cạnh Có thể coi E là tập các cặp(u,v) với u và v là hai đỉnh của V

Một số hình ảnh của đồ thị

Sơ đồ giao thông Mạng máy tính

Hình 1: Ví dụ về mô hình đồ thị

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Có thể phân loại đồ thị theo đặc tính và số lượng của tập các cạnh E:

Cho đồ thị G = (V, E) Định nghĩa 1:

Một đơn đồ thị vô hướng là một bộ G = , trong đó:

- V ≠  là tập hợp hữu hạn gồm các đỉnh của đồ thị

- E là tập hợp các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh

Theo định nghĩa, trong một đồ thị đơn, không thể tồn tại các cặp cạnh nối cùng một cặp đỉnh vì tập hợp E không cho phép các cặp trùng nhau Các cạnh trong đồ thị không phân biệt thứ tự, do đó cạnh [u,v] và cạnh [v,u] được xem là một cạnh duy nhất, phù hợp với việc biểu diễn các con đường hai chiều Ngoài ra, không có cặp [u,u] nào trong tập hợp E.

Đồ thị vô hướng có thể được phân loại thành đơn đồ thị và không phải đơn đồ thị Đơn đồ thị là loại đồ thị không có cặp cạnh nối cùng một cặp đỉnh, trong khi đó, đồ thị không phải đơn có thể có các cặp cạnh nối giữa các đỉnh giống nhau hoặc có cạnh nối một đỉnh với chính nó.

Hình 2: Đơn đồ thị vô hướng và không phải đơn đồ thị vô hướng

Trong thực tế, hệ thống giao thông có thể có nhiều con đường nối hai địa điểm hoặc một con đường quay lại chính nó, như trong trường hợp con đường nội bộ của trung tâm mua sắm Do đó, định nghĩa về đồ thị vô hướng không đủ để biểu diễn các tình huống này Để mô tả chính xác hơn, cần sử dụng đa đồ thị vô hướng, được định nghĩa là một bộ G = .

- E là một họ các cặp không có thứ tự của V gọi là các cạnh

- Khi ta nói E là một họ nghĩa là nó có thể có những cặp trùng nhau (khác với khái niệm tập hợp)

- Các cạnh nối cùng một cặp đỉnh được gọi là các cạnh song song

- Các cạnh nối từ một đỉnh với chính nó được gọi là khuyên

Ví dụ a) Đa đồ thị vô hướng: e1 và e2 là các cạnh song song b) Đa đồ thị vô hướng: e là khuyên

Hình 3: Đa đồ thị vô hướng e1 e2 e

Đồ thị có hướng và đồ thị không có hướng đều có đặc điểm chung là tính chất vô hướng của các cạnh Tuy nhiên, trong một số trường hợp, tính có hướng của các cạnh lại rất quan trọng, chẳng hạn như trong việc biểu diễn các con đường một chiều Do đó, chúng ta có thể phân loại đồ thị thành đơn đồ thị có hướng và đa đồ thị có hướng Hai loại đồ thị này tương tự như các loại đã được định nghĩa trước đó, với điểm khác biệt chính là tính chất có thứ tự của các cạnh Định nghĩa 3: Đơn đồ thị có hướng là một bộ G = , trong đó

- E là tập hợp các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung

Đơn đồ thị có hướng là loại đồ thị mà mỗi cạnh chỉ có một chiều Ngược lại, nếu đồ thị có các cặp cung nối cùng một cặp đỉnh, thì nó không phải là đơn đồ thị có hướng Thêm vào đó, nếu có cung nối một đỉnh với chính nó, đồ thị cũng không được coi là đơn đồ thị có hướng.

Hình 4: Đơn đồ thị có hướng và không phải đơn đồ thị có hướng Định nghĩa 4: Đa đồ thị có hướng là một bộ G = , trong đó

- E là một họ các cặp có thứ tự của V gọi là các cung

Các cung nối cùng một cặp đỉnh được gọi là các cung song song

Ví dụ a) Đa đồ thị có hướng: e1 và e2 là các cung song song b) Đa đồ thị có hướng: e là khuyên

Hình 5: Đa đồ thị có hướng Định nghĩa 5:

Một giả đồ thị G = (V, E) gồm một tập các đỉnh V, một tập các cạnh E và một hàm f từ E tới {{u,v} | u, v  V } Một cạnh là một khuyên nếu f(e) {u} với một đỉnh u nào đó

Một số thuật ngữ cơ bản

+ Cho đồ thị vô hướng G =

- Hai đỉnh u và v của đồ thị được gọi là kề nhau nếu (u,v) là một cạnh của đồ thị

Cạnh e = (u,v) trong đồ thị liên kết hai đỉnh u và v, được gọi là đỉnh đầu của cạnh e Cạnh này thể hiện mối quan hệ giữa hai đỉnh, với u và v là các đỉnh mà cạnh e nối kết.

+ Cho đồ thị vô hướng G = Bậc của đỉnh v trong đồ thị, ký hiệu là e2 e1 e

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn, trong lý thuyết đồ thị, deg(v) là số cạnh liên kết với đỉnh v Đỉnh có bậc 0 được gọi là đỉnh cô lập, trong khi đỉnh có bậc 1 được gọi là đỉnh treo.

Cho đồ thị vô hướng G = sau:

Hình 6: Đơn đồ thị vô hướng

- Đỉnh 6 là đỉnh cô lập

Trong đồ thị vô hướng G = , tổng số bậc của các đỉnh luôn bằng hai lần số cạnh của đồ thị Điều này có nghĩa là tổng bậc của các đỉnh phản ánh số lượng cạnh của đồ thị một cách chính xác.

-Trong đồ thị vô hướng, số đỉnh bậc lẻ là một số chẵn

+ Cho đồ thị có hướng G =

- Hai đỉnh u và v của đồ thị được gọi là kề nhau nếu (u,v) là một cung của đồ thị

Trong lý thuyết đồ thị, nếu e=(u,v) là một cung, thì cung này đi ra từ đỉnh u và đi vào đỉnh v Đỉnh u được gọi là đỉnh đầu của cung e, trong khi đỉnh v được gọi là đỉnh cuối của cung e.

+ Cho đồ thị có hướng G=

- Bán bậc ra của đỉnh v trong đồ thị, ký hiệu là deg + (v), là số cạnh đi ra khỏi v

- Bán bậc vào của đỉnh v trong đồ thị, ký hiệu là deg - (v), là số cạnh vào v

Xét đồ thị có hướng G = sau:

Hình 7: Đồ thị có hướng

- Bán bậc ra: deg + (1)=2 deg + (2)=2 deg + (3)=1 deg + (4)=1 deg + (5)=2 deg + (6)=2

- Bán bậc vào: deg - (1)=1 deg - (2)=2 deg - (3)=2 deg - (4)=2 deg - (1)=2 deg - (1)=1

Tương tự như đồ thị vô hướng, đối với đồ thị có hướng ta cũng có kết quả gần tương tự về bậc của các đỉnh của đồ thị

+ Cho G = là đồ thị có hướng Tổng bán bậc ra của các đỉnh bằng tổng bán bậc vào của các đỉnh và bằng số cạnh của đồ thị

+ Đồ thị vô hướng G = được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó

Lý thuyết đồ thị có ứng dụng rộng rãi trong nhiều lĩnh vực, nhưng để sử dụng hiệu quả trên máy tính, cần có cách biểu diễn và xử lý đồ thị phù hợp Việc sử dụng hình vẽ và mô tả tập hợp không còn hiệu quả cho lưu trữ và xử lý dữ liệu Do đó, việc tìm kiếm một cấu trúc dữ liệu thích hợp để biểu diễn đồ thị trên máy tính là điều cần thiết.

Có nhiều phương pháp để biểu diễn đồ thị trên máy tính, và trong bài viết này, chúng ta sẽ khám phá một số phương pháp phổ biến Một trong những phương pháp đó là danh sách cạnh, cho phép lưu trữ thông tin về các cạnh của đồ thị một cách hiệu quả.

Khi đồ thị có n đỉnh và m cạnh, ta có thể sử dụng danh sách cạnh để biểu diễn đồ thị Phương pháp này liệt kê tất cả các cạnh của đồ thị trong một danh sách, trong đó mỗi phần tử đại diện cho một cặp.

Cặp (u, v) đại diện cho một cạnh trong đồ thị, trong đó nếu đồ thị có hướng, (u, v) sẽ tương ứng với một cung, với u là đỉnh đầu và v là đỉnh cuối Danh sách các cạnh này được lưu trữ trong bộ nhớ dưới dạng mảng hoặc danh sách liên kết.

Ví dụ với đồ thị dưới đây:

Cài đặt trên danh sách móc nối:

Hình 8: Ví dụ biểu diễn đồ thị danh sách cạnh Ưu điểm của danh sách cạnh:

Trong đồ thị thưa, với số cạnh ít (m < 6n), việc sử dụng danh sách cạnh sẽ tiết kiệm không gian lưu trữ, vì chỉ cần 2m ô nhớ để lưu trữ danh sách này.

• Trong một số trường hợp, ta phải xét tất cả các cạnh của đồ thị thì

ĐỘ PHỨC TẠP TÍNH TOÁN VÀ TÍNH HIỆU QUẢ CỦA THUẬT TOÁN

Thuật toán là một chuỗi các bước hữu hạn, trong đó mỗi bước xác định rõ ràng các phép toán hoặc hành động cần thực hiện nhằm giải quyết một bài toán cụ thể.

An operation, also known as a task, command, or instruction, refers to an action that must be executed by the algorithm's execution mechanism.

Mỗi thao tác trong quá trình giải bài toán chuyển đổi từ trạng thái nhập sang trạng thái xuất, thường sử dụng các đối tượng trong trạng thái nhập và tạo ra các đối tượng mới trong trạng thái xuất Quan hệ giữa các đối tượng này là yếu tố quan trọng trong việc hiểu và thực hiện các thao tác biến đổi.

Thuật toán hoạt động thông qua hai trạng thái xuất và nhập, phản ánh tác động của các thao tác Dãy thao tác liên tiếp nhằm chuyển đổi bài toán từ trạng thái ban đầu đến trạng thái kết quả, bao gồm các thao tác e1, e6, e4, e3, e2 và e7.

Mỗi thao tác có thể được phân tích thành các thao tác đơn giản hơn, và trình tự thực hiện các thao tác này cần phải được xác định rõ ràng trong thuật toán Việc sắp xếp cùng một tập hợp thao tác theo các trình tự khác nhau sẽ dẫn đến những kết quả khác nhau.

1.2.2 Phân tích độ phức tạp của thuật toán

Khi giải một bài toán, có nhiều giải thuật khác nhau có thể được áp dụng, tuy nhiên, việc đánh giá và lựa chọn giải thuật tốt nhất là rất quan trọng Thông thường, người ta dựa vào các tiêu chí cụ thể để thực hiện đánh giá này.

- Tiêu chuẩn về tính đúng đắn của thuật toán, thuật toán có cho lời giải đúng của bài toán hay không ?

Tiêu chuẩn về tính đơn giản của thuật toán là rất quan trọng, đặc biệt đối với những thuật toán chỉ sử dụng một vài lần Chúng ta thường mong muốn có những thuật toán dễ hiểu và dễ lập trình, vì công sức và thời gian để xây dựng chúng thường lớn hơn nhiều so với thời gian thực hiện.

Tiêu chuẩn về thời gian là yếu tố quan trọng trong việc đánh giá hiệu suất của thuật toán Thời gian chạy nhanh giúp tiết kiệm thời gian thực hiện chương trình, đặc biệt khi chương trình được sử dụng nhiều lần hoặc khi xử lý các bài toán có dữ liệu đầu vào lớn Do đó, hiệu suất thời gian trở thành một tiêu chí thiết yếu trong việc phát triển và tối ưu hóa các thuật toán.

Trong phần này ta quan tâm chủ yếu đến độ phức tạp thời gian của thuật toán

Các bước trong quá trình phân tích đánh giá thời gian chạy của thuật toán:

Bước đầu tiên trong việc phân tích thời gian chạy của thuật toán là xác định kích thước dữ liệu đầu vào, điều này sẽ giúp quyết định thuật toán nào là phù hợp để phân tích Thời gian chạy của thuật toán có thể được coi là một hàm phụ thuộc vào kích thước của dữ liệu nhập.

Thời gian thực hiện T của thuật toán phụ thuộc vào kích thước dữ liệu nhập n, được biểu diễn dưới dạng hàm T(n) Thông thường, T(n) được xem là thời gian thực hiện trong trường hợp xấu nhất cho dữ liệu có kích thước n, tức là thời gian tối đa cần thiết để thực hiện chương trình với mọi dữ liệu có cùng kích thước n.

Bước thứ hai trong phân tích thời gian chạy của thuật toán là tách biệt các thao tác trừu tượng để phân tích độc lập với cài đặt Tốc độ xử lý của máy tính và các bộ dịch ngôn ngữ lập trình cao cấp ảnh hưởng đến thời gian chạy, nhưng không đồng đều giữa các loại máy Ví dụ, cần phân biệt số phép toán so sánh trong thuật toán sắp xếp với thời gian chạy trên một máy tính cụ thể Yếu tố đầu tiên được xác định bởi tính chất của thuật toán, trong khi yếu tố thứ hai phụ thuộc vào tính năng của máy tính Do đó, T(n) không thể biểu diễn bằng giây hay phút, mà nên được thể hiện qua số lượng chỉ thị trong thuật toán.

Tối ưu thuật toán là quá trình cải tiến các sửa đổi nhằm tạo ra phiên bản chạy nhanh hơn Nguyên lý chính trong việc tối ưu là nguyên lý Profile, tức là tìm ra điểm gây tốn thời gian nhất trong thuật toán Một số kỹ thuật phổ biến được sử dụng để tối ưu hóa thuật toán bao gồm phân tích hiệu suất và tối ưu mã nguồn.

Kỹ thuật tối ưu hóa vòng lặp và rẽ nhánh là yếu tố quan trọng hàng đầu trong việc cải tiến thuật toán, vì vòng lặp thường làm tăng độ phức tạp Tập trung vào việc cải thiện các khía cạnh này sẽ giúp nâng cao hiệu suất của thuật toán.

- Cố gắng giảm các vòng lặp lồng nhau

- Tăng số lệnh thực hiện trong một bước lặp để giảm số lượng các bước lặp

- Tách các lệnh không phụ thuộc vào chỉ số lặp ra khỏi vòng lặp.

BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ VÀ CÁC THUẬT TOÁN

ĐỒ THỊ HAI PHÍA

Phần này được tham khảo trong các tài liệu [1], [7], [10]

Đồ thị vô hướng G = (V, E) được coi là đồ thị hai phía khi tập hợp các đỉnh V có thể được chia thành hai tập con không rỗng và rời nhau, gọi là X và Y, sao cho mọi cạnh của đồ thị kết nối một đỉnh từ tập X với một đỉnh từ tập Y.

Đồ thị hai phía G được ký hiệu là (X, Y, E), trong đó X là tập các đỉnh trái và Y là tập các đỉnh phải Các đỉnh thuộc tập X được gọi là các X_đỉnh, trong khi các đỉnh thuộc tập Y được gọi là các Y_đỉnh Đồ thị hai phía có cấu trúc đặc biệt và khác biệt so với các loại đồ thị khác.

Để xác định xem một đồ thị liên thông có phải là đồ thị hai phía hay không, chúng ta có thể áp dụng một thuật toán kiểm tra cụ thể Hình 15 minh họa ví dụ về đồ thị hai phía và đồ thị không phải hai phía, giúp người đọc dễ dàng hình dung sự khác biệt giữa chúng.

Với một đỉnh v bất kỳ:

Đồ thị hai phía được xác định qua quá trình X := X ∪ Kề(Y) cho đến khi (X∩Y ≠ ∅) hoặc (X và Y là tối đại) Nếu X∩Y ≠ ∅, thì không phải là đồ thị hai phía; ngược lại, nếu không có giao nhau, đây là đồ thị hai phía với X là tập các đỉnh trái, tức là các đỉnh có thể đến từ v qua một số chẵn cạnh, còn Y là tập các đỉnh phải, tức là các đỉnh có thể đến từ v qua một số lẻ cạnh Đồ thị hai phía xuất hiện trong nhiều mô hình thực tế, chẳng hạn như mối quan hệ hôn nhân giữa nam và nữ, sự lựa chọn trường học của sinh viên, sự phân công tiết dạy của giáo viên trong thời khóa biểu, và bài toán xếp lớp theo học chế tín chỉ.

• một đồ thị là hai phía khi và chỉ khi nó không chứa chu trình lẻ

• kích thước của phủ đỉnh nhỏ nhất bằng kích thước của cặp ghép lớn nhất

• kích thước của tập độc lập lớn nhất cộng kích thước của cặp ghép lớn nhất bằng số đỉnh

• trong đồ thị hai phía liên thông, kích thước của phủ cạnh nhỏ nhất bằng kích thước tập độc lập lớn nhất

• trong đồ thị hai phía liên thông, kích thước của phủ cạnh nhỏ nhất cộng kích thước của phủ đỉnh nhỏ nhất bằng số đỉnh

• một đồ thị là hai phía khi và chỉ khi có thể tô nó bằng hai màu

2.1.2 Các bài toán trên đồ thị hai phía Đồ thị hai phía thường được dùng để mô hình các bài toán ghép cặp

Bài toán matching, chẳng hạn như bài toán phân công công việc, có thể được mô hình hóa bằng đồ thị, trong đó tập đỉnh bao gồm nhóm người P và tập công việc J Trong mô hình này, không phải tất cả mọi người đều phù hợp với mọi công việc, điều này tạo ra sự cần thiết phải tìm kiếm các cặp người và công việc tương thích.

J Nếu người pi có thể làm công việc ji, đồ thị sẽ có một cạnh nối giữa pi và ji Định lý hôn nhân cung cấp một đặc điểm của đồ thị hai phía: tồn tại cặp ghép hoàn hảo (perfect matching) Đồ thị hai phía được sử dụng trong lý thuyết mã hóa (coding theory) hiện đại, đặc biệt khi giải mã các codeword nhận được từ kênh Đồ thị nhân tử (factor graph) và đồ thị Tanner là các ví dụ Đồ thị hai phía được ứng dụng rất nhiều trong thực tế Chính vì vậy có rất nhiều bài toán trên đồ thị hai phía đã được phát biểu Một số các bài toán đó là :

- Bài toán ghép đôi không trọng

- Bài toán tìm bộ ghép cực đại với tổng trọng số cực đại hoặc cực tiểu trên đồ thị hai phía

BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ HAI PHÍA

Phần này được tham khảo trong các tài liệu [6], [7]

2.2.1 Bài toán ghép đôi không trọng và các khái niệm

Đồ thị hai phía G = (X, Y, E) bao gồm hai tập đỉnh X và Y, trong đó X là tập các đỉnh trái và Y là tập các đỉnh phải, với X = {x[1], x[2], , x[m]} và Y = {y[1], y[2], , y[n]} Một bộ ghép của G là tập hợp các cạnh của G không có đỉnh chung, tức là mỗi đỉnh chỉ xuất hiện trong một cạnh duy nhất.

Bài toán ghép đôi là tìm một bộ ghép lớn nhất (nghĩa là có số cạnh lớn nhất) của G

Xét một bộ ghép M của G

• Các đỉnh trong M gọi là các đỉnh đậm, các đỉnh khác là đỉnh nhạt

• Các cạnh trong M gọi là các cạnh đậm, các cạnh khác là cạnh nhạt

Nếu định hướng lại các cạnh của đồ thị thành cung, các cạnh nhạt sẽ được định hướng từ X sang Y, trong khi các cạnh đậm sẽ định hướng từ Y về X Trên đồ thị đã được định hướng, một đường đi xuất phát từ một đỉnh nhạt X được gọi là đường pha (alternating path), và một đường đi từ đỉnh nhạt X tới đỉnh nhạt Y được gọi là đường mở (augmenting path).

Một cách dễ hiểu, có thể quan niệm như sau:

Một đường pha trong đồ thị G là một chuỗi đi đơn bắt đầu từ đỉnh nhạt x_đỉnh, di chuyển qua các cạnh nhạt và đậm theo thứ tự xen kẽ, từ Y đến X và ngược lại.

• Một đường mở là một đường pha Bắt đầu từ một x_đỉnh là đỉnh nhạt kết thúc bằng một Y_đỉnh là đỉnh nhạt

Trong đồ thị hai phía được trình bày trong hình 16, bộ ghép được xác định là M = {(x[l], y[1]), (x[2], y[2])} Các đỉnh x[3] và y[3] là những đỉnh nhạt, trong khi các đỉnh còn lại là đỉnh đậm Đường đi (x[3], y[2], x[2], y[l]) được gọi là đường pha, trong khi đường đi (x[3], y[2], x[2], y[l], x[l], y[3]) được gọi là đường mở.

Hình 16: Đồ thị hai phía

Thuật toán đường mở để tìm một bộ ghép lớn nhất:

Bắt đầu từ một bộ ghép bất kỳ M (thông thường bộ ghép được khỏi gán bằng bộ ghép rỗng hay được tìm bằng thuật toán tham lam)

Nếu bước 2 xác định được đường mở, hãy mở rộng bộ ghép M: Trên đường mở, loại bỏ các cạnh đã ghép (cạnh đậm) khỏi M và thêm vào M những cạnh chưa ghép (cạnh nhạt) Sau đó, tiếp tục lặp lại bước 2.

 Nếu bước 2 không tìm được đường mở thì thuật toán kết thúc

Ví dụ: Như ví dụ trên, với bộ ghép hai cạnh M = {(X1, Y1), (X2, Y2)} và đường mở tìm được gồm các cạnh:

Vậy thì ta sẽ loại đi các cạnh (Y2, X2) và (Y1, X1) trong bộ ghép cũ và thêm vào đó các cạnh (X3,Y2), (X2, Y1), (X1, Y3) được bộ ghép 3 cạnh

2.2.3 Độ phức tạp của thuật toán

Đường mở bắt đầu từ một đỉnh chưa ghép thuộc tập X, đi qua một cạnh chưa ghép sang tập Y, rồi theo một cạnh đã ghép trở về tập X, và kết thúc tại một đỉnh thuộc tập Y chưa ghép Độ dài của đường mở là lẻ và số cạnh thuộc M trên đường mở ít hơn số cạnh không thuộc M một đơn vị Thuật toán tìm kiếm theo chiều rộng (BFS) có thể được sử dụng để tìm đường mở ngắn nhất, giúp giảm bớt công việc trong bước tăng cặp ghép Chi phí thời gian thực hiện thuật toán này trong trường hợp xấu nhất là O(n^3) đối với đồ thị dày và O(n(n+m)logn) đối với đồ thị thưa, trong đó n là số đỉnh và m là số cạnh của đồ thị.

BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI VỚI TỔNG TRỌNG SỐ CỰC ĐẠI HOẶC CỰC TIỂU TRÊN ĐỒ THỊ HAI PHÍA

2.3.1 Bài toán phân công Đây là một dạng bài toán phát biểu như sau: Có m người (đánh số 1, 2, , m) và n công việc (đánh số 1, 2, , n), mỗi người có khả năng thực hiện một số công việc nào đó Để giao cho người i thực hiện công việc j cần một chi

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn yêu cầu phân công công việc cho các thợ, với phí thực hiện c[i, j] ≥ 0 Mục tiêu là đảm bảo mỗi thợ chỉ thực hiện một công việc, nhằm tối đa hóa số lượng công việc có thể hoàn thành.

≥ 2 phương án đều thực hiện được nhiều công việc nhất thì chỉ ra phương án chi phí ít nhất

Dựng đồ thị hai phía G = (X Y, E) với X là tập m người, Y là tập n việc và

(u, v) E với trọng số c[u, v] nếu như người u làm được công việc v Bài toán đưa về tìm bộ ghép nhiều cạnh nhất của G có trọng số nhỏ nhất

Gọi k = max(m, n) Bổ sung vào tập X và Y một số đỉnh giả để |X|=|Y| k

Gọi M là một số dương lớn hơn chi phí của tất cả các phép phân công khả thi Đối với mỗi cặp đỉnh (u, v) với u thuộc tập X và v thuộc tập Y, nếu (u, v) không nằm trong tập E, chúng ta sẽ thêm cạnh (u, v) vào E với trọng số M.

Đồ thị G là một đồ thị hai phía đầy đủ, trong đó giữa mỗi đỉnh của tập X và tập Y đều có cạnh nối Khi tìm được bộ ghép đầy đủ k cạnh với trọng số nhỏ nhất, ta chỉ cần loại bỏ những cạnh có trọng số M vừa thêm vào để có kế hoạch phân công 1 người cho 1 việc Bộ ghép đầy đủ với trọng số nhỏ nhất đồng nghĩa với việc có ít cạnh trọng số M nhất, dẫn đến số phép phân công tối đa Do đó, trong các phương án ghép với ít cạnh trọng số M nhất, phương án này sẽ có tổng chi phí thấp nhất cho các phép phân công.

2.3.2 Thuật toán tìm cặp ghép với tổng trọng số trên các cạnh là lớn nhất hoặc nhỏ nhất

* Thuật toán tìm cặp ghép với tổng trọng số trên các cạnh là lớn nhất:

+ Tạo đồ thị hai phía (X là phía máy có M đỉnh, Y là phía người có N đỉnh)

Có cung (i,j) với trọng số C[i,j] nếu công nhân i làm việc trên máy j tạo lợi nhuận C[ij]

+ Tạo nhãn ban đầu chấp nhận được Fx và Fy theo quy tắc:

Fx[i] = Max( C[i,j], Vj: 1 = 0 Sau khi sửa nhãn cho các đỉnh thuộc dây chuyền “dở dang”, chúng có khả năng kết hợp với các đỉnh j bên Y để tạo ra một dây chuyền hoàn chỉnh mới.

Tăng cặp ghép: Đổi màu các cung, bắt đầu từ cung nhạt cuối cùng của dây chuyền đổi ngược dần về cung nhạt đầu tiên của dây chuyền

Tìm dây chuyền trong đồ thị có thể thực hiện theo hai cách: tìm kiếm theo chiều sâu hoặc chiều rộng Dây chuyền bắt đầu từ một đỉnh nhạt của X và kết thúc tại một đỉnh nhạt của Y, với điều kiện các cung nhạt và đậm phải xen kẽ nhau Đặc biệt, cung đầu và cung cuối đều nhạt, do đó số lượng cung nhạt sẽ nhiều hơn số cung đậm một đơn vị.

Để giải bài toán tìm tổng nhỏ nhất, ta cần đổi dấu C[i,j] và sau đó đổi dấu tổng Hoặc có thể khởi trị C[i,j] = vô cùng Đặt nhãn ban đầu cho mọi i thuộc X là Fx[i] = Min { C[i,j] với mọi j thuộc Y}, và Fy[j] = 0 cho mọi j thuộc Y Lượng sửa nhãn được tính là m = Min { C[i,j] – Fx[i] – Fy[j] }.

2.3.3 Thuật toán Hung-ga-ri

Bước 2: Với mọi đỉnh x *  X, ta tìm các ghép x *

Bắt đầu từ đỉnh x * , thử tìm đường mở bắt đầu ở x * bằng thuật toán tìm kiếm trên đồ thị Có 2 khả năng xẩy ra:

Khi tìm được một đường mở, ta có thể loại bỏ các cạnh đã ghép khỏi tập M và thêm vào các cạnh chưa ghép Quá trình này tạo ra một bộ ghép mới với số lượng cạnh nhiều hơn bộ ghép cũ một cạnh, đồng thời biến đỉnh x* thành đỉnh đã ghép.

 Hoặc không tìm thấy đường mở thì có thể xác định được

VisitedX = {Tập những X_đỉnh có thể đến được từ x* bằng một đường pha}

VisitedY = {Tập những Y_đỉnh có thể đến được từx* bằng một đường pha}

Gọi ∆ là trọng số nhỏ nhất của các cạnh nối giữa một đỉnh thuộc VisitedX và một đỉnh không thuộc VisitedY Có thể dễ dàng nhận thấy rằng ∆ phải lớn hơn 0, vì nếu ∆ bằng 0, sẽ tồn tại một cạnh (x, y) với x thuộc VisitedX và y không thuộc VisitedY Tuy nhiên, vì x* có thể đến được x bằng một đường pha và (x, y) là một cạnh, nên x* cũng có thể đến được y bằng một đường pha, dẫn đến việc y phải thuộc VisitedY, điều này tạo ra mâu thuẫn.

Biến đổi đồ thị G như sau: Với ∀x ∈VisitedX, trừ ∆ vào trọng số những cạnh liên thuộc với x, Với ∀y ∈VisitedY, cộng ∆ vào trọng số những cạnh liên thuộc với y

Lặp lại thủ tục tìm kiếm trên đồ thị thử tìm đường mở xuất phát ở

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn x* cho tới khi tìm ra đường mở

Bước 3:Sau bước 2 thì mọi X_đỉnh đều được ghép, in kết quảvề bộ ghép tìm được

Mô hình cài đặt của thuật toán có thể viết như sau:

; for (x*∈X) do begin repeat

; if then ; until ;

; end;

Để tránh nhầm lẫn trong việc hình dung, cần hiểu rằng các cạnh không có trọng số được coi là 0_cạnh, trong khi các cạnh không được vẽ có trọng số lớn sẽ không cần tính đến Các cạnh nét đậm biểu thị những cạnh đã được ghép, còn các cạnh nét thanh là những cạnh chưa được ghép.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn x * = X1 Tìm được đường mở:

X1 →Y1 Tăng cặp x*= X2 Tìm được đường mở:

X2 →Y1 →X1 →Y2 Tăng cặp x*= X3 Tìm được đường mở:

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn x*= X4 Không tìm được đường mở:

Tập những X_đỉnh đến được từ X4 bằng một đường pha:

Tập những Y_đỉnh đến được từ X4 bằng một đường pha:

Trừ tất cả trọng số những cạnh liên thuộc với {X3,X4} đi 1 Cộng tất cả trọng số những cạnh liên thuộc với Y3 lên 1 x*= X4 Vẫn không tìm được đường mở:

Tập những X_đỉnh đến được từ X4 bằng một đường pha:

Tập những Y_đỉnh đến được từ X4 bằng một đường pha:

Trừ tất cả trọng số những cạnh liên thuộc với {X1, X2, X3, X4} đi 2

Cộng tất cả trọng số những cạnh liên thuộc với {Y1, Y2, Y3} lên 2

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn x*= X4 Tìm được đường mở:

Trong quá trình tăng cặp, nếu không tìm thấy đường mở từ x*, quá trình tìm kiếm trên đồ thị sẽ tạo ra một cây pha gốc x* Giá trị xoay ∆ là trọng số nhỏ nhất của cạnh nối một đỉnh X trong cây pha với một đỉnh Y ngoài cây pha Việc trừ ∆ từ các cạnh liên thuộc với đỉnh X và cộng ∆ vào các cạnh liên thuộc với đỉnh Y sẽ làm cho cạnh ngoài trở thành 0_cạnh, trong khi các cạnh khác vẫn giữ trọng số ≥0 Quan trọng hơn, tất cả các cạnh trong cây pha vẫn là 0_cạnh, đảm bảo rằng quá trình tìm kiếm sau đó sẽ xây dựng được cây pha mới lớn hơn cây pha cũ, thể hiện qua việc tập Visited Y sẽ mở rộng ít nhất một phần tử Do tập các đỉnh Y đã ghép là hữu hạn, sau không quá k bước, sẽ có ít nhất một đỉnh Y chưa ghép thuộc Visited Y, tức là tìm ra được đường mở.

2.3.4 Phương pháp đối ngẫu Kuhn-Munkres

Phương pháp đối ngẫu Kuhn-Munkres đi tìm hai dãy số Fx[l k] và Fy[l k] thoả mãn:

• Tập các cạnh (x[i], y[j]) thoả mãn C[i,j] – Fx[i] – Fy[j] = 0 chứa trọn

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn một bộ ghép đầy đủ k cạnh, đây chính là bộ ghép cần tìm

Rõ ràng nếu tìm được hai dãy số thoả mãn trên thì ta chỉ việc thực hiện hai thao tác:

+ Với mỗi đỉnh x[i], trừ tất cả trọng số của những cạnh liên thuộc với x[i] đi một lượng Fx[i]

+ Với mỗi đỉnh y[j], trừ tất cả trọng số của những cạnh liên thuộc với y[j] đi một lượng Fy[j]

(Hai thao tác này tương đương với việc trừ tất cả trọng số của các cạnh (x[i], y[j]) đi một lượng Fx[i] + Fy[j] tức là C[i,j] := C[i,j] – Fx[i] – Fy[j])

Đồ thị mới được tạo ra sẽ bao gồm các cạnh có trọng số không âm cùng với những cạnh có trọng số bằng 0, đảm bảo rằng nó chứa đầy đủ một bộ ghép.

Phương pháp đối ngẫu Kuhn-Munkres chuyển đổi bài toán biến đổi đồ thị G (biến đổi ma trận C) thành việc biến đổi hai dãy số Fx và Fy Việc trừ một lượng delta vào trọng số tất cả các cạnh liên quan đến x[i] tương đương với việc tăng Fx[i] lên delta, trong khi việc cộng delta vào trọng số tất cả các cạnh liên quan đến y[j] tương đương với việc giảm Fy[j] đi delta Để xác định trọng số cạnh (x[i], y[j]) sau các bước biến đổi, chúng ta sẽ sử dụng ký hiệu thay vì viết C[i,j].

Sơ đồ cài đặt phương pháp đối ngẫu Kuhn-Munkres có thể viết như sau:

+ Việc khởi tạo các Fx, Fy có thể có nhiều cách miễn sao C[i,j] – Fx[i] – Fy[j] >= 0, đơn giản nhất có thể đặt tất cả các Fx[.], Fy[.] bằng 0

Bước 2: Với mọi đỉnh x*  X, ta tìm cách ghép x* như sau:

Bắt đầu từ đỉnh x*, thử tìm đường mở bắt đầu ở x* bằng thuật toán tìm kiếm trên đồ thị (BFS hoặc DFS) Có hai khả năng xảy ra:

+ Hoặc tìm được đường mở thì dọc theo đường mở, ta loại bỏ những cạnh đã ghép khỏi M và thêm vào M những cạnh chưa ghép

+ Hoặc không tìm được đường mở thì xác định được:

MỘT SỐ BÀI TOÁN ỨNG DỤNG TRONG THỰC TẾ

BÀI TOÁN ĐIỀU HÀNH TAXI

Trong thành phố có N nút giao thông mà khách hàng thường yêu cầu hãng Taxi TN cho tới Khoảng cách giữa hai nút giao thông là C[i,j]

Hãng Taxi TN có k chiếc Taxi hiện đang đỗ tại k nút giao thông trong

N nút kể trên Giả sử có k yêu cầu của khách hàng tới k nút giao thông trong thành phố

Hãy tìm cách di chuyển k Taxi đến k địa điểm khách đứng sao cho tổng khoảng cách di chuyển của các xe là ngắn nhất

3.1.2 Phân tích bài toán và xây dựng thuật toán

Bài toán điều hành Taxi nảy sinh từ việc nhiều khách hàng cùng yêu cầu xe, dẫn đến việc các xe di chuyển từ nơi đỗ đến địa điểm đón khách tiêu tốn nhiên liệu và tăng chi phí cho hãng Điều này ảnh hưởng trực tiếp đến doanh thu của công ty Do đó, nhà điều hành cần tối ưu hóa việc lựa chọn và điều động xe để giảm thiểu chi phí di chuyển đến địa điểm đón khách.

Để đáp ứng nhu cầu thực tế, tôi đã quyết định áp dụng công nghệ thông tin để giải quyết bài toán điều động Taxi Nhờ vào hệ thống này, nhân viên có thể nhanh chóng lựa chọn phương án di chuyển tối ưu cho các xe Taxi, từ đó nâng cao hiệu quả kinh tế cho hãng.

Bài toán điều hành Taxi sử dụng thuật toán Tìm cặp ghép có tổng trọng số trên các cung là nhỏ nhất

Bài toán được biểu diễn bằng mô hình đồ thị như sau:

Xây dựng đồ thị G = (V, E), trong đó:

Mỗi một đỉnh vi  V của đồ thị đại diện cho một nút giao thông

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn trong thành phố

Mỗi cạnh ei trong tập hợp E kết nối hai đỉnh của đồ thị, tượng trưng cho lộ trình giữa hai nút giao thông Trọng số của cạnh ei thể hiện khoảng cách giữa hai nút giao thông mà nó nối.

Tại mỗi nút giao thông, taxi đỗ được đánh dấu bằng lá cờ có chữ "Start", trong khi khách hàng đứng chờ được biểu thị bằng chữ "Finish".

Khi thực hiện thuật toán, đường di chuyển của các Taxi được tô đậm từ điểm đỗ đến điểm đón khách

Kết quả của bài toán chính là bộ ghép có tổng trọng số nhỏ nhất tìm được

+ Xây dựng ma trận chi phí C, với C[i,j] là trọng số nhỏ nhất để đi từ nút giao thông i đến nút giao thông j

+ Ma trận T là ma trận chứa chỉ số của nút giao thông trung gian, với T[i,j]

0 T[i,j] chứa đỉnh trung gian trên quãng đường đi từ nút giao thông i đến nút giao thông j

Tạo đồ thị hai phía bằng ma trận A, trong đó phía Old đại diện cho các đỉnh có Taxi đỗ với k đỉnh, và phía New đại diện cho các đỉnh có khách hàng đứng, cũng với k đỉnh Giá trị A[i,j] là trọng số âm thể hiện quãng đường đi từ nút giao thông Old[i] đến nút giao thông New[j].

+ Tạo nhãn ban đầu chấp nhận được Fx và Fy theo quy tắc:

(FX, FY gọi là chấp nhận được nếu thoả mãn bất đẳng thức Fx[i] + Fy[j] = 0 Sau khi sửa nhãn cho các đỉnh thuộc dây chuyền “dở dang”, chúng có khả năng kết hợp với các đỉnh j bên New để tạo thành một dây chuyền hoàn chỉnh, xuất hiện những cặp (i,j) mới thỏa mãn Fx[i] + Fy[j] = A[i,j).

Tăng cặp ghép: Đổi màu các cung, bắt đầu từ cung nhạt cuối cùng của dây

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn chuyền đổi ngược dần về cung nhạt đầu tiên của dây chuyền

Tìm dây chuyền theo chiều sâu yêu cầu bắt đầu từ một đỉnh nhạt của Old và kết thúc tại một đỉnh nhạt của New, trong đó các cung nhạt và đậm phải xen kẽ nhau liên tiếp.

Trong thành phố có 10 nút giao thông được đánh số từ 1 đến 10

Khoảng cách giữa các nút giao thông được cho trong ma trận sau:

Có 4 Taxi, với các điểm đỗ của các Taxi đó là: 1.2.3.4 khách hàng đang đứng tại các nút giao thông : 10, 9,

8, 7 Khi đó: thực hiện theo thuật toán ta được kết quả:

Taxi 1: Đi từ nút GT 1 —> nút GT 7

Taxi 3: Đi từ nút GT 3 —> nút GT 4 —> nút GT 8

Với tổng khoảng cách di chuyển của cả 4 Taxi là: 5 (km)

Dữ liệu vào từ File:

Dòng đầu ghi hai số N và K

N dòng tiếp theo cho ma trận khoảng cách C: số ở dòng i, cột j là độ dài đường đi một chiều từ nút giao thông i đến nút giao thông j trong thành phố

+ Dòng thứ nhất gồm K số hiệu của nút giao thông mà các Taxi đang đỗ

+ Dòng thứ hai gồm K số hiệu của nút giao thông mà các khách hàng của hãng Taxi TN đang đứng

Cách di chuyển K Taxi tới K địa điểm khách hàng đứng mà tổng khoảng cách di chuyển là ngắn nhất

Các hàm và thủ tục chính của chương trình: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace BTTaxi

The code snippet defines several public integer arrays, including Old, New, Fx, Fy, and others, to store various data points It also initializes two-dimensional arrays A, T, C, and an empty two-dimensional array Ng Additionally, it includes instances of classes G, TX, and Dich, which may represent specific functionalities or data structures within the program.

The digitalization process at the Learning Resource Center of TNU involves initializing variables such as public integers 'n' and 'k' set to zero, along with integer arrays 'r', 'l', and 'sld', which are initialized to empty Additionally, a boolean variable 'ok' is defined and set to true.

C = new int[G.SoDinh][]; for (int i=0; i < G.SoDinh; i++)

The code initializes several integer arrays to facilitate graph operations It creates a 2D array `C` with dimensions based on the number of vertices (`SoDinh`) in the graph, setting all values to zero Additionally, it allocates arrays for old and new values, as well as for `Fx` and `Fy`, each corresponding to the number of vertices The code also initializes two more 2D arrays, `A` and `T`, both sized according to the graph's vertices Finally, it sets up one-dimensional arrays for `Tr`, `Dx`, and `Dy`, ensuring all necessary data structures are in place for further computations.

{ this.n = this.G.SoDinh; this.k = this.Tx.SoLuong; for (int i = 0; i < this.G.SoCanh; i++)

C[this.G.DScanh[i].DinhDau][this.G.DScanh[i].DinhCuoi] = this.G.DScanh[i].TrongSo.GiaTri; for (int i = 0; i < this.G.SoCanh; i++) for (int j = 0; j < this.G.SoCanh; j++)

{ if (this.C[i][j] == 0) this.C[i][j] = 20000; if (i == j) this.C[i][j] = 0;

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn for (int i = 0; i < this.Tx.SoLuong; i++) this.Old[i]

= this.Tx.DS[i].Dinh; for (int i = 0; i < this.Dich.SoLuong; i++) this.New[i] = this.Dich.DS[i];

{ for (int i = 0; i < this.G.SoDinh; i++) for (int j = 0; j < this.G.SoDinh; j++) this.T[i][j] = -1; for (int m = 0; m < this.n; m++) for (int i = 0; i < this.n; i++) for (int j = 0; j < this.n; j++)

{ if (this.C[i][m] < this.C[i][j]) this.C[i][j] = this.C[i][m] + this.C[m][j];

{ this.A[i][j] = - this.C[this.Old[i]][this.New[j]]; if (this.A[i][j] > p) p = this.A[i][j];

} this.Fx[i] = p; for (int j = 0; j < this.G.SoDinh; j++) this.Fy[j]

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn this.l[j] = i; j = p;

{ if (this.ok) return; this.Dx[i] = 1; for (int j = 0; j < this.k; j++)

{ if(this.Dy[j] == -1) if (this.Fx[i] + this.Fy[j] == this.A[i][j]) { this.Tr[i] = j; if (this.l[j] == -1)

{ this.Dy[j] = 1; this.TimDayChuyen(this.l[j]);

{ int ph = 20000; for (int i = 0; i < this.k; i++)

{ if (this.Dy[j] == -1) if (this.Fx[i] + this.Dy[j] < ph) ph = this.Fx[i] + this.Dy[j] - this.A[i][j];

{ int d = this.Min(); for (int i = 0; i < this.k; i++)

{ if (this.Dx[i] == 1) this.Fx[i] += d; if (this.Dy[i] == 1) this.Fy[i] += d;

{ this.l = new int[this.G.SoDinh]; this.r = new int[this.G.SoDinh]; for (int i = 0; i < this.G.SoDinh; i++)

{ this.ok = false; for (int z = 0; z < this.G.SoDinh; z++) { this.Dx[z] = -1; this.Dy[z] = -1; this.Tr[z] = -1;

} this.TimDayChuyen(i); if (!this.ok) this.SuaNhan(); else this.TangCapGhep(this.l[i]);

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn int dem = 0; public void Tim(int tt, int x, int y)

{ int tg = this.T[x][y]; if (tg == -1)

{ if (dem == 0 || (dem > 0 && x != this.Ng[tt][dem - 1]))

{ dem++; this.Ng[tt][dem - 1] = x;

} dem++; this.Ng[tt][dem - 1] = y;

The current date and time are captured using DateTime.Now, and an array is initialized to hold integer values based on the variable 'k' A nested loop is used to create a two-dimensional array, 'Ng', where each sub-array corresponds to the number of vertices defined by 'SoDinh' The variable 'sld' is also initialized to store counts for each 'k' A total sum, 'tong', is calculated by iterating through the array 'A' and accumulating values at specific indices defined by 'r' Finally, the sum is negated for further processing.

{ dem = 0; this.Tim(i, this.Old[i], this.New[this.r[i]]); this.sld[i] = dem;

//Ket qua trong mang this.Ng

{ public int SoDinh; public int SoCanh; public DanhSachCanh[] DScanh;

{ public int DinhCuoi; public int Dinh; public int DinhDau; public TrongSo TrongSo;

{ public int SoLuong; public DanhSachCanh[] DS;

{ public int[] DS; public int SoLuong;

BÀI TOÁN XẾP LỚP HỌC THEO TÍN CHỈ

3.2.1 Mô hình đào tạo theo học chế tín chỉ

Khác với mô hình đào tạo theo niên chế, đào tạo theo học chế tín chỉ mang lại sự linh hoạt cao, khuyến khích sinh viên chủ động, tự học và tự nghiên cứu Nhà trường và giảng viên tạo điều kiện thuận lợi để sinh viên tích lũy kiến thức và kỹ năng, đồng thời quản lý chặt chẽ quá trình học tập của từng sinh viên nhằm đảm bảo chất lượng đào tạo.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn Đầu mỗi khoá học, nhà trường thông báo cho sinh viên về:

Chương trình đào tạo toàn khoá cho từng ngành học

Quy chế học tập và các quy định của trường

Quyền lợi và nghĩa vụ của sinh viên Đầu mỗi học kỳ, nhà trường có trách nhiệm thông báo cho sinh viên về:

Danh mục các học phần dự kiến giảng dạy trong học kỳ bao gồm thông tin về số lượng tín chỉ của từng học phần và các điều kiện cần thiết để sinh viên có thể đăng ký học những học phần này.

Mỗi học kỳ, sinh viên cần nắm rõ chương trình đào tạo và đăng ký các học phần theo phiếu đăng ký của trường Số lớp học dự kiến và thời khóa biểu cho từng học phần sẽ được công bố để sinh viên dễ dàng theo dõi và chuẩn bị cho việc học.

Mô hình đào tạo theo học chế tín chỉ hiện nay cho phép sinh viên tự do đăng ký các học phần, tuy nhiên, điều này có thể dẫn đến tình trạng mất cân bằng trong số lượng sinh viên giữa các lớp học Cụ thể, một số lớp có thể đông học viên, trong khi những lớp khác lại chỉ có rất ít sinh viên theo học.

Trên cơ sở thực tế như vây em cho rằng nên cho sinh viên đăng ký học theo một cách mới mềm dẻo hơn đó là:

Sinh viên cần đăng ký số lượng học phần cho học kỳ và cung cấp danh sách các học phần có thể theo học Tổng số học phần trong danh sách này phải lớn hơn hoặc bằng số lượng học phần đã đăng ký.

Dựa trên phiếu đăng ký của sinh viên, nhà trường sẽ sắp xếp cho từng sinh viên học đủ số lượng học phần đã đăng ký Tất cả các học phần mà sinh viên theo học đều nằm trong danh sách học phần có thể đăng ký, đảm bảo rằng số lượng sinh viên cho mỗi học phần được cân nhắc hợp lý.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn theo học chênh lệch nhau càng ít càng tốt

Có M sinh viên đăng ký học trong năm học 2014-2015, nhà trưòng dự kiến mở lớp cho N học phần

Phiếu đăng ký của sinh viên được biểu diễn bằng mảng A cấp (MxN) với: A[i,j]=0 nếu sinh viên i đăng ký học học phần j

A[i,j]=2 nếu sinh viên i không đăng ký học học phần j

Mảng p biểu diễn số học phần muốn học của mỗi sinh viên, với P[i] là số học phần muốn học của sinh viên i

Cần sắp xếp cho sinh viên học các học phần phù hợp với nguyện vọng của họ, đồng thời giảm thiểu sự chênh lệch về số lượng sinh viên theo học giữa các học phần.

3.2.3 Phân tích bài toán và xây dựng thuật toán

Danh sách sinh viên giả định được cung cấp từ chương trình quản lý sinh viên, lưu trữ trong cơ sở dữ liệu Mỗi sinh viên sẽ được gán một mã riêng biệt theo quy định của nhà trường.

Tất cả các học phần của các ngành học đã được lưu trữ trong cơ sở dữ liệu, với mỗi học phần được gán một mã riêng theo quy định của nhà trường.

Các học phần giảng dạy trong học kỳ

Số lượng học phần mỗi sinh viên muốn học

Danh sách các học phần có thể theo học của mỗi sinh viên

(Giả sử với lựa chọn bất kỳ cho mỗi sinh viên, tổng số tín chỉ theo học của mỗi sinh viên không nằm ngoài giới hạn của nhà trường.)

Danh sách sinh viên theo học từng học phần

Bài toán được giải quyết bằng thuật toán phỏng theo thuật toán

Bước 1: Tạo phương án ban đầu:

For i:=l to m do đổi các giá trị A[i,j] = 0 thành 1 với j chạy từ 1 ->N cho đến khi đủ số lượng sinh viên i muốn học tức là bằng P[i]

Tao_day_voi; // tạo cột đầy, cột vơi Gán_số;

Nếu tìm được dãy vơi thì sửa;

Until không tìm được dãy vơi nữa

Tìm trong mảng a tổng t của cột có tổng số các số 1 ít nhất

Khi duyệt từ cột 1 đến cột N, các cột được phân loại dựa trên tổng số 1 Cột nào có tổng số 1 bằng t sẽ được gọi là cột đầy, trong khi cột nào có tổng số 1 nhỏ hơn t - 2 sẽ được xem là cột vơi.

Nếu cột j là cột đầy thì:

Gán số 0 cho các cột j;

Xét tất cả các hàng i, gán số j cho các hàng i chưa được gán sô; }

Nếu hàng i đã được gán số thì

Nếu sinh viên i có thể theo học được học phần j (coi ô [i, j] là ô trắng )

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn thì

Gán số i cho các cột j chưa được gán số

Tìm vơi: Kiểm tra trong các hàng xem có tồn tại cột vơi hay không Nếu phát hiện cột vơi, hãy điều chỉnh dây chuyền bằng cách xen kẽ các ô xanh và ô trắng, trong đó ô xanh đại diện cho các ô a[i,j] được gán giá trị 1.

Có 8 sinh viên đăng ký học, các sinh viên được đánh số từ 1 đến 8, nhà trường dự kiến mở lớp dạy 8 học phần kí hiệu từ 1 đến 8

Thông tin phiếu đăng ký của các sinh viên được biểu diễn trong bảng sau:

Số lượng học phần các sinh viên muốn theo học cho trong bảng sau:

Thực hiện ví dụ này theo thuật toán ta có kết quả như sau:

Sinh viên 1: Học các học phần: 1, 6, 8

Sinh viên 2: Học các học phần: 2, 3, 4, 5

Sinh viên 3: Học các học phần: 1, 7

Một số giao diện trong chương trình

Chức năng thêm học phần cho học kỳ

Chức năng đăng ký học phần

Chức năng xem kết quả

Các hàm và thủ tục chính của chương trình: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace DangKyTinChi.Common

{ public int[] P = null/*So Hoc Phaan sv muon hoc*/, Day = null/*Day day hay voi*/

, Gc = null/*Gan cot*/, Gh = null/*Gan hang*/; public int[][] A = null; public int M = 0/*So SV*/, N = 0/*So Hoc Phan*/, J0 = 0; public void Prepare()

The code initializes several integer arrays, including P, Gc, Gh, and Day, which are sized according to the variables M and N Additionally, a two-dimensional array A is created, where each row is filled with the value 2 This setup is crucial for managing data within the specified dimensions, and the method Hang is defined to operate on the integer index i.

{ int dem = 0; for (int j = 0; j < this.N; j++)

{ if (this.A[i][j] == 0 && dem < this.P[i]) { this.A[i][j] = 1; dem++;

/// Tao Phuong An Ban Dau

{ for (int j = 0; j < this.N; j++) this.Day[j] = 0; int t = this.TongCot(0); for (int j = 1; j < this.N; j++)

{ int tongCotJ = this.TongCot(j); if (t < tongCotJ) t = tongCotJ;

{ int tongCotJ = this.TongCot(j); if (t == tongCotJ) this.Day[j] = 1; //Cot Day //if (t >= tongCotJ + 2) this.Day[j] = -1; //Cot Voi 1< t -2 if (tongCotJ < t - 2) this.Day[j] = -1;

{ this.Gc[j] = 0; for (int i = 0; i < this.M; i++)

{ if (this.A[i][j] == 1) if (this.Gh[i] == -1) this.Gh[i] = j; }

{ if (this.A[i][j] == 0) if (this.Gc[j] == -1) this.Gc[j] = i; }

{ int dem = 0; for (int i = 0; i < this.M; i++)

{ this.Gh[i] = -1; for (int j = 0; j < this.N; j++)

{ if (this.Day[j] == -1 && this.Gc[j] > 0)

} private void Sua(int i, int j)

{ i = this.Gc[j]; this.A[i][j] = 1 - this.A[i][j]; j = this.Gh[i]; if (j > 0) this.A[i][j] = 1 - this.A[i][j]; }

GanSo(); if (TimVoi()) Sua(this.Gc[this.J0], this.J0);

Sau khi nghiên cứu lý thuyết đồ thị và khám phá các ứng dụng cũng như tính thiết thực của lĩnh vực này, luận văn đã đạt được những kết quả đáng chú ý.

-Tìm hiểu các khái niệm cơ bản của đồ thị, đồ thị hai phía

-Tìm hiểu các thuật toán giải bài toán bộ ghép cực đại trên đồ thị hai phía và trên đồ thị tổng quát

Tìm hiểu về ứng dụng của lý thuyết đồ thị giúp người học nắm bắt cách triển khai lý thuyết vào thực tiễn Hai bài toán tiêu biểu là bài toán xếp lớp học theo tín chỉ và bài toán điều hành taxi Những ứng dụng này không chỉ nâng cao khả năng giải quyết vấn đề mà còn góp phần tối ưu hóa quy trình trong các lĩnh vực giáo dục và vận tải.

Cài đặt chương trình mô phỏng thuật toán Hungary để giải quyết bài toán xếp lớp học theo học chế tín chỉ mang lại tính ứng dụng cao và thực tiễn.

Định dạng
Số trang	80
Dung lượng	1,78 MB