Thuật Toán

GIẢI HỆ BẤT PHƯƠNG TRÌNH BẰNG THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT (PHẦN 1)

 

Kiến thức cần biết

  • Các khái niệm cơ bản trong lý thuyết đồ thị
  • Các thuật toán tìm đường đi ngắn nhất (Ford-Bellman, Dijkstra, …)

Bài toán mở đầu

Cho một hệ gồm các bất phương trình có dạng xj −xi ≤ wi,j. Hãy tìm một nghiệm x1,x2,…, bất kì của hệ bất phương trình trên (hoặc cho biết hệ vô nghiệm).

Trong tiếng Anh, bài toán trên được gọi là “System of difference constraints”.

Ví dụ 1:

  • x1−x2 ≤ 5
  • x2−x3 ≤ −3
  • x3−x1  ≤−4
  • x1−x4 ≤ 0

Hệ bất phương trình trên vô nghiệm.

Ví dụ 2:

  • x1−x2 ≤ -3
  • x3−x2 ≤ −4
  • x2−x4 ≤ −1
  • x4 −x1 ≤ 5
  • x4−x2 ≤ 1

Một nghiệm của hệ bất phương trình trên: x1= −3, x2, x3= −4, x4=

Lời giải

Ta sẽ xây dựng một đồ thị gồm n đỉnh (đỉnh i đại diện cho biến x). Với mỗi bất phương trình xj −xi ≤ wi,j, ta sẽ thêm cạnh một chiều từ i đến j với trọng số wi,j.

Trường hợp 1: Tồn tại chu trình âm


Ta sẽ chứng minh rằng: Nếu tồn tại một chu trình âm (tổng trọng số các cạnh trong chu trình nhỏ hơn 0) trong đồ thị thì hệ bất phương trình vô nghiệm.

Giả sử tồn tại chu trình âm 1→2→…→k→1. Chu trình trên tương đương với các bất phương trình sau:

  • x2−x1 ≤ w1,2
  • x3−x2 ≤ w2,3
  • …
  • xk−xk-1 ≤ wk-1,k
  • x1−xk ≤ wk,1

Cộng vế theo vế, ta có: 0 ≤ w1,2+ w2,3+…+ wk-1,k+ wk,1. Nói cách khác, tổng trọng số của các cạnh trong chu trình là không âm, mâu thuẫn với giả thiết. Do đó, hệ bất phương trình vô nghiệm.

Việc kiểm tra chu trình âm có thể được thực hiện bằng thuật toán Ford-Bellman trong O(nm)(với n là số biến, m là số bất phương trình).

Trường hợp 2: Không tồn tại chu trình âm


Trong trường hợp này, ta luôn tìm được nghiệm cho hệ bất phương trình bằng cách sau:

Tạo một đỉnh giả . Với mọi đỉnh i, thêm cạnh một chiều từ s đến i với trọng số 0 (việc thêm cạnh này sẽ không tạo ra chu trình âm). Ta định nghĩa D(i,j) là độ dài đường đi ngắn nhất từ đỉnh i đến đỉnh j. Khi đó, xi =D(s,i) là một nghiệm của hệ.

Để chứng minh đều trên là đúng, xét bất phương trình xj −xi ≤ wi,j bất kì của hệ. Theo tính chất của đường đi ngắn nhất, ta có D(s,j) ≤ D(s,i)+wi,j. Mà xi = D(s,i), xj =D(s,j) nên bất phương trình xj −xi ≤ wi,j được thỏa.

Do đồ thị có trọng số âm, ta sẽ sử dụng thuật toán Ford-Bellman để tìm đường đi ngắn nhất từ s đến mọi đỉnh. Do đó, hệ gồm m bất phương trình và n biến có thể được giải trong độ phức tạp O(n(m+n)) (lưu ý rằng do ta thêm n cạnh xuất phát từ đỉnh giả nên đồ thị có tổng cộng n+m cạnh).

BÀI TẬP VÍ DỤ

