Chào các bạn. Trong bài giảng lần này, chúng ta sẽ đề cập đến cách giải quyết vấn đề.
Và chúng ta sẽ tìm hiểu vai trò của các cách tiếp cận khác nhau trong việc tìm lời giải cho các vấn đề.
Khi bạn nghĩ về một vấn đề,
cách tiếp cận là cách bạn biểu diễn nó.
Trong bài giảng trước, chúng ta đã nói về mô hình dãy núi.
Mô hình dãy núi là một cách biểu diễn
các lời giải theo trục ngang này
và giá trị của chúng theo trục đứng.
Đây là cách mô tả ẩn dụ
việc giải quyết một vấn đề diễn ra như thế nào.
Đó là tìm các điểm tốt nhất trên dãy núi này.
Bây giờ chúng ta sẽ chuẩn hóa định nghĩa này,
và một phần mục đích của bài giảng này là hiểu vấn đề một khoa học,
và rõ ràng hơn.
Vậy tôi sẽ chuyển hình ảnh ẩn dụ dãy núi này thành một mô hình chuẩn.
Chúng ta làm như thế nào?
Đầu tiên, chúng ta sẽ định nghĩa cách tiếp cận là gì.
Chúng ta phát biểu hình ảnh ẩn dụ này theo một cách toán học.
Cách tiếp cận là
biểu diễn toàn bộ các phương án có thể.
Giống như một cách mã hóa tập các lời giải của một bài toán.
Khi chúng ta đã mã hóa được tập hợp các phương án đó,
chúng ta sẽ tạo ra mô hình dãy núi bằng cách gán một giá trị nào đó cho mỗi phương án này.
Kết quả sẽ là một dãy núi như bạn đã thấy lúc trước.
Rất nhiều người trong chúng ta đã quen với các cách tiếp cận,
kể cả khi chúng ta không biết về nó.
Tôi sẽ đưa ra một vài ví dụ.
Bạn có nhớ toán sơ cấp không?
Chúng ta đã học về cách biểu diễn một điểm trên hệ trục tọa độ.
Có 2 cách biểu diễn cơ bản.
Cách thứ nhất là hệ tọa độ Descartes.
Cho một điểm, chúng ta biểu diễn nó bằng
2 giá trị X và Y trên mặt phẳng.
Chẳng hạn, đây là 5 đơn vị,
và điểm này có tọa độ là (5,2).
5 đơn vị theo chiều X và 2 đơn vị theo chiều Y.
Nhưng còn một cách biểu diễn khác,
đó là hệ tọa độ cực.
Chúng ta xem xét điểm này,
Bán kính R là khoảng cách từ gốc tọa độ tới điểm đó,
và một góc theta
biểu diễn chúng ta cần di chuyển một góc bao nhiêu
để chạm tới điểm đã mô tả.
Vậy có 2 cách biểu diễn một điểm.
X và Y, R và theta.
Descartes và hệ tọa độ cực.
Cách nào tốt hơn?
Câu trả lời là tùy trường hợp.
Tôi sẽ giải thích lí do.
Chẳng hạn, nếu tôi muốn biểu diễn đường này.
Khi đó, hệ tọa độ Descartes là lựa chọn tốt hơn,
vì tôi chỉ cần nói: Y = 3 và X từ 2 đến 5.
Rất đơn giản.
Nhưng nếu tôi cần mô tả cung này.
Trong trường hợp đó,
sử dụng hệ tọa độ Descartes trở nên khá phức tạp,
tốt hơn là nên dùng hệ tọa độ cực,
vì bán kính là cố định.
Và tôi chỉ cần cho bạn biết bán kính là bao nhiêu,
đây là khoảng cách R,
và góc theta dịch chuyển từ A đến B.
Như vậy, kết quả phụ thuộc vào cái tôi cần mô tả.
Nếu là một đường thẳng, tôi dùng hệ tọa độ Descartes.
Nếu là cung, tôi sẽ dùng hệ tọa độ cực.
Do đó, cách tiếp cận phụ thuộc vào bài toán.
Bây giờ, chúng ta sẽ giải thích
cách tiếp cận giúp chúng ta tìm lời giải của một bài toán như thế nào
và tại sao mà cách tiếp cận có thể giúp chúng ta tạo ra đột phá?
Trong lịch sử khoa học, có rất nhiều bước ngoặt:
Newton,
với thuyết vạn vật hấp dẫn
đó thực ra là những cách tiếp cận mới cho các vấn đề cũ.
Hãy lấy một ví dụ.
Mendeleev đã phát hiện ra bảng tuần hoàn,
và trong bảng tuần hoàn, ông biểu diễn các nguyên tố theo khối lượng nguyên tử.
Ông đã đặt chúng vào các cột khác nhau.
Bằng việc sắp xếp các nguyên tố theo khối lượng nguyên tử,
Mendeleev đã tìm ra các quy luật.
Tất cả kim loại nằm trên một cột, hay những thứ tương tự thế.
Hãy nhớ lại môn hóa học một chút nhé.
Bảng tuần hoàn thực chất là một cách tiếp cận: đó là một cách biểu diễn các nguyên tố.
Mendeleev có thể biểu diễn các nguyên tố theo thứ tự abc.
Nhưng cách này không có ý nghĩa gì.
Biểu diễn bằng thứ tự abc sẽ không cho biết một quy luật nào cả.
Trong khi biểu diễn bằng nguyên tử khối lại cho biết rất nhiều quy luật.
Thực tế, khi Mendeleev sắp xếp
tất cả các nguyên tố được phát hiện ra ở thời điểm đó theo nguyên tử khối,
có những ô bị bỏ trống.
Có một số nguyên tố bị thiếu.
Về sau, các nguyên tố mới được tìm thấy là Scandi, Galli, và Germani.
Chúng được tìm thấy sau 10 đến 15 năm sau,
sau khi ông đã hoàn thành bảng tuần hoàn.
Mọi người dựa vào đó và đã tìm ra các nguyên tố còn thiếu.
Cách tiếp cận theo nguyên tử khối
đã trở nên cực kì hiệu quả khi chúng ta nghiên cứu về nguyên tố hóa học.
Chúng ta sử dụng bảng tuần hoàn mọi lúc.
Khi bạn gặp một vấn đề,
bạn sẽ nhận ra bạn luôn sử dụng một vài cách tiếp cận để giải quyết nó.
Giả sử bạn muốn thuê một người vào công ty của bạn.
Bạn nhận được một chồng hồ sơ các ứng viên cho vị trí này.
Và bạn nghĩ,
tôi sẽ phân loại các ứng viên này ra sao?
Giả sử có tới 500 ứng viên.
Một phương án là bạn sắp xếp các hồ sơ theo điểm trung bình (GPA)
Lấy điểm trung bình từ cao xuống thấp.
Đó là một cách biểu diễn.
Bạn thường sử dụng cách này nếu bạn cần một người có năng lực.
Nhưng, bạn có thể lại cần người có kinh nghiệm.
Trong trường hợp đó, bạn có thể sắp xếp
chồng hồ sơ đó theo độ dày của chúng.
Những hồ sơ dày tương ứng với những người
đã trải qua rất nhiều công việc và có kinh nghiệm.
Bạn cũng có thể cần người có tính sáng tạo.
Vậy thì, bạn có thể đặt những hồ sơ sáng tạo nhất sang một bên,
và những hồ sơ kém sáng tạo hơn sang một bên khác.
Đây là cách thứ ba để phân loại hồ sơ.
Phụ thuộc vào nhu cầu tuyển dụng của bạn,
phụ thuộc vào các ứng viên,
bất kì ai cũng có thể trở thành vị trí mà bạn mong muốn.
Vấn đề là cách tổ chức và phân loại hồ sơ.
Với mỗi cách sắp xếp,
thực chất đó là một cách tiếp cận.
Và cách tiếp cận sẽ quyết định độ khó của vấn đề bạn cần giải quyết.
Để tôi giải thích một chút.
Hãy quay lại hình ảnh ẩn dụ về dãy núi.
Khi dãy núi trở nên mấp mô,
ý tôi là nó không chỉ có duy nhất một đỉnh
mà có rất nhiều đỉnh.
Bây giờ tôi sẽ chuẩn hóa khái niệm về đỉnh.
Tôi làm như sau:
Tôi sẽ định nghĩa cực đại địa phương.
Cực đại địa phương là một điểm,
mà lân cận của điểm này
có giá trị thấp hơn nó.
Cơ bản đó là một điểm có giá trị cục bộ là lớn nhất.
Quay lại ví dụ về dãy núi,
có 3 cực đại địa phương: 1, 2 và 3.
Tại bất kì điểm nào trong số 3 điểm này, tôi rơi vào bế tắc.
Phía bên trái hay bên phải
đều không cho kết quả tốt hơn.
Vậy thì, một cách tiếp cận tốt
sẽ không có quá nhiều cực đại địa phương.
Và ngược lại, một cách tiếp cận tồi sẽ sinh ra rất nhiều cực đại địa phương.
Tôi sẽ đưa ra một ví dụ.
Giả sử tôi cần lựa chọn sản xuất một loại kẹo.
Nhiệm vụ của tôi là sản xuất một loại kẹo mới.
Đội đầu bếp đã chế biến được rất nhiều mẫu khác nhau,
và tôi cần lựa chọn mẫu tốt nhất.
Tuy nhiên, có rất nhiều khả năng xảy ra,
đến mức tôi không biết phải tiếp cận theo cách nào.
Một phương án có thể là sắp xếp các thanh kẹo theo lượng calo.
Sắp xếp các thanh kẹo theo hàm lượng calo có trong chúng.
Theo cách này, có thể tôi có 3 cực đại địa phương.
Cách tiếp cận này khá hợp lí.
Nhưng cũng có thể, tôi sẽ sắp xếp các thanh kẹo
theo thời gian mà tôi nhai chúng.
Thanh này có thể mất 2 phút để nhai,
và thanh kia có thể mất tới 20 phút.
Sử dụng thời gian nhai kẹo để phân loại có thể không phải cách tốt nhất.
Kết quả là, mô hình dãy núi tôi nhận được có nhiều đỉnh hơn.
Nhiều đỉnh hơn, tức là tôi sẽ gặp khó khăn hơn trong khi lựa chọn.
Đó không phải một cách biểu diễn lời giải tốt
Vậy cách tiếp cận này không thực sự tốt.
Cách lí tưởng nhất sẽ là một mô hình chúng ta gọi là Đỉnh Phú Sĩ.
Duy nhất chỉ có một đỉnh.
Và dãy núi này được gọi là Núi Phú Sĩ.
Nếu bạn đã từng đến Nhật Bản,
bạn sẽ trông thấy hình ảnh đỉnh Phú Sĩ rất giống như thế này.
Thực ra cũng không hẳn, trên đỉnh còn có tuyết.
Nhưng hình dáng nói chung là một mũi nhọn.
Nếu mô hình của bạn có dạng núi Phú Sĩ,
và nếu bạn đang đừng tại một điểm,
bạn chỉ cần leo lên theo một đường sẽ hướng tới đỉnh núi.
Một dãy núi có duy nhất một đỉnh, tuyệt vời
bởi vì vấn đề bạn cần giải quyết
trở nên cực kì đơn giản.
Tôi sẽ lấy một ví dụ nổi tiếng.
Ví dụ này xuất phát từ lí thuyết quản lý theo khoa học (hay chủ nghĩa Taylor)
do Frederick Taylor xây dựng nên.
Taylor đã giải quyết vấn đề về việc tính toán kích thước tối ưu của chiếc xẻng xúc than.
Hãy nghĩ đến mô hình dãy núi mô tả kích thước xẻng.
Theo trục này là kích thước.
Và trục này là giá trị.
Giá trị ở đây là gì?
Không phải theo việc tôi sẽ bán được chiếc xẻng với giá bao nhiêu
mà là năng suất mà chiếc xẻng có thể tạo ra.
Giả sử chúng ta có một chiếc xẻng xúc than,
hãy nghĩ
với chiếc xẻng đó, một người có thể xúc được bao nhiêu kg than một ngày?
Đây là hàm biểu diễn kích thước chiếc xẻng.
Xuất phát từ điểm 0.
Đây là kích thước của lòng xẻng.
Nếu lòng xẻng có kích thước là 0,
(chúng ta thường quen gọi nó là cái gậy)
chúng ta không thể xúc được than.
Một cái gậy không thể làm được gì trong trường hợp này.
Nếu như tôi làm cho lòng xẻng to hơn,
chẳng hạn như bằng kích thước của một chiếc thìa,
chúng ta có thể xúc được một ít.
Nếu chiếc xẻng càng ngày càng to ra,
công nhân của tôi sẽ xúc được nhiều than hơn.
Nhưng, đến một điểm nào đó, chiếc xẻng trở nên quá to
và quá nặng.
Công nhân sẽ cảm thấy mệt mỏi
và năng suất sẽ giảm.
Tiếp tục, năng suất càng ngày càng giảm
cho đến khi chiếc xẻng trở nên quá to và quá nặng
đến mức công nhân không thể nhấc nổi nó lên.
nó cũng sẽ vô dụng như chiếc gậy vậy.
Vậy nếu tôi chọn lượng than xúc được làm hàm biểu diễn kích thước của chiếc xẻng,
tôi sẽ có mô hình núi Phú Sĩ, có duy nhất một đỉnh.
Thật đơn giản để giải quyết vấn đề.
Vậy nếu như chúng ta có thể mô tả các vấn đề khoa học theo cách này,
hoặc chúng ta có thể biểu diễn các vấn đề mang tính kĩ thuật theo cách này, rồi leo dần lên đỉnh,
về cơ bản được gọi là Chủ nghĩa Taylor.
Ý tưởng là
tìm ra các cực đại địa phương trên mô hình dãy núi.
để tìm các lời giải tối ưu.
Chúng ta chỉ có thể chắc chắn tìm ra đáp số tối ưu
nếu chỉ có duy nhất một đỉnh trên mô hình dãy núi này.
Nếu nó trông gồ ghề như thế này,
Nếu mô hình giống như núi Phú Sĩ, cách tiếp cận của bạn là tốt.
Nếu mô hình trở nên gồ ghề như thế này
thì do bạn đã có một cách tiếp cận tồi,
khi đó, nếu bạn leo lên đỉnh,
bạn có thể gặp bế tắc ở bất kì chỗ nào.
Tất nhiên, bạn sẽ mong muốn một mô hình như núi Phú Sĩ,
trong trường hợp như cái xẻng này, mọi chuyện rất đơn giản.
Tôi sẽ đưa ra thêm một ví dụ nữa.
Một ví dụ rất thú vị.
Đây là trò chơi tôi yêu thích có tên gọi “Tổng 15”
do Herb Simon phát triển.
Ông từng đoạt giải Nobel về kinh tế.
“Tổng 15” được đưa ra để chứng tỏ
vai trò của cách tiếp cận có ích lợi như thế nào,
tại sao có những cách tiếp cận làm vấn đề trở nên đơn giản
như đỉnh Phú Sĩ
hoặc có những cách làm vấn đề trở nên phức tạp.
Trò chơi “Tổng 15” diễn ra như sau:
Có 9 quân bài từ 1 đến 9 được đặt trên bàn.
9 quân bài trước mặt bạn.
Có 2 người chơi.
Họ luân phiên nhau lấy từng quân bài,
cho đến khi không còn quân bài nào, nhưng trò chơi có thể kết thúc sớm hơn.
Bất cứ lúc nào một người kết thúc lượt của mình, nếu người đó cầm trên tay 3 quân bài có tổng đúng bằng 15, anh ta thắng.
Luật chơi rất đơn giản.
9 quân bài. Lấy luân phiên.
3 quân có tổng bằng 15 là thắng.
Tôi sẽ minh họa một lần chơi
giữa 2 người
ta gọi họ là Paul và David.
Paul chơi trước. Bạn thường nghĩ rằng
chọn quân số 5 sẽ là lí tưởng để bắt đầu.
Nhưng Paul đưa ra một quyết định kì lạ. Cậu chọn quân bài 4.
Đến lượt David, cậu chọn 5.
Paul lấy quân 6.
Thật là lạ,
bởi 4 + 5 + 6 = 15 (trong khi 5 đã thuộc về David)
Có vẻ như không còn cách nào để Paul thắng.
David cảm thấy khó hiểu.
Cậu lấy quân 8.
Để ý rằng 2 + 5 + 8 = 15,
nên Paul phải lấy quân 2.
Anh ta đã lấy quân 2.
Chuyện gì xảy ra tiếp theo?
2 + 4 = 6
nên David sẽ thua nếu cậu không lấy quân 9.
Nhưng 2 + 6 = 8
nên David sẽ thua nếu cậu không lấy quân 7.
Vậy là Paul thắng
bất chấp lựa chọn của David ở lượt kế tiếp.
Thật khó hiểu, phải không?
Khi người thiết kế trò chơi là một người đã đoạt giải Nobel,
bạn có thể tưởng tượng sẽ có rất nhiều chiến thuật trong trò chơi này.
Bây giờ tôi sẽ đưa ra một cách tiếp cận khác đối với trò chơi này.
Bạn còn nhớ ma phương trong toán lớp bảy không?
Tổng các dòng bằng 15.
8+3+4, 1+5+9, 6+7+2
Các cột cũng vậy.
8+1+6=15
3+5+7=15.
và cả đường chéo cũng vậy.
8 + 5 + 2 = 15.
6 + 5 + 4 = 15.
Tổng mỗi dòng, cột hay đường chéo đều là 15.
Bây giờ chúng ta sẽ chơi lại trò chơi kia trên Ma phương,
một cách tiếp cận khác của “Tổng 15”
Paul chơi trước, cậu chọn 4.
David chọn 5.
Paul chọn 6, khá kì lạ vì có vẻ như cậu không thể thắng.
David chọn 8, Paul chặn bằng việc chọn 2.
Kết quả là Paul thắng bất kể David chọn 7 hay 9 ở lượt kế tiếp.
Trò chơi này là gì?
Đúng vậy, Tic-tac-toe (ND: một phiên bản của cờ Caro trên bàn cờ có kích thước bị giới hạn)
“Tổng 15” chẳng qua chỉ là Tic-tac-toe
trên một cách tiếp cận khác.
Vậy nếu bạn biến đổi “Tổng 15”,
di chuyển các quân bài để tạo thành một ma phương
việc bạn làm là việc tạo là một mô hình núi Phú Sĩ,
làm vấn đề trở nên rất đơn giản.
Rất nhiều đột phá,
như bảng tuần hoàn,
Thuyết vạn vật hấp dẫn,
đó là những cách tiếp cận vấn đề
biến những thứ phức tạp và khó mường tượng
trở nên cực kì đơn giản và có ý nghĩa,
để dễ dàng tìm ra lời giải.
Định lí sau đây được gọi là Savant Existance Theoem.
Với mỗi bài toán,
tồn tại cách biểu diễn
sao cho nó trông giống một đỉnh Phú Sĩ.
Tại sao lại như vậy?
Thực ra chứng minh khá là đơn giản.
Tất cả những gì bạn phải làm là,
nếu bạn đã biểu diễn tập các lời giải như thế này
bạn chỉ cần đặt cái tốt nhất vào giữa.
Những cái tồi nhất ra hai đầu
và sắp xếp phần còn lại vào các khoảng trống còn lại
để tạo ra một đỉnh Phú Sĩ.
Rất rõ ràng phải không.
Vấn đề là, để tạo ra được một núi Phú Sĩ,
bạn cần phải biết được toàn bộ các lời giải trước đó.
Phương án này rõ ràng là không khả thi
nhưng nó chứng tỏ rằng luôn có cách sắp xếp như vậy.
Tức là luôn có một khả năng
một ai đó nhìn vào một vấn đề cụ thể và nói
“Nếu tôi tiếp cận được bài toán theo cách này thì sao?”
Và có thể cách giải đấy sẽ biến một mô hình dãy núi gồ ghề
thành một mô hình có dạng đỉnh Phú Sĩ.
Vấn đề nằm ở chỗ
có quá nhiều cách tiếp cận tồi.
Luôn có cách tiếp cận tạo ra đỉnh Phú Sĩ,
nhưng cũng có rất nhiều cách tiếp cận tồi tệ.
Giả sử rằng tôi có 10 phương án
và tôi cần xác định có bao nhiêu cách đặt chúng trên mô hình dãy núi
10 chỗ trống lúc đầu
9 chỗ trống cho cái thứ 2,
8 chỗ cho cái thứ 3, v.v
Tức là có 10 giai thừa, xấp xỉ 3,6 triệu cách tiếp cận
mà phần lớn là kém hiệu quả.
Chúng không biểu diễn tập phương án theo một cách hữu ích.
Chỉ một vài cách tiếp cận có thể tạo ra đỉnh Phú Sĩ.
Chúng ta hãy nghĩ về giá trị của các cách tiếp cận, chúng ta sẽ nhận thấy:
Luôn luôn có những cách tiếp cận hiệu quả
mà những người thông minh có thể nghĩ ra,
chúng thực sự là các cách tiếp cận tốt cho các vấn đề
làm mô hình dãy núi trở nên bớt gồ ghề.
Nếu chúng ta chỉ tiếp cận theo một cách ngẫu nhiên,
mô hình dãy núi nhận được nói chung là rất gồ ghề,
làm chúng ta bế tắc ở bất cứ chỗ nào.
Theo cách đó, chúng ta sẽ không thể tìm ra lời giải.
Chúng ta sẽ đương đầu với những mô hình gồ ghề
với vô số vô số đỉnh.
Bây giờ, hãy suy nghĩ xem, làm sao tìm ra được một lời giải tốt trên những mô hình gồ ghề này?
Khi đã đứng tại một điểm, bạn tìm đến điểm tốt hơn bằng cách nào?
Có phương án nào khác ngoài “leo đồi” không?
Bởi vì “leo đồi” thực chất chỉ hữu ích trên không gian một chiều.
Nếu có nhiều chiều hơn thì sao?
Tôi sẽ phải làm như thế nào.
Vậy chúng ta học được gì từ bài giảng này?
Thứ nhất, khi chúng ta tìm cách giải quyết một vấn đề,
khi chúng ta mã hóa nó theo một cách nào đó,
đây là một cách tiếp cận.
Một cách tiếp cận sẽ tạo ra cực đại địa phương.
Cách tiếp cận tốt sẽ có ít cực đại địa phương.
Cách tồi hơn sẽ có nhiều cực đại địa phương hơn.
Số lượng cách tiếp cận cho một vấn đề
có thể lên tới hàng tỉ.
Bởi vì có hàng tỉ cách tiếp cận,
phần đông tỏ ra không thực sự hiệu quả.
Một vài cách tiếp cận biến bài toán thành một mô hình núi Phú Sĩ.
Đôi khi, chỉ có thiên tài
như Newton hay Mendeleev
mới có thể tìm ra cách tiếp cận
biến một mô hình phức tạp, gồ ghề
thành một đỉnh Phú Sĩ.
Trong những trường hợp khác, chẳng hạn như bài toán về kích thước xẻng,
hẳn nhiều người có thể tìm ra cách tiếp cận
để bài toán trở thành một đỉnh Phú Sĩ.
Điểm mấu chốt là:
Khi chúng ta giải quyết một bài toán, đầu tiên hãy mô tả nó.
Chúng ta sẽ có một số cách tiếp cận vấn đề.
Cách mô tả sẽ quyết định độ khó của bài toán.
Nếu có thể biểu diễn được bài toán thành đỉnh Phú Sĩ, bài toán sẽ là đơn giản.
Nếu nó trở nên mấp mô,
vấn đề có lẽ khá phức tạp.
Trong bài giảng tiếp theo,
chúng ta sẽ đề cập đến việc
một khi chúng ta đã có mô hình dãy núi này,
làm cách nào để tìm kiếm phương án tối ưu trên mô hình đó?
Chúng ta đã từng đề cập đến “leo đồi”
nhưng cũng có rất nhiều cách để bạn có thể leo.
Và đó là vấn đề chúng ta sẽ đề cập trong bài kế tiếp: hàm đánh giá kinh nghiệm được sử dụng trên mô hình dãy núi.
Cảm ơn các bạn đã theo dõi.