Giới thiệu một số bài toán cổ

[Vy Vy]

Giới thiệu một số bài toán cổ - kỳ 1




Chuyên đề Những bài toán cổ kỳ này xin giới thiệu với các bạn một bài toán khá nổi tiếng trong lịch sử, đó là bài toán Bảy cây cầu Euler, hay còn gọi là Bảy cầu ở Königsberg. Trong ảnh là bản đồ Königsberg thời Euler, mô tả vị trí thực của bảy cây cầu và sông Pregel.

Bài toán bảy cây cầu Euler, còn gọi là Bảy cầu ở Königsberg nảy sinh từ nơi chốn cụ thể. Thành phố Königsberg, Đức (nay là Kaliningrad, Nga) nằm trên sông Pregel, bao gồm hai hòn đảo lớn nối với nhau và với đất liền bởi bảy cây cầu. Câu hỏi đặt ra là có thể đi theo một tuyến đường mà đi qua mỗi cây cầu đúng một lần rồi quay lại điểm xuất phát hay không. Năm 1736, Leonhard Euler đã chứng minh rằng điều đó là không thể được.
Người ta kể rằng, khoảng năm 1750, vào các ngày Chủ nhật, những người dân giàu có và học thức của thành phố đã đi dạo quanh để tìm cách giải bài này, nhưng đây có lẽ chỉ là một truyền thuyết.
Lời giải của Euler

Để chứng minh kết quả, Euler đã phát biểu bài toán bằng các thuật ngữ của lý thuyết đồ thị. Ông loại bỏ tất cả các chi tiết ngoại trừ các vùng đất và các cây cầu, sau đó thay thế mỗi vùng đất bằng một điểm, gọi là đỉnh hoặc nút, và thay mỗi cây cầu bằng một đoạn nối, gọi là cạnh hoặc liên kết. Cấu trúc toán học thu được được gọi là một đồ thị.

→ →

Hình thù của đồ thị có thể bị bóp méo theo đủ kiểu nhưng không làm đồ thị bị thay đổi, miễn là các liên kết giữa các nút giữ nguyên. Việc một liên kết thẳng hay cong, một nút ở bên phải hay bên trái một nút khác là không quan trọng.

Euler nhận ra rằng bài toán có thể được giải bằng cách sử dụng bậc của các nút. Bậc của một nút là số cạnh nối với nó; trong đồ thị các cây cầu Königsberg, ba nút có bậc bằng 3 và một nút có bậc 5. Euler đã chứng minh rằng một chu trình có dạng như mong muốn chỉ tồn tại khi và chỉ khi không có nút bậc lẻ. Một đường đi như vậy được gọi là một chu trình Euler. Do đồ thị các cây cầu Königsberg có bốn nút bậc lẻ, nên nó không thể có chu trình Euler.

Có thể sửa đổi bài toán để yêu cầu một đường đi qua tất cả các cây cầu nhưng không cần có điểm đầu và điểm cuối trùng nhau. Đường đi như vậy được gọi là một đường đi Euler. Một đường đi như vậy tồn tại khi và chỉ khi đồ thị có đúng hai đỉnh bậc lẻ. (Như vậy điều này cũng không thể đối với bảy cây cầu ở Königsberg.)

Ý nghĩa của bài toán đối với lịch sử toán học

Trong lịch sử toán học, lời giải của Euler cho bài toán bảy cây cầu ở Königsberg được coi là định lý đầu tiên của lý thuyết đồ thị, ngành nghiên cứu mà nay được coi là một nhánh của toán học tổ hợp ( combinatorics), tuy các bài toán tổ hợp đã được quan tâm đến từ sớm hơn rất nhiều.

Ngoài ra, nhận xét của Euler rằng thông tin quan trọng là số cây cầu và danh sách các vùng đất ở đầu cầu (chứ không phải vị trí chính xác của chúng) đã là dấu hiệu cho sự phát triển của ngành tôpô học. Sự khác biệt giữa sơ đồ thực và sơ đồ đồ thị là một ví dụ tốt rằng tôpô học không quan tâm đến hình thù cứng nhắc của các đối tượng.

Nguồn: ThuVienToanHoc.Net

Phú Sĩ St

[Vy Vy]

Giới thiệu một số bài toán cổ - kỳ 2



Xin giới thiệu một bài toán hay nữa, đó là bài toán Xếp ba lô. Bài toán xếp ba lô (một số sách ghi là bài toán cái túi) là một bài toán tối ưu hóa tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vào trong một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Các bài toán tương tự thường xuất hiện trong kinh doanh, toán tổ hợp, lý thuyết độ phức tạp tính toán, mật mã học và toán ứng dụng.