Ví dụ 1: Little K’s Farm

Link đề bài

Tóm tắt đề:

Little K có n nông trại. Ông nhớ m thông tin về các nông trại, mỗi thông tin thuộc 1 trong 3 dạng sau:

  • 1 a b c: Nông trại a có nhiều hơn nông trại b tối thiểu cây trồng
  • 2 a b c: Nông trại a có nhiều hơn nông trại b tối đa c cây trồng
  • 3 a b: Nông trại a có số cây trồng bằng nông trại b

Hãy cho có tồn tại trường hợp nào mà số cây trồng trong mỗi nông trại thỏa mãn cả m thông tin trên hay không.

Giới hạn: 1≤n, m, a, b, c≤ 5×103

Hướng dẫn giải:

Ta định nghĩa xi là số cây trồng của nông trại thứ i.

Khi đó:

  • Thông tin 1 a b c tương đương với bất phương trình xa −xb ≥ c⇔ xb−xa ≤ −c
  • Thông tin 2 a b c tương đương với bất phương trình xa −xb ≤ c
  • Thông tin 3 a b tương đương với phương trình xa= xb⇔(xa ≤ xb

Ta xây dựng hệ bao gồm các bất phương trình trên, và áp dụng phương pháp trong bài toán mở đầu để kiểm tra xem hệ có nghiệm hay không.

Độ phức tạp: O(nm) (ta cần sử dụng thuật toán Ford-Bellman do đồ thị có trọng số âm)

Ví dụ 2: King

Link đề bài

Tóm tắt đề:

Xét các dãy số a gồm n phần tử. Có m ràng buộc, mỗi ràng buộc được cho bởi bộ ba số nguyên (s,n,k) và chuỗi o:

  • Nếu o là chuỗi lt thì sum(s,s+n)<k (kí hiệu sum(l,r) là tổng của các phần tử từ vị trí l đến vị trí r của dãy a)
  • Nếu o là chuỗi gt thì sum(s,s+n)>k

Hãy cho biết có tồn tại dãy nào thỏa mãn tất cả các ràng buộc trên hay không.

Giới hạn: 1≤n, m≤100

Hướng dẫn giải: 

Ta định nghĩa x0 =c (c là một số nguyên bất kì) và xi =a1 +a2+…+ai+c. Khi đó: sum(l,r)=xr−xl-1 

Ta có thể biến đổi các loại ràng buộc trong đề bài về các bất phương trình như sau:

  • sum(s,s+n)<k⇔xs+n−xs-1 ≤ k
  • sum(s,s+n)>k⇔xs+n−xs-1 ≥ k

Từ đó, ta có thể áp dụng phương pháp trong bài toán mở đầu để kiểm tra xem hệ bất phương trình trên có nghiệm hay không.

Độ phức tạp: O(nm) (ta cần sử dụng thuật toán Ford-Bellman do đồ thị có trọng số âm)

Tổng kết

Phần đầu của bài viết đã giới thiệu về cách xác định xem hệ bất phương trình có nghiệm hay không, và tìm một nghiệm bất kì của hệ.

xj −xi ≤ wi,j

Phần tiếp theo của bài viết sẽ đề cập đến cách tìm nghiệm với một số tính chất đặc biệt max{xi}−min{xi}  nhỏ nhất; max{xi}−min{xi} lớn nhất; xi≤0 và tổng giá trị xi lớn nhất; …).

Bài tập thêm

Các bài tập được sắp xếp theo ước tính độ khó tăng dần

  1. Is the Information Reliable? (POJ)
  2. Restore Array (RMI 2019, bài 3 ngày 1)
  3. Sequence (NOI 1999, bài 1 ngày 1)
  4. Halum (UVa)
  5. Cashier Employment (POJ)
  6. Flights (Bayan 2012-2013 Elimination Round, bài E)

Tài liệu tham khảo

  1. https://courses.csail.mit.edu/6.006/spring11/lectures/lec17.pdf
  2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, chapter 24.4