Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
PROFESSOR
All right.
Được rồi.
OK. Giant slides — check. Students — check. OK.
OK. Slide khổng lồ, xong. Sinh viên, xong. OK.
How is everybody?
Mọi người khỏe không?
STUDENT
Good.
Khỏe ạ.
PROFESSOR
Good. It's the post-lunch lecture slot. OK. Today we're going to talk about constraint satisfaction problems or CSPs, as we lovingly call them for short.
Tốt. Đây là tiết học sau bữa trưa. OK. Hôm nay chúng ta sẽ nói về các bài toán thỏa mãn ràng buộc, hay CSP, cái tên thân thương mà ta hay gọi cho ngắn.
So far, we've been talking about search, and we can ask, what's search for? Search is for a very particular class of problems.
Từ đầu đến giờ ta nói về tìm kiếm, và ta có thể hỏi: tìm kiếm dùng để làm gì? Tìm kiếm dành cho một lớp bài toán rất cụ thể.
When you have a problem that can be formulated in that way, search is an algorithm you can use to solve your problem.
Khi bài toán của bạn có thể được biểu diễn theo cách đó, tìm kiếm là thuật toán bạn có thể dùng để giải.
But in order to apply search, it's going to make certain assumptions about the world. It's going to assume that there's just one agent. That's you.
Nhưng để áp dụng tìm kiếm, ta phải đưa ra một số giả định về thế giới. Ta giả định chỉ có một tác tử. Đó là bạn.
You're making your plan, but there's no other agents whose actions can be uncertain or adversarial. It means the world is deterministic.
Bạn lập kế hoạch của mình, nhưng không có tác tử nào khác mà hành động của họ có thể không chắc chắn hay đối kháng. Nghĩa là thế giới có tính xác định.
You have to be able to assume that the plan you've come up with — your master plan — when executed, will go exactly the way it worked, according to your model.
Bạn phải giả định rằng kế hoạch bạn nghĩ ra, kế hoạch tổng thể của bạn, khi thực thi sẽ diễn ra đúng như vậy, theo mô hình của bạn.
That means your model has to be correct and the world has to be deterministic. It also assumes that you're in a fully observed state.
Tức là mô hình phải đúng và thế giới phải có tính xác định. Nó cũng giả định bạn ở trạng thái quan sát đầy đủ.
So you know the way the world is now, and so you can predict in simulation how it will evolve when you model it, and then you have your plan, and you can go execute it.
Bạn biết thế giới hiện giờ ra sao, nên bạn có thể mô phỏng và dự đoán nó sẽ tiến triển thế nào theo mô hình, rồi bạn có kế hoạch và đi thực thi nó.
It also assumes that your state space is discrete.
Nó cũng giả định không gian trạng thái là rời rạc.
So these are all simplifications, and during this semester, we're going to unpack and relax some of these, and show how we can come up with new algorithms when the world isn't quite so single agent deterministic, fully observed, and discrete as we may like.
Đây đều là những sự đơn giản hóa, và trong học kỳ này, ta sẽ phân tích và nới lỏng một số giả định đó, và xem cách tạo ra thuật toán mới khi thế giới không đơn giản như ta mong muốn: một tác tử, xác định, quan sát đầy đủ và rời rạc.
Search in general, so far, has been for a class of search problems that are called planning problems. And in a planning problem, what you're interested in is the sequence of actions.
Tìm kiếm cho đến giờ nói chung là dành cho một lớp bài toán tìm kiếm gọi là bài toán lập kế hoạch. Trong bài toán lập kế hoạch, thứ bạn quan tâm là chuỗi hành động.
When you find your goal state, what you really want to know is what is that master plan that gets me from the start state to the goal?
Khi tìm được trạng thái đích, điều bạn thật sự muốn biết là kế hoạch tổng thể nào đưa tôi từ trạng thái đầu đến đích?
And so the path to the goal is the important thing, and this gets us into discussions of things like paths having costs and depths.
Vì vậy đường đi đến đích là điều quan trọng, và dẫn ta đến việc bàn về đường đi có chi phí và độ sâu.
You either want a cheap path or maybe a short path, and the way that you inject information about a particular search problem, as opposed to just a black box uninformed search procedure is through heuristics, which sort of give a little bit of a certain kind of a hint to the problem.
Bạn muốn đường đi rẻ, hoặc có thể là ngắn, và cách bạn đưa thông tin về một bài toán tìm kiếm cụ thể vào, thay vì chỉ dùng thủ tục tìm kiếm mù như hộp đen, là thông qua hàm heuristic, nó đưa ra một chút gợi ý nào đó cho bài toán.
It says, hey, the goals may be over this way. You're headed in the wrong direction.
Nó nói: này, đích có thể nằm về phía này. Bạn đang đi sai hướng.
And that's a way to take this fully generic notion of a search problem and inject a little bit of bias that helps you solve your problem better because you know something about it, maybe because it's embedded in space or something like that.
Đó là cách lấy khái niệm bài toán tìm kiếm hoàn toàn tổng quát và thêm vào một chút thiên lệch giúp giải bài toán tốt hơn vì bạn biết đôi điều về nó, có thể vì nó nằm trong không gian hay điều gì đó tương tự.
And here in the illustration, you can imagine this ninja robot who's trying to steal the gem.
Và trong hình minh họa này, bạn có thể hình dung robot ninja đang cố đánh cắp viên ngọc.
And what the ninja robot really wants to do is figure out what is the complex, precise sequence of actions which will get me through the maze of security into that gym.
Điều robot ninja thật sự muốn làm là tìm ra chuỗi hành động phức tạp, chính xác nào sẽ đưa nó qua mê cung an ninh để vào được căn phòng đó.
But there's another class of search problems, as well, and these are the identification problems. These problems usually take the form of an assignment of values to variables.
Nhưng còn một lớp bài toán tìm kiếm khác, đó là các bài toán nhận dạng (identification). Các bài toán này thường có dạng gán giá trị cho các biến.
And in identification problems, you're not really so concerned with how long the solution is. In general, they're all the same length because all the variables get an assignment.
Và trong bài toán nhận dạng, bạn không quá quan tâm lời giải dài bao nhiêu. Nhìn chung chúng đều dài như nhau vì mọi biến đều được gán giá trị.
And you're not concerned with the path. You're not concerned with how you came up with this assignment. You just want to know the assignment itself. And CSPs are a special class of identification problems.
Và bạn không quan tâm đến đường đi. Bạn không quan tâm mình tìm ra phép gán đó bằng cách nào. Bạn chỉ muốn biết bản thân phép gán. CSP là một lớp đặc biệt của bài toán nhận dạng.
And because they're a special class of identification problems, we have new algorithms that let us exploit the fact that instead of a black box search procedure, where all you really get to know is a successor function and a goal test and maybe some costs, now, suddenly we're going to have a little bit of visibility into the CSP, and that little bit of visibility is going to let us tailor algorithms that
Và vì là một lớp đặc biệt của bài toán nhận dạng, ta có các thuật toán mới tận dụng được thực tế rằng thay vì tìm kiếm hộp đen, nơi bạn chỉ biết hàm sinh trạng thái kế tiếp, kiểm tra đích và có thể là chi phí, thì giờ đây ta có thể nhìn thấy phần nào bên trong CSP, và chút khả năng nhìn thấy đó cho phép ta thiết kế thuật toán
are more efficient because we can make more assumptions about the problem.
hiệu quả hơn vì ta có thể đưa ra nhiều giả định hơn về bài toán.
So in this case, you might have the detective robot who comes to the scene and needs to figure out what's going on, but it's not so important which rug he looks under first.
Ở đây bạn có thể có robot thám tử đến hiện trường và cần tìm ra chuyện gì đang xảy ra, nhưng nó nhìn dưới tấm thảm nào trước không quan trọng.
He just wants to know what is the explanation for everything I'm seeing, and that might be a case of an identification problem.
Nó chỉ muốn biết lời giải thích cho mọi thứ nó thấy, và đó có thể là một trường hợp của bài toán nhận dạng.
It's also very common in identification problems that paths are all at the same depth. And that means it's going to totally change our outlook on things like breadth first versus depth first search.
Trong bài toán nhận dạng cũng rất phổ biến là các đường đi đều có cùng độ sâu. Và điều đó sẽ thay đổi hoàn toàn cách nhìn của ta về tìm kiếm theo chiều rộng so với theo chiều sâu. tìm kiếm đầu tiên.
So let's talk about CSPs. What we're going to do today is we're going to define them.
Vậy hãy nói về CSP. Hôm nay ta sẽ định nghĩa chúng.
We're going to see some examples that sort of stretch different sides of CSPs, and then we're going to talk about algorithms for solving them.
Ta sẽ xem vài ví dụ cho thấy nhiều khía cạnh khác nhau của CSP, rồi nói về các thuật toán để giải chúng.
And just like in search, there are different algorithms for solving them that are going to have trade-offs between various kinds of computation and efficiency.
Và giống như tìm kiếm, có nhiều thuật toán khác nhau để giải chúng, với những đánh đổi giữa các loại tính toán và hiệu quả.
One of the running problems we're going to have is map coloring. So how many people have seen map coloring in some class somewhere? OK. It's pretty intuitive.
Một bài toán ta sẽ dùng xuyên suốt là tô màu bản đồ. Có bao nhiêu bạn đã thấy bài toán tô màu bản đồ trong lớp nào đó chưa? OK. Khá trực quan.
You're going to have a map. There's no colors. You want to put colors on the countries, and it's really, really bad if two adjacent countries have the same color, right?
Các em có một tấm bản đồ. Chưa có màu nào cả. Mình muốn tô màu cho các quốc gia, và sẽ rất tệ nếu hai quốc gia kề nhau có cùng một màu, đúng không?
It's like crossing the streams. You don't do it. And so we're going to have constraints that say, don't do that, and we're going to work through that as an example.
Giống như "băng qua các luồng" vậy. Không được làm thế. Vậy nên ta sẽ có các ràng buộc nói rằng đừng làm thế, và ta sẽ đi qua ví dụ này.
It's certainly not the only CSP, so don't go thinking that all the CSPs in the world involve colors and inequality constraints. OK.
Tất nhiên đây không phải CSP duy nhất, đừng nghĩ rằng mọi CSP trên đời đều liên quan đến màu sắc và ràng buộc khác nhau. OK.
So let's talk about how CSPs are different from a standard search problem. Remember in a search problem, as I said, a state is a black box. It's some data structure.
Giờ ta xem CSP khác với một bài toán tìm kiếm chuẩn ở điểm nào. Nhớ rằng trong bài toán tìm kiếm, như thầy đã nói, một trạng thái là một hộp đen. Nó là một cấu trúc dữ liệu nào đó.
Who knows what it is? You'll see this in your projects. You can't look into the state — oh, there's a hash table and I can look up the values.
Ai biết bên trong là gì? Các em sẽ thấy điều này trong các project. Em không thể nhìn vào trạng thái, kiểu "à, có một bảng băm và mình tra cứu các giá trị".
You don't get any of that. The only thing you can do on a state is what? You can call get successor and you can call is goal, and that's it.
Không có chuyện đó. Vậy em chỉ làm được gì với một trạng thái? Em gọi được get successor và is goal, chỉ vậy thôi.
That's your whole API, and whatever is behind that search abstraction — no idea.
Đó là toàn bộ API, còn đằng sau phần trừu tượng hóa tìm kiếm đó là gì thì không biết.
And that abstraction is powerful, but it's limiting because the successor function can be anything and the goal test can be any function over states. So you can think of this like a judge.
Phần trừu tượng này mạnh, nhưng cũng hạn chế vì hàm kế tiếp có thể là bất cứ thứ gì và phép kiểm tra đích có thể là bất kỳ hàm nào trên các trạng thái. Các em có thể xem nó như một vị thẩm phán.
These search states come along the conveyor belt and the judge is like, not a goal, not a goal, not a goal, goal, right? And that's all you have.
Các trạng thái tìm kiếm chạy qua băng chuyền và thẩm phán nói: không phải đích, không phải, không phải, đích, đúng không? Và đó là tất cả những gì em có.
You can present a complete plan to the judge, and you either get told, yup, that's a goal, or no, that's not.
Em có thể đưa một kế hoạch hoàn chỉnh cho thẩm phán, và được báo là đúng, đó là đích, hoặc không, không phải.
In a CSP, we've got some structure, and the structure is the hook that lets us have better algorithms. And in that structure, we assume it's not just a black box in our state.
Trong CSP, ta có một cấu trúc, và cấu trúc đó là điểm mấu chốt giúp ta có các thuật toán tốt hơn. Và trong cấu trúc đó, ta giả sử trạng thái không chỉ là một hộp đen.
In a CSP, you have a set of variables, often called x sub i. And each variable has values that come from a domain. Sometimes the domain varies by i, and that's a domain, d.
Trong CSP, có một tập các biến, thường gọi là x chỉ số i. Mỗi biến có các giá trị lấy từ một miền giá trị. Đôi khi miền thay đổi theo i, và đó là miền D.
And so each of these variables takes on a value, and you can talk about an assignment of values in the domain to the variables. That's your state.
Mỗi biến nhận một giá trị, và ta có thể nói về một phép gán các giá trị trong miền cho các biến. Đó chính là trạng thái của ta.
So successor functions now are things like assign a new variable, and that's it because you know what your state looks like. You also know what your goal test is.
Vậy hàm kế tiếp giờ là những thứ như gán một biến mới, và chỉ có thế vì ta biết trạng thái trông như thế nào. Ta cũng biết phép kiểm tra đích là gì.
Your goal test is a set of constraints which specify which combinations of values and variables are legal.
Phép kiểm tra đích là một tập các ràng buộc quy định những tổ hợp giá trị và biến nào là hợp lệ.
OK, so instead of a judge just telling you, legal, illegal, illegal, legal — instead, you've got a list of rules.
OK, thay vì thẩm phán chỉ nói hợp lệ, không hợp lệ, không hợp lệ, hợp lệ... thì em có một danh sách các quy tắc.
You've got the laws, and you can look at these and you can see, OK, I'm good. I'm good. Oh, I'm breaking this law right now. OK, I violated a constraint here.
Em có các điều luật, em nhìn vào và thấy, OK, mình ổn. Mình ổn. Ồ, mình đang vi phạm điều luật này. OK, mình đã vi phạm một ràng buộc ở đây.
And because your goal function has sort of been decomposed into multiple rules, you can do things like detect errors early.
Và vì hàm đích của em đã được phân rã thành nhiều quy tắc, em có thể làm những việc như phát hiện lỗi sớm.
This is also a simple example — it's our first, but not our last example of a formal representation language. So like in the real world, there are CSP solvers.
Đây cũng là một ví dụ đơn giản, là ví dụ đầu tiên chứ không phải cuối cùng về một ngôn ngữ biểu diễn hình thức. Ngoài thực tế, có các bộ giải CSP.
They're super complicated. They do all the things they do inside. And when you write a CSP, you write, OK, well here aer my values. Here are my variables.
Chúng cực kỳ phức tạp. Bên trong chúng làm đủ thứ. Và khi viết một CSP, em viết: OK, đây là các giá trị của tôi. Đây là các biến của tôi.
Here are their values. Here are the constraints between these. Here's an explicit constraint. Here's an implicit constraint.
Đây là các giá trị của chúng. Đây là các ràng buộc giữa chúng. Đây là một ràng buộc tường minh. Đây là một ràng buộc ngầm định.
And in doing that, you're writing down a model of the world in CSP speak. It's not the only way to write a model.
Làm vậy là em đang viết ra một mô hình của thế giới bằng ngôn ngữ CSP. Đó không phải cách duy nhất để viết mô hình.
It's not the only one we'll see here, but it's a representation language that then — the problem solver on the other side has special purpose algorithms to find you a solution.
Cũng không phải cách duy nhất ta sẽ thấy ở đây, nhưng đó là một ngôn ngữ biểu diễn mà bộ giải ở phía bên kia có các thuật toán chuyên dụng để tìm ra lời giải cho em.
As we already talked about, because we can peek inside the state, we can have better algorithms than standard search. OK. So we're going to do some examples.
Như ta đã nói, vì ta có thể nhìn vào bên trong trạng thái, ta có thể có các thuật toán tốt hơn so với tìm kiếm chuẩn. OK. Giờ ta sẽ làm vài ví dụ.
Hopefully, you all know your geography of Australia, because we're going to talk about it a lot. This is all you need to know.
Hy vọng các em đều biết địa lý nước Úc, vì ta sẽ nói về nó rất nhiều. Chỉ cần biết bấy nhiêu thôi.
Australia is divided into — I believe they're called states, and we're going to color them colors. So our first example is map coloring, as I said. So we're going to see Australia a lot.
Nước Úc được chia thành... thầy tin là gọi là các bang, và ta sẽ tô màu cho chúng. Vậy ví dụ đầu tiên là tô màu bản đồ, như thầy đã nói. Ta sẽ gặp nước Úc rất nhiều.
It's also running example in the book.
Nó cũng là ví dụ xuyên suốt trong sách giáo trình.
And in this case, we want to color the map and we want to have adjacent countries not have the same color, so we need to formalize this as a CSP.
Trong trường hợp này, ta muốn tô màu bản đồ sao cho các quốc gia kề nhau không cùng màu, nên ta cần hình thức hóa nó thành một CSP.
So step 1 — we need variables. Here, the variables will be the different states. So WA is the variable for Western Australia. That was unexpected.
Bước 1: ta cần các biến. Ở đây, các biến sẽ là các bang khác nhau. WA là biến cho Western Australia. Cái đó nằm ngoài dự kiến.
That was also unexpected.
Cái này cũng ngoài dự kiến.
All right. In the worst case, you can all come huddle around my laptop. OK. So Western Australia — that's a variable.
Được rồi. Tệ nhất thì các em có thể xúm lại quanh laptop của thầy. OK. Vậy Western Australia là một biến.
The Northern Territory in the north. South Australian in the south. Queensland, New South Wales, and Victoria on the east, and Tasmania is a sort of disconnected island.
Northern Territory ở phía bắc. South Australia ở phía nam. Queensland, New South Wales và Victoria ở phía đông, còn Tasmania là một hòn đảo tách biệt.
You can Color it whatever you want because it's disconnected from the rest. That's actually going to be really important later. So there the variables. There are going to be domains.
Các bạn có thể tô nó màu gì tùy ý, vì nó không nối với phần còn lại. Điều này thực ra sẽ rất quan trọng về sau. Vậy đó là các biến. Tiếp theo sẽ có các miền giá trị.
Now I'm paranoid. I'm looking back. If it goes out, catch my attention. Otherwise, I'll just — I can see it.
Giờ tôi thấy hơi lo. Tôi đang nhìn lại phía sau. Nếu nó tắt thì nhắc tôi nhé. Còn không thì tôi sẽ — Tôi thấy rồi.
OK, so what are the domains? Well, we need values to assign, and the domains here might be red, green, and blue in this map coloring here.
Được, vậy các miền giá trị là gì? Chúng ta cần các giá trị để gán, và miền giá trị ở đây có thể là đỏ, xanh lá và xanh dương trong bài tô màu bản đồ này.
Now of course, if that was it — there were just variables and domains — a solution would be an assignment of variables, giving each variable a value on the domain.
Dĩ nhiên, nếu chỉ có vậy, tức là chỉ có biến và miền giá trị, thì một nghiệm là một phép gán biến, cho mỗi biến một giá trị trong miền của nó.
So we just color it all red and we say we're done. So we need some constraints. We need something that tells us coloring everything red is not OK.
Vậy ta tô tất cả màu đỏ rồi bảo là xong. Nên ta cần một số ràng buộc. Ta cần thứ gì đó cho biết tô mọi thứ màu đỏ là không được.
And so the constraints here, in English, say adjacent regions must have different colors. How are we going to write that down? Well, we could write them down as what are called implicit constraints.
Ràng buộc ở đây, nói bằng lời, là các vùng kề nhau phải có màu khác nhau. Ta sẽ viết nó ra thế nào? Ta có thể viết chúng dưới dạng cái gọi là ràng buộc ẩn (implicit constraint).
Like we might write WA not equal to NT.
Ví dụ ta viết WA khác NT.
Effectively, an implicit constraint is a little snippet of code that you can execute and will tell you whether or not everything's OK or whether or not it's broken.
Về bản chất, ràng buộc ẩn là một đoạn mã nhỏ mà bạn có thể chạy, và nó sẽ cho bạn biết mọi thứ có ổn hay đã bị vi phạm.
So here's a little snippet of code that looks up the value of WA, looks up the value of NT, and if they're not the same, it says thumbs up OK.
Đây là một đoạn mã nhỏ tra giá trị của WA, tra giá trị của NT, nếu chúng không giống nhau thì nó báo ổn được.
So an implicit constraint is a piece of code you execute to see if you violated the constraint. But of course, any quality like this — we could write it out explicitly.
Vậy ràng buộc ẩn là một đoạn mã bạn chạy để xem có vi phạm ràng buộc hay không. Nhưng dĩ nhiên, bất kỳ quan hệ nào như vậy ta cũng có thể viết tường minh.
An explicit constraint is something like, the pair, WA, NT has the following elements as legal elements of their joint cross-domain.
Một ràng buộc tường minh (explicit constraint) là kiểu cặp WA, NT có các phần tử sau là phần tử hợp lệ của tích miền giá trị chung của chúng.
So WA, comma, NT can be one of the following pairs — red, green, red, blue, blue, green, whatever. So on and so on. But not red, red. OK.
Vậy WA, NT có thể là một trong các cặp sau: đỏ-xanh lá, đỏ-xanh dương, xanh dương-xanh lá, v.v. Cứ thế tiếp tục. Nhưng không được đỏ-đỏ. Được.
Implicit versus explicit constraints. It's going to be an important distinction that's going to keep coming up.
Ràng buộc ẩn so với tường minh. Đây là một sự phân biệt quan trọng và sẽ liên tục xuất hiện.
A solution is an assignment where every variable takes on a value in the domain that satisfies all the constraints. So here's one. This is the one that's in the picture, as well.
Một nghiệm là một phép gán mà mỗi biến nhận một giá trị trong miền sao cho thỏa mãn mọi ràng buộc. Đây là một nghiệm. Cũng chính là nghiệm trong hình.
Western Australia's red, Northern Territories are green, Queensland's red, New South Wales is green, and so on. There are other solutions. This isn't the only one. This is a solution.
Western Australia màu đỏ, Northern Territory màu xanh lá, Queensland màu đỏ, New South Wales màu xanh lá, v.v. Còn có những nghiệm khác. Đây không phải nghiệm duy nhất. Đây là một nghiệm.
In general in CSPs, we're asking the question, find me a solution. There may be a lot. In general, if there's one, there's going to be a lot. There's often exponentially many.
Nói chung với CSP, ta đặt câu hỏi: hãy tìm cho tôi một nghiệm. Có thể có rất nhiều. Nói chung, nếu có một nghiệm thì sẽ có rất nhiều. Thường là số mũ.
Here's another example. N-Queens. How many of you know the N-Queens problem? How many of you would say you're frequent N-Queens players?
Đây là một ví dụ khác. N-Queens. Có bao nhiêu bạn biết bài toán N-Queens? Có bao nhiêu bạn tự nhận là hay chơi N-Queens?
OK. So what's N-Queens? N-Queens is a puzzle. You have a chess board of some usually square size, and so this is four by four.
Được. Vậy N-Queens là gì? N-Queens là một câu đố. Bạn có một bàn cờ thường là hình vuông, ở đây là bàn 4x4.
And on that square chessboard, you're going to place Queens. And they follow the normal queen attack or threat configurations. So for example, this one here attacks to here, to here, and on these diagonals.
Trên bàn cờ vuông đó, bạn đặt các quân Hậu. Chúng tuân theo cách tấn công hay đe dọa bình thường của quân Hậu. Ví dụ quân này tấn công đến đây, đến đây, và trên các đường chéo này.
And so what you want in N-Queens is to be able to place N of these Queens on the board, such that none of them are threatening.
Điều ta muốn trong N-Queens là đặt được N quân Hậu lên bàn cờ, sao cho không quân nào đe dọa quân nào.
OK, so we know the rules that make Queens fight, and we would like to have a peaceful kingdom. So let's formulate this as a CSP. You need a CSP, you need variables.
Vậy ta biết các luật khiến các quân Hậu đánh nhau, và ta muốn có một vương quốc hòa bình. Giờ hãy mô hình hóa nó thành một CSP. Một CSP cần có các biến.
So here's our first formulation. Our first formulation — well, what are the variables? Let's make the variables the squares. So how many variables will we have?
Đây là cách mô hình hóa đầu tiên. Cách đầu tiên: biến là gì? Ta cho biến là các ô vuông. Vậy ta có bao nhiêu biến?
We'll have kind of four by four of them. You'll have the two dimensional grid of variables. So we'll have a bunch of x, i, js. So in N, there are now quadratically many variables.
Khoảng 4x4 biến. Ta có một lưới biến hai chiều. Nên ta có một loạt biến x, i, j. Vậy theo N, số biến là bậc hai.
And what is on each square? Well, it's either Queened or un-Queened, right? It's either full or empty.
Và trên mỗi ô có gì? Hoặc có Hậu hoặc không có, đúng không? Hoặc đầy hoặc trống.
So we could say the domains are maybe 0 or 1, or we could write it as empty, comma, queen, or something like that. So we've got variables and we've got domains.
Nên miền giá trị có thể là 0 hoặc 1, hoặc ta viết là trống, phẩy, hậu, hay đại loại vậy. Vậy ta có biến và có miền giá trị.
And if this were the end of the CSP, we'd just leave it blank or whatever, or we'd put Queens wherever we want. It would all be fine. So we need some constraints.
Và nếu CSP chỉ có thế, ta cứ để trống hoặc gì cũng được, hoặc đặt Hậu tùy ý. Thế nào cũng ổn. Nên ta cần một số ràng buộc.
So what are the constraints? The constraints need to be the things that say certain configurations are OK and certain ones aren't. So we could write them down.
Vậy các ràng buộc là gì? Ràng buộc phải là thứ cho biết cấu hình nào được và cấu hình nào không. Ta có thể viết chúng ra.
So we could say, for example, for any pair — so here is i, j, and k. So x, i, j, and x, i, k.
Ví dụ, với mọi cặp — đây là i, j và k. Tức x, i, j và x, i, k.
So that's like this one and this one because they share a coordinate.
Tức là ô này và ô này vì chúng chung một tọa độ.
We could say, explicitly, the legal elements of their cross-domain that are allowed are 0, 0, 0, 1, or 1, 0, but not 1, 1 because these two variables — if you're x, i, j and x, i, k, and you're both 1, that's a threat.
Ta có thể nói tường minh rằng các phần tử hợp lệ của tích miền giá trị của chúng là 0,0; 0,1; hoặc 1,0, nhưng không phải 1,1 vì hai biến này — nếu bạn là x, i, j và x, i, k, và cả hai cùng bằng 1, thì đó là một mối đe dọa.
And so somewhere in here is buried the information that you're not allowed to threaten vertically.
Vậy là đâu đó trong này có chứa thông tin rằng các em không được đe dọa nhau theo chiều dọc.
And you can have all the rest — the thing that says you can't threaten vertically, you can't threaten horizontally, and you can't threaten along a diagonal.
Và các em có thể có tất cả phần còn lại — ràng buộc nói rằng không được đe dọa theo chiều dọc, không được đe dọa theo chiều ngang, và không được đe dọa theo đường chéo.
And you could write those out, and there would be a bunch of these things that say, for these two squares, here's the joint constraint on those two variables.
Các em có thể viết hết ra, và sẽ có cả một loạt những ràng buộc như thế nói rằng, với hai ô này, đây là ràng buộc chung trên hai biến đó.
This is almost right. So if I wrote out all these constraints and these variables, there's a really easy solution. What's the easy solution under all these?
Cách này gần đúng rồi. Nếu tôi viết ra tất cả các ràng buộc và các biến này, sẽ có một lời giải rất dễ. Lời giải dễ đó là gì?
Yeah, set everything to 0. It doesn't violate any of these constraints, and there's nothing here that says you have to have anything about N-Queens in your N-Queen problem.
Đúng, đặt mọi thứ bằng 0. Nó không vi phạm ràng buộc nào ở đây, và không có gì ở đây nói rằng phải có quân hậu nào trong bài toán N-Queens của các em.
So we would need one more constraint, and we could write that out in various ways.
Nên ta cần thêm một ràng buộc nữa, và ta có thể viết nó theo nhiều cách.
Here is an implicit way of writing that out — that if you sum up all of the x, i, js, you'll get N, right?
Đây là cách viết ngầm định: tổng tất cả các x, i, j phải bằng N, đúng không?
In order to figure out whether or not you're OK, you're going to have to run some code that loops maybe two for loops and a sum — something like that.
Để biết có thỏa hay không, các em phải chạy một đoạn mã có vòng lặp, chẳng hạn hai vòng for và một phép tính tổng — đại loại như vậy.
This one is backed by code. In general, when we do the analysis, we'll always think about their explicit versions. OK. So that's N-Queens.
Ràng buộc này được hỗ trợ bằng mã. Nói chung, khi phân tích, ta sẽ luôn nghĩ đến dạng tường minh của chúng. OK. Đó là N-Queens.
This isn't a very good formulation of N-Queens, just like in search problems, you can sometimes formulate things a different way that builds more of the solution structure into the problem — more constraint — and therefore makes it easier to solve.
Đây không phải cách biểu diễn N-Queens tốt, giống như trong bài toán tìm kiếm, đôi khi ta có thể biểu diễn theo cách khác, đưa nhiều cấu trúc của lời giải hơn vào bài toán — nhiều ràng buộc hơn — và nhờ đó dễ giải hơn.
Often, this gives you a smaller space that's easier to solve, and this is true for both search and for CSPs. So what else could we do?
Thường thì cách này cho không gian nhỏ hơn, dễ giải hơn, và điều này đúng cho cả tìm kiếm lẫn CSP. Vậy ta còn làm được gì nữa?
How else could we set up our variables here?
Ta có thể thiết lập các biến theo cách nào khác?
We could use the information that we know that there's going to be one Queen in each, let's say, row.
Ta có thể dùng thông tin rằng mỗi hàng sẽ có đúng một quân hậu. hàng.
If we did that, we could say the variables — each row has a q, sub k.
Khi đó, các biến là: mỗi hàng có một q chỉ số k.
And now, the domains are different because now, the variables represent — in row 3, where is the queen?
Và miền giá trị giờ khác đi, vì biến biểu diễn: ở hàng 3, quân hậu nằm ở đâu?
We know there has to be one, and so we don't have to worry about that sum to end constraint. And now the domains just say, which column is that queen in?
Ta biết chắc phải có một quân, nên ta không cần lo về ràng buộc tổng bằng N nữa. Giờ miền giá trị chỉ cho biết quân hậu ấy ở cột nào.
Now again, we have to write down the constraints, and here, the constraints are actually a little bit more complicated.
Một lần nữa, ta phải viết ra các ràng buộc, và ở đây, các ràng buộc thực ra phức tạp hơn một chút.
So we could write them down implicitly, saying, for all i and j — that means for all pairs of Queens — they don't threaten each other.
Ta có thể viết ngầm định, rằng với mọi i và j — nghĩa là mọi cặp quân hậu — chúng không đe dọa nhau.
Or we could just start writing this down, like Queen 1 and Queen 2 together can't take on any values other than 1, 3. That's OK. 1,4. That's OK.
Hoặc ta có thể viết ra, như Quân hậu 1 và Quân hậu 2 cùng nhau chỉ được nhận các giá trị như 1, 3. Cái đó được. 1, 4. Cái đó cũng được.
But like, 1, 2 would not be OK because then, they would be diagonally threatening. OK? That's N-Queens. Any questions?
Nhưng 1, 2 thì không được, vì khi đó chúng đe dọa nhau theo đường chéo. OK? Đó là N-Queens. Có câu hỏi nào không?
Because we have variables and there are constraints between them, we have another tool that's going to be at the core of a lot of the algorithms that we're going to develop for CSPs, and actually, this is all going to show up again later when we talk about Bayes nets, sort of in an isomorphic way.
Vì ta có các biến và các ràng buộc giữa chúng, ta có thêm một công cụ sẽ là cốt lõi của rất nhiều thuật toán mà ta sẽ phát triển cho CSP, và thực ra, tất cả điều này sẽ xuất hiện lại sau này khi nói về mạng Bayes, theo một cách đồng cấu.
And that is, we can talk about the constraint graph. This is the graph that is formed by having a node for each variable, and then some representation for constraints.
Đó là ta có thể nói về đồ thị ràng buộc. Đây là đồ thị được tạo bằng cách mỗi biến là một nút, và dùng một cách biểu diễn nào đó cho các ràng buộc.
If all the constraints are binary, that is, they connect two variables. We can have arcs represent constraints. There's another notation that we'll see in a second.
Nếu mọi ràng buộc đều là nhị phân, tức là nối hai biến, ta có thể dùng các cung để biểu diễn ràng buộc. Lát nữa ta sẽ thấy một ký hiệu khác.
So here, this is Australia decomposed into a node for each of the variables and an arc for each of the constraints.
Đây là nước Úc được phân rã thành một nút cho mỗi biến và một cung cho mỗi ràng buộc.
So because Western Australia and Southern Australia share a border, there's an arc here, which tells you right here, there is a constraint between them.
Vì Western Australia và Southern Australia có chung biên giới, nên có một cung ở đây, cho biết ngay tại đây có một ràng buộc giữa chúng.
But you'd have to, like, peek inside to see that that constraint is actually an inequality constraint.
Nhưng các em phải nhìn vào bên trong mới thấy ràng buộc đó thực ra là ràng buộc khác nhau.
The constraint graph doesn't tell you what the constraints are, but it tells you where they are, and that gives you powerful pieces of information to let you decompose and use different algorithms that are appropriate for different shapes and topologies of these graphs.
Đồ thị ràng buộc không cho biết ràng buộc là gì, nhưng cho biết chúng ở đâu, và đó là thông tin mạnh giúp các em phân rã và dùng các thuật toán khác nhau phù hợp với các hình dạng và cấu trúc tô-pô khác nhau của đồ thị.
OK. So a binary CSP is one in which each constraint relates, at most, two variables. So often, you have what are called unary constraints, which are really just domain reductions.
OK. CSP nhị phân là CSP mà mỗi ràng buộc liên quan đến nhiều nhất hai biến. Thường thì còn có cái gọi là ràng buộc đơn biến, thực chất chỉ là thu hẹp miền giá trị.
This state has to be green, for whatever reason. A constraint graph, nodes, or variables — arc show constraints. And the structure will speed up the search problem.
Bang này phải màu xanh lá, vì lý do nào đó. Đồ thị ràng buộc: nút là các biến — cung thể hiện các ràng buộc. Và cấu trúc sẽ giúp tăng tốc bài toán tìm kiếm.
So let's take a look and see what this looks like for N-Queens. All right. So what's N-Queens look like? The way we've been drawing it, let's do five Queens.
Giờ ta hãy xem nó trông thế nào với N-Queens. Được rồi. N-Queens trông thế nào? Theo cách ta vẫn vẽ, hãy lấy năm quân hậu.
All right. And we could call these a, b, c, d, and e, and then we could call the columns 1, 2, 3, 4, 5, and then we could place a queen right here.
Được rồi. Ta có thể gọi các hàng là a, b, c, d và e, rồi gọi các cột là 1, 2, 3, 4, 5, và đặt một quân hậu ngay đây.
And that would be the assignment that a equals — it's gone. a equals 5. a equals 2. All right.
Đó sẽ là phép gán a bằng — nó mất rồi. a bằng 5. a bằng 2. Được rồi.
Let's look at this as a graph. This is going to be in an applet that we'll see a couple of times. It's a nice applet by the folks at AI Space.
Giờ ta nhìn nó dưới dạng đồ thị. Đây là một applet mà ta sẽ gặp lại vài lần. Một applet rất hay của nhóm AI Space.
And in here, each variable is a circle, and you can see something other than just the names of the variables here.
Ở đây, mỗi biến là một hình tròn, và bạn thấy được nhiều hơn là chỉ tên của các biến.
You can see their domains, and right now, their domains are all 1 through 5 because we haven't picked anything yet for our CSP.
Bạn thấy cả miền giá trị, và hiện giờ miền giá trị đều là từ 1 đến 5 vì ta chưa chọn gì cho CSP của mình.
You can also see that between two things, like between a and b, there is this constraint that is helpfully called Queens 1. What the heck is Queens 1?
Bạn cũng thấy giữa hai biến, như giữa a và b, có một ràng buộc được đặt tên rất tiện là Queens 1. Queens 1 là cái gì vậy?
It's a constraint between a and b. So what is it going to say under the hood there? It's going to be things like, 1, 1 is not OK because then, they'd be vertically threatening.
Đó là ràng buộc giữa a và b. Vậy bên trong nó nói gì? Nó sẽ nói kiểu như: 1, 1 không được vì khi đó hai quân sẽ chiếu nhau theo chiều dọc.
1, 2 is not OK because then they'd be diagonally threatening. 1, 3 is OK, and that's what lives inside Queens 1.
1, 2 không được vì khi đó chúng chiếu nhau theo đường chéo. 1, 3 thì được, và đó là nội dung của Queens 1.
So from this graph here, you can see the structure of which nodes are connected to each other by constraints. You just can't see what the constraints are.
Từ đồ thị này, bạn thấy được cấu trúc các nút nào nối với nhau bằng ràng buộc. Chỉ là bạn không thấy ràng buộc đó là gì.
We'll come back and see this again later when we talk about constraint propagation.
Ta sẽ quay lại phần này khi nói về lan truyền ràng buộc.
Here's another example. Maybe some of you have done these cryptoarithmetic problems.
Đây là một ví dụ khác. Có thể một số bạn đã làm các bài toán mật mã số học.
The idea is you're supposed to make each letter be a digit, such that the math works out, and in this case, it'll work out both in words and in numbers.
Ý tưởng là gán mỗi chữ cái thành một chữ số sao cho phép tính đúng, và ở đây nó đúng cả khi viết bằng chữ lẫn bằng số.
And so the variables would be the ts, the ws, the os — all of those letters. But there's also some other variables you need. OK, in this case, you need three extra variables.
Các biến sẽ là các chữ t, w, o, tất cả những chữ cái đó. Nhưng bạn còn cần thêm vài biến khác. Trong trường hợp này, cần thêm ba biến.
Does anybody know what those variables represent?
Có ai biết các biến đó biểu diễn gì không?
Because you're going to want to write something like, o plus o equals r, but that's not quite right. There's something else going on here. Those are the carry bits.
Vì bạn sẽ muốn viết kiểu o cộng o bằng r, nhưng thế chưa đúng. Còn có chuyện khác đang diễn ra. Đó là các bit nhớ.
So we need to introduce some variables here for the carry bits, and their domains are going to be the digits, and the carry bits will maybe have limited domains.
Nên ta cần đưa vào các biến cho bit nhớ, miền giá trị của chúng là các chữ số, và bit nhớ có thể có miền giá trị hạn chế hơn.
What about the constraints? Well, one constraint that goes with these problems is that they'll all be different. Otherwise, you'd just assign everything to 0, and it would be fine.
Còn các ràng buộc thì sao? Một ràng buộc đi kèm với các bài này là tất cả phải khác nhau. Nếu không, bạn cứ gán mọi thứ bằng 0 là xong.
OK, so an all diff constraint is an interesting constraint because it's a constraint that touches a whole bunch of variables.
Ràng buộc all diff là một ràng buộc thú vị vì nó liên quan đến cả loạt biến.
In this case, that's not so bad because you can actually break it up into a bunch of pair-wise, all different constraints.
Ở đây thì không tệ lắm vì bạn có thể tách nó thành nhiều ràng buộc khác nhau từng cặp.
And you would have other constraints, like o plus o equals r, plus 10 times the carry bit, whatever it is — 0 or 1. And you could write all of these down.
Và bạn sẽ có các ràng buộc khác, như o cộng o bằng r, cộng 10 nhân bit nhớ, bit nhớ là gì cũng được, 0 hoặc 1. Bạn có thể viết hết chúng ra.
If you drew out the constraint graph, though, you'd have a problem because what about this all different constraint? How do you draw an arc that touches more than two things?
Nhưng nếu vẽ đồ thị ràng buộc thì sẽ gặp vấn đề: còn ràng buộc all different thì sao? Làm sao vẽ một cung nối hơn hai thứ?
And the answer is, in general, that people draw squares to represent the constraints, and then a bunch of lines going to all of the participating variables.
Câu trả lời là, nói chung, người ta vẽ hình vuông để biểu diễn ràng buộc, rồi vẽ nhiều đường nối tới tất cả các biến tham gia.
OK, and you can see this is sort of a special case at the other one when you just put a square in the middle of every arc. OK.
Và bạn thấy cách kia là một trường hợp đặc biệt khi ta đặt một hình vuông ở giữa mỗi cung. Được rồi.
How many people have played Sudoku? OK. Sudoku is fun. The variables are the open squares.
Ai đã chơi Sudoku rồi? Được. Sudoku rất vui. Các biến là những ô còn trống.
The domains are 1 through 9. The constraints here say that for each column, they all have to be different. For each row, all the digits have to be different.
Miền giá trị là từ 1 đến 9. Các ràng buộc ở đây nói rằng với mỗi cột, tất cả phải khác nhau. Với mỗi hàng, các chữ số cũng phải khác nhau.
And also, for each little region, they all have to be different.
Và với mỗi vùng nhỏ, tất cả cũng phải khác nhau.
There's actually one more kind of constraint in a Sudoku problem, which is, typically, there are a lot of squares that are already filled in with values, and you can think of those as unary constraints.
Thực ra còn một loại ràng buộc nữa trong Sudoku, đó là thường có nhiều ô đã được điền sẵn giá trị, và bạn có thể coi đó là các ràng buộc đơn.
In your solution, this square right here must be the number 1. And you can imagine a unary constraint where this one can be 3 or 7.
Trong lời giải của bạn, ô ngay đây phải là số 1. Bạn có thể hình dung một ràng buộc đơn mà ô này có thể là 3 hoặc 7.
As far as I know, that's not a thing you do in Sudoku, but you could. You could call it CS 188 Sudoku with unary constraints.
Theo tôi biết, Sudoku không có kiểu đó, nhưng bạn có thể làm vậy. Có thể gọi nó là Sudoku CS 188 với ràng buộc đơn.
Interestingly, you may know that some Sudoku problems are really easy.
Thú vị là, có thể bạn biết một số bài Sudoku rất dễ.
You pick something, and then there's another one that's pinned down, and then you pick another one that's pinned down, and another one, and then you're solved.
Bạn chọn một ô, rồi có một ô khác bị xác định, rồi chọn tiếp một ô nữa bị xác định, rồi thêm ô nữa, và thế là giải xong.
In other cases, you scratch your head and you try things and you backtrack and you try a couple of things and you detect a problem and you backtrack.
Ở các bài khác, bạn vò đầu bứt tai, thử đủ thứ, rồi quay lui, thử vài hướng rồi phát hiện vấn đề và lại quay lui.
And actually, that difficulty in computation that you have doing harder Sudoku problems compared to easier ones has a really deep connection to the algorithms we're going to learn for CSPs and their complexity.
Và thực ra, độ khó về tính toán khi giải Sudoku khó so với các bài dễ có mối liên hệ rất sâu với các thuật toán ta sắp học cho CSP và độ phức tạp của chúng.
OK, one of our last examples here — the Waltz algorithm. This is not how people do computer vision today, but it's an early computer vision algorithm that is an algorithm for interpreting line drawing.
Được rồi, một trong những ví dụ cuối ở đây: thuật toán Waltz. Ngày nay người ta không làm thị giác máy tính như vậy, nhưng đây là một thuật toán thị giác máy tính thời đầu dùng để diễn giải các bản vẽ nét.
So if I look at these three dimensional-ish drawings here, you might notice things like, well, this sort of corner here — these three lines — they're like an outie, right?
Nếu tôi nhìn các hình vẽ kiểu ba chiều này, bạn có thể nhận ra, chẳng hạn, góc này, ba đường thẳng này, trông như một góc lồi ra, đúng không?
And these ones here, at least in the easy interpretation — that's an innie. And so you look at these things and you kind of can't tell. Your brain does it, but what's sticking out?
Còn những cái này, ít nhất theo cách hiểu dễ nhất, là một góc lõm vào. Nhìn những hình này, bạn khó mà nói được. Não bạn làm được, nhưng cái nào nhô ra?
What's in? What's occluding what?
Cái nào lõm vào? Cái nào che khuất cái nào?
And these kinds of questions — that is an interpretation of these line drawings, and you can pose this as a CSP, where you say, well, each intersection — so here and here and here and here and here and here — each intersection is going to be a variable.
Và những câu hỏi kiểu này chính là việc diễn giải các bản vẽ nét này, và bạn có thể phát biểu nó thành một CSP, trong đó mỗi giao điểm, tức là chỗ này, chỗ này, chỗ này, chỗ này, chỗ này và chỗ này, mỗi giao điểm sẽ là một biến.
And the values are sort of going to be things like, it's an outie versus it's an innie.
Còn các giá trị thì kiểu như nhô ra hay lõm vào.
And the constraints are going to be things like if two things are connected, you can't have one that's kind of convex and the other is concave.
Và các ràng buộc thì giống như nếu hai thứ nối với nhau, thì không thể có một cái lồi còn cái kia lại lõm.
So like if you're connected to something, then you're both sort of outies in the appropriate way or innies.
Tức là nếu bạn nối với một thứ gì đó, thì cả hai cùng nhô ra hoặc cùng lõm vào theo đúng cách.
And so the solutions correspond to physically realizable 3D interpretations of these drawings, and this is an early example of a case where computation gives rise to intelligence or reasoning in an AI domain that was kind of very different from search.
Vì vậy các lời giải tương ứng với những diễn giải 3D khả thi về mặt vật lý của các bản vẽ này, và đây là một ví dụ ban đầu cho thấy tính toán tạo ra trí thông minh hay khả năng suy luận trong lĩnh vực AI theo cách rất khác với tìm kiếm.
Any questions on that before we get into varieties and solutions? OK. All right. There are a bunch of kinds of CSPs in the world — those that we'll talk about and those we won't.
Có câu hỏi nào về phần này không trước khi ta chuyển sang các loại CSP và cách giải? Được. Được rồi. Có nhiều loại CSP trên đời, có loại ta sẽ nói, có loại không.
What we're going to talk about most in this class is CSPs that have discrete variables.
Loại ta nói nhiều nhất trong lớp này là CSP với biến rời rạc.
In general, we're going to talk about ones with finite domains, and that means that if each domain has d values in that domain, then the complete assignments are something like order d to the n.
Nói chung ta sẽ xét các miền giá trị hữu hạn, nghĩa là nếu mỗi miền có d giá trị, thì số phép gán đầy đủ cỡ d mũ n.
That's already bad news, right? That's already exponential in the number of variables in the CSP.
Đó đã là tin xấu rồi, đúng không? Nó đã tăng theo hàm mũ của số biến trong CSP.
This includes things like Boolean CSPs including satisfiability, where each of the variables has two things — true and false — and the constraints are things like conjuncts clauses and things like that.
Loại này gồm các CSP Boolean, trong đó có bài toán khả thỏa, mỗi biến chỉ có hai giá trị, đúng và sai, còn các ràng buộc là các mệnh đề hội và những thứ tương tự.
And we already know that this is NP Hard. This is NP Complete, which you should have gotten from other classes. But there are other CSPs.
Ta biết bài này là NP-khó. Nó là NP-đầy đủ, điều mà các bạn hẳn đã học ở các lớp khác. Nhưng còn những CSP khác.
For example, cases where any integer is a valid member of the domain or string valued variables, which are even harder.
Ví dụ, trường hợp mọi số nguyên đều thuộc miền giá trị, hoặc biến nhận giá trị chuỗi, còn khó hơn nữa.
When things have linear constraints — things like job scheduling, where this job has to end before this job starts and things like that — these things are solvable, though they're still very hard to solve.
Khi có các ràng buộc tuyến tính, như lập lịch công việc, việc này phải kết thúc trước khi việc kia bắt đầu chẳng hạn, thì giải được, dù vẫn rất khó giải.
Once you have non-linear constraints, things can sort of get undecidable very quickly.
Khi có ràng buộc phi tuyến, mọi thứ có thể trở nên bất khả quyết rất nhanh.
And of course, there's also continuous variables like we're going to have a telescope, and it's going to have non-integer, sort of abstract times.
Và dĩ nhiên cũng có biến liên tục, ví dụ ta có một kính thiên văn, và nó có các thời điểm không phải số nguyên, kiểu trừu tượng.
It's going to have real valued times or any number of cases, and in the case of linear constraints — these are linear programs, and you saw, I think, a little bit in CS 70 and certainly in 170, how to solve these.
Thời gian nhận giá trị thực, hay nhiều trường hợp khác, và với ràng buộc tuyến tính đó là quy hoạch tuyến tính, và tôi nghĩ các bạn đã thấy chút ít trong CS 70 và chắc chắn trong 170 cách giải chúng.
There are good polynomial time approaches to these, but in general, continuous variables are also very hard. Varieties of constraints. We talked about unary constraints.
Có những cách giải thời gian đa thức tốt, nhưng nói chung biến liên tục cũng rất khó. Các loại ràng buộc. Ta đã nói về ràng buộc đơn.
Those are — you should think of them as restrictions on a domain.
Hãy xem chúng như các hạn chế trên một miền giá trị.
That's important because we're going to have algorithms that also restrict domains, and you're going to need to know how those relate to unary constraints. Binary constraints — doesn't mean the variables are binary.
Điều này quan trọng vì ta sẽ có các thuật toán cũng thu hẹp miền, và bạn cần biết chúng liên hệ thế nào với ràng buộc đơn. Ràng buộc hai ngôi không có nghĩa là biến là nhị phân. Đó là biến nhị phân, miền nhị phân. Ràng buộc hai ngôi liên quan đến hai biến cùng lúc, như SA và WA không bằng nhau.
Those are binary variables — binary domains. Binary constraints involve two variables at a time, like SA and WA are not equal.
Ràng buộc bậc cao hơn giống như trong bài cryptoarithmetic, có thể có ba biến trở lên.
And higher order constraints are like what we saw in cryptoarithmetic where you can have three or more. There's also preferences or what people call soft constraints, like color this map, but I like red.
Cũng có các sở thích, hay còn gọi là ràng buộc mềm, như tô màu bản đồ này, nhưng tôi thích màu đỏ. Dùng màu đỏ nếu được. Đỏ tốt hơn xanh lá. Chúng thường được biểu diễn bằng các phép gán biến có chi phí, hoặc chi phí trên miền giá trị, hoặc trên các ràng buộc mềm.
Use red if you can. Red is better than green. And these are often represented by having variable assignments that have costs — either costs on the domains or costs sort of on soft constraints.
This gives a kind of constrained optimization problem that we're going to say nothing about here, but is going to be sort of — it's going to be very relevant when we get to Bayes nets because Bayes nets are a form of reasoning over these kinds of graph structures with real value costs.
Điều này cho ra một bài toán tối ưu có ràng buộc mà ở đây ta sẽ không bàn, nhưng sẽ rất liên quan khi ta học mạng Bayes vì mạng Bayes là một dạng suy luận trên các cấu trúc đồ thị như vậy với chi phí giá trị thực. Được. Nhưng không phải hôm nay. CSP có mặt khắp nơi trong thực tế.
OK. But not today.
Đây là công nghệ rất phổ biến. Có lẽ bạn gặp CSP suốt.
CSPs are all over in the real world. They're actually really common technology. You probably run into CSPs all the time. Probably the most common one is, hey, I have a bunch of friends.
Có lẽ phổ biến nhất là: tôi có một nhóm bạn. Khi nào tất cả cùng họp được? Hoặc phải họp vì việc gì đó liên quan công việc. Đây là lúc tôi rảnh.
When can we all meet? Or got to meet for some work related thing. Here's when I'm available. I'm available here, and try and find intersections of those things.
Tôi rảnh lúc này, rồi cố tìm giao của các khoảng thời gian đó. Cũng có thời khóa biểu, như lịch mà trường phải xếp để biết lớp nào học ở đâu để có thể xếp vừa tất cả sinh viên với mức dư thừa tối thiểu.
There's also timetabling, like that schedule that campus has to do to figure out which classes go where so that we can fit all the students with kind of minimum overflow.
Các phiên bản của bài này là CSP, và chúng thực sự có mặt khắp nơi.
Versions of this are CSPs, and they're really all over the place. So this is the kind of technology that crops up all over the place in the real world.
Đây là loại công nghệ xuất hiện khắp nơi trong đời thực. Trong thực tế, dĩ nhiên nhiều bài như vậy có biến giá trị thực chứ không chỉ rời rạc. điều này xuất hiện ở khắp nơi trong thế giới thực.
In the real world, of course, a lot of these things have real valued variables, and not just discrete ones.
Tất nhiên, trong thế giới thực, rất nhiều thứ như vậy có các biến giá trị thực, chứ không chỉ là các biến rời rạc.
Let's solve some CSPs. All right. So we're going to be CSP detectives here.
Hãy giải một vài CSP nào. Được rồi. Giờ chúng ta sẽ làm thám tử CSP.
So we'll start with the standard search formulation for CSPs. We'll talk about another formulation next lecture. In the standard search formulation for CSPs, states are defined by the values that are assigned so far.
Ta bắt đầu với cách phát biểu tìm kiếm chuẩn cho CSP. Bài sau ta sẽ nói về một cách phát biểu khác. Trong cách phát biểu tìm kiếm chuẩn cho CSP, trạng thái được xác định bởi các giá trị đã gán cho đến lúc này.
So you can call these partial assignments.
Ta gọi đó là các phép gán từng phần.
So the initial state at the root of the search tree is going to be an empty assignment where no variables have any values, and the successor function is going to assign a value to an unassigned variable.
Vậy trạng thái ban đầu ở gốc của cây tìm kiếm là phép gán rỗng, tức là chưa biến nào có giá trị, và hàm kế tiếp sẽ gán một giá trị cho một biến chưa được gán.
The goal test is going to not just be is it a complete full assignment, but it also has to satisfy all of the constraints.
Kiểm tra đích không chỉ hỏi đó có phải phép gán đầy đủ hay không, mà còn phải thỏa mãn mọi ràng buộc.
OK, this would be the simplest way of mapping CSPs into search. Your successor function assigns another variable, and the goal test is all constraints are satisfied and I've assigned all the variables.
Đây là cách đơn giản nhất để chuyển CSP thành bài toán tìm kiếm. Hàm kế tiếp gán thêm một biến, và kiểm tra đích là mọi ràng buộc được thỏa mãn và tôi đã gán hết các biến.
So we'll start with the dumbest thing that could possibly work. We will see that it doesn't work, and we'll improve it. So let's think about this graph here.
Ta sẽ bắt đầu với cách ngốc nhất có thể chạy được. Ta sẽ thấy nó không hiệu quả, rồi ta cải thiện nó. Hãy nghĩ về đồ thị này.
This is the map coloring problem for the Australia problem. And we could think, what's breadth-first search going to do?
Đây là bài toán tô màu bản đồ nước Úc. Ta thử nghĩ xem tìm kiếm theo chiều rộng sẽ làm gì.
Well, there's going to be a search tree and there's going to be a root, right? Remember breadth-first search from before? What's going to be at the root is the empty assignment.
Sẽ có một cây tìm kiếm và có một gốc, đúng không? Nhớ tìm kiếm theo chiều rộng hồi trước chứ? Ở gốc là phép gán rỗng.
And that's got successors, and what do the successors look like? They look like things like Western Australia equals red.
Nó có các nút kế tiếp, và các nút kế tiếp trông thế nào? Chúng giống như Western Australia bằng đỏ.
And that's going to have some successors, like Western Australia equals red and South Australia equals green.
Nút đó lại có các nút kế tiếp, như Western Australia bằng đỏ và South Australia bằng xanh lá.
And that's going to have successors, which will have successors. And you've got this big exponential tree that encodes all of the combinatorially many ways of assigning these values to these variables.
Rồi nó lại có các nút kế tiếp, và những nút đó lại có nút kế tiếp nữa. Bạn có một cây khổng lồ tăng theo hàm mũ mã hóa toàn bộ vô số cách tổ hợp để gán các giá trị này cho các biến này.
What's breadth-first search going to do? It's going to take the one off the top. It's going to say, are you a goal? Nope.
Tìm kiếm theo chiều rộng sẽ làm gì? Nó lấy nút trên cùng ra. Nó hỏi: bạn có phải đích không? Không.
So it's going to stripe through the second level of the tree. Is it going to find any solutions? No, because on this level, there's only one value assigned to each variable.
Rồi nó quét hết tầng thứ hai của cây. Nó có tìm thấy lời giải nào không? Không, vì ở tầng này mỗi biến mới chỉ được gán một giá trị.
So it'll go to the third level of the tree, accumulating an enormous queue as it does so. Stripe through the third level. Any solutions? Nope.
Nên nó đi xuống tầng thứ ba, và hàng đợi cứ phình ra khổng lồ. Quét hết tầng thứ ba. Có lời giải nào không? Không.
Nope. Nope. Nope. Nope.
Không. Không. Không. Không.
OK. And then where are the solutions?
Được. Vậy các lời giải nằm ở đâu?
They're at the bottom. They're all at the bottom. This is like the nightmare scenario for breadth-first search.
Ở dưới đáy. Tất cả đều nằm ở đáy. Đây là kịch bản ác mộng của tìm kiếm theo chiều rộng.
OK, breadth-first search stays up at night worrying about what's going to happen if all the solutions are at the bottom, because that means it has to explore the entire tree.
Tìm kiếm theo chiều rộng thức đêm lo lắng chuyện gì sẽ xảy ra nếu mọi lời giải đều nằm ở đáy, vì khi đó nó phải duyệt toàn bộ cây.
This is the worst possible case because you have to do everything at the other levels before you can even get to the bottom. So before, we sort of made fun of depth-first search, right?
Đây là trường hợp tệ nhất vì bạn phải làm xong mọi thứ ở các tầng khác trước khi có thể xuống tới đáy. Trước đây ta từng chế giễu tìm kiếm theo chiều sâu, đúng không?
We love you, depth-first search, but you find weird solutions. Suddenly, depth-first search maybe doesn't seem so crazy because our search tree looks like this, except it's sort of exponentially big on the bottom.
Chúng tôi yêu bạn, tìm kiếm theo chiều sâu, nhưng bạn tìm ra những lời giải kỳ quặc. Bỗng nhiên tìm kiếm theo chiều sâu có lẽ không còn điên rồ nữa, vì cây tìm kiếm của ta trông như thế này, chỉ là phần đáy to ra theo hàm mũ.
All the solutions are down here, and depth-first search is at least going to make a decent effort at getting to where the solutions live, whereas breadth-first search is going to look everywhere where they aren't first.
Mọi lời giải đều ở dưới này, và tìm kiếm theo chiều sâu ít nhất cũng nỗ lực khá để đi tới nơi có lời giải, còn tìm kiếm theo chiều rộng thì đi xem hết những nơi không có lời giải trước.
So all of the methods we're going to talk about are actually based on depth-first search, even though we spent all of last week making fun of depth-first search.
Vì vậy mọi phương pháp ta sắp nói thực ra đều dựa trên tìm kiếm theo chiều sâu, dù cả tuần trước ta đã chế giễu tìm kiếm theo chiều sâu.
So let's take a look. So here is a search graph. This is for a map coloring problem — three colors — adjacent things, which are connected by lines here — can't be the same.
Ta cùng xem nhé. Đây là một đồ thị tìm kiếm. Đây là bài toán tô màu bản đồ với ba màu, hai nút kề nhau, được nối bằng các đường ở đây, thì không được cùng màu.
And what we're going to do is we're going to run naive search. This is actually even already a bit of an improvement, but this is basically just the naive thing.
Và việc ta sắp làm là chạy tìm kiếm ngây thơ. Thực ra cách này đã được cải thiện đôi chút rồi, nhưng về cơ bản vẫn là cách ngây thơ.
We're at the root, OK. So we're going to do depth-first search. We're going to add an assignment and recurse. So we're going to assign the first thing to blue.
Ta đang ở gốc. Ta sẽ chạy tìm kiếm theo chiều sâu. Ta thêm một phép gán rồi đệ quy. Ta gán cái đầu tiên là xanh dương.
Great. We're going to go to the next level in the tree because depth-first search follows the deepest thing on the queue. So we're going to do another assignment.
Tốt. Ta xuống tầng tiếp theo của cây vì tìm kiếm theo chiều sâu đi theo nút sâu nhất trong hàng đợi. Ta thực hiện thêm một phép gán.
What are we going to assign? It's going to be this circle here to the right of the blue one. What are we going to assign to it? Remember, it's blue, green, and red.
Ta sẽ gán cho cái nào? Là hình tròn này bên phải hình xanh dương. Ta gán màu gì cho nó? Nhớ là có xanh dương, xanh lá và đỏ.
Blue! And now the next one. Blue. Blue.
Xanh dương! Và cái tiếp theo. Xanh dương. Xanh dương.
Blue. Blue. Blue. Blue.
Xanh dương. Xanh dương. Xanh dương. Xanh dương.
Blue. Blue. We have no successors and we're also not a goal, so we'll pull something off the queue. And we'll sort of keep this up for a while.
Xanh dương. Xanh dương. Không còn nút kế tiếp và cũng không phải đích, nên ta lấy một nút khác ra khỏi hàng đợi. Và ta cứ tiếp tục như vậy một lúc.
In the interest of doing anything else in the lecture, I won't actually run this whole thing, but this is what depth-first search would do with a naive formulation.
Để còn có thời gian làm việc khác trong buổi học, tôi sẽ không chạy hết toàn bộ quá trình này, nhưng đây là những gì tìm kiếm theo chiều sâu sẽ làm với cách mô hình hóa ngây thơ.
So this is kind of crazy, right? Why would you solve a CSP like this, where you keep doing assignments, and then only at the end discover that it doesn't work out?
Thế này thì hơi điên rồ, đúng không? Sao lại giải một CSP như thế này, cứ liên tục gán giá trị, rồi đến cuối cùng mới phát hiện là không ổn?
So we should be able to do better than this. How are we going to do better? Any ideas?
Vậy ta phải làm tốt hơn thế. Làm sao để tốt hơn? Có ý kiến gì không?
Ideas.
Ý kiến nào?
Yeah, so we should be checking these constraints as we go.
Đúng, ta nên kiểm tra các ràng buộc ngay trong lúc làm.
The answer was, here, maybe the successor function could have the constraints built in, or at least we could look at the constraints as we go.
Câu trả lời là: có thể hàm sinh trạng thái kế tiếp được tích hợp sẵn các ràng buộc, hoặc ít nhất ta xem xét các ràng buộc trong lúc làm.
Basically, we want to apply that goal test incrementally as we go. And the simplest version of this is what's called backtracking search. It's not a very helpful name.
Về cơ bản, ta muốn áp dụng phép kiểm tra đích một cách tăng dần trong quá trình đó. Và phiên bản đơn giản nhất của ý này là tìm kiếm quay lui. Tên này không gợi ý nhiều lắm.
It's just a classic name for this. It's the basic, uninformed algorithm for CSPs. First idea — we do one variable at a time.
Nó chỉ là tên gọi kinh điển thôi. Đây là thuật toán cơ bản, không có thông tin, cho CSP. Ý đầu tiên: mỗi lần chỉ xét một biến.
Strictly speaking, the naive thing could assign any variable at any time, and it would still be a valid successor.
Nói chặt chẽ thì cách ngây thơ có thể gán bất kỳ biến nào vào bất kỳ lúc nào, và đó vẫn là một trạng thái kế tiếp hợp lệ.
But since these variable assignments are commutative, it doesn't matter what order you got to them. Remember, the path doesn't matter here.
Nhưng vì các phép gán biến có tính giao hoán, nên thứ tự gán không quan trọng. Nhớ rằng ở đây đường đi không quan trọng.
We're just going to fix an ordering, then we consider one variable at a time. And we're going to check constraints as we go. So as soon as we violate a constraint, we're done.
Ta chỉ cần cố định một thứ tự, rồi xét từng biến một. Và ta kiểm tra các ràng buộc trong lúc làm. Nên ngay khi vi phạm một ràng buộc là xong.
We don't have to keep going and checking whether somehow, deeper in this tree, this is going to look better. Remember, we couldn't do that with search.
Ta không cần đi tiếp để kiểm tra xem biết đâu sâu hơn trong cây này mọi thứ sẽ ổn hơn. Nhớ rằng với tìm kiếm thông thường ta không làm vậy được.
This is only because in CSPs, once you violate a constraint, there's nothing you can do to un-violate it later. That's important. It's not true for search problems in general.
Điều này chỉ đúng vì trong CSP, một khi đã vi phạm ràng buộc, ta không thể làm gì để hết vi phạm về sau. Điều này quan trọng. Nó không đúng với các bài toán tìm kiếm nói chung.
It's true here, so we can stop early, as soon as we have violated a constraint. Think of it as an incremental goal test. Keep looking. Have I messed up yet?
Ở đây nó đúng, nên ta có thể dừng sớm, ngay khi vi phạm một ràng buộc. Hãy xem đó như một phép kiểm tra đích tăng dần. Cứ tiếp tục xem xét. Mình đã sai chưa?
Have I messed up yet? Depth-first search with these two improvements is called backtracking search.
Mình đã sai chưa? Tìm kiếm theo chiều sâu với hai cải tiến này được gọi là tìm kiếm quay lui.
And in general, just a sort of a sanity check here, you can solve N-Queen problems for about N equals 25, and I'll track this number as we go up.
Và nói chung, để kiểm tra nhanh, bạn giải được bài toán N quân hậu với N khoảng 25, và tôi sẽ theo dõi con số này khi ta đi tiếp.
Of course, you can always throw compute and get a little bit further, but these are exponential situations. All right.
Tất nhiên, bạn luôn có thể dùng thêm sức tính toán để đi xa hơn một chút, nhưng đây là các tình huống mũ. Nhưng chúng vẫn tăng theo hàm mũ. Được rồi.
All right. Here's an example. This is the root, and so we have three successors, which take the first variable and the ordering here, WA. We assign it in three different ways.
Được rồi. Đây là một ví dụ. Đây là gốc, và ta có ba trạng thái kế tiếp, lấy biến đầu tiên theo thứ tự ở đây, WA. Ta gán nó theo ba cách khác nhau.
We'll expand one of them. Now we'll have two things assigned.
Ta mở rộng một trong số đó. Giờ có hai biến đã được gán.
And then right here, we're going to look, and as soon as we see that we've made a mistake, we're going to cross things off.
Và ngay tại đây, ta sẽ kiểm tra, và ngay khi thấy mình đã sai, ta sẽ gạch bỏ.
So the third successor here that has Western Australia and Northern Australia both assigned to red — it's crossed off.
Trạng thái kế tiếp thứ ba ở đây, có Western Australia và Northern Australia đều được gán màu đỏ, bị gạch bỏ.
So the whole tree below it, which is all doomed to failure, we don't even explore, and that's a big improvement. We can keep going.
Vậy toàn bộ cây bên dưới, vốn chắc chắn thất bại, ta không cần khám phá, và đó là một cải tiến lớn. Ta có thể tiếp tục.
Here's the pseudo-code for this, which I won't go through in sort of gory detail, except to note a couple of things. One — it's often implemented recursively.
Đây là mã giả của thuật toán, mà tôi sẽ không đi vào chi tiết, trừ vài điểm cần lưu ý. Một: nó thường được cài đặt bằng đệ quy.
This is a very bad idea with search because we would grow this giant cue that we wanted detailed control over. But here, we pretty much just want to recurse and backtrack.
Với tìm kiếm thông thường đó là ý rất tệ vì ta sẽ có một hàng đợi khổng lồ mà ta muốn kiểm soát chi tiết. Nhưng ở đây, ta chỉ cần đệ quy và quay lui.
So how does it work? If the assignment is complete, you're done because if you're going to break a constraint, we would have seen it along the way.
Vậy nó hoạt động thế nào? Nếu phép gán đã hoàn chỉnh thì xong, vì nếu vi phạm ràng buộc nào thì ta đã thấy trên đường đi.
If it's not complete, then we have to select a variable that isn't assigned, and that's going to be a choice point. And then we have to go through the values in some order.
Nếu chưa hoàn chỉnh, ta phải chọn một biến chưa được gán, và đó là một điểm lựa chọn. Rồi ta phải duyệt các giá trị theo một thứ tự nào đó.
That's going to be a choice point. For now, let's just assume there's a fixed order for those things. Then we're going to check a constraint. So what is this?
Đó cũng là một điểm lựa chọn. Tạm thời cứ giả sử có một thứ tự cố định cho những thứ này. Rồi ta kiểm tra ràng buộc. Vậy đây là gì?
This is depth-first search plus variable ordering plus a [? failing ?] violation. Let's take a look and see how that does in the applet.
Đây là tìm kiếm theo chiều sâu cộng với thứ tự biến cộng với việc dừng khi vi phạm ràng buộc. Hãy xem nó chạy thế nào trong applet.
All right. So let's reset this.
Được rồi. Ta đặt lại.
Let's go to backtracking. None of the other fancy things. First thing we'll get assigned — blue.
Chọn quay lui. Không dùng các tính năng cao cấp khác. Đầu tiên được gán màu xanh dương.
The next thing we'll get assigned — red, because there is no successor with blue because that successor violates a constraint.
Tiếp theo được gán màu đỏ, vì không có trạng thái kế tiếp với màu xanh dương, do nó vi phạm một ràng buộc.
So at least we don't make a mistake on our second step, which we will not discover — we will not sort of fix until we do an exponential amount of work.
Nên ít nhất ta không mắc lỗi ở bước thứ hai, thứ mà ta sẽ không phát hiện, không sửa được cho đến khi làm một lượng việc theo hàm mũ.
So that's good. All right. What's next? Well, blue.
Vậy là tốt. Được rồi. Tiếp theo là gì? Xanh dương.
And then what? Red. Now green because blue would be a violation. And if we do this, it doesn't mean we don't backtrack.
Rồi sao nữa? Đỏ. Giờ là xanh lá vì xanh dương sẽ vi phạm. Và làm vậy không có nghĩa là ta không phải quay lui.
So green didn't actually work out because — let's go back — because even though this green was OK, when you get to this — can you see my cursor — when you get to this one here, suddenly there's nothing left.
Xanh lá thực ra không ổn vì... ta quay lại xem... vì dù màu xanh lá này ổn, nhưng khi đi tới đây... các em thấy con trỏ của tôi không... khi đi tới nút này, đột nhiên không còn gì để chọn.
There's nothing legal, and so we have to go back to the queue. But we can sort of keep going. I'll just let it play. Faster.
Không còn giá trị hợp lệ nào, nên ta phải quay lại hàng đợi. Nhưng ta vẫn có thể tiếp tục. Tôi cứ để nó chạy. Nhanh hơn.
And so there's a little bit of backtracking, but now we can get through the small graph because at least we're only doing things that are legal so far, and there's a limited amount of backtracking when we make something whose problem is a little further downstream.
Vậy là có một chút quay lui, nhưng giờ ta đã giải xong đồ thị nhỏ này vì ít nhất ta chỉ làm những bước hợp lệ cho đến lúc này, và việc quay lui bị giới hạn khi ta chọn một giá trị mà vấn đề của nó nằm hơi xa phía sau.
OK.
Được rồi.
All right. One nice thing about CSPs is often, they are general purpose ideas that aren't like — they're not like A star heuristics that are custom to your search problem.
Được rồi. Một điểm hay của CSP là thường đó là những ý tưởng đa dụng, không giống các hàm heuristic của A star được thiết kế riêng cho bài toán tìm kiếm của em.
They're general purpose, and they often give huge gains in speed across a wide range of problems. There's basically three classes of ideas, and we'll have time to do one to two of them today.
Chúng đa dụng, và thường giúp tăng tốc rất lớn trên nhiều loại bài toán. Về cơ bản có ba nhóm ý tưởng, và hôm nay ta sẽ kịp học một đến hai nhóm.
The first one is ordering. Which variable should I actually work on next, and what order should I try the values? Maybe there are some variables that are better to work on now.
Nhóm đầu là thứ tự. Nên xử lý biến nào tiếp theo, và nên thử các giá trị theo thứ tự nào? Có thể có vài biến nên xử lý trước.
Maybe there are some values that are more likely to work out. So that ordering of how you structure the choice of variable and value exploration is a big deal.
Có thể có vài giá trị dễ thành công hơn. Vì vậy cách sắp xếp thứ tự khi chọn biến và khám phá giá trị là rất quan trọng.
The next thing is filtering. Is there a way to detect inevitable failure early, as opposed to just sort of waiting until you hit a dead end in your search?
Nhóm tiếp theo là lọc (filtering). Có cách nào phát hiện sớm thất bại không thể tránh thay vì cứ chờ đến khi gặp ngõ cụt trong lúc tìm kiếm?
And the last thing is — the last class of approaches for improving CSPs is structure based approaches.
Và nhóm cuối cùng là... nhóm cuối để cải thiện CSP là các cách tiếp cận dựa trên cấu trúc.
Can we look at the graph, detect something efficient about its structure, and use some algorithm that exploits that structure?
Ta có thể nhìn đồ thị, phát hiện điểm hiệu quả trong cấu trúc của nó, và dùng thuật toán khai thác cấu trúc đó không?
And this is going to work for some kinds of graphs and not others, and we'll talk about these algorithms probably on Thursday.
Cách này hiệu quả với một số loại đồ thị chứ không phải mọi loại, và ta sẽ bàn về các thuật toán này có lẽ vào thứ Năm.
So for today, let's talk about filtering.
Hôm nay ta nói về lọc.
So what's filtering about? Filtering is about ruling out candidates.
Vậy lọc là gì? Lọc là loại bỏ các ứng viên.
Unlike assignment, where you say, all right, I'm going to try this variable, filtering is about ruling out candidates for the variables you haven't yet considered in your assignment, OK.
Khác với phép gán, nơi ta nói: được rồi, tôi sẽ thử biến này, lọc là loại bỏ ứng viên cho những biến em chưa xét đến trong phép gán.
So the simplest kind of filtering is something called forward checking. I'll illustrate what it is, and then we'll talk about the general idea behind this and how it extends to other filtering algorithms.
Dạng lọc đơn giản nhất gọi là forward checking. Tôi sẽ minh họa nó là gì, rồi ta sẽ bàn ý tưởng chung đằng sau và cách mở rộng sang các thuật toán lọc khác.
So in filtering, what we do is we keep track of domains for the unassigned variables. This is different. Before, it was just like there are variables, and as we go, we assign them.
Trong lọc, ta theo dõi miền giá trị của các biến chưa được gán. Điều này khác trước. Trước đây chỉ có các biến, và khi đi tiếp, ta gán giá trị cho chúng.
There's the ones that have a value and the ones that don't. Now there's a new idea here.
Có biến đã có giá trị và biến chưa có. Giờ có một ý tưởng mới.
Even before you assign a variable of value, you have a sort of domain cloud sitting there, which says, as far as I know, these are the legal candidates.
Ngay cả trước khi gán giá trị cho biến, nó có một đám mây miền giá trị nằm đó, cho biết theo hiểu biết hiện tại, đây là các ứng viên hợp lệ.
And so here, what we can see is all of the Australia nodes — none of them assigned to a color, but all of them with sort of a cloud, saying all three values, as far as I know, are still in play.
Ở đây ta thấy tất cả các nút của Australia, không nút nào được gán màu, nhưng nút nào cũng có đám mây cho biết cả ba giá trị, theo hiểu biết hiện tại, vẫn còn khả dĩ.
We're going to keep track of domains for these unassigned variables, and under certain circumstances, which will vary by the filtering algorithm, we're going to cross things off. It doesn't mean assigning the variable.
Ta sẽ theo dõi miền giá trị của các biến chưa gán này, và trong một số trường hợp nhất định, tùy thuật toán lọc, ta sẽ gạch bỏ các giá trị. Điều đó không có nghĩa là gán biến.
It just means ruling things out so we can detect future failures. In what's called forward checking, we cross off values that violate a constraint if they're added to the existing assignment.
Nó chỉ là loại bỏ các giá trị để ta phát hiện được thất bại trong tương lai. Trong forward checking, ta gạch bỏ các giá trị vi phạm ràng buộc nếu được thêm vào phép gán hiện có.
So let's look at how this would work. So we look at the initial assignment and we say, everything's OK so far.
Hãy xem nó hoạt động thế nào. Ta xét phép gán ban đầu và thấy mọi thứ đều ổn cho đến giờ.
We have to assign something, and so maybe we assign red to the WA node, Western Australia. So what do things look like now?
Ta phải gán gì đó, nên có thể gán màu đỏ cho nút WA, Western Australia. Vậy bây giờ mọi thứ trông thế nào?
Let's — before I do it, I'll just do it out here. So let's assign red here. So WA has gone from unassigned to assigned. So it's red now.
Trước khi làm, tôi sẽ làm ngay ở đây. Ta gán đỏ ở đây. WA đã từ chưa gán thành đã gán. Giờ nó màu đỏ.
This would be it for backtracking search. We'd assign it and we'd look for successors. But what forward checking does is forward checking says, all right, well, I've made an assignment to WA.
Với tìm kiếm quay lui thì đến đây là hết bước này. Ta gán rồi tìm các nút kế tiếp. Nhưng forward checking thì nói rằng, được rồi, tôi vừa gán giá trị cho WA.
So I'm going to go and I'm going to visit all of the other variables and check to see whether they have any values in their domains, which would trigger a violation — a constraint violation when combined with my current assignment.
Vậy tôi sẽ đi thăm tất cả các biến khác và kiểm tra xem miền giá trị của chúng có giá trị nào gây vi phạm ràng buộc khi kết hợp với phép gán hiện tại không.
And so I would go and I would say, all right, Queensland.
Tôi sẽ đi và nói, được rồi, Queensland.
All right. All of those still work. How about the Northern Territories?
Được rồi. Tất cả đều vẫn dùng được. Còn Northern Territories thì sao?
I would look at that and I would say, well, green and blue are still fine, but red is not going to work anymore because it would violate the inequality constraint against WA.
Tôi nhìn nó và thấy xanh lá và xanh dương vẫn ổn, nhưng đỏ thì không còn dùng được nữa vì nó sẽ vi phạm ràng buộc khác nhau với WA.
So I would go and I would — see if this will work. Magic. OK. It's gone.
Vậy tôi sẽ... xem cái này có chạy không. Phép màu. Được rồi. Nó đã biến mất.
So we would go through and we would visit all of the other variables — not assign them, but just cross things off their domain if it triggers a constraint violation.
Ta sẽ đi qua và thăm tất cả các biến khác, không gán chúng, mà chỉ gạch giá trị khỏi miền của chúng nếu nó gây vi phạm ràng buộc.
So the neighbors to WA would lose red, and then we could keep going.
Các nút kề WA sẽ mất màu đỏ, rồi ta có thể tiếp tục.
We could assign green over here to Queensland, which would assign green to q, and then everything that neighbors q would lose its green value.
Ta có thể gán xanh lá ở đây cho Queensland, tức là gán xanh lá cho q, và rồi mọi thứ thì mọi nút kề với q sẽ mất giá trị green.
And so what you can see is even in the variables that I haven't assigned yet, I'm starting to see variables having their domains shrink.
Như các em thấy, ngay cả với những biến mà tôi chưa gán, ta đã bắt đầu thấy các biến bị thu hẹp miền giá trị.
And if a domain ever shrinks to 0, that means there's not going to be any possible way to do an assignment there, and that means we might as well stop now.
Và nếu một miền giá trị co lại về 0, nghĩa là sẽ không còn cách nào để gán giá trị ở đó, và điều đó có nghĩa là ta nên dừng lại ngay.
So whenever you do filtering and a domain goes empty, you backtrack. All right. So, sorry. Keep going.
Vậy mỗi khi lọc mà có một miền giá trị rỗng, thì ta quay lui. Được rồi. Xin lỗi. Tiếp tục nhé.
As soon as we assign to v a blue, even though we haven't tried to assign anything to Australia, it's lost all of its values from its domain, and we know that there's no way to solve this.
Ngay khi ta gán blue cho v, dù ta chưa hề thử gán gì cho Australia, nó đã mất hết giá trị trong miền của mình, và ta biết là không có cách nào giải được.
Now, if you think, looking really closely, you might already realize that we are in trouble. Let me get a color.
Giờ nếu các em nhìn thật kỹ, có thể các em đã nhận ra ta gặp rắc rối rồi. Để tôi lấy một màu khác.
You might realize we were already in trouble up here, right, because we knew NT was blue and we also knew SA was going to be blue.
Các em có thể nhận ra ta đã gặp rắc rối từ trên này, vì ta biết NT là blue và ta cũng biết SA sẽ là blue.
And if you look closely, they're next to each other. But this is not forward checking's problem. Forward checking does not think this hard.
Nhìn kỹ thì hai nơi này nằm cạnh nhau. Nhưng đây không phải lỗi của forward checking. Forward checking không nghĩ sâu đến vậy.
All it does is check for immediate violations between unassigned variables and the assignment to date. Anything further is thinking too hard for forward checking. OK. Any questions on that?
Nó chỉ kiểm tra các vi phạm trực tiếp giữa các biến chưa gán và phép gán hiện tại. Xa hơn nữa là nghĩ quá sâu đối với forward checking. OK. Có câu hỏi nào về phần này không?
Let's do a demo on that. We'll do one more idea, and then we'll take a break. Let's do a demo on that one. So let's go to forward checking.
Ta xem demo nhé. Ta sẽ làm thêm một ý nữa rồi nghỉ giải lao. Xem demo cho ý này. Ta chuyển sang forward checking.
So even before I assign anything, the domains have appeared inside the variables, and they all have complete domains because nothing's happened yet.
Ngay cả trước khi tôi gán gì, các miền giá trị đã hiện trong các biến, và đều còn đầy đủ vì chưa có gì xảy ra.
But as soon as I assign to the first variable, which in this ordering, is the bottom left. And the kind of strike order here is blue first, then red, then green.
Nhưng ngay khi tôi gán biến đầu tiên, trong thứ tự này là ô dưới cùng bên trái. Thứ tự thử ở đây là blue trước, rồi red, rồi green.
If I assign blue, think about what's going to happen.
Nếu tôi gán blue, hãy nghĩ xem chuyện gì sẽ xảy ra.
We're going to look at all the other variables that are connected by a constraint, which are just its neighbors, and we're going to cross blue off. So there it is.
Ta sẽ xét mọi biến khác có ràng buộc với nó, tức là các biến kề, và ta gạch blue khỏi miền của chúng. Đây rồi.
We've propagated the constraint out, but not very far. And so when we go to the next one, it's either going to be red or green because blue has already been crossed off.
Ta đã lan truyền ràng buộc ra ngoài, nhưng chưa xa lắm. Và khi sang biến tiếp theo, nó sẽ là red hoặc green vì blue đã bị gạch rồi.
We're going to assign red, and a bunch of its neighbors lose a variable — lose a value. Blue. Now look at this. Do you have a bad feeling about this?
Ta gán red, và một loạt biến kề mất một biến... à, mất một giá trị. Blue. Giờ nhìn này. Các em có linh cảm xấu về chuyện này không?
I have a bad feeling about this. Do you know who doesn't have a bad feeling about this? Forward checking. Forward checking is going, all right, so we assign here, we assign here.
Tôi có linh cảm xấu. Các em biết ai không có linh cảm xấu không? Forward checking. Forward checking cứ thế: được, ta gán ở đây, gán ở đây.
Now we detect the problem. We don't detect the problem until we actually trigger the constraint check between those two variables with an assignment conflicting with an adjacent unassigned value.
Giờ mới phát hiện ra vấn đề. Ta không phát hiện vấn đề cho đến khi thực sự kích hoạt kiểm tra ràng buộc giữa hai biến đó bằng một phép gán xung đột với một giá trị chưa gán ở biến kề.
So of course, we're going to have to backtrack. So forward checking helps us avoid some future mistakes, but it's still going to make mistakes. You're still going to have to backtrack.
Nên tất nhiên ta sẽ phải quay lui. Vậy forward checking giúp tránh một số sai lầm về sau, nhưng vẫn sẽ mắc sai lầm. Ta vẫn phải quay lui.
And when you backtrack, domains repopulate, and then we keep going through. And maybe this time — no, not quite. This time, we get through. OK.
Và khi quay lui, các miền giá trị được khôi phục, rồi ta tiếp tục chạy. Có thể lần này... không, chưa được. Lần này thì qua được. OK.
So that's filtering. But in the back of our minds, we realize we could be working harder. We could be thinking further into the future to detect these violations before they happen.
Đó là lọc. Nhưng trong đầu ta nhận ra mình có thể làm việc chăm chỉ hơn. Ta có thể nghĩ xa hơn về tương lai để phát hiện các vi phạm này trước khi chúng xảy ra.
OK. In general, forward checking is going to propagate information from assigned to unassigned variables, but does not provide early detection for all failures.
OK. Nói chung, forward checking lan truyền thông tin từ biến đã gán sang biến chưa gán, nhưng không phát hiện sớm mọi thất bại.
In particular, it doesn't detect looming conflicts between unassigned and other unassigned variables. That would require checking lots of pairs of variables all throughout the graph to see if anything's broken anywhere.
Cụ thể, nó không phát hiện các xung đột sắp xảy ra giữa các biến chưa gán với nhau. Điều đó đòi hỏi kiểm tra rất nhiều cặp biến trên khắp đồ thị để xem có chỗ nào hỏng không.
We're going to do that. We're going to do that right after the break, but let's look at the reason why we want this.
Ta sẽ làm điều đó. Ta sẽ làm ngay sau giờ nghỉ, nhưng trước hết xem vì sao ta cần nó.
We want this here because if you look at this, as before, NT and SA can't both be blue, but that involves looking at those two variables at the same time.
Ta cần nó vì, như trước, nhìn ở đây, NT và SA không thể cùng là blue, nhưng điều đó đòi hỏi xét hai biến đó cùng lúc.
And we should be able to detect that. So we're going to talk about algorithms for richer constraint propagation, which reason from constraint to constraint and propagate these vanishing domains throughout the graph.
Và ta phải phát hiện được điều này. Vì vậy ta sẽ nói về các thuật toán lan truyền ràng buộc mạnh hơn, suy luận từ ràng buộc này sang ràng buộc khác và lan truyền các miền giá trị đang biến mất khắp đồ thị.
When we come back from break, I will show you an algorithm for constraint propagation involving a concept called arc consistency, which is our core conceptual piece for this.
Sau giờ nghỉ, tôi sẽ chỉ cho các em một thuật toán lan truyền ràng buộc dựa trên khái niệm gọi là nhất quán cung, là phần khái niệm cốt lõi cho việc này.
Then we'll talk about ordering based methods, and then we'll be done for the day. So let's take a couple minute break now, and when we get back, arc consistency.
Sau đó ta sẽ nói về các phương pháp dựa trên thứ tự, rồi hôm nay ta kết thúc. Giờ nghỉ vài phút nhé, và khi quay lại sẽ là nhất quán cung.
All right.
Được rồi.
All right.
Được rồi.
The moment we've all been waiting for — arc consistency. Until today, we didn't even know about arc consistency. All right.
Khoảnh khắc ta chờ đợi bấy lâu: nhất quán cung. Cho đến hôm nay, ta còn chưa biết gì về nhất quán cung. Được rồi.
So we were talking about forward checking like it was checking some constraints, but then there were other constraints that it didn't check, and if only it would check them.
Ta đã nói về forward checking như thể nó kiểm tra một số ràng buộc, nhưng còn những ràng buộc khác mà nó không kiểm tra, giá mà nó kiểm tra được.
What is this checking a constraint? What is this? So we need to formalize the notion of what it means to have checked a constraint.
Kiểm tra một ràng buộc nghĩa là gì? Nó là gì vậy? Vậy ta cần hình thức hóa khái niệm "đã kiểm tra một ràng buộc" nghĩa là gì.
And the key concept that is going to show up in these algorithms is almost your intuitive notion of checking a constraint, with a little twist.
Và khái niệm then chốt sẽ xuất hiện trong các thuật toán này gần như chính là cách hiểu trực giác của bạn về việc kiểm tra ràng buộc, chỉ thêm một chút khác biệt.
And it has to do with the notion of a consistency of an arc. So an arc — remember there's a graph, right?
Nó liên quan đến khái niệm nhất quán của một cung. Vậy một cung, nhớ là ta có một đồ thị, đúng không?
There's a graph where we have nodes for the variables and we have edges connecting them if there's a constraint between those two variables.
Đồ thị có các nút cho các biến và các cạnh nối chúng nếu có ràng buộc giữa hai biến đó.
So an arc — if this is a, b, c — an arc from a to b is going to be almost like the edge to a to b, but it's going to be directed.
Vậy một cung, nếu đây là a, b, c, cung từ a đến b gần giống cạnh a b, nhưng nó có hướng.
And that means for every edge on the graph, there are actually two arcs you could check — a to b and b to a. So it's directional, even though the underlying constraint graph isn't.
Nghĩa là với mỗi cạnh trên đồ thị, thực ra có hai cung ta có thể kiểm tra: a đến b và b đến a. Vậy nó có hướng, dù đồ thị ràng buộc bên dưới thì không.
There's just a constraint on a and b, but we can check whether it's satisfied in two different directions, which I'll get into in a minute.
Chỉ có một ràng buộc trên a và b, nhưng ta có thể kiểm tra xem nó có được thỏa mãn không theo hai hướng khác nhau, mà lát nữa tôi sẽ nói.
The other thing is conceptually, you can check an arc between two things that aren't connected by a constraint.
Điều nữa là về mặt khái niệm, bạn có thể kiểm tra một cung giữa hai thứ không nối với nhau bằng ràng buộc.
So I could check whether or not a to c was OK, even though there isn't a constraint there. So it is almost the same as a constraint arc, but it's not quite.
Tôi có thể kiểm tra a đến c có ổn không, dù ở đó không có ràng buộc. Vậy nó gần giống một cung ràng buộc, nhưng không hoàn toàn.
It's a directed arc between any two nodes. And we say that arc is consistent. Intuitively, it's consistent if there's no constraint violation along that arc. But formally, it's sort of half of that.
Nó là cung có hướng giữa hai nút bất kỳ. Và ta nói cung đó nhất quán. Theo trực giác, nó nhất quán nếu không có vi phạm ràng buộc nào dọc theo cung đó. Nhưng chính thức thì nó chỉ là một nửa của điều đó.
It's consistent if, for every x in the tail of the arc, there is some y in the head, which could be assigned without violating a constraint.
Nó nhất quán nếu với mọi x ở đuôi của cung, có một y nào đó ở đầu có thể được gán mà không vi phạm ràng buộc.
So this means sort of — if there was actually an assignment to a and b or to x and y, we could check whether the assignment satisfies a constraint.
Nghĩa là đại khái nếu thực sự có phép gán cho a và b hay x và y, ta có thể kiểm tra phép gán có thỏa ràng buộc không.
But in general, an arc is going to have a couple of things in the tail and a couple of things in the head.
Nhưng nói chung, một cung sẽ có vài giá trị ở đuôi và vài giá trị ở đầu.
And the notion of consistent is for everything in the tail, there is at least one OK option in the head. So let's do some examples.
Và khái niệm nhất quán là với mọi giá trị ở đuôi, có ít nhất một lựa chọn ổn ở đầu. Ta làm vài ví dụ.
We could look here and we could say, all right, Western Australia here is assigned. It's assigned to red.
Ta nhìn vào đây và nói, được rồi, Western Australia ở đây đã được gán, gán màu đỏ.
The Northern Territories are not assigned, but I can still look at the two of them and check if this arc is consistent, all right? So let's do it.
Northern Territory thì chưa được gán, nhưng tôi vẫn có thể xét cả hai và kiểm tra cung này có nhất quán không. Làm thử nhé.
We have to ask the question. We check everything in the tail.
Ta phải đặt câu hỏi. Ta kiểm tra mọi thứ ở đuôi.
So we look at the Northern Territories and we say, is there anything in your domain, even though it's unassigned — is there anything in your remaining domain which would have no continuation into the head?
Ta nhìn Northern Territory và hỏi, trong miền giá trị của bạn, dù chưa gán, có giá trị nào trong miền còn lại mà không có cách tiếp tục nào sang đầu không?
So we say, well, if I assigned you blue, would it be OK? Yeah, that would be OK. If I assigned you green, would it be OK? Yeah, that would be OK.
Nếu tôi gán xanh dương cho bạn thì có ổn không? Có, ổn. Nếu gán xanh lá thì có ổn không? Có, ổn.
What if I assigned you red to NT? Not OK.
Còn nếu gán đỏ cho NT? Không ổn.
So red is something in the tail for which there is no assignments in the head, which doesn't cause a constraint violation. OK. So this arc is not consistent.
Vậy đỏ là giá trị ở đuôi mà không có phép gán nào ở đầu mà không gây vi phạm ràng buộc. OK. Vậy cung này không nhất quán.
We can, however, make it consistent. What can we do? We can remove things from the tail. What can I do?
Tuy nhiên ta có thể làm cho nó nhất quán. Ta làm được gì? Ta có thể loại bỏ giá trị khỏi đuôi. Tôi làm gì?
Well, I can do just what forward checking did. I can wipe out the value that caused a conflict. OK. So now we can check other consistencies, but let's try this one. q to WA.
Tôi có thể làm đúng như forward checking. Xóa giá trị gây xung đột. OK. Giờ ta có thể kiểm tra các cung khác, nhưng thử cái này: q đến WA.
You'll notice these two don't actually — they are not connected by a constraint, so it should be easy to check.
Bạn sẽ thấy hai cái này thực ra không nối với nhau bằng ràng buộc, nên kiểm tra sẽ dễ.
But I can ask the question — if I assign red to q, is there an assignment which does not yet violate a constraint for WA? Yes. Red. How about green?
Nhưng tôi có thể hỏi: nếu gán đỏ cho q, có phép gán nào cho WA mà chưa vi phạm ràng buộc không? Có. Đỏ. Còn xanh lá?
Yes, red, blue. Yes, red. So this arc is already consistent. I do not need to do anything to it in order to make it consistent.
Có, đỏ, xanh dương. Có, đỏ. Vậy cung này đã nhất quán rồi. Tôi không cần làm gì với nó để làm cho nó nhất quán.
So in general, there's a question of how do you remember this? Right? There's heads and there's tails. It's very easy to get the order.
Nói chung, câu hỏi là làm sao nhớ được điều này? Đúng không? Có đầu và có đuôi. Rất dễ nhầm thứ tự.
Here's how I remember it. Remember, CSPs — the constraints are like rules, and these algorithms are like police. They're going to go and they're going to enforce the rules.
Tôi nhớ như thế này. Nhớ là trong CSP, các ràng buộc giống như luật, còn các thuật toán này giống như cảnh sát. Họ sẽ đi thực thi các luật.
And you can imagine this arc is going to get pulled over by your algorithm, which is the CSP police. So here, they pull it over.
Bạn có thể tưởng tượng cung này sẽ bị thuật toán của bạn chặn xe lại, tức là cảnh sát CSP. Họ chặn xe lại.
And what do they do when they pull the arc over? Right, they pop open the trunk and they look for anything that's illegal.
Và họ làm gì khi chặn cung lại? Họ mở cốp xe ra và tìm bất cứ thứ gì phạm pháp.
So they're going to fish around in the trunk and if they find anything bad, they're going to take it out. So this is the algorithm. You pull over the arcs one by one.
Họ sẽ lục trong cốp xe và nếu thấy thứ gì xấu, họ sẽ lấy ra. Đó chính là thuật toán. Bạn chặn từng cung một.
The algorithms differ in terms of which arcs you pull over first, how many you pull over — all that stuff. But all these algorithms have the same shape.
Các thuật toán khác nhau ở chỗ chặn cung nào trước, chặn bao nhiêu cung, những thứ như vậy. Nhưng tất cả các thuật toán này đều có cùng khuôn mẫu.
You pull over an arc, you fish around in its trunk, and if there's anything in that trunk — any assignment to the tail, which is guaranteed to fail, given what's left in the head — you cross it off.
Bạn kéo một cung ra, lục trong "cốp xe" của nó, và nếu trong cốp đó có thứ gì — bất kỳ phép gán nào ở đuôi chắc chắn sẽ thất bại, với những gì còn lại ở đầu — thì bạn gạch nó đi.
OK. That's it. That's enforcing the consistency of a single arc. Now we're going to have to do a whole bunch of arcs in order to get a filtering algorithm.
OK. Chỉ có vậy thôi. Đó là đảm bảo tính nhất quán của một cung. Giờ ta sẽ phải làm với cả loạt cung để có được một thuật toán lọc.
OK. So remember — delete from the tail. Delete from the tail. OK.
OK. Nhớ nhé: xóa khỏi đuôi. Xóa khỏi đuôi. OK.
Forward checking. Forward checking was enforcing the consistency of the arcs that point to each new assignment.
Forward checking. Forward checking là đảm bảo tính nhất quán của các cung trỏ tới mỗi phép gán mới.
So when I had that, if I assigned to red here, I would say, all right, let's go to NT and delete anything that causes a conflict. Let's go to q.
Nên khi tôi gán màu đỏ ở đây, tôi sẽ nói: được rồi, sang NT và xóa mọi giá trị gây xung đột. Sang q.
New South Wales, Victoria, Southern Australia.
New South Wales, Victoria, Southern Australia.
And if all you do is, upon every assignment, look at all the arcs pointing to that assignment and enforce consistency, which means delete things from their tail if they cause a constraint violation, you would recover the forward checking algorithm.
Và nếu mỗi lần gán, bạn chỉ xét các cung trỏ tới phép gán đó và đảm bảo tính nhất quán, nghĩa là xóa khỏi đuôi những giá trị vi phạm ràng buộc, thì bạn có lại thuật toán forward checking.
Now we can start talking about enforcing the consistency of lots of arcs — even ones that don't point to our assignment. And that's going to give us richer filtering algorithms.
Giờ ta có thể bàn đến việc đảm bảo tính nhất quán của nhiều cung, kể cả những cung không trỏ tới phép gán của ta. Và điều đó cho ta các thuật toán lọc mạnh hơn.
So we can talk about arc consistency of an entire CSP. So let's look at this.
Vậy ta có thể nói về nhất quán cung của cả một CSP. Hãy xem ví dụ này.
This is a CSP that's sort of in like a — we're in the middle of the movie here, OK. WA and q have been assigned — red and green.
Đây là một CSP đang ở giữa chừng — ta đang ở giữa bộ phim, OK. WA và q đã được gán: đỏ và xanh lá.
And that's shown on the map, as well. NT, NSW, and SA have had their domains reduced by some previous pruning.
Điều đó cũng hiện trên bản đồ. NT, NSW và SA đã bị thu nhỏ miền giá trị do một lần cắt tỉa trước đó.
So they haven't been assigned yet, even though some of them only have one value left. They haven't been assigned, but they're in various kind of stages of having been filtered.
Chúng chưa được gán, dù có biến chỉ còn một giá trị. Chúng chưa được gán, nhưng đang ở các giai đoạn lọc khác nhau.
And so what we can do is we can look at this and say, all right, here's a partially assigned CSP. I can go visit arcs.
Và ta có thể nhìn vào đây và nói, được rồi, đây là một CSP đã gán một phần. Tôi có thể đi thăm các cung.
It can be like — go be the arc police. We're going to visit all the arcs and we're going to check them. So first, we check this arc.
Giống như là — hãy làm cảnh sát cung. Ta sẽ đi qua mọi cung và kiểm tra chúng. Đầu tiên, kiểm tra cung này.
We checked V to NSW. First, we look at our graph and we notice that they are neighbors. All right.
Ta kiểm tra V tới NSW. Trước hết, nhìn đồ thị ta thấy chúng là láng giềng. Được rồi.
This is the first time we're checking the consistency of an arc that doesn't point to an assignment. So I go through and I check the tail is V.
Đây là lần đầu ta kiểm tra tính nhất quán của một cung không trỏ tới phép gán. Tôi kiểm tra, đuôi là V.
So I'm going to check all the values. I'm going to get my police pen out here in white.
Tôi sẽ kiểm tra mọi giá trị. Tôi lấy bút cảnh sát màu trắng ra.
I'm going to check the values and I'm going to say, what if I assigned V blue? Is there a choice at NSW that will avoid a constraint violation?
Tôi kiểm tra các giá trị và hỏi: nếu tôi gán V màu xanh dương thì sao? Ở NSW có lựa chọn nào tránh được vi phạm ràng buộc không?
Yes. I could assign it red. You're like, but there's one that creates a problem. That's fine.
Có. Tôi có thể gán màu đỏ. Bạn sẽ nói: nhưng có một giá trị gây vấn đề. Không sao.
There only has to be some way that the head can be assigned in order to license things staying in the tail. So blue is fine. Check. OK.
Chỉ cần có một cách gán nào đó cho đầu để cho phép giá trị đó ở lại trong đuôi. Vậy xanh dương ổn. Đạt. OK.
How about green? That's fine because if I assign green at V, then NSW could be either red or blue. What if I assign red?
Còn xanh lá? Ổn, vì nếu gán xanh lá ở V thì NSW có thể là đỏ hoặc xanh dương. Nếu gán đỏ thì sao?
Well now, at NSW, I can't use red, but I can use blue. So this arc checks out. We declare it to be consistent and we let it get on with its day.
Lúc này ở NSW không dùng được đỏ, nhưng dùng được xanh dương. Vậy cung này đạt. Ta tuyên bố nó nhất quán và để nó đi tiếp việc của mình.
All right. Let's look at this one. SA to NSW. Right.
Được rồi. Xem cung này. SA tới NSW. Đúng.
Keep staring at the map. SA and NSW are adjacent, so I'm going to look at SA and I'm going to say, well, what's in the tail? Blue.
Cứ nhìn vào bản đồ. SA và NSW kề nhau, nên tôi nhìn SA và hỏi, trong đuôi có gì? Xanh dương.
If I pick blue, do I have a choice at NSW that will be OK?
Nếu chọn xanh dương, ở NSW có lựa chọn nào ổn không?
Survey says yes. So I don't have to cross anything out. So far, this is pretty boring because I've checked a bunch of consistent arcs. But let's check the arc in the other direction.
Khảo sát cho thấy là có. Nên tôi không phải gạch gì cả. Đến giờ khá chán vì tôi mới kiểm tra một loạt cung nhất quán. Nhưng hãy kiểm tra cung theo chiều ngược lại.
OK, so it's the same constraint that NSW and SA can't be the same, but head and tail have been flipped. It's important for understanding these algorithms. And so we need to check it again.
Vẫn là ràng buộc NSW và SA không được giống nhau, nhưng đầu và đuôi đã đảo. Điều này quan trọng để hiểu các thuật toán này. Nên ta cần kiểm tra lại.
So now I look at NSW and I say, is read OK? Well, if NSW is red, V could be blue. Is blue OK? Well, if NSW was blue, we're toast.
Giờ tôi nhìn NSW và hỏi, đỏ có ổn không? Nếu NSW là đỏ thì V có thể là xanh dương. Xanh dương có ổn không? Nếu NSW là xanh dương thì toi.
So we have to fish out of its trunk. Got to erase that. Got to erase that. Now it's consistent.
Nên ta phải lôi nó ra khỏi cốp. Phải xóa cái đó. Phải xóa cái đó. Giờ nó nhất quán.
It was not consistent before, but now that I've deleted blue from the domain of NSW, this arc has become consistent. OK. There's a tricky case. Anybody see the tricky case?
Trước đó nó không nhất quán, nhưng giờ khi tôi đã xóa xanh dương khỏi miền giá trị của NSW, cung này đã trở nên nhất quán. OK. Có một trường hợp hóc búa. Có ai thấy trường hợp hóc búa không?
We were just here. We just checked V pointing to NSW. We just declared it consistent, but that was on the basis of having blue and red available in the head at NSW.
Ta vừa ở đây. Ta vừa kiểm tra V trỏ tới NSW. Ta vừa tuyên bố nó nhất quán, nhưng điều đó dựa trên việc đầu còn cả xanh dương và đỏ ở NSW.
And one of those is gone. So the consistency may no longer hold.
Và một trong hai giá trị đó đã mất. Nên tính nhất quán có thể không còn đúng nữa.
And so I have to go back to V and I have to check — are there any assignments to V which cannot be extended to assignments at NSW without violating a constraint?
Vì vậy tôi phải quay lại V và kiểm tra — có phép gán nào cho V mà không thể mở rộng sang phép gán cho NSW mà không vi phạm ràng buộc không?
Blue — OK. Green — OK. Red — no longer OK. It used to be OK because blue was supporting red's OK-ness.
Blue — được. Green — được. Red — không còn được nữa. Trước đây red ổn vì blue hỗ trợ nó.
But blue is gone, so we have to check this one again. And in order to make it consistent, I have to make further modification. Now, it's consistent again.
Nhưng blue đã bị xóa, nên ta phải kiểm tra lại cung này. Và để làm nó nhất quán, tôi phải sửa đổi thêm. Giờ nó lại nhất quán.
OK.
OK.
So any time you delete a value from a domain, every arc pointing into it that was declared consistent is now questionable again because that value that you just deleted may have been supporting their consistency.
Vậy mỗi khi bạn xóa một giá trị khỏi miền giá trị, mọi cung trỏ vào nó mà đã được xác nhận là nhất quán giờ lại đáng ngờ, vì giá trị bạn vừa xóa có thể đã hỗ trợ tính nhất quán của chúng.
OK. So I could keep doing this. The whole reason to do this is actually a completely different arc. It's the one between SA and NT, neither of which is assigned.
OK. Tôi có thể cứ làm tiếp như vậy. Thật ra lý do để làm việc này là một cung hoàn toàn khác. Đó là cung giữa SA và NT, cả hai đều chưa được gán.
But if you just look at them for a second — if you look at that arc in either direction, you will see that, in fact, you have to delete blue from the tail, which results in an empty domain, and an empty domain means a detected failure, which means backtracking.
Nhưng nếu bạn nhìn chúng một chút — nếu nhìn cung đó theo cả hai chiều, bạn sẽ thấy thực ra phải xóa blue khỏi đuôi, dẫn đến một miền rỗng, và miền rỗng nghĩa là phát hiện thất bại, tức là phải quay lui.
So if we went around and we just kind of checked all the different arcs, we would know as soon as we assigned WA to red and Q, we made green.
Nên nếu ta đi một vòng và kiểm tra tất cả các cung, ta sẽ biết ngay khi vừa gán WA là red và Q là green.
We would be able to detect this sort of secondary violation between unassigned variables.
Ta sẽ phát hiện được vi phạm thứ cấp này giữa các biến chưa được gán.
This is a kind of constraint propagation, and if you enforce the arc consistency of all arcs at once — that's called making the graph arc consistent — that is a powerful kind of filtering.
Đây là một dạng lan truyền ràng buộc, và nếu bạn bắt buộc nhất quán cung cho mọi cung cùng lúc — gọi là làm cho đồ thị nhất quán cung — thì đó là một kiểu lọc rất mạnh.
OK. What do we need to know?
OK. Ta cần biết gì?
If x loses a value, its neighbors need to be rechecked, which might mean their neighbors need to be rechecked, which might mean their neighbors need to be rechecked.
Nếu x mất một giá trị, các nút lân cận của nó cần được kiểm tra lại, nghĩa là lân cận của chúng cũng cần được kiểm tra lại, và rồi lân cận của chúng nữa cũng cần kiểm tra lại.
You could worry, is this whole thing going to even converge? OK. Arc consistency is going to detect failure earlier than forward checking because this was the case where we were like, forward checking.
Bạn có thể lo là liệu quá trình này có hội tụ không? OK. Nhất quán cung phát hiện thất bại sớm hơn forward checking, vì đây là trường hợp mà forward checking không thấy.
Just think a little harder. Arc consistency will expose this if you make the graph arc consistent. You can run this either as a preprocessor, or more commonly, you run this after every assignment.
Phải nghĩ kỹ hơn một chút. Nhất quán cung sẽ lộ ra điều này nếu bạn làm cho đồ thị nhất quán cung. Bạn có thể chạy nó như bước tiền xử lý, hoặc phổ biến hơn là chạy sau mỗi phép gán.
You're still in a backtracking search, but after every assignment, you go around, you think really hard, you do a bunch of consistency checks, and you filter a bunch of stuff so that you don't have to backtrack quite so much.
Vẫn là tìm kiếm quay lui, nhưng sau mỗi phép gán, bạn đi một vòng, suy nghĩ thật kỹ, làm hàng loạt kiểm tra nhất quán và lọc bớt nhiều thứ để không phải quay lui nhiều như vậy.
So this is great. What's the downside of enforcing arc consistency on a graph after every assignment in a backtracking search? Your hand was up really quick. Yeah.
Vậy là rất tốt. Nhược điểm của việc bắt buộc nhất quán cung trên đồ thị sau mỗi phép gán trong tìm kiếm quay lui là gì? Bạn giơ tay nhanh thật. Mời bạn.
Yeah, runtime could be bad. I didn't even tell you if this thing converges. Spoiler alert — it converges. But it's a lot of compute.
Đúng, thời gian chạy có thể tệ. Tôi còn chưa nói nó có hội tụ không. Tiết lộ trước: nó hội tụ. Nhưng tốn rất nhiều tính toán.
So you won't have to do as many assignments, in general, but for each assignment, you're going to have to do all of this work and bookkeeping in order to enforce arc consistency.
Nói chung bạn sẽ ít phải gán hơn, nhưng với mỗi phép gán, bạn sẽ phải làm toàn bộ công việc và ghi chép này để đảm bảo nhất quán cung.
This should remind you of something from search. Does this remind anybody of anything you learned last week? Like really loosely. This is like — yeah.
Điều này nên gợi bạn nhớ đến thứ gì đó trong tìm kiếm. Có ai thấy nó giống gì đã học tuần trước không? Chỉ cần giống một cách mơ hồ. Nó giống — mời bạn.
Uniform cost search?
Uniform cost search?
OK. It reminds me of A star because in A star, you do a lot of work on each node to figure out which nodes to not explore, right?
OK. Tôi thấy nó giống A star, vì trong A star bạn làm nhiều việc trên mỗi nút để biết nên không khám phá nút nào, đúng không?
This is doing a lot of work on each assignment so you don't have to do as many assignments. Are you going to come out ahead? Maybe.
Ở đây cũng làm nhiều việc trên mỗi phép gán để không phải gán nhiều. Liệu có lợi hơn không? Có thể.
And so there's a trade-off between doing more filtering and just making the core search run faster. In general, this is a very powerful method, and it usually pays for itself.
Vậy có sự đánh đổi giữa lọc nhiều hơn và làm cho tìm kiếm cốt lõi chạy nhanh hơn. Nhìn chung đây là phương pháp rất mạnh, và thường đáng giá.
But it varies, problem by problem. Also remember to delete from the tail. I'll try to tell you this every four slides or something. Here's the algorithm.
Nhưng tùy từng bài toán. Cũng nhớ là xóa từ đuôi. Tôi sẽ cố nhắc điều này cứ khoảng bốn slide một lần. Đây là thuật toán.
This is an algorithm called AC3. Arc consistency is a property. A graph is either arc consistent or not. It's arc consistent if all arcs in the graph are consistent.
Thuật toán này gọi là AC3. Nhất quán cung là một tính chất. Một đồ thị hoặc nhất quán cung hoặc không. Nó nhất quán cung nếu mọi cung trong đồ thị đều nhất quán.
You can have graphs in which some arcs are consistent and some are not. Arc consistency means all arcs are consistent.
Có đồ thị mà một số cung nhất quán và một số thì không. Nhất quán cung nghĩa là mọi cung đều nhất quán.
The algorithm that gets you there is called AC3, or rather, this particular algorithm is called AC3, and it gets you there. How does it work? Here's the highlights.
Thuật toán giúp đạt được điều đó gọi là AC3, hay đúng hơn, thuật toán cụ thể này gọi là AC3, và nó giúp ta đạt được điều đó. Nó hoạt động thế nào? Đây là những điểm chính.
So first of all, so far, we're only talking about binary CSPs, because otherwise, you're talking about arcs and how they interact with three way constraints, and we haven't talked about that yet.
Trước hết, cho đến giờ ta chỉ nói về CSP nhị phân, vì nếu không, ta phải bàn về các cung tương tác thế nào với ràng buộc ba biến, mà ta chưa nói đến.
So they're only for binary CSPs or this algorithm is, and what do you do? You're going to have a queue, right?
Nên thuật toán này chỉ dành cho CSP nhị phân, và bạn làm gì? Bạn sẽ có một hàng đợi, đúng không?
So inside this search, which has a queue, you're going to have a filtering algorithm, which has a queue. Like Inception. OK. So what we're going to do with our queue is the following.
Bên trong tìm kiếm này vốn có một hàng đợi, bạn sẽ có một thuật toán lọc, cũng có một hàng đợi. Như phim Inception. OK. Ta sẽ làm với hàng đợi như sau.
We're going to pop an arc off the queue. The queue is our to-do list of arcs to check for consistency — to pull over and pull things out of the trunk.
Ta lấy một cung ra khỏi hàng đợi. Hàng đợi là danh sách việc cần làm gồm các cung cần kiểm tra nhất quán, như tấp xe vào lề để lấy đồ ra khỏi cốp.
So we're going to remove something from the queue and we're going to take out all the inconsistent values.
Vậy ta lấy một cung ra khỏi hàng đợi và loại bỏ tất cả các giá trị không nhất quán.
And if you found an inconsistent value in the process of making this arc consistent, you're going to throw a whole bunch of its neighbors back on the queue because you just invalidated their consistency.
Và nếu bạn tìm thấy một giá trị không nhất quán trong quá trình làm cho cung này nhất quán, bạn sẽ ném cả loạt nút láng giềng của nó trở lại hàng đợi, vì bạn vừa làm mất tính nhất quán của chúng.
That's it. That's the flow. You take things off the queue, and whenever you actually change something, you throw some neighbors back on the queue. What do you do when you pull over an arc?
Chỉ có vậy thôi. Đó là luồng chạy. Bạn lấy các cung ra khỏi hàng đợi, và mỗi khi thực sự thay đổi gì đó, bạn lại đưa một số láng giềng trở lại hàng đợi. Khi lấy một cung ra thì bạn làm gì?
You go through every value in the tail domain. I should write a t. Every value in the tail domain. Every value in the head domain.
Bạn duyệt qua mọi giá trị trong miền của đuôi. Lẽ ra tôi phải viết chữ t. Mọi giá trị trong miền của đuôi. Mọi giá trị trong miền của đầu.
Did I get those in the right order? You go through every value in the tail domain and then you go through every value in the head domain, and you check, hey, constraint?
Tôi nói đúng thứ tự chưa nhỉ? Bạn duyệt qua mọi giá trị trong miền của đuôi rồi duyệt qua mọi giá trị trong miền của đầu, và kiểm tra xem ràng buộc thế nào.
Are these two OK? And then if there's values in the tail for which no values in the head are OK, you delete them. So what's the runtime here?
Hai giá trị này có ổn không? Và nếu có giá trị ở đuôi mà không giá trị nào ở đầu phù hợp, bạn xóa nó đi. Vậy thời gian chạy là bao nhiêu?
We got two for loops, right? We've got to check all the domains in the tail, and then we've got to do a loop over everything in the head.
Ta có hai vòng lặp for, đúng không? Ta phải kiểm tra mọi giá trị trong miền của đuôi, rồi lặp qua mọi giá trị trong miền của đầu.
So the stuff down here is going to be d squared, right? We've got to check everything in the cross-product, at worst. How much work are you going to do up here?
Vậy phần bên dưới này là d bình phương, đúng không? Trong trường hợp xấu nhất phải kiểm tra toàn bộ tích Descartes. Còn phần bên trên này thì làm bao nhiêu việc?
Well, how many arcs are you going to have to look at? Well, if you didn't re-in-queue things and there's n nodes — how many arcs? n squared.
Ta phải xét bao nhiêu cung? Nếu không đưa lại vào hàng đợi và có n nút thì có bao nhiêu cung? n bình phương.
You look at all of them in both directions. But here's the problem. Whenever you process an arc, you might delete something from the tail.
Bạn xét tất cả theo cả hai chiều. Nhưng đây là vấn đề. Mỗi khi xử lý một cung, bạn có thể xóa một giá trị khỏi đuôi.
And if you do, you might have to throw a whole bunch of arcs back on. So maybe this won't even converge, but it will. Anybody see why this might converge?
Và nếu vậy, bạn có thể phải ném cả loạt cung trở lại. Nên có thể nó thậm chí không hội tụ, nhưng thực ra là có. Ai thấy vì sao nó có thể hội tụ không?
Exactly. Say that again.
Chính xác. Bạn nói lại đi.
It can only go back as many times as there are things in the domain because you only get sent back into the queue if something was deleted from the domain you point towards, and that can only happen d times.
Nó chỉ quay lại nhiều nhất bằng số phần tử trong miền, vì cung chỉ bị đưa lại vào hàng đợi nếu có giá trị bị xóa khỏi miền mà nó trỏ tới, và điều đó chỉ xảy ra tối đa d lần.
So worst case here, you get a factor of d. This looks like it's going to be d cubed, n squared. You can do some tricks to get a factor of d out of that.
Vậy trường hợp xấu nhất ta có thêm một thừa số d. Có vẻ nó sẽ là d mũ ba nhân n bình phương. Có thể dùng vài mẹo để bớt đi một thừa số d.
But you know, we're not — this is going to be polynomial. It's not that bad. But we know that detecting all future problems is going to be np hard.
Nhưng dù sao đây cũng là đa thức. Không tệ lắm. Nhưng ta biết việc phát hiện mọi vấn đề trong tương lai là NP-khó.
And why do we know that?
Và vì sao ta biết vậy?
What if I told you satisfiability was a CSP? Now maybe it seems like bad news, right? So we know that CSPs, in general, or np hard.
Nếu tôi nói bài toán thỏa mãn được (satisfiability) là một CSP thì sao? Có vẻ đây là tin xấu, đúng không? Ta biết CSP nói chung là NP-khó.
Filtering — this algorithm is not going to solve them. It's just going to detect a certain class of violations.
Lọc thế này, thuật toán này sẽ không giải được chúng. Nó chỉ phát hiện một lớp vi phạm nhất định.
Let's watch this algorithm in motion, and then we'll finish up our filtering and talk really quickly about ordering. All right. I don't want to do this.
Hãy xem thuật toán này chạy, rồi ta sẽ kết thúc phần lọc và nói thật nhanh về việc sắp thứ tự. Được rồi. Tôi không muốn làm cái này.
I want to do this. OK. So here is the graph for N-Queens. Remember, each letter is the location of one of the Queens, and the values are which column that Queen is in.
Tôi muốn làm cái này. OK. Đây là đồ thị của bài toán N-Queens. Nhớ rằng mỗi chữ cái là vị trí của một quân Hậu, và các giá trị là cột mà quân Hậu đó đứng.
And there's a bunch of constraints. Now I can check by clicking here. I can check — when I click here, this is going to check the arc from a to b, and it's consistent.
Và có một loạt ràng buộc. Giờ tôi có thể kiểm tra bằng cách nhấp vào đây. Khi nhấp vào đây, nó kiểm tra cung từ a đến b, và nó nhất quán.
And now I'm going to check b to a, and it's consistent. And I'm going to check e to something. It's consistent. So I'm going to just let the applet go wild.
Giờ tôi kiểm tra b đến a, và nó nhất quán. Rồi tôi kiểm tra e với một nút nào đó. Nhất quán. Vậy tôi cứ để applet chạy tự do.
And if I do this, it'll go around. It's got a queue. You can't see the queue, but it's got a queue. It's checking everything.
Nếu làm thế, nó sẽ chạy một vòng. Nó có một hàng đợi. Bạn không thấy hàng đợi, nhưng nó có. Nó đang kiểm tra mọi thứ.
And you'll notice nothing's actually happening. And that's because at the beginning, the arcs are all consistent because there aren't any values that sort of immediately cause a conflict, right?
Và bạn sẽ thấy thực ra chẳng có gì xảy ra. Đó là vì lúc đầu, các cung đều nhất quán, vì chưa có giá trị nào gây xung đột ngay lập tức, đúng không?
Until we start assigning things, we're not going to really get any value out of arc consistency in this problem.
Cho đến khi ta bắt đầu gán giá trị, ta sẽ chưa thu được lợi ích gì từ nhất quán cung trong bài toán này.
But now I can go to a and I can say, all right, I'm going to put that — OK, it looks like I have a star at 2, so I'm going to say, I'm going to assign you to 2.
Nhưng giờ tôi có thể vào a và nói, được rồi, tôi sẽ đặt cái đó... OK, có vẻ tôi có một ngôi sao ở 2, nên tôi sẽ nói, tôi gán a bằng 2.
Notice what happened. Notice all the arcs, at least in the way that this applet draws them, they've turned blue for pointing into a because a just changed.
Hãy để ý chuyện gì xảy ra. Hãy để ý tất cả các cung, ít nhất theo cách applet này vẽ, chúng chuyển sang màu xanh khi trỏ vào a vì a vừa thay đổi.
Everything that used to point to a that used to be declared consistent — back on the queue. So we can go and we can start enforcing them.
Mọi cung từng trỏ vào a mà trước đó được coi là nhất quán đều quay lại hàng đợi. Thế là ta có thể bắt đầu thực thi chúng.
So when I enforce the consistency of b to a, right — that's over here, remember?
Khi tôi thực thi tính nhất quán của b đến a, ở ngay đây, nhớ chứ?
It's going to say, are there any places that b can't go without being able to be extended to a? And yeah, there are because 1 isn't OK anymore.
Nó sẽ hỏi: có chỗ nào b không thể đi mà không mở rộng được sang a không? Và có, vì 1 không còn ổn nữa.
It was before, when a wasn't assigned, but it's not OK now. And 2 is not OK and 3 is not OK.
Trước đó thì ổn, khi a chưa được gán, nhưng giờ thì không. 2 cũng không ổn và 3 cũng không ổn.
And so when I do this, a bunch of things are going to disappear from b.
Và khi tôi làm vậy, một loạt giá trị sẽ biến mất khỏi b.
1, 2, and 3 are gone, and a whole bunch of things just went onto the queue because they were relying on previous values of b.
1, 2 và 3 biến mất, và cả loạt cung vừa được đưa vào hàng đợi vì chúng dựa vào các giá trị cũ của b.
And so we can let this applet execute the whole queue, and you'll notice every red flash means I deleted something. Things go back on the queue.
Giờ ta có thể để applet chạy hết hàng đợi, và bạn sẽ thấy mỗi lần nháy đỏ nghĩa là tôi đã xóa một giá trị. Các cung lại quay về hàng đợi.
And this will keep going — it won't go forever — until it quiesces and there's nothing left going on the queue, and everything is arc consistent.
Và nó sẽ cứ chạy tiếp, nhưng không chạy mãi đâu, cho đến khi nó lắng xuống và không còn gì trong hàng đợi nữa, và mọi thứ đều nhất quán cung.
You think it's going to end up with a single solution? We're going to find out.
Các em nghĩ cuối cùng sẽ chỉ còn một nghiệm duy nhất không? Chúng ta sẽ xem.
So if you look at it right now, a whole bunch of values have vanished from those domains, but I still have to do a backtracking search because I don't actually know whether 4 is going to work out at b, or 5.
Nếu nhìn bây giờ, rất nhiều giá trị đã biến mất khỏi các miền giá trị đó, nhưng tôi vẫn phải tìm kiếm quay lui vì tôi chưa biết b nhận 4 hay 5 thì sẽ ổn.
Maybe they'll both work out. Maybe neither will work out. But let's say I assign one. What would you guys like?
Có thể cả hai đều ổn. Có thể cả hai đều không ổn. Giả sử tôi gán một giá trị. Các em muốn giá trị nào?
4. Decisive. OK. Let's do it.
4. Quyết đoán đấy. Được. Làm thôi.
We could detect. No luck. All right. We would detect that by seeing a domain go empty.
Ta có thể phát hiện ra. Không may rồi. Được rồi. Ta phát hiện điều đó khi thấy một miền giá trị trở nên rỗng.
And it's — the whole thing is arc consistent. Now it turns out, even though the other ones aren't assigned, they only have one thing in their domain, and assigning isn't going to do anything.
Và toàn bộ đồ thị đều nhất quán cung. Bây giờ, dù các biến còn lại chưa được gán, miền giá trị của chúng chỉ còn một giá trị, nên việc gán cũng chẳng thay đổi gì.
And you can sort of see that this is going to finish now without any backtracking. That's not always true. Arc consistency — enforcing arc consistency does not prevent all backtracking.
Và có thể thấy là bài này sẽ kết thúc ngay mà không cần quay lui. Không phải lúc nào cũng vậy. Nhất quán cung, tức là áp dụng nhất quán cung, không loại bỏ hết được việc quay lui.
OK. See what's next. So let's talk a little bit more about this, then we're going to quickly wrap up with ordering.
Được rồi. Xem tiếp nhé. Ta nói thêm một chút về điều này, rồi nhanh chóng kết thúc với phần thứ tự.
So after you enforce arc consistency, the following can be possible. You can have one solution left. We just saw that happen.
Sau khi áp dụng nhất quán cung, có thể xảy ra các trường hợp sau. Còn lại đúng một nghiệm. Ta vừa thấy điều đó.
We enforced arc consistency after a couple assignments, and there was one solution left. You can have multiple solutions left and you can have no solutions left and not know it.
Ta áp dụng nhất quán cung sau vài lần gán, và chỉ còn lại một nghiệm. Có thể còn nhiều nghiệm, hoặc hết nghiệm mà ta không hề biết.
So let's look at these two examples here. Let's look at this top one. We can look at it and say, is it arc consistent? Well, let's look.
Hãy xem hai ví dụ này. Xem cái ở trên trước. Ta xem nó có nhất quán cung không? Xem nào.
This arc pointing up — assuming these are all inequality constraints, is there anything that you have to delete from the tail to be consistent with the head? No, they'll both work.
Cung hướng lên này, giả sử đây đều là ràng buộc bất đẳng thức, có giá trị nào ở đuôi phải xóa đi để nhất quán với đầu không? Không, cả hai đều ổn.
And I can check this one and this one. These are the tricky ones, right? One's going to be blue. One's going to be green.
Tôi kiểm tra cung này và cung này. Đây là những cung khó, đúng không? Một cái sẽ là xanh dương. Một cái sẽ là xanh lá.
But both values are consistent. And so that top one is consistent, and you can see there's two solutions in there, right? One where the left goes green and one where the right goes green.
Nhưng cả hai giá trị đều nhất quán. Vậy cái trên cùng là nhất quán, và có hai nghiệm trong đó, đúng không? Một nghiệm là bên trái xanh lá, một nghiệm là bên phải xanh lá.
How about down here? Are there any solutions left to the CSP, assuming those are inequality constraints? There is no way.
Còn cái ở dưới này thì sao? Bài CSP còn nghiệm nào không, giả sử đó là các ràng buộc bất đẳng thức? Không thể nào.
There is no solution there, but this arc is consistent because between those two, there are two solutions left. And this arc is consistent and this arc is consistent.
Không có nghiệm nào, nhưng cung này nhất quán vì giữa hai nút đó còn lại hai nghiệm. Cung này nhất quán và cung này cũng nhất quán.
All the arcs are consistent. So what went wrong? Arc consistency let us down here. What went wrong here?
Tất cả các cung đều nhất quán. Vậy sai ở đâu? Nhất quán cung đã làm ta thất vọng ở đây. Sai ở chỗ nào?
What went wrong is what's — is the problem here is between three nodes, and arc consistency traffics in pairs, right? And it will not detect violations, in general, that are between three.
Vấn đề ở đây là mâu thuẫn nằm giữa ba nút, mà nhất quán cung chỉ xử lý theo từng cặp, đúng không? Nói chung nó sẽ không phát hiện các vi phạm liên quan đến ba nút.
All right. So it also still runs backtracking search. So let's see all of that, and then we'll quickly talk about ordering.
Được rồi. Vì vậy ta vẫn phải chạy tìm kiếm quay lui. Ta xem hết phần này, rồi nói nhanh về thứ tự.
I want this one. All right. You're ready for the big graph. All right.
Tôi muốn cái này. Được rồi. Các em sẵn sàng cho đồ thị lớn chưa. Được rồi.
Each node has its demands.
Mỗi nút đều có những đòi hỏi riêng.
We're still going to start in the lower left because we haven't talked about ordering yet, and if I assign something to the lower left, I'm going to assign blue, and you can think in your head what's going to happen.
Ta vẫn bắt đầu ở góc dưới bên trái vì ta chưa nói về thứ tự, và nếu tôi gán giá trị cho nút dưới trái, tôi sẽ gán xanh dương, và các em hãy tự nghĩ xem điều gì sẽ xảy ra.
First, we're going to be forward checking. So I assign blue and its neighbors lose blue. OK, great. So I'll go to one of those neighbors and it loses red.
Trước hết, ta dùng forward checking. Tôi gán xanh dương và các nút lân cận mất màu xanh dương. Tốt. Tôi sang một nút lân cận và nó mất màu đỏ.
And look in the upper left. It's got to be green. Forward checking has discovered this. So let's keep going.
Nhìn nút trên cùng bên trái. Nó buộc phải là xanh lá. Forward checking đã phát hiện ra điều này. Ta tiếp tục.
Blue, red. So we've discovered that this one has to be green and this one has to be green. Forward checking has discovered this. Are you worried?
Xanh dương, đỏ. Vậy là nút này phải là xanh lá và nút này cũng phải là xanh lá. Forward checking đã phát hiện ra điều này. Các em có lo không?
You're worried. Guess who's not worried? Forward checking is not worried. So we continue.
Các em lo rồi. Đoán xem ai không lo? Forward checking không lo. Nên ta tiếp tục.
So we keep on assigning things. We know it's doomed to failure. All this computation is a waste. It's already doomed.
Ta cứ tiếp tục gán các giá trị. Ta biết nó chắc chắn thất bại. Tất cả tính toán này đều phí công. Nó đã hỏng rồi.
It's doomed. You're doomed. Now it figures it out. Once it actually assigns — only through assignment do things propagate further into the graph with forward checking.
Hỏng rồi. Hỏng rồi nhé. Giờ nó mới nhận ra. Chỉ khi thực sự gán giá trị thì với forward checking, thông tin mới lan sâu hơn vào đồ thị. Vậy ta sẽ quay lui và thử lại.
So we are going to backtrack and try again. And I'll play this. So it's going to backtrack. I'll speed it up.
Vậy ta sẽ quay lui và thử lại. Và tôi sẽ chạy cái này. Nên nó sẽ quay lui. Tôi sẽ tua nhanh.
It will eventually compute its way through this, but it keeps sort of running into this because the problem happened when? It happened, like — when did this go wrong?
Cuối cùng nó cũng sẽ giải xong, nhưng nó cứ vấp phải chỗ này, vì vấn đề xảy ra khi nào? Nó hỏng từ lúc nào nhỉ?
Sort of like instantly, right? It was in that fourth node we were already sort of doomed. But it'll muddle through. OK.
Gần như ngay lập tức, đúng không? Đến nút thứ tư là chúng ta đã coi như thất bại rồi. Nhưng nó vẫn sẽ mò mẫm vượt qua. OK.
Let's compare that to if we enforce arc consistency, where I assign blue. And again, its neighbor stopped being blue. I assign red.
Hãy so sánh với khi ta áp dụng nhất quán cung, trong đó tôi gán màu xanh dương. Và nút lân cận lại hết là xanh dương. Tôi gán màu đỏ.
Notice the upper left turns green, but also, this node down here — like way in the middle of the graph — has lost green because we've propagated the consequences of that, which means as soon as we assign blue here, we already know that node that we kept trying to make green — it can't be green.
Hãy chú ý nút phía trên bên trái chuyển sang xanh lá, nhưng nút ở dưới này nữa — ngay giữa đồ thị — cũng mất màu xanh lá vì ta đã lan truyền hệ quả của việc đó, nghĩa là ngay khi gán xanh dương ở đây, ta đã biết nút mà ta cứ cố tô xanh lá thì không thể là xanh lá.
It's going to be red.
Nó sẽ là đỏ.
And this node here that we had to sort of mess around with until we discovered it needed to be green — arc consistency knows and doesn't have to backtrack here.
Còn nút này, nút mà ta phải loay hoay mãi mới phát hiện ra nó cần là xanh lá — nhất quán cung biết trước và không phải quay lui ở đây.
But will it get through without backtracking?
Nhưng liệu nó có chạy xong mà không quay lui không?
No. But the backtracking is not quite as bad, and it's pretty local. OK? So that's a lot better.
Không. Nhưng việc quay lui không tệ đến thế, và nó khá cục bộ. OK? Vậy là tốt hơn nhiều.
I'm going to quickly talk about one more concept that should be pretty easy now that we have arc consistency, and then we'll be done for the day.
Tôi sẽ nói nhanh thêm một khái niệm nữa, giờ có nhất quán cung rồi thì nó khá dễ, và sau đó ta kết thúc buổi học.
OK, and that is the concept of ordering. So you are journeying down your CSP. You're making decisions like which variable do I do next?
OK, đó là khái niệm về thứ tự. Bạn đang đi xuống theo CSP của mình. Bạn phải quyết định như: biến nào làm tiếp theo?
And within a variable, which values am I going to try next? And there's good decisions and bad decisions. And so far, we've just been filtering.
Và trong một biến, thử giá trị nào tiếp theo? Có quyết định tốt và quyết định tệ. Từ đầu đến giờ ta mới chỉ lọc.
We have not been trying to do a good job at picking variables and picking values. One very powerful idea is that you should pick the variable that has the fewest remaining values.
Ta chưa cố chọn cho khéo biến và giá trị. Một ý tưởng rất mạnh là bạn nên chọn biến có ít giá trị còn lại nhất.
How are you going to know how many values there are? Well, if you're running filtering, you can see, right? So it's minimum remaining values with respect to a filtering algorithm.
Làm sao biết còn bao nhiêu giá trị? Nếu đang chạy lọc thì bạn thấy được, đúng không? Vậy đó là minimum remaining values dựa trên một thuật toán lọc.
So right now, everything looks the same. I'm going to assign red. But now, look. I have a choice here.
Lúc này mọi thứ trông như nhau. Tôi gán màu đỏ. Nhưng giờ hãy xem. Tôi có một lựa chọn.
I could either work on this part of the graph that's sort of next to what I've already done or I could just teleport over here and go into the east or Tasmania or whatever.
Tôi có thể làm tiếp phần đồ thị nằm cạnh phần đã làm hoặc nhảy sang đây, đến phía đông hay Tasmania gì đó.
What should I do? Well, intuitively, I should keep working around where I'm placing constraints by my assignments. Or rather, where constraints are kicking in.
Nên làm gì? Theo trực giác, tôi nên tiếp tục quanh chỗ mà các phép gán của tôi đặt ra ràng buộc. Hay đúng hơn, nơi các ràng buộc bắt đầu có tác dụng.
And so I should move here to the Northern Territories, and one way to formalize that is to notice that at this point here, the only things left are blue and green, whereas over in Tasmania, I still have red available.
Nên tôi chuyển sang Northern Territories, và một cách hình thức hóa là nhận thấy ở điểm này chỉ còn xanh dương và xanh lá, còn ở Tasmania thì vẫn còn màu đỏ.
So in general, if you see a domain starting to shrink, you know there's action at that variable, and you might want to do your compute there. OK.
Nói chung, nếu thấy miền giá trị bắt đầu co lại, bạn biết có chuyện xảy ra ở biến đó, và bạn nên dồn tính toán vào đó. OK.
Why should it be min rather than max? Why don't I go for the variables that are most unconstrained — most free?
Tại sao là min chứ không phải max? Sao không chọn biến ít bị ràng buộc nhất, tức tự do nhất?
The idea here is, unfortunately, you are going to have to assign every single variable.
Ý ở đây là, tiếc thay, bạn sẽ phải gán cho từng biến một.
And so if there is a problem in your assignment, given that you're going to have to backtrack, you might as well backtrack now. It's called fail fast.
Nên nếu phép gán có vấn đề, mà bạn vốn sẽ phải quay lui, thì quay lui ngay bây giờ cũng được. Gọi là fail fast (thất bại nhanh).
If you think a problem is brewing — and a sign a problem is brewing is the domains are starting to shrink rapidly — you should go focus your compute there.
Nếu bạn nghĩ có vấn đề đang hình thành — và dấu hiệu là các miền giá trị bắt đầu co lại nhanh — bạn nên dồn tính toán vào đó.
And so you should always rush into the scary door because you're going to have to assign every variable. OK. So let's take a look at this, and then we'll talk about one last thing.
Nên hãy luôn lao vào cánh cửa đáng sợ vì bạn phải gán mọi biến. OK. Giờ ta xem cái này, rồi sẽ nói về một điều cuối cùng, hứa đấy.
promise. OK. All right. Let's — forward checking.
OK. Được rồi. Ta dùng forward checking.
We need to do some filtering, but let's do minimum remaining value. I'm going to assign — so this is not arc consistency.
Cần lọc một chút, nhưng hãy dùng minimum remaining value. Tôi sẽ gán — đây không phải nhất quán cung.
This is still just forward checking, but I make an assignment to blue and I make an assignment to red.
Đây vẫn chỉ là forward checking, nhưng tôi gán xanh dương và gán đỏ.
And remember before, there was this problem of kind of the consequences of that green in the upper left corner and there was propagation from arc consistency?
Nhớ lúc trước có vấn đề về hệ quả của màu xanh lá ở góc trên bên trái và nhất quán cung đã lan truyền nó chứ?
Well, we could just go work on the upper left corner, right? We're running the show here. We can go to the upper left corner and assign that to green.
Ta có thể xử lý góc trên bên trái ngay, đúng không? Ta là người điều khiển ở đây. Ta có thể sang góc trên bên trái và gán xanh lá.
And if we do that, now, where are we going to work? This is the variable that's — well, it could be either of those, really. Watch.
Làm vậy rồi thì giờ ta làm ở đâu? Đây là biến mà — thật ra có thể là một trong hai cái kia. Xem nhé.
It's going to do the thing I don't expect. No, it goes there.
Nó sẽ làm điều tôi không ngờ. Không, nó đi vào đây.
And so you can see where sort of our running down the consequence of our computation so that we can find the tricky parts of the problem and sort of disentangle them right now, where the backtracking will be local and relevant, as opposed to teleporting all over the place.
Vậy bạn thấy ta lần theo hệ quả của phép tính để tìm ra những phần hóc búa của bài toán và gỡ chúng ngay lúc này, khi việc quay lui sẽ mang tính cục bộ và liên quan, thay vì nhảy lung tung khắp nơi.
OK. So minimum remaining values. It's called most constrained variable. Also called fail fast ordering.
OK. Vậy là minimum remaining values. Còn gọi là biến bị ràng buộc nhiều nhất. Cũng gọi là thứ tự fail fast.
You're going to have to do every variable. You might as well do the hard ones now, right?
Dù sao bạn cũng phải xử lý mọi biến. Vậy thì làm luôn các biến khó ngay bây giờ, đúng không?
There's another way to do ordering, which is the ordering on values.
Còn một cách sắp thứ tự khác, đó là sắp thứ tự theo giá trị.
So this is — OK, let's run headfirst to the tricky parts of the CSP and work on them so that we backtrack as quickly as possible and get all that backtracking done in a local part of the search, rather than having to backtrack through a whole bunch of combinatorial stuff.
Ở đây ta lao thẳng vào những phần khó của CSP và giải quyết chúng trước, để quay lui càng sớm càng tốt, và dồn toàn bộ việc quay lui vào một phần cục bộ của tìm kiếm, thay vì phải quay lui qua cả một đống tổ hợp lộn xộn.
What about values? So let's say we're in this scenario here, where we've assigned red and we've assigned green. And we're trying to decide, should we assign red or blue over here to Queensland?
Còn với giá trị thì sao? Giả sử ta đang ở tình huống này, ta đã gán đỏ và gán xanh lá. Và ta đang phân vân nên gán đỏ hay xanh dương cho Queensland ở đây?
Now before, we made our lives as hard as possible. Go to the hardest part of the map — work there. Here, the idea is you want to pick the least constraining value.
Lúc nãy, ta tự làm khó mình tối đa. Đi đến phần khó nhất của bản đồ và làm ở đó. Còn ở đây, ý tưởng là chọn giá trị ít ràng buộc nhất.
That is the value that rules out the fewest other values. How the heck am I supposed to know what's ruled out? You're going to have to run some more filtering.
Đó là giá trị loại bỏ ít giá trị khác nhất. Làm sao tôi biết cái gì bị loại bỏ? Bạn sẽ phải chạy thêm một bước lọc nữa.
This is an expensive thing to compute. But it's interesting. When we picked a variable, we wanted the hardest variable. But when we pick a value, we want the easiest value.
Việc này tính toán khá tốn kém. Nhưng nó thú vị. Khi chọn biến, ta muốn biến khó nhất. Nhưng khi chọn giá trị, ta muốn giá trị dễ nhất.
We want the one that has the least impact on the rest of the graph.
Ta muốn giá trị ảnh hưởng ít nhất đến phần còn lại của đồ thị.
So why is that?
Tại sao vậy?
Why is it when we pick a variable, we want to do the thing that is hardest, but when we pick a value, we want to do the thing that looks least likely to fail?
Tại sao khi chọn biến, ta làm điều khó nhất, còn khi chọn giá trị, ta lại làm điều có vẻ ít thất bại nhất?
It's because it's a CSP, and in a CSP, you have to do every variable. Sooner or later, you have to do it. You might as well do it now.
Vì đây là CSP, và trong CSP bạn phải xử lý mọi biến. Sớm muộn gì cũng phải làm. Vậy thì làm luôn bây giờ.
You don't have to do every value. If you play your cards right, you might not have to do very many values at all. And so you might as well do the hard variables first.
Nhưng bạn không phải thử mọi giá trị. Nếu chơi khéo, có thể bạn chẳng cần thử nhiều giá trị chút nào. Nên cứ làm các biến khó trước.
But if you're picking values, you want to pick the ones that are likely to work out, and maybe you don't even have to try the hard ones. OK.
Nhưng khi chọn giá trị, ta muốn chọn giá trị có khả năng thành công, và biết đâu còn khỏi phải thử những giá trị khó. OK.
So when it comes to values, you take the easy door. OK. I'm going to show you one more thing. OK.
Vậy với giá trị, hãy chọn cánh cửa dễ. OK. Tôi sẽ cho các bạn xem thêm một thứ nữa. OK.
All of this together — ordering these ideas can let you do very large problems that might have been intractable without these heuristics. Let's take a look. Backtracking — [INAUDIBLE] discard.
Kết hợp tất cả những ý tưởng sắp thứ tự này có thể giải được những bài toán rất lớn mà nếu không có các hàm heuristic này thì gần như bất khả thi. Ta xem thử nhé. Quay lui... [KHÔNG NGHE RÕ] bỏ.
All right. Last thing for the day. We're going to do arc consistency and minimum remaining value, and see what happens. So we'll start in the corner, like we always do.
Được rồi. Phần cuối của hôm nay. Ta sẽ dùng nhất quán cung và giá trị còn lại tối thiểu, rồi xem chuyện gì xảy ra. Ta bắt đầu từ góc, như mọi khi.
Blue. So we're going to filter — we're going to propagate the consequences of our constraint, but we're going to jump to a variable that has a minimal domain.
Xanh dương. Ta sẽ lọc, lan truyền hệ quả của ràng buộc, nhưng nhảy đến biến có miền giá trị nhỏ nhất.
So maybe we'll do this one. Now we're going to go up to the green one in the upper left, and then we're going to follow this through.
Có lẽ ta chọn biến này. Giờ ta lên ô xanh lá ở góc trên bên trái, rồi lần theo đó.
And we are both propagating and jumping around the graph to the areas that seem to be hot spots. And so in this case, that's solved quite quickly.
Ta vừa lan truyền vừa nhảy quanh đồ thị đến những vùng có vẻ là điểm nóng. Và trường hợp này được giải khá nhanh.
We would need a bigger graph to show why you would need the least constraining value here. We're hitting the limits — our algorithms are being good enough that this toy problem isn't hard.
Ta cần một đồ thị lớn hơn để thấy vì sao cần giá trị ít ràng buộc nhất ở đây. Ta đang chạm giới hạn: thuật toán đủ tốt nên bài toán đồ chơi này không còn khó.
The big problems are still hard. CSPs can be very hard to solve. Next time, we'll talk about when problems are big, what kinds of techniques will work.
Các bài toán lớn vẫn khó. CSP có thể rất khó giải. Lần sau, ta sẽ bàn khi bài toán lớn thì loại kỹ thuật nào hiệu quả.
We'll talk about other methods other than backtracking search and we'll talk about exploiting the structure of your CSP. That's it. See you all on Thursday.
Ta sẽ nói về các phương pháp khác ngoài tìm kiếm quay lui và về việc khai thác cấu trúc của CSP. Hết rồi. Hẹn gặp lại các bạn vào thứ Năm.
STUDENT
I'm going to be using that one.
Em sẽ dùng cái đó.
STUDENT
Got it.
Được rồi.
STUDENT
Oh, really?
Ồ, thật à?
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.