Nội dung bài toán như sau:

Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có n mặt hàng có trọng lượng và giá trị khác nhau, nhưng hắn chỉ mang theo một cái túi có sức chứa về trọng lượng tối đa là M. Vậy kẻ trộm nên bỏ vào ba lô những món nào và số lượng bao nhiêu để đạt giá trị cao nhất trong khả năng mà hắn có thể mang đi được.

Dạng bài toán quyết định của bài toán xếp ba lô là câu hỏi "có thể đạt được một giá trị ít nhất bằng V mà không vượt ngưỡng chi phí C hay không?"
Phát biểu bài toán

Ta có n loại đồ vật, x1 tới xn. Mỗi đồ vật xj có một giá trị pj và một khối lượng wj. Khối lượng tối đa mà ta có thể mang trong ba lô là C.
Bài xếp ba lô dạng 0-1

Hạn chế số đồ vật thuộc mỗi loại là 0 (không được chọn) và 1 (được chọn).
Bài xếp ba lô 0-1 có thể được phát biểu bằng toán học như sau:

Cực đại hóa

sao cho


Bài xếp ba lô bị chặn hạn chế số đồ vật thuộc mỗi loại không được vượt quá một lượng nào đó.
Bài xếp ba lô bị chặn có thể được phát biểu bằng toán học như sau:
Cực đại hóa


sao cho


Bài xếp ba lô không bị chặn không có một hạn chế nào về số lượng đồ vật mỗi loại.
Một trường hợp đặc biệt của bài toán này nhận được nhiều quan tâm, đó là bài toán với các tính chất:

• là một bài toán quyết định
• là một bài toán 0/1
• với mỗi đồ vật, chi phí bằng giá trị: C = V

Lưu ý rằng trong trường hợp đặc biệt này, bài toán tương đương với:
Cho một tập các số nguyên, tồn tại hay không một tập con có tổng đúng bằng C? Hoặc nếu đồ vật được phép có chi phí âm và C được chọn bằng 0, bài toán có dạng:
Cho trước một tập các số nguyên, tồn tại hay không một tập con có tổng đúng bằng 0? Trường hợp đặc biệt này được gọi là bài toán tổng các tập con ( subset sum problem). Với một số lý do, trong ngành mật mã học, người ta thường dùng cụm từ "bài toán xếp ba lô" khi thực ra đang có ý nói về "bài toán tổng con".
Bài toán xếp ba lô thường được giải bằng quy hoạch động, tuy chưa có một thuật toán thời gian đa thức cho bài toán tổng quát. Cả bài xếp ba lô tổng quát và bài toán tổng con đều là các bài NP-khó, và điều này dẫn đến các cố gắng sử dụng tổng con làm cơ sở cho các hệ thống mật mã hóa khóa công khai, chẳng hạn Merkle-Hellman. Các cố gắng này thường dùng nhóm thay vì các số nguyên. Merkle-Hellman và một số thuật toán tương tự khác đã bị phá, do các bài toán tổng con cụ thể mà họ tạo ra thực ra lại giải được bằng các thuật toán thời gian đa thức.
Phiên bản bài toán quyết định của bài xếp ba lô được mô tả ở trên là NP-đầy đủ và trong thực tế là một trong 21 bài toán NP-đầy đủ của Karp.
Bài xếp ba lô dạng phân số

Với mỗi loại, có thể chọn một phần của nó (ví dụ: 1Kg bơ có thể được cắt ra thành nhiều phần để bỏ vào ba lô)
Cách giải bằng quy hoạch động

Bài toán xếp ba lô có thể được giải trong thời gian giả-đa thức bằng quy hoạch động. Dưới đây là lời giải quy hoạch động cho bài toán xếp ba lô không bị chặn.
Gọi các chi phí là c1, ..., cn và các giá trị tương ứng là v1, ..., vn. Ta cần cực đại hóa tổng chi phí với điều kiện tổng chi phí không vượt quá C. Khi đó, với mỗi i ≤ C, đặt A( i) là giá trị lớn nhất có thể đạt được với tổng chi phí không vượt quá i. Rõ ràng, A( C) là đáp số của bài toán.
Định nghĩa A( i) một cách đệ quy như sau:

• A(0) = 0
• A( i) = max { vj + A( i − cj) | cj ≤ i }

