Gửi bởi
huybaichay
Để làm rõ hơn về sai số trong các phần mềm, mình xin viết tiếp.
Bạn NhimBong đã có những câu hỏi rất hay, mình xin viết thêm để mọi người có thể hiểu thêm về nghề IT nói chung, cũng như các software dùng trong cờ nói riêng, và từ đó có quan điểm riêng của mỗi người.
Máy tính là vật vô tri vô giác, nó không hiểu những định nghĩa mà chỉ con người hiểu được, muốn tính toán, muốn chạy, máy phải có các tập lệnh cơ bản, định nghĩa cơ bản do con người nhập vào, ví dụ, con người định nghĩa 1+1=2, thì máy dựa vào đó, nó làm phép tính rất nhanh, nhưng cách tính, phương pháp tính, thì lại do con người định nghĩa. Nếu định nghĩa 1+1=3, máy vẫn tính rất nhanh, nhưng lúc này rõ ràng máy tính sai, vì đầu vào, input do con người đưa vào.
Trở lại bài toán lập lịch, vì sao thế giới đã chứng minh nó không có lời giải tối ưu, mà chỉ có lời giải gần đúng(heuristic), chúng ta hãy đi vào ví dụ bài toán cụ thể sau:
Một trường trung học cs có lịch sử dụng phòng máy vi tính như sau(chỉ có 1 phòng duy nhất tên là C1)
Điều kiện 1) Cô Nga dạy các học sinh lớp 6 vào sáng thứ 2,4,6 tại phòng C1
Điều kiện 2) Cô Bình dạy các học sinh lớp 6 khác vào sáng thứ 3,5,7 tại phòng C1
Với N=2, có 2 điều kiện đầu vào, rõ ràng, máy giải quyết êm ru, lúc này, bài toán có lời giải, lập trình viên định nghĩa cho máy các khái niệm C1, thứ 2,3,4....cô Nga, cô Bình, lớp 6, máy dựa vào đó giải lần lượt các yêu cầu cho cô Nga trước, cô Bình sau, đáp án ra chính xác 100%.
Bây giờ ta thêm điều kiện 3, N=3
Điều kiện 3) Cô Linh muốn dùng phòng C1 vào các buổi sáng cho các lớp 9 vào các ngày trong tuần.
Lúc này, chắc chúng ta dễ hình dung được, rõ ràng khi N tăng, điều kiện 3 sẽ xung đột với điều kiện 2, đáp ứng điều kiện 1,2 thì chắc chắn điều kiện 3 không thể xảy ra được, còn đáp ứng điều kiện 3 thì điều kiện 1,2 không thể sắp xếp, Lúc này bài toán không có lời giải tối ưu, mà chỉ có lời giải gần đúng.
Lời giải gần đúng, tùy từng phần mềm, tùy từng lập trình viên, và tùy từng điều kiện thực tế cuộc sống, mà người ta ưu tiên các điều kiện, ví dụ lớp 9 cuối cấp, 3 năm các em chưa được dùng phòng máy, thì ưu tiên các em trước chẳng hạn, lúc này lập trình viên phải thiết kế phần mềm, thiết kế phương pháp tính, đưa điều kiện 3 lên trước để ưu tiên, hoặc có trường lại yêu cầu lập trình viên phải ưu tiên khối 6 trước, hoặc có trường lại yêu cầu làm ngẫu nhiên, một nửa trong tuần ưu tiên khối 6, một nửa sau ưu tiên khối 9. Rồi lại ngẫu nhiên các lớp trong các khối.
Ví dụ trên cho thấy, khi N càng lớn, xác suất mâu thuẫn và xung đột giữa các điều kiện càng lớn, phần mềm chỉ giải quyết được tỷ lê % nào đó, còn lại, phần mềm buộc phải không thỏa mãn, và tồn tại sai số, bởi bản chất của nó là không có lời giải tối ưu.
Quay trở lại bài toán lập lịch thi đấu cho cờ tướng, N có các điều kiện sau
1) Không ai gặp nhau quá 1 lần
2) Gặp nhau theo nhóm điểm, nếu lẻ sẽ gặp nhóm điểm dưới
3) Các kỳ thủ trong đội, cùng địa phương, hoặc anh em họ hàng không gặp nhau
4) Không ai đi tiên quá 2 ván
5) Không ai đi hậu quá 2 ván
6) ......
Rõ ràng lúc này, sẽ là tuyệt vời, nếu 6 điều kiện trên không mâu thuẫn nhau, tức nó không phụ thuộc nhau, nhưng rõ ràng, do chúng ta không tính hết được các khả năng tổ hợp các xác suất mâu thuẫn nhau, lúc này, ví dụ do để đảm bảo điều kiện 1,2,3 xảy ra, thì phải hi sinh điều kiện 4,5, bài toán lúc này là cách giải gần đúng, và máy tính phần mềm buộc phải dùng cách giải gần đúng mà chuyên ngành bọn em gọi là giải thuật heuristic. Tức là chọn cách giải sao cho thỏa mãn nhiều điều kiện nhất, và chấp nhận không thỏa mãn các điều kiện còn lại.
Như ví dụ NhimBong đưa ra, phần mềm, vốn do con người định nghĩa, chấp nhận có sai sót, vì bài toán không có lời giải tối ưu.
Em ví dụ thêm về giải thuật gần đúng áp dụng trong cuộc sống đời thường, các bác vẫn hay áp dụng mà không biết tên gọi của nó, ví dụ các bác cần đi từ điểm A đến điểm B, thường các bác ước lượng và chọn đường gần nhất, có thể nó không chính xác, vì chẳng ai đo, nhưng nó gần đúng nhất, hoặc trong việc chọn đối tác làm ăn, chọn bạn đời, chọn người yêu, chọn nghề, chọn nước đi chính xác trong cờ, không thể tính hết được các biến, chúng ta chọn cách gần đúng với những bài toán khá phức tạp, và chấp nhận sai sót các điều kiện còn lại. Ví dụ đường gần nhất thì lại kẹt xe, cô người yêu xinh nhưng lại lười, công việc tốt nhưng gặp ông sếp dở hơi :D
Em xin hết.