Ở đây, giá trị lớn nhất của tập rỗng được lấy bằng 0. Tính dần các kết quả từ A(0) tới A( C), ta sẽ được lời giải. Do việc tính mỗi A( i) đòi hỏi xem xét n đồ vật (tất cả các giá trị này đã được tính từ trước), và có C giá trị của các A( i) cần tính, nên thời gian chạy của lời giải quy hoạch động là O( nC).
Điều này không mâu thuẫn với thực tế rằng bài toán xếp ba lô là NP-đầy đủ, do C, không như n, không thuộc mức đa thức theo độ dài của đầu vào cho bài toán. Độ dài đầu vào bài toán tỉ lệ thuật với số bit trong C, chứ không tỉ lệ với chính C.
Một giải pháp quy hoạch động tương tự cho bài toán xếp ba lô 0-1 cũng chạy trong thời gian giả-đa thức. Cũng như trên, gọi các chi phí là c1, ..., cn và các giá trị tương ứng là v1, ..., vn. Ta cần cực đại hóa tổng giá trị với điều kiện tổng chi phí không vượt quá C. Định nghĩa một hàm đệ quy A( i, j) là giá trị lớn nhất có thể đạt được với chi phí không vượt quá j và sử dụng các đồ vật trong khoảng từ x1 tới xi.
A( i, j) được định nghĩa đệ quy như sau:

• A(0, j) = 0
• A( i, 0) = 0
• A( i, j) = A( i - 1, j) if ci > j
• A( i, j) = max( A( i - 1, j), vi + A( i - 1, j - ci)) if ci ≤ j

Để có lời giải, ta tính A( n, C). Để làm điều này, ta có thể dùng 1 bảng để lưu các tính toán trước đó. Cách giải này do đó sẽ chạy trong thời gian O( nC) và không gian O( nC), tuy ta có thể giảm độ phức tạp không gian xuống O( C) bằng một số sửa đổi nhỏ.

Thuật toán tham lam

Martello và Toth (1990) đã đưa ra một thuật toán gần đúng kiểu tham lam ( greedy approximation algorithm) để giải bài toán xếp ba lô. Giải thuật này sắp xếp các đồ vật theo thứ tự giảm dần về giá trị, sau đó theo thứ tự đó xếp các đồ vật vào ba lô cho đến khi không cho thêm được đồ vật nào vào nữa.

Nguồn: ThuVienToanHoc.Net

Phú Sĩ St

[Vy Vy]

Giới thiệu một số bài toán cổ - kỳ 3




Xin giới thiệu một bài toán rất quen thuộc và có rất nhiều ứng dụng trong đời sống, đó là bài toán Tháp Hà Nội. Bài toán tháp Hà Nội (tiếng Anh gọi là Tower of Hanoi hay Towers of Hanoi) xuất phát từ trò chơi đố Tháp Hà Nội.

Mục đích của bài toán là thực hiện được yêu cầu của trò chơi. Dạng bài toán thông dụng nhất là: "Người chơi được cho ba cái cọc và một số đĩa có kích thước khác nhau có thể cho vào các cọc này. Ban đầu sắp xếp các đĩa theo trật tự kích thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón. Người chơi phải di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc sau:

• một lần chỉ được di chuyển một đĩa
• một đĩa chỉ có thể được đặt lên một đĩa lớn hơn (không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất)".

Bài toán này có lời giải chính xác. Tuy nhiên các mở rộng cho trường hợp có nhiều hơn ba cọc cho đến nay vẫn chưa được giải cặn kẽ.
Cách giải

Đa số các trò chơi dạng này có 8 đĩa. Đối với người mới chơi thì có vẻ khó nhưng thật ra thuật giải của nó hết sức đơn giản.

Gợi ý lời giải cho 3 đĩa

Gợi ý lời giải cho 4 đĩa

Thuật giải đệ quy

• đặt tên các cọc là A, B, C -- những tên này có thể chuyển ở các bước khác nhau
• gọi n là tổng số đĩa
• đánh số đĩa từ 1 (nhỏ nhất, trên cùng) đến n (lớn nhất, dưới cùng)

Để chuyển n đĩa từ cọc A sang cọc B thì cần:

1. chuyển n-1 đĩa từ A sang C. Chỉ còn lại đĩa #n trên cọc A
2. chuyển đĩa #n từ A sang B
3. chuyển n-1 đĩa từ C sang B cho chúng nằm trên đĩa #n

Phương pháp trên được gọi là thuật giải đệ quy: để tiến hành bước 1 và 3, áp dụng lại thuật giải cho n-1. Toàn bộ quá trình là một số hữu hạn các bước, vì đến một lúc nào đó thuật giải sẽ áp dụng cho n = 1. Bước này chỉ đơn giản là chuyển một đĩa duy nhất từ cọc A sang cọc C.
Ngôn ngữ Pascal biểu diễn giải thuật trên là:

Giải thích thuật giải Sau đây là dạng dễ xem hơn của thuật giải này:

1. chuyển đĩa 1 sang cọc C
2. chuyển đĩa 2 sang cọc B
3. chuyển đĩa 1 từ C sang B sao cho nó nằm lên 2

Vậy ta hiện có 2 đĩa đã nằm trên cọc C, cọc B hiện thời trống

1. chuyển đĩa 3 sang cọc C
2. lặp lại 3 bước trên để chuyển 1 & 2 cho nằm lên 3

Mỗi lần dựng xong tháp từ đĩa i đến 1, chuyển đĩa i+1 từ cọc A là cọc xuất phát, rồi lại di chuyển tháp đã dựng lên đĩa i+1.
Giải thuật bằng biểu diễn nhị phân

Các vị trí đĩa có thể xác định được trực tiếp từ biểu diễn nhị phân của số thứ tự di chuyển (cơ số 2 với một chữ số cho mỗi đĩa) trong đó các dãy 1 và các dãy 0 tượng trưng cho các dãy các đĩa liền nhau trên cùng cọc, và mỗi khi chữ số có thay đổi thì đĩa kế tiếp sẽ dời sang trái hay phải một cọc (hay chuyển sang cọc ngoài cùng phía đối diện). Chữ số ở đầu đại diện cho đĩa lớn nhất và nếu là chữ số 0 thì có nghĩa là đĩa lớn nhất không dời khỏi cọc xuất phát và ngược lại. Đặt các chữ số 1 và 0 luân phiên bên dưới các chữ số của một bước chuyển cho phép biết được di chuyển theo một chiều khi nó hợp với chữ số của bước chuyển tại nơi chữ số thay đổi và theo chiều kia khi nó không hợp. Do đó bước chuyển 00000000... có nghĩa là đặt 8 đĩa lớn nhất lên cọc ban đầu, bước chuyển 11111111... có nghĩa là đặt chúng lên cọc cuối cùng, và bước chuyển 11011000... có hai đĩa lớn nhất trên cọc đích, đĩa tiếp theo trên cọc xuất phát, hai đĩa tiếp theo ở cọc trung gian, và ba đĩa tiếp theo nữa trên cọc xuất phát, bất kể có thêm bao nhiêu chữ số đại diện các đĩa nhỏ hơn. Ta có thể dễ dàng tính được các vị trí của các đĩa trong một bộ tám mươi đĩa sau một số các bước tiến, nếu giới hạn đủ lớn để chứa nó. Việc dùng phương pháp đệ quy cho trường hợp tám mươi đĩa như thế này có thể không thực tế.
Ứng dụng

Tháp Hà Nội là một bài toán thường được dùng để dạy về lập trình cơ bản. Một phiên bản bằng hình của bài toán này được lập trình trong chương trình soạn thảo emacs, có thể truy cập được bằng cách gõ M-x hanoi. Ngoài ra cũng có một thuật giải mẫu viết bằng ngôn ngữ Prolog.
Bài toán Tháp Hà Nội thường được dùng trong nghiên cứu tâm lý về cách giải quyết vấn đề. Cũng có những biến thể khác của bài toán này gọi là Tháp Luân Đôn dùng trong chuẩn đoán và điều trị thần kinh tâm lý đối với các chức năng thực hành.
Trường hợp bốn cọc trở lên

Mặc dù thuật giải tương đối đơn giản, bài toán với n đĩa sẽ cần ít nhất 2n-1 lần di chuyển. Tuy nhiên với số lượng Cọc nhiều hơn 3 thì vẫn chưa biết được sẽ cần ít nhất bao nhiêu lần di chuyển để giải bài toán. Do vậy việc áp dụng bước tiến dãy (tiếng Anh sequential advancement) để xác định vị trí của một số lượng lớn các đĩa trên ba cọc sau một số lớn tuỳ ý các bước tiến là không thực tế. Lời giải tối ưu cho bài toán Tháp Hà Nội với bốn cọc hay nhiều hơn vẫn còn là một bài toán mở. Đây là một ví dụ tiêu biểu cho thấy một bài toán đơn giản, có thể giải được vẫn có thể trở thành khó hơn rất nhiều bằng cách hơi nới lỏng một số ràng buộc của nó.
Mặc dù không biết được chính xác cần bao nhiêu lần di chuyển, có thể có một vài kết quả tiệm cận. Có một "lời giải được coi như tối ưu" có thể áp dụng một cách đệ quy để tìm một lời giải–xem giải thích cũng như một vài biến thể của bài toán bốn cọc trong bài khảo sát của Paul Stockmeyer (tiếng Anh).
Mặc dù với số đĩa nhỏ thử nghiệm trên máy tính thì "lời giải được coi như tối ưu" này là thực sự tối ưu, nhưng nó vẫn chưa có một chứng minh tổng quát để coi là thực sự tối ưu. Tuy nhiên, những kết quả nghiên cứu trong năm 2004 (tiếng Anh) đã cho thấy lời giải được coi như tối ưu phải nằm trong cùng độ lớn với lời giải tối ưu.

Nguồn: ThuVienToanHoc.Net

Phú Sĩ St