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
OK, let's get started.
Được rồi, chúng ta bắt đầu nhé.
So today, we're going — I'm loud again. All right. I'll try to control my enthusiasm, but it's hard, because we're going to talk about CSPs again.
Hôm nay chúng ta sẽ — Em lại nghe tiếng tôi to rồi. Được rồi. Tôi sẽ cố kiềm chế sự hào hứng của mình, nhưng khó lắm, vì chúng ta lại nói về CSP.
So today, we're going to continue talking about CSPs, and, in particular, we're going to talk about ways to solve them efficiently that extend and go beyond what we did in the last lecture.
Hôm nay chúng ta sẽ tiếp tục nói về CSP, và cụ thể là các cách giải chúng hiệu quả hơn, mở rộng và vượt ra ngoài những gì chúng ta đã làm ở bài giảng trước.
And we're also going to talk about a related but more general topic of local search methods that apply not only to CSPs but also to the other kinds of search problems that we've seen so far.
Chúng ta cũng sẽ nói về một chủ đề liên quan nhưng tổng quát hơn, đó là các phương pháp tìm kiếm cục bộ, áp dụng không chỉ cho CSP mà còn cho các loại bài toán tìm kiếm khác mà ta đã thấy từ đầu đến giờ.
So let's do a quick recap. We're going to do more solutions — solving of CSPs, so let's remind ourselves what a constraint satisfaction problem is. Well, first of all, what are the ingredients?
Ta cùng ôn lại nhanh. Ta sẽ giải thêm các CSP, nên hãy nhắc lại bài toán thỏa mãn ràng buộc là gì. Trước hết, các thành phần là gì?
First of all, there are variables. The variables usually represent some quantity or abstraction that we are trying to reason about.
Đầu tiên là các biến. Biến thường biểu diễn một đại lượng hay một khái niệm trừu tượng mà ta đang cần suy luận.
And so in our running example of map coloring, the variables might be countries on a map. Each of those variables has a domain, which are the set of values that it might take on.
Trong ví dụ xuyên suốt về tô màu bản đồ, các biến có thể là các quốc gia trên bản đồ. Mỗi biến có một miền giá trị, là tập các giá trị mà nó có thể nhận.
And for map coloring, that was red, green, and blue. This is a great running example.
Với tô màu bản đồ, đó là đỏ, xanh lá và xanh dương. Đây là ví dụ rất hay.
It illustrates all kinds of things, but it's really important to remember that almost all CSPs are not map coloring, and almost all domains are not red, green, and blue, and almost all constraints are not inequality constraint.
Nó minh họa đủ thứ, nhưng cần nhớ rằng hầu hết CSP không phải là tô màu bản đồ, hầu hết miền giá trị không phải đỏ, xanh lá, xanh dương, và hầu hết ràng buộc không phải là ràng buộc khác nhau.
So you're going to see a lot of these in this example, but CSPs, arbitrary domains — arbitrary information hidden inside those constraints. So it's the variables, the domains, and the constraints.
Các em sẽ thấy nhiều ví dụ kiểu này, nhưng CSP có miền giá trị tùy ý, và thông tin tùy ý ẩn trong các ràng buộc. Vậy là có biến, miền giá trị và ràng buộc.
And when we talk about constraints in a CSP, they come in two flavors in terms of how we specify them.
Về cách đặc tả, ràng buộc trong CSP có hai dạng.
There's implicit constraints, and an implicit constraint is basically a little snippet of code that you run in order to tell you whether or not the variables in its input have an OK assignment, because remember, constraints look at one or more variables and say thumbs up to that assignment or thumbs down.
Ràng buộc ngầm định, về cơ bản là một đoạn mã nhỏ mà ta chạy để biết phép gán cho các biến đầu vào có chấp nhận được hay không, vì hãy nhớ, ràng buộc xét một hay nhiều biến rồi giơ ngón cái lên hoặc xuống với phép gán đó.
That breaks one of the rules. Each constraint is a rule. So an implicit constraint is a snippet of code that you have to execute. That's great, because it's general.
Tức là phép gán vi phạm một quy tắc. Mỗi ràng buộc là một quy tắc. Vậy ràng buộc ngầm định là đoạn mã mà ta phải thực thi. Điều này tốt vì nó tổng quát.
But it's bad in a couple of ways, too.
Nhưng cũng có vài điểm xấu.
You actually have to run them to see what's going to happen, so there's a lot of static analysis that you can't do pre-computation, and it can also be slower, because you often have to call out to these things in practice.
Ta phải chạy chúng mới biết kết quả, nên có nhiều phân tích tĩnh không thể tính trước, và nó cũng có thể chậm hơn, vì trong thực tế thường phải gọi ra ngoài để chạy chúng.
The other form of constraints are explicit constraints, and in an explicit constraint, you actually literally enumerate for, say, these two variables that are being constrained. Here are the tuples that you're willing to allow.
Dạng còn lại là ràng buộc tường minh, trong đó ta liệt kê đúng nghĩa đen, chẳng hạn cho hai biến bị ràng buộc này, các bộ giá trị mà ta cho phép.
And so this is Country A, and this is Country B. I could have an implicit piece of code that looks at the two values, runs equality, negates that, and then returns whatever.
Đây là nước A, và đây là nước B. Tôi có thể viết đoạn mã ngầm định lấy hai giá trị, so sánh bằng, rồi phủ định kết quả và trả về.
An explicit constraint would say, for A, comma, B, the legal tuples are red, comma, green, green, comma, blue, and so on, leaving out the illegal ones.
Còn ràng buộc tường minh sẽ nói, với A, B, các bộ hợp lệ là đỏ, xanh lá; xanh lá, xanh dương; v.v., bỏ qua các bộ không hợp lệ.
That's how you specify these, and in these constraint graphs, you kind of — the line in the constraint graph is going to indicate the presence of a constraint between two variables.
Đó là cách đặc tả chúng, và trong đồ thị ràng buộc, đường nối trong đồ thị ràng buộc cho biết có một ràng buộc giữa hai biến. Nhưng nội dung bên trong ràng buộc thì phải tra trong ràng buộc ngầm định hoặc tường minh.
But that information of what's buried inside — you have to look that up in either an implicit or an explicit constraint.
Ý tưởng tương tự sẽ quay lại sau này với mạng Bayes, nơi cấu trúc đồ thị cho ta biết sự phụ thuộc giữa các biến.
And the same idea is going to come back later with [INAUDIBLE],, where the graph structure will tell us what the dependencies are between the variables.
Nhưng để biết bản chất của các xác suất có điều kiện, ta phải nhìn vào bên trong và xem thứ không có trên đồ thị.
But to actually know what the nature of those conditional probabilities are, we're going to have to look under the hood and see something that's not present in the graph.
Ràng buộc cũng có nhiều loại.
When we talk about constraints, they come in different [INAUDIBLE]. So a unary constraint is really just a restricted domain. It says this country can only be red or green, for whatever reason.
Ràng buộc đơn thực chất chỉ là thu hẹp miền giá trị. Nó nói nước này chỉ có thể là đỏ hoặc xanh lá, vì lý do nào đó. Vậy ràng buộc đơn biến thực chất chỉ là một miền giá trị bị giới hạn. Nó nói rằng nước này chỉ có thể là màu đỏ hoặc xanh lá, vì lý do nào đó không quan trọng.
There are binary constraints. This is different from a binary domain.
Có ràng buộc nhị phân. Cái này khác với miền giá trị nhị phân.
A variable with a binary domain is either true or false or some other of two values, but a binary constraint is a constraint that lives on top of two variables.
Biến có miền nhị phân là đúng hoặc sai hoặc hai giá trị nào đó, còn ràng buộc nhị phân là ràng buộc đặt lên hai biến.
And there are higher order constraints. You could have a three area constraint, a four area constraint, and, in general, higher unary constraints.
Và có các ràng buộc bậc cao hơn. Có thể có ràng buộc ba biến, bốn biến, và tổng quát là các ràng buộc bậc cao.
Some of the algorithms work with them, and some of them do not. What's the goal of a CSP? In this class, the goal is to find a solution.
Một số thuật toán xử lý được chúng, một số thì không. Mục tiêu của một CSP là gì? Trong lớp này, mục tiêu là tìm một lời giải.
So when I present you with a CSP and say, please solve this, what I'm asking for is for you to produce an assignment of values from the domains to the variables that satisfies all of the constraints.
Khi tôi đưa ra một CSP và bảo hãy giải nó, tôi yêu cầu các em đưa ra một phép gán giá trị từ miền giá trị cho các biến sao cho thỏa mãn mọi ràng buộc.
So we're looking at find any solution. There are other things you could imagine doing with a CSP, like finding all the solutions.
Vậy ta tìm một lời giải bất kỳ. Còn nhiều việc khác có thể làm với CSP, như tìm tất cả các lời giải.
That might be bad news, because there might be exponentially many of them. Find me the best solution. Maybe there are some weights involved.
Việc đó có thể tệ, vì có thể có số lượng lời giải lên đến cấp số mũ. Tìm lời giải tốt nhất. Có thể có liên quan đến trọng số.
Tell me whether or not there's any solution in which this node is green.
Cho biết có lời giải nào mà nút này màu xanh lá hay không.
These are all questions that you could ask of a CSP, but the algorithms we're talking about today and last class don't. They're just, give me a solution. As soon as you find one, stop.
Đây đều là những câu hỏi có thể đặt ra với một CSP, nhưng các thuật toán hôm nay và buổi trước không làm vậy. Chúng chỉ đưa ra một lời giải. Tìm được một lời giải là dừng.
We had a basic algorithm, which we're going to extend, and then find an alternative to today, called backtracking search. And we did a bunch of demos of these.
Ta có một thuật toán cơ bản, mà ta sẽ mở rộng, rồi hôm nay tìm một phương án thay thế, gọi là tìm kiếm quay lui (backtracking search). Và chúng ta đã xem khá nhiều demo về nó.
And basically, backtracking search takes a CSP, and it takes a search formulation of that CSP, where the state of the search problem is partial assignment.
Về cơ bản, tìm kiếm quay lui nhận một CSP, và nhận một cách phát biểu CSP đó dưới dạng bài toán tìm kiếm, trong đó trạng thái của bài toán tìm kiếm là một phép gán từng phần.
So at the top of that search tree is the empty assignment, where no variables have any values.
Vậy ở đỉnh 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ị.
And then as you go down the successor function in that search problem, takes variables, and adds a value.
Rồi đi xuống, hàm kế tiếp trong bài toán tìm kiếm này lấy một biến và thêm một giá trị.
And so it extends the assignment, and then at the bottom of the tree are all the complete assignments in which every variable is assigned.
Như vậy nó mở rộng phép gán, và ở đáy của cây là tất cả các phép gán đầy đủ, trong đó mọi biến đều đã được gán.
So you can imagine there's this tree, and up here is the empty assignment, and down here are all the complete assignments. And of course, this tree doesn't look like this.
Bạn có thể hình dung có một cái cây thế này, ở trên này là phép gán rỗng, còn dưới này là tất cả các phép gán đầy đủ. Tất nhiên, cây này không có dạng như vậy.
It looks like this or something. It gets exponentially big exponentially fast.
Nó trông giống thế này hơn. Nó to lên theo hàm mũ, và rất nhanh.
So although the actual implementation that we talk about is a recursive implementation, this is still depth first search, and it's going to behaviorally act just like depth first search from last week, where you could imagine that there is a fringe, and you explore the deepest thing.
Dù cách cài đặt thực tế mà chúng ta nói là cài đặt đệ quy, nó vẫn là tìm kiếm theo chiều sâu, và về hành vi nó hoạt động y hệt tìm kiếm theo chiều sâu của tuần trước, trong đó bạn có thể hình dung có một biên (fringe), và bạn khám phá nút sâu nhất.
That fringe isn't embodied in this code as an actual cue. It's embodied in the sort of the call trace, but it does the exact same thing. So what was this algorithm that we had?
Biên đó không được thể hiện trong code như một hàng đợi thực sự. Nó nằm ngầm trong ngăn xếp lời gọi, nhưng làm đúng cùng một việc. Vậy thuật toán này như thế nào?
Well, if you have a complete assignment, great. You return it. Otherwise, you pick a variable. That's the next variable you're going to assign as your work your way down the tree.
Nếu bạn có một phép gán đầy đủ, tốt. Bạn trả về nó. Nếu không, bạn chọn một biến. Đó là biến tiếp theo bạn sẽ gán khi đi xuống cây.
And then you're going to loop over the values. So you pick a value. If that doesn't work out, and you recurse back, you're going to pick the next value.
Rồi bạn duyệt qua các giá trị. Bạn chọn một giá trị. Nếu không được, và bạn quay lui từ đệ quy, bạn sẽ chọn giá trị tiếp theo.
So you're going to have both the opportunity to choose what variable is next and the opportunity to choose what order to try the values in.
Vậy bạn có cả cơ hội chọn biến nào đi tiếp, và cơ hội chọn thứ tự thử các giá trị.
And if the value is consistent, meaning adding it to the assignment does not yet break any constraints, then you're going to recurse and extend and extend. If it doesn't work, you're going to backtrack.
Và nếu giá trị nhất quán, nghĩa là thêm nó vào phép gán chưa vi phạm ràng buộc nào, thì bạn đệ quy và cứ thế mở rộng tiếp. Nếu không được, bạn quay lui.
So this is our basic backtracking search. It's not very fast. In general, CSPs — solving CSPs is an empty, hard endeavor.
Đây là tìm kiếm quay lui cơ bản của chúng ta. Nó không nhanh lắm. Nói chung, giải CSP là một việc NP-khó.
And that means whatever we do today, whatever cool algorithms we come up with, there's going to be some CSPs that are just going to be, to the best of our knowledge, really, really hard to solve.
Nghĩa là dù hôm nay ta làm gì, nghĩ ra thuật toán hay đến đâu, vẫn sẽ có những CSP mà theo hiểu biết của chúng ta thì thực sự rất khó giải.
It is an empty hard problem, but there are often instances which have certain properties that allow us to solve them faster.
Đó là bài toán NP-khó, nhưng thường có những trường hợp có một số tính chất cho phép ta giải nhanh hơn.
So on top of that backtracking search, last time, we talked about several general purpose ideas to improve things and to solve the CSP faster.
Vậy trên nền tìm kiếm quay lui, lần trước chúng ta nói về vài ý tưởng đa dụng để cải thiện và giải CSP nhanh hơn.
So this is different than, for example, a star search, where the heuristic was specific to a single problem. I have my problem.
Điều này khác với, chẳng hạn, tìm kiếm A*, nơi hàm heuristic dành riêng cho một bài toán. Tôi có bài toán của mình.
I come up with a heuristic using my own creativity to figure out what might be a good lower bound on the costs.
Tôi tự sáng tạo ra một hàm heuristic để tìm cận dưới tốt cho chi phí.
These are general purpose ideas that will work for some CSPs but not others. And there are three classes. We talked about two of them last time.
Còn đây là các ý tưởng đa dụng, hiệu quả với một số CSP nhưng không phải tất cả. Và có ba nhóm. Lần trước ta đã nói về hai nhóm.
We're going to talk about the third one today. The first class of ways to speed up a CSP is by what's called filtering. And that's what we talked about last class.
Hôm nay ta sẽ nói về nhóm thứ ba. Nhóm đầu tiên để tăng tốc CSP là cái gọi là lọc (filtering). Đó là điều ta đã bàn ở buổi trước.
So we want — when we make an assignment, it may be that things look good so far.
Khi ta thực hiện một phép gán, có thể mọi thứ trông vẫn ổn.
I haven't violated a constraint so far, but in some sense, this whole subtree of the search is doomed, because there's an inevitable failure that's a consequence of the decisions I've already made.
Đến giờ tôi chưa vi phạm ràng buộc nào, nhưng theo một nghĩa nào đó, cả cây con này của tìm kiếm đã vô vọng, vì thất bại là không thể tránh khỏi, hệ quả của những quyết định tôi đã đưa ra.
Filtering did that sort of propagation and look-ahead to check to see whether there were consequences of the assignment that I just made.
Lọc thực hiện lan truyền và nhìn trước như vậy để kiểm tra xem có hệ quả nào từ phép gán tôi vừa thực hiện không.
And we looked at forward checking, which isn't very good, and enforcing our consistency, which is much better as a filtering mechanism. It's still not perfect, because these are still NP-hard problems.
Ta đã xem kiểm tra tiến (forward checking), cách này không tốt lắm, và duy trì nhất quán cung, tốt hơn nhiều, như một cơ chế lọc. cơ chế. Nó vẫn chưa hoàn hảo, vì đây vẫn là các bài toán NP-khó.
But it's a lot better than forward checking, though it comes with a computational cost. So that's filtering.
Nhưng nó tốt hơn nhiều so với kiểm tra tiến, dù phải trả giá bằng chi phí tính toán. Đó là lọc.
Every time I make an assignment, I look ahead to see if there's any sort of doom on the horizon, and I backtrack if there is.
Mỗi lần gán, tôi nhìn trước xem có điềm gở nào ở phía chân trời không, và nếu có thì tôi quay lui.
Another way of speeding up CSPs in general were ordering methods, so asking questions like, which variable should I assign next as I do my recursive search?
Một cách khác để tăng tốc CSP nói chung là các phương pháp sắp thứ tự, tức là đặt câu hỏi như biến nào nên được gán tiếp theo khi tôi thực hiện tìm kiếm đệ quy?
And there's an important distinction here, because you are eventually going to have to do every variable. You can't luck out and not have to assign some of the variables.
Và có một điểm khác biệt quan trọng ở đây, vì cuối cùng bạn vẫn phải gán mọi biến. Bạn không thể may mắn mà khỏi phải gán một số biến.
And since you're going to have to do them all, there's going to be easy ones and hard ones, where we can make that formal by talking about how big their remaining domains are.
Và vì phải làm hết, sẽ có biến dễ và biến khó, ta có thể hình thức hóa điều này bằng kích thước miền giá trị còn lại của chúng.
You might as well do the difficult ones first.
Vậy thì cứ làm các biến khó trước.
This is called fail fast ordering, and this is so you work on the tricky parts of the CSP early so that when you backtrack, you're not buried deep in the tree.
Đây gọi là sắp thứ tự thất bại nhanh (fail fast), để bạn xử lý phần hóc búa của CSP từ sớm, nhờ đó khi quay lui, bạn không bị vùi sâu trong cây.
You don't have to backtrack across exponential stuff and have to redo a whole lot of work.
Bạn không phải quay lui qua một lượng khổng lồ theo hàm mũ và làm lại rất nhiều việc.
You want to do your backtracking early, locally in a sort of tightly coupled way so that you figure things out, and then move on to another part of the tree.
Bạn muốn quay lui sớm, mang tính cục bộ, chặt chẽ, để giải quyết xong rồi chuyển sang phần khác của cây.
So that was which variable should be next. The minimum remaining values is a proxy for the hard parts of the problem, and that's where you want to go first.
Đó là về việc biến nào nên đi tiếp theo. Số giá trị còn lại tối thiểu là một thước đo gián tiếp cho những phần khó của bài toán, và đó là nơi bạn muốn đi trước.
When you pick a variable, you sort of, like, charge right into the danger. But once you've picked a variable, you have to decide what order you're going to try the values.
Khi bạn chọn một biến, bạn kiểu như, lao thẳng vào chỗ nguy hiểm. Nhưng khi đã chọn xong một biến, bạn phải quyết định thử các giá trị theo thứ tự nào.
And this is a very, very different story, because you don't actually have to try all the values. If the first one you try works out, great. You don't have to try the rest.
Và chuyện này hoàn toàn khác, vì thực ra bạn không cần thử hết mọi giá trị. Nếu giá trị đầu tiên bạn thử chạy được, quá tốt. Bạn không cần thử những giá trị còn lại.
So we want to be sort of pessimistic when we pick a variable, but we want to be optimistic when we pick a value, so we're going to pick values that appear to be most promising.
Nên ta muốn bi quan một chút khi chọn biến, nhưng lại lạc quan khi chọn giá trị, tức là ta sẽ chọn những giá trị có vẻ hứa hẹn nhất.
How the heck do you operationalize that? One way to operationalize that is what's called the least constraining value.
Vậy làm sao để biến điều đó thành thao tác cụ thể? Một cách là dùng cái gọi là giá trị ít ràng buộc nhất (least constraining value).
It's a little tricky even to do this, and there are more complicated things people have come up with. But the idea here is you tentatively assign a value.
Ngay cả việc này cũng hơi khó làm, và người ta cũng đã nghĩ ra những cách phức tạp hơn. Nhưng ý tưởng ở đây là bạn gán thử một giá trị.
You run some filtering, and you check to see whether elements are vanishing out of domains left and right. And if so, this is a constraining value.
Bạn chạy một bước lọc, rồi kiểm tra xem các phần tử có biến mất khỏi miền giá trị hàng loạt hay không. Nếu có, thì đây là một giá trị có tính ràng buộc cao.
But if this assignment doesn't really impact anything else and leaves most of the domains intact, this is probably a value that's likely to work out.
Còn nếu phép gán này gần như không ảnh hưởng đến gì khác và giữ nguyên hầu hết các miền giá trị, thì nhiều khả năng đây là giá trị sẽ dùng được.
Not all the time — none of these are guaranteed to speed things up. But these are often very, very effective in practice, especially when you can combine them.
Không phải lúc nào cũng vậy, không cái nào trong số này đảm bảo chạy nhanh hơn. Nhưng chúng thường rất hiệu quả trong thực tế, nhất là khi kết hợp được với nhau.
The last thing that we're going to talk about today is how to exploit problem structure.
Điều cuối cùng hôm nay ta sẽ nói tới là cách khai thác cấu trúc của bài toán.
That is how to look at the graph structure of the constraint satisfaction problem and detect whether either there's a special purpose algorithm that might run faster than the general purpose ones or maybe some way to improve the graph structure.
Tức là nhìn vào cấu trúc đồ thị của bài toán thỏa mãn ràng buộc và phát hiện xem có thuật toán chuyên dụng nào có thể chạy nhanh hơn các thuật toán tổng quát không, hoặc có cách nào để cải thiện cấu trúc đồ thị.
And we'll talk about these kinds of techniques today. In order to do what we need to do today, we're going to have to extend our discussion about arc consistency.
Hôm nay ta sẽ nói về những kỹ thuật này. Để làm được những việc hôm nay, ta cần mở rộng phần thảo luận về nhất quán cung.
So we're going to start with arc consistency, which you will remember is this idea that you look at a pair of variables. It's one variable at the tail of the arc.
Ta bắt đầu với nhất quán cung, mà các bạn còn nhớ là ý tưởng xét một cặp biến. Có một biến ở đuôi của cung.
That's the trunk of the car. And then it points to another variable. You are the arc consistency police. You will pull over that arc.
Đó là cốp xe. Và nó trỏ tới một biến khác. Bạn là cảnh sát nhất quán cung. Bạn sẽ chặn cung đó lại.
You will check out all the values in the tail, and you'll delete them, if necessary. And we'll do a couple of more examples of this.
Bạn kiểm tra mọi giá trị ở đuôi, và xóa chúng nếu cần. Ta sẽ làm thêm vài ví dụ về việc này.
That was the notion of making an arc consistent, and we use this to build forward checking, and we also use this to do filtering based on enforcing arc consistency of an entire graph.
Đó là khái niệm làm cho một cung nhất quán, và ta dùng nó để xây dựng forward checking, đồng thời dùng nó để lọc bằng cách ép nhất quán cung trên toàn đồ thị.
We're going to do a third thing today.
Hôm nay ta sẽ làm một việc thứ ba.
So let's first remind ourselves mechanically exactly what it is to enforce consistency of an arc versus a graph, because this distinction is going to be very important when we talk about tree structured and — tree structured algorithms and consistency of higher orders.
Trước hết hãy nhắc lại về mặt cơ học việc ép nhất quán một cung khác với ép trên cả đồ thị thế nào, vì sự khác biệt này sẽ rất quan trọng khi nói về các thuật toán có cấu trúc cây và — các thuật toán cấu trúc cây và nhất quán bậc cao hơn.
So let's do a quick example. You'll remember we had this running example of the Australia coloring graph. Here we are. We are in our backtracking search.
Ta làm nhanh một ví dụ. Các bạn nhớ ta có ví dụ xuyên suốt là đồ thị tô màu nước Úc. Đây rồi. Ta đang trong quá trình tìm kiếm quay lui.
All kinds of filterings still have backtracking searches. The thing's still NP-hard. You're still, in the worst case, going to have to check everything.
Mọi kiểu lọc vẫn là tìm kiếm quay lui. Bài toán vẫn là NP-hard. Trong trường hợp xấu nhất, bạn vẫn phải kiểm tra mọi thứ.
It's just after every step in the backtracking search, you filter some stuff in the same way that at every step in a star search, you run that heuristic.
Chỉ là sau mỗi bước quay lui, bạn lọc bớt một số thứ, giống như ở mỗi bước của tìm kiếm A*, bạn chạy hàm heuristic.
You might have to run the heuristic on every node in the state space. You might not actually gain anything, but you might gain quite a lot.
Bạn có thể phải chạy heuristic trên mọi nút trong không gian trạng thái. Có thể bạn chẳng được lợi gì, nhưng cũng có thể được lợi khá nhiều.
So here we are in the middle of our backtracking search.
Giờ ta đang ở giữa quá trình tìm kiếm quay lui.
So right now, this is the state we're in, where we've assigned Western Australia to red, Queensland to green, and remember, adjacent countries can't have the same color in this example.
Đây là trạng thái hiện tại của ta, ta đã gán Western Australia màu đỏ, Queensland màu xanh lá, và nhớ rằng, các vùng liền kề không được trùng màu trong ví dụ này.
You will also see on the right here that we have an assignment to w, a, and q — red and green — but we also have filtering running on the other variables.
Bên phải bạn cũng thấy ta đã gán w, a và q, đỏ và xanh lá, nhưng ta cũng đang chạy lọc trên các biến còn lại.
So the Northern Territory, New South Wales, Victoria, and South Australia, they're all unassigned. But they have had 2 of their domain values crossed off by previous filtering.
Northern Territory, New South Wales, Victoria và South Australia đều chưa được gán. Nhưng mỗi biến đã bị gạch bỏ 2 giá trị trong miền bởi các lần lọc trước.
So what we're going to do now is we're going to go around and visit arcs, making them consistent. So you're like the arc-consistency police. You're going to clean up any violations you find.
Bây giờ ta sẽ đi qua từng cung và làm cho chúng nhất quán. Bạn như cảnh sát nhất quán cung vậy. Bạn sẽ dọn dẹp mọi vi phạm tìm thấy.
And we're going to see what the consequences are. So for example, we might start with s arc. And remember, when we look at an arc, it's very myopic.
Và xem hậu quả ra sao. Ví dụ ta có thể bắt đầu với cung của s. Nhớ rằng khi xét một cung, ta rất thiển cận.
You look at these two variables. And even worse, you look at them directionally. And you only look at from, in this case, V, pointing to New South Wales.
Bạn chỉ nhìn hai biến này. Tệ hơn nữa, bạn nhìn chúng theo một chiều. Và chỉ xét từ V, trong trường hợp này, trỏ tới New South Wales.
You say, in the tail, in V, is there anything here that is sort of doomed, guaranteed to fail?
Bạn hỏi, ở đuôi, tức V, có giá trị nào chắc chắn là vô vọng, đảm bảo thất bại không?
Meaning there is no choice at New South Wales that can be assigned as an extension without violating a constraint. So we go through, and we say, red at V that's fine.
Nghĩa là không có lựa chọn nào ở New South Wales có thể mở rộng mà không vi phạm ràng buộc. Ta duyệt qua: đỏ ở V thì ổn.
Because I'll choose blue at NSW. Green at V, that's fine. I can choose whatever I want at New South W. Blue at V, well, that's fine, because I'll choose red.
Vì tôi sẽ chọn xanh dương ở NSW. Xanh lá ở V cũng ổn. Tôi chọn gì ở New South Wales cũng được. Xanh dương ở V cũng ổn, vì tôi sẽ chọn đỏ.
So in this case, this arc is already consistent. I can look at other arcs. So here, SA to NSW, they also share a border.
Vậy trong trường hợp này, cung này đã nhất quán. Tôi có thể xét các cung khác. Đây, SA tới NSW, hai vùng này cũng chung biên giới.
So I can look at SA and say, well, there's only one thing in its trunk, which is blue. Is there an extension to NSW that is legal? Yeah, red.
Tôi xét SA và thấy chỉ có một giá trị ở đuôi, là xanh dương. Có cách mở rộng hợp lệ nào cho NSW không? Có, đỏ.
You say, what about blue? Well, blue is really about the other direction. So in this direction, the arc is consistent. Everything is fine.
Bạn hỏi, thế còn xanh dương? Xanh dương thì liên quan đến chiều ngược lại. Vậy theo hướng này, cung là nhất quán. Mọi thứ đều ổn.
But if we visit the other direction, we might get a different answer. And so here, when we look at NSW pointing to SA, this arc is not consistent.
Nhưng nếu ta xét theo hướng ngược lại, ta có thể nhận được kết quả khác. Ở đây, khi ta xét NSW trỏ tới SA, cung này không nhất quán.
And the reason it's not consistent is because if I pick red at NSW, I can extend to that by choosing blue — my only choice — at SA.
Và lý do nó không nhất quán là vì nếu tôi chọn đỏ ở NSW, tôi có thể mở rộng bằng cách chọn xanh dương, lựa chọn duy nhất, ở SA.
But if I pick blue, I'm toast, because blue and blue conflict. And so the way I make this inconsistent arc consistent is I delete stuff from the tail until it's happy.
Nhưng nếu tôi chọn xanh dương thì toi, vì xanh dương với xanh dương xung đột. Và cách để biến cung không nhất quán này thành nhất quán là xóa bớt giá trị ở đuôi cho đến khi nó thỏa.
And in this case, I delete that blue. And I can continue this. So remember, this arc was nice and consistent before.
Trong trường hợp này, tôi xóa màu xanh dương đó. Và tôi có thể tiếp tục. Hãy nhớ rằng cung này trước đó đang nhất quán.
But that argument of its consistency was based on the presence of blue at NSW. Blue's gone. That means some of my reasoning from before needs to be rereasoned.
Nhưng lập luận về tính nhất quán của nó dựa trên việc NSW có xanh dương. Xanh dương mất rồi. Nghĩa là một số suy luận trước đó của tôi cần được suy luận lại.
And so in particular, red used to be OK at V because I could pick blue at NSW. That's no longer OK. And I'm going to need to eject red here.
Cụ thể, trước đây đỏ ổn ở V vì tôi có thể chọn xanh dương ở NSW. Giờ thì không còn ổn nữa. Và tôi sẽ phải loại màu đỏ ở đây.
Now, the arc is consistent again. For any choice at V, there is a legal extension at NSW. So here's the interesting case if you remember the example from before.
Giờ cung lại nhất quán. Với mọi lựa chọn ở V, đều có một mở rộng hợp lệ ở NSW. Còn đây là trường hợp thú vị, nếu bạn nhớ ví dụ lúc trước.
The interesting case is between SA and NT. Neither has been assigned, yet we know from existing filtering that, if anything, they have to be blue. But they're adjacent.
Trường hợp thú vị là giữa SA và NT. Cả hai chưa được gán giá trị, nhưng từ việc lọc trước đó ta biết, nếu có thì chúng phải là xanh dương. Nhưng chúng kề nhau.
They can't both be blue. This arc is inconsistent. The only way to make it consistent is to start pulling things out of its trunk. I can delete that blue.
Chúng không thể cùng xanh dương. Cung này không nhất quán. Cách duy nhất để làm nó nhất quán là bắt đầu lấy giá trị ra khỏi đuôi. Tôi có thể xóa màu xanh dương đó.
But as soon as I do that, I have an empty domain. And as soon as you have an empty domain, you know that the CSP has no solution, and you have to backtrack.
Nhưng ngay khi làm vậy, tôi có một miền rỗng. Và ngay khi có một miền rỗng, bạn biết CSP không có nghiệm, và bạn phải quay lui.
Why? Because as we filter, we delete values. And we have a sort of outer bound of what might be legal at that node. If you delete something, it's definitely illegal given the current assignment.
Tại sao? Vì khi lọc, ta xóa các giá trị. Và ta có một dạng cận ngoài của những gì có thể hợp lệ ở nút đó. Nếu bạn xóa một giá trị, nó chắc chắn bất hợp lệ với phép gán hiện tại.
But if something is present, it might still be illegal. You just can't really tell yet. But as soon as something is empty, there's no secret fourth color. We're going to backtrack.
Nhưng nếu một giá trị còn đó, nó vẫn có thể bất hợp lệ. Chỉ là chưa thể biết được. Nhưng ngay khi một miền rỗng, không có màu thứ tư bí mật nào cả. Ta sẽ quay lui.
OK, so that's our consistency of an arc. An arc is either consistent or not. And there's an algorithm. You can call it removing consistent that makes it consistent.
Vậy đó là tính nhất quán của một cung. Một cung hoặc nhất quán hoặc không. Và có một thuật toán. Bạn có thể gọi là loại bỏ giá trị không nhất quán, để làm cho nó nhất quán.
If you do a bunch of arcs, you basically do them to exhaustion, that is the algorithm AC3 for enforcing arcing consistency and making the whole graph arc-consistent.
Nếu bạn làm với nhiều cung, về cơ bản làm đến cạn kiệt, thì đó là thuật toán AC3 để đảm bảo nhất quán cung và làm cho toàn bộ đồ thị nhất quán cung.
And as we saw here, you have to visit arcs over and over again.
Và như ta thấy, bạn phải duyệt lại các cung nhiều lần.
That's actually OK, because every time you visit it, it's because its head has fewer values in its domain than it did before. And so you can't visit it in an indefinite number of times.
Điều đó thật ra ổn, vì mỗi lần duyệt lại là do đầu của nó có ít giá trị hơn trong miền so với trước. Nên bạn không thể duyệt nó vô hạn lần.
You can only visit it size of domain number of times. So arc-consistency detects failure earlier than forward checking. If x loses a value, all the neighbors incoming to x need to be rechecked.
Bạn chỉ duyệt tối đa bằng kích thước miền. Vậy nhất quán cung phát hiện thất bại sớm hơn kiểm tra tiến (forward checking). Nếu x mất một giá trị, mọi lân cận trỏ tới x cần được kiểm tra lại.
That can trigger cascades of repeated visitation of arcs. But that's OK, because it will all terminate. Another important thing to remember is after you do all this filtering, you're going to do an assignment.
Điều đó có thể kéo theo chuỗi duyệt lại các cung. Nhưng không sao, vì tất cả sẽ kết thúc. Một điều quan trọng khác cần nhớ là sau khi lọc xong, bạn sẽ thực hiện một phép gán.
And then you start the filtering again. So this isn't something you run once. This is something you run once for every single node in your search tree.
Rồi bạn bắt đầu lọc lại. Vậy đây không phải thứ chạy một lần. Đây là thứ chạy một lần cho mỗi nút trong cây tìm kiếm.
We talked about limitations. We're going to address some of these limitations today, though, in two very different ways.
Ta đã nói về các hạn chế. Hôm nay ta sẽ giải quyết một số hạn chế đó theo hai cách rất khác nhau.
After enforcing arc-consistency, meaning taking your graph, deleting things as necessary until all the arcs are consistent, you can be in a bunch of different states.
Sau khi đảm bảo nhất quán cung, nghĩa là lấy đồ thị, xóa giá trị khi cần cho đến khi mọi cung đều nhất quán, bạn có thể ở nhiều tình huống khác nhau.
You can have one solution left, and you can greedily assign, and everything will be great.
Có thể còn một nghiệm, và bạn gán tham lam, mọi thứ sẽ ổn.
You can have multiple solutions left, for example, like the top graph here, where there's two solutions here.
Có thể còn nhiều nghiệm, ví dụ như đồ thị trên cùng ở đây, có hai nghiệm.
One of them has to be blue. The other is green. It can go either way. You can also have no solutions left and not know it.
Một nút phải là xanh dương. Nút kia là xanh lá. Cách nào cũng được. Cũng có thể không còn nghiệm nào mà bạn không biết.
We didn't talk about how to solve this yesterday, but we're going to talk about how to solve it today or at least a way to think about it.
Hôm qua ta chưa nói cách giải việc này, nhưng hôm nay ta sẽ nói cách giải hoặc ít nhất là một cách nghĩ về nó.
And in this case, every pair of arcs is fine. But all together, the three arcs aren't OK. You need to look at triples.
Và trong trường hợp này, mọi cặp cung đều ổn. Nhưng gộp cả ba cung lại thì không ổn. Bạn cần xét các bộ ba.
Arc-consistency is only about pairs, and so you can't detect this problem.
Nhất quán cung chỉ xét các cặp, nên bạn không phát hiện được vấn đề này.
That's actually OK, because there's still a backtracking search which will detect this problem instantly as soon as you assign one of the nodes. That's why our consistency still needs a backtracking search.
Điều đó thật ra ổn, vì vẫn còn tìm kiếm quay lui sẽ phát hiện vấn đề này ngay lập tức khi bạn gán một trong các nút. Đó là lý do nhất quán vẫn cần tìm kiếm quay lui.
OK, those are consistency. Any questions on that? Yes.
Được rồi, đó là phần nhất quán. Có câu hỏi nào không? Vâng.
STUDENT
[INAUDIBLE] PROFESSOR: Yeah, so why does arc-consistency sometimes detects failure earlier than forward checking?
[KHÔNG NGHE RÕ] GIÁO SƯ: Vâng, vậy tại sao nhất quán cung đôi khi phát hiện thất bại sớm hơn kiểm tra tiến?
Remember, failure is when you see the consequence of your existing assignment is that some node you know has no legal assignments.
Hãy nhớ, thất bại là khi bạn thấy hệ quả của phép gán hiện có là có một nút mà bạn biết không còn phép gán hợp lệ nào.
The more arcs you check, the more likely you are to detect such a configuration. And in particular, in arc-consistency, you sort of chain the information throughout the graph, and you can detect remote failures.
Bạn kiểm tra càng nhiều cung, càng có khả năng phát hiện ra cấu hình như vậy. Và cụ thể, trong nhất quán cung, bạn lan truyền thông tin đi khắp đồ thị, và bạn có thể phát hiện các thất bại ở xa.
Forward checking only detects failures that are right in front of you. And in fact, you were going to find them in the next step anyway, at least under certain orderings.
Forward checking chỉ phát hiện những thất bại ngay trước mắt bạn. Thực ra, bạn cũng sẽ tìm ra chúng ở bước kế tiếp thôi, ít nhất là với một số thứ tự nhất định.
So forward checking doesn't do a lot.
Nên forward checking không giúp được nhiều.
It's sort of the minimum amount of filtering you need to be able to flash your filtering badge and say, I do filtering, which is important, because a lot of things, like minimum rating values, require a full-term computation to even be defined.
Nó là mức lọc tối thiểu để bạn có thể giơ huy hiệu lọc ra và nói: tôi có lọc đấy, điều này quan trọng, vì nhiều thứ, như các giá trị xếp hạng tối thiểu, cần tính toán đầy đủ các hạng tử thì mới được định nghĩa.
Arc-consistency's better.
Nhất quán cung thì tốt hơn.
Let's talk about k-consistency. So arc-consistency is a really powerful notion, which is basically the notion that for any two nodes in a graph, if you assign one, you can extend to the second.
Giờ ta nói về k-consistency. Nhất quán cung là một khái niệm rất mạnh, về cơ bản nó nói rằng với hai nút bất kỳ trong đồ thị, nếu bạn gán giá trị cho một nút, bạn có thể mở rộng sang nút thứ hai.
What happens at the third node? All bets are off. But at least for every pair of nodes, you're OK.
Còn ở nút thứ ba thì sao? Không đảm bảo gì cả. Nhưng ít nhất với mọi cặp nút thì ổn.
We talked about arc-consistency as being like the CSP Police pull you over and make some modification.
Ta đã nói nhất quán cung giống như cảnh sát CSP kéo bạn vào lề và bắt sửa đổi gì đó.
Let's imagine, instead of being pulled over by this little guy, you get pulled over by mega Robocop here.
Giờ hãy tưởng tượng, thay vì bị anh chàng nhỏ này chặn lại, bạn bị Robocop khổng lồ này chặn lại.
That's the basic idea with k-consistency, where instead of just enforcing that all arcs are following the rules, we're going to enforce that all triples or quads are also following the rules.
Đó là ý tưởng cơ bản của k-consistency, thay vì chỉ đảm bảo mọi cung tuân thủ luật, ta sẽ đảm bảo mọi bộ ba hay bộ bốn cũng tuân thủ luật.
This is an expensive thing to do, but it is also powerful. And there's a trade-off between computation in the filtering and the amount of backtracking you're going to have to do.
Việc này tốn kém, nhưng cũng mạnh. Và có sự đánh đổi giữa chi phí tính toán của việc lọc và lượng quay lui mà bạn phải làm.
And there's no way to know in advance for sure for an arbitrary graph whether that trade-off will be in your favor. So k-consistency is a little bit of mathy concept.
Và không có cách nào biết trước chắc chắn với một đồ thị bất kỳ liệu sự đánh đổi đó có lợi cho bạn hay không. K-consistency là một khái niệm hơi nặng toán.
I'm going to go over this now. We're going to talk about, in general, how to think about this kind of consistency.
Giờ tôi sẽ đi qua nó. Ta sẽ nói chung về cách nghĩ về loại nhất quán này.
And then we're going to talk about specific algorithms that work for specific graph structures. OK, so the smallest kind of consistency is so silly it's not worth talking about.
Rồi ta sẽ nói về các thuật toán cụ thể hoạt động cho các cấu trúc đồ thị cụ thể. Loại nhất quán nhỏ nhất thì quá tầm thường nên không đáng nói.
It's 1-consistency. It's sometimes called node-consistency. This says that every node's domain has at least one value that meets that node's constraints. This basically just means you enforce unary constraints.
Đó là 1-consistency. Đôi khi gọi là node-consistency. Nó nói rằng miền giá trị của mỗi nút có ít nhất một giá trị thỏa các ràng buộc của nút đó. Về cơ bản chỉ là áp dụng các ràng buộc đơn biến.
And when you get a CSP, you can easily just enforce the unary constraints right off the bat once and be done with it. So one consistency, we don't have to think too hard about.
Khi nhận một CSP, bạn có thể dễ dàng áp dụng các ràng buộc đơn biến ngay từ đầu một lần là xong. Vậy 1-consistency thì ta không cần nghĩ nhiều.
Two consistency — this is actually what arc-consistency is, but I'm going to state it in a particularly weird way, so that we can extend it to higher orders.
2-consistency thực ra chính là nhất quán cung, nhưng tôi sẽ phát biểu theo một cách hơi lạ, để ta có thể mở rộng lên bậc cao hơn.
Arc-consistency phrased this way says, for any pair of nodes — so I grab two nodes in my graph — if you have a consistent — meaning does not violate constraints — assignment to one, it can be extended to the other.
Phát biểu như vậy, nhất quán cung nói: với mọi cặp nút, tức tôi lấy hai nút trong đồ thị, nếu bạn có một phép gán nhất quán, nghĩa là không vi phạm ràng buộc, cho một nút, thì nó có thể mở rộng sang nút kia.
So that means, for any assignment to the tail, there is an assignment to the head that extends that tail assignment without violating a constraint.
Nghĩa là với mọi phép gán cho đuôi, có một phép gán cho đầu mở rộng phép gán đuôi đó mà không vi phạm ràng buộc nào.
And that's just what we talked about all along here, which says, for any assignment in the tail, there's an extension to the head that doesn't violate a constraint.
Và đó đúng là điều ta đã nói suốt nãy giờ: với mọi phép gán ở đuôi, có một phần mở rộng ở đầu không vi phạm ràng buộc. Nếu có tính chất đó, đồ thị của bạn nhất quán cung.
If you have that property, your graph is arc consistent. And then we had an algorithm for making it so. K-consistency is a generalization of this.
Rồi ta có một thuật toán để làm cho nó như vậy. K-consistency là sự tổng quát hóa của điều này.
It says for each k-node — so instead of picking up two, which is an arc, a pair, I pick up three or five or 30 — k-consistency says that if I have k-node, and I manage to assign k minus 1 one them without breaking any constraints, that there is guaranteed to be an extension to that kth node
Nó nói với mỗi k nút, tức thay vì lấy hai, là một cung, một cặp, tôi lấy ba hay năm hay 30 nút, k-consistency nói rằng nếu tôi có k nút, và gán được k trừ 1 nút trong đó mà không phá ràng buộc nào, thì chắc chắn có một phần mở rộng cho nút thứ k mà không vi phạm ràng buộc nào.
that does not violate any constraints. It says, if you can get to k minus 1, you can get to k. Arc-consistency says, if you can get one assigned, you can get two assigned.
Nó nói: nếu bạn tới được k trừ 1, bạn tới được k. Nhất quán cung nói: nếu gán được một nút, bạn gán được hai nút. Ta có thể nói về các bậc cao hơn.
We can talk about higher orders. As k goes up, this gets more and more expensive. Because you start talking about looking at not just pairs of domains — triples, quads, arbitrary numbers of domains.
Khi k tăng, việc này càng tốn kém. Vì bạn phải xét không chỉ các cặp miền giá trị mà cả bộ ba, bộ bốn, số lượng miền tùy ý. Chi phí tăng theo hàm mũ của k rất nhanh.
This gets exponential in k very fast. So higher k are more expensive. In this class, you only really need to know about k equals 2, which is arc-consistency.
Nên k càng cao càng tốn kém. Trong lớp này, bạn thật sự chỉ cần biết k bằng 2, tức nhất quán cung. Nhưng ý tưởng chung về các bậc cao hơn thì quan trọng.
But the general idea of the higher orders are important.
Khi nói về consistency, về mặt toán học nó hơi kỳ.
So when I talk about consistency, it's sort of mathematically a little weird. Because it assumes that you can get to k minus 1, but who says you actually can?
Vì nó giả định bạn tới được k trừ 1, nhưng ai nói là bạn thật sự tới được?
There is a stronger notion called strong k-consistency. which includes all the lower orders as a package deal. So if I say it's strong 5-consistent. That also means it's 1-consistent, 2-consistent, 3-consistent, and 4-consistent.
Có một khái niệm mạnh hơn gọi là strong k-consistency gồm trọn gói tất cả các bậc thấp hơn. Nếu tôi nói nó strong 5-consistent. Điều đó cũng có nghĩa là nó 1-consistent, 2-consistent, 3-consistent và 4-consistent. Đây là một khẳng định.
So here's a claim. And then we'll talk about how this is useful or not.
Rồi ta sẽ bàn nó hữu ích hay không.
The claim is that you have strong n-consistency — where you have n nodes in your graph — means you can solve without backtracking. Why is that true?
Khẳng định là nếu bạn có strong n-consistency, với n là số nút trong đồ thị, thì bạn giải được mà không cần quay lui. Tại sao đúng vậy?
Well, it's strong n-consistency, which means if I pick up a node, we're 1-consistent.
Đó là strong n-consistency, nghĩa là nếu tôi chọn một nút, ta 1-consistent. Tức là có một giá trị trong miền của nút đó để gán mà không vi phạm ràng buộc, nghĩa là chỉ ràng buộc đơn biến.
That means there's a value that I can assign that node sitting in its domain that will not violate constraints, which just means the unary constraint. Good, lock it in, OK?
Tốt, chốt giá trị đó. Ta sẽ không quay lui. Chọn nút thứ hai.
We're not going to backtrack. Pick up a second node. We'll, there's an arc from the first node to the second node.
Có một cung từ nút đầu đến nút thứ hai. Và vì cung đó là 2-consistent, Ta sẽ không quay lui.
And because that arc is 2-consistent, arc-consistent, no matter what I picked at node number 1, there is a legal extension to node number 2. So pick one. Lock it in.
và vì cung đó là 2-consistent, nhất quán cung, thì dù ở nút số 1 em chọn gì, cũng có một phần mở rộng hợp lệ cho nút số 2. Cứ chọn một giá trị. Chốt lại.
Pick up the third node. Because its 3-consistent, any assignment to the first two that has not violated, a constraint can be extended to the third.
Lấy nút thứ ba. Vì nó nhất quán 3, nên mọi phép gán cho hai nút đầu mà không vi phạm ràng buộc nào đều có thể mở rộng sang nút thứ ba.
So if you happen to have this by induction, you can show that you can solve the entire thing without backtracking. This isn't super useful.
Nếu có được tính chất này, thì bằng quy nạp, ta chứng minh được có thể giải toàn bộ bài toán mà không cần quay lui. Điều này không hữu ích lắm.
I mean, it would be great if we didn't have to backtrack. But why is this not super useful? How do you know this is not super useful?
Ý tôi là, sẽ tuyệt nếu không phải quay lui. Nhưng tại sao nó không hữu ích lắm? Làm sao biết nó không hữu ích lắm?
Well, you know this problem you're solving is NP-hard, right? This is an AI class. Everything is NP-hard, right?
Thì các em biết bài toán đang giải là NP-hard, đúng không? Đây là lớp AI mà. Cái gì cũng NP-hard, đúng không?
So since you can solve it very quickly without backtracking, establishing strong k-consistency must have been really hard, and it is, in general.
Vì ta giải rất nhanh mà không cần quay lui, nên việc thiết lập nhất quán k mạnh hẳn là rất khó, và nói chung đúng là như vậy.
But this basic idea that if you have the right kind of consistency, you could just kind of go forward, extending without worrying about messing up your assignments so far is actually at the core of an algorithm that we can run.
Nhưng ý tưởng cơ bản là nếu có đúng loại nhất quán, ta có thể cứ tiến lên, mở rộng mà không lo làm hỏng các phép gán đã có, thực ra nằm ở cốt lõi của một thuật toán ta có thể chạy.
It just doesn't work for arbitrary graphs. And we'll talk about that really soon. So 1-consistency is free. 2-consistency is arc-consistency.
Chỉ là nó không hoạt động với đồ thị tùy ý. Và chúng ta sẽ nói về điều đó rất sớm. Vậy nhất quán 1 thì miễn phí. Nhất quán 2 là nhất quán cung.
And we have an algorithm for that. N-consistency is intractable, but it would be awesome if we could get it. So there's this whole middle ground in between that you could imagine doing.
Và ta có thuật toán cho nó. Nhất quán N thì không khả thi, nhưng sẽ rất tuyệt nếu đạt được. Vậy có cả một khoảng giữa mà ta có thể hình dung để làm.
In particular, 3-consistency has a name. It's called path-consistency. You imagine three nodes form a line, form a path. By the time you get to 4-consistency, things are just getting really expensive.
Đặc biệt, nhất quán 3 có một cái tên. Gọi là nhất quán đường đi (path-consistency). Hình dung ba nút tạo thành một đường thẳng, một đường đi. Đến nhất quán 4 thì mọi thứ trở nên rất tốn kém.
Any questions about any of that before we talk about structure, which will let us actually exploit these ideas to come up with algorithms that are guaranteed to be efficient?
Có câu hỏi nào không trước khi nói về cấu trúc, thứ cho phép ta khai thác các ý tưởng này để tạo ra thuật toán đảm bảo hiệu quả?
Yep.
Mời em.
STUDENT
[INAUDIBLE] PROFESSOR: Are there examples of graphs that are in a state that are k-consistency but not strongly k-consistency?
[KHÔNG NGHE RÕ] GIÁO SƯ: Có ví dụ nào về đồ thị ở trạng thái nhất quán k nhưng không nhất quán k mạnh không?
Yes, there are. However, one thing that's important to kind of think through is, what does arc-consistency do? You just have your CSP.
Có chứ. Tuy nhiên, điều quan trọng cần nghĩ kỹ là nhất quán cung làm gì? Em có một CSP.
Is not arc-consistent, and you go and you wave your arc-consistency wand, and you make it arc-consistent. What has changed? Values have been deleted from domains at nodes.
Nó chưa nhất quán cung, em vẫy cây đũa thần nhất quán cung, và nó trở nên nhất quán cung. Điều gì đã thay đổi? Các giá trị bị xóa khỏi miền giá trị tại các nút.
So some domains that were fully populated, a bunch of them blink out.
Một số miền đang đầy đủ, nhiều miền biến mất.
I was going to make an Avengers joke, but that may be a spoiler still. What about 3-consistency? That's really tricky.
Tôi định đùa về Avengers, nhưng có thể vẫn bị spoil. Còn nhất quán 3 thì sao? Cái đó khá phức tạp.
So when I enforced 3-consistency, what it says is that any two things can be extended to a third.
Khi áp dụng nhất quán 3, nó nói rằng hai thứ bất kỳ đều có thể mở rộng sang thứ ba.
And that means that what you leave in your wake when you wave your 3-consistency wand is actually not unary shrinking, unary constraints. You leave binary constraints.
Và điều đó nghĩa là thứ còn lại sau khi em vẫy đũa thần nhất quán 3 không phải là thu hẹp đơn biến, ràng buộc đơn. Mà là các ràng buộc hai biến.
You introduce all kinds of constraints to the graph.
Em thêm đủ loại ràng buộc vào đồ thị.
When we talk about higher order k-consistencies, you actually have trouble drawing these examples. So it's a little hard for me to throw in on the PowerPoint. Good office hours question though.
Khi nói đến nhất quán k bậc cao hơn, thực ra rất khó vẽ các ví dụ này. Nên tôi khó đưa vào PowerPoint. Dù vậy là câu hỏi hay cho giờ office hours.
Let's talk about structure.
Giờ nói về cấu trúc.
So you are remember the CSP detective. And it is your job to solve this giant CSP case.
Các em còn nhớ thám tử CSP chứ. Nhiệm vụ của em là phá vụ án CSP khổng lồ này.
And you look at your nodes, and there's a whole bunch of them, and they're connected in this web of constraints. But then you see something.
Em nhìn các nút, có cả đống, nối với nhau trong mạng lưới ràng buộc. Nhưng rồi em nhận ra điều gì đó.
And so in this particular cartoon, you see there's the big boss in the center. And you have this intuition that we should be able to exploit this.
Trong hình hoạt họa này, có tên đầu sỏ ở giữa. Và em có trực giác rằng ta nên khai thác được điều này.
Maybe you go after the one in the center. Maybe you start at the edges and work up. And this is the basic idea behind structure.
Có thể em xử lý nút ở giữa trước. Có thể em bắt đầu từ các rìa rồi đi lên. Đây là ý tưởng cơ bản của cấu trúc.
It's that just looking at the structure of the graph gives you ways to make the problem simpler if you can recognize certain syntactic patterns inside the CSP's graph itself.
Chỉ cần nhìn cấu trúc của đồ thị là có cách làm bài toán đơn giản hơn nếu nhận ra được một số mẫu cú pháp nhất định bên trong chính đồ thị của CSP.
So let's start with an extreme case of exploiting structure. So remember the Australia graph here. We keep forgetting about poor Tasmania. It's an island.
Hãy bắt đầu với một trường hợp cực đoan của khai thác cấu trúc. Nhớ đồ thị nước Úc ở đây. Ta cứ quên mất Tasmania tội nghiệp. Nó là một hòn đảo.
But that's actually good for map coloring, right? Because it's an island, you can color it whatever you want. That's because it's an independent sub-problem.
Nhưng điều đó lại tốt cho tô màu bản đồ, đúng không? Vì là đảo, em tô màu gì cũng được. Đó là vì nó là một bài toán con độc lập.
And in general, if you're doing map coloring, the different continents or however things are separated on your map don't interact. And that means they're independent problems.
Nói chung, khi tô màu bản đồ, các lục địa, hay những phần tách biệt trên bản đồ, không tương tác với nhau. Nghĩa là chúng là các bài toán độc lập.
You can solve them separately, and they don't interact. And there's no constraints between them. Independent sub-problems are easily identified from the graph, because you can look for connected components.
Có thể giải riêng, chúng không tương tác. Và không có ràng buộc nào giữa chúng. Các bài toán con độc lập dễ dàng nhận ra từ đồ thị, vì ta có thể tìm các thành phần liên thông.
How do you find that? You start at some node. You do a search, and you see what's reachable CS-70 style. So you can find the connected components of a graph.
Tìm thế nào? Bắt đầu từ một nút. Chạy tìm kiếm và xem đến được những nút nào, kiểu CS-70. Như vậy ta tìm được các thành phần liên thông của đồ thị.
You can solve them independently. This is incredibly powerful. If you have a big graph made out of a bunch of small, independent components, it can make all the difference.
Ta có thể giải chúng độc lập. Điều này cực kỳ mạnh. Nếu có một đồ thị lớn gồm nhiều thành phần nhỏ độc lập, nó có thể tạo ra khác biệt lớn.
So imagine we have some graph of n variables. So let's draw this. Here's this graph of n. But it turns out, you can break this thing into a bunch of little problems.
Hình dung ta có đồ thị n biến. Vẽ ra nhé. Đây là đồ thị n biến. Nhưng hóa ra, ta có thể chia cái này thành nhiều bài toán nhỏ.
We're going to hit the limit of my artistic ability. You can break this into a bunch of little problems where each one is of size c.
Mình sắp chạm giới hạn khả năng vẽ của mình rồi. Ta có thể chia nó thành nhiều bài toán nhỏ mà mỗi bài có kích thước c.
So instead of one giant thing of size n, you have a bunch of problems of size c. How many of them do you have? You have n divided by c of them.
Vậy thay vì một khối khổng lồ kích thước n, ta có nhiều bài toán kích thước c. Có bao nhiêu bài như vậy? Có n chia c bài.
Looks a little bit like a danish.
Trông hơi giống cái bánh Đan Mạch.
How much work are we going to have to do to solve this thing? Well, CSPs, we have a lot of cool algorithms.
Ta phải làm bao nhiêu việc để giải cái này? Với CSP, ta có nhiều thuật toán hay.
But in the end, you basically have to be prepared to enumerate all of the assignments and check them all one by one. That's what that research is going to do if there's no solutions.
Nhưng cuối cùng, về cơ bản bạn phải sẵn sàng liệt kê mọi phép gán và kiểm tra từng phép một. Đó là điều phép tìm kiếm này sẽ làm nếu không có lời giải.
It's going to sweep through the whole thing. It's going to check everything. You're going to backtrack till millennia pass, and then it's going to say no solutions.
Nó sẽ quét qua toàn bộ. Nó sẽ kiểm tra mọi thứ. Bạn sẽ quay lui cho tới khi hàng thiên niên kỷ trôi qua, rồi nó mới báo là không có lời giải.
So these things are pretty slow when there's no solutions if there's not some way to detect that easily.
Nên những thứ này khá chậm khi không có lời giải, nếu không có cách nào để phát hiện điều đó dễ dàng.
So in the worst case, well, in the full problem, we would have to say, I'm going to assign all n variables each of their d values. It's d to the n.
Vậy trong trường hợp xấu nhất, với bài toán đầy đủ, ta phải gán cho cả n biến mỗi biến d giá trị. Đó là d mũ n.
It's exponential here. And as n grows, it's really bad news. But in this Danish problem here, we only have little problems of d to the c. We just have a lot of those problems.
Ở đây là hàm mũ. Và khi n tăng thì thật tệ. Nhưng với bài toán bánh Đan Mạch này, ta chỉ có các bài nhỏ d mũ c. Chỉ là có rất nhiều bài như thế.
And so if you run the numbers, this is the difference between, say, n is 80, and d is 2, and c is 20.
Và nếu bạn tính thử, đây là khác biệt giữa, chẳng hạn, n là 80, d là 2, và c là 20.
And you make some assumptions about how many assignments you can churn through per second. That's like billions of years for the whole problem. That's not even a very big problem.
Và bạn giả định mỗi giây có thể xử lý bao nhiêu phép gán. Cả bài toán mất cỡ hàng tỷ năm. Mà đó còn chưa phải bài lớn.
Billions of years is a long time. But it's just less than a second under the same assumptions if you can divide it up into bunch of independent problems.
Hàng tỷ năm là rất lâu. Nhưng chưa tới một giây với cùng giả định nếu bạn chia được nó thành nhiều bài toán độc lập.
So independence is great. You solve the problem separately, divide, and conquer.
Vậy tính độc lập rất tuyệt. Bạn giải riêng từng bài, chia để trị.
How useful is this on a scale of 1 to 10?
Cái này hữu ích đến mức nào trên thang 1 đến 10?
0. 1. Why?
0. 1. Tại sao?
You will never in your life run into a CSP that has independent problems. Because the whole point of posing a CSP is to say, here's a bunch of variables that interact.
Cả đời bạn sẽ không bao giờ gặp một CSP có các bài toán độc lập. Vì mục đích của việc đặt ra một CSP là nói rằng, đây là một loạt biến có tương tác với nhau.
Figure their interactions out. Often, in the formulation of the problem, you've already broken up the independent sub-problems. But it's a good mental exercise. And I guess, in map coloring, it could really happen.
Hãy tìm ra các tương tác đó. Thường thì khi mô hình hóa bài toán, bạn đã tách sẵn các bài toán con độc lập rồi. Nhưng đây là một bài tập tư duy hay. Và trong tô màu bản đồ, điều này có thể xảy ra thật.
And you could just not know it, because you haven't done the analysis.
Và bạn có thể không biết, vì bạn chưa phân tích.
But it's a good exercise to realize that the structure of the graph could shine light on ways to just solve it much, much faster.
Nhưng đây là bài tập hay để nhận ra rằng cấu trúc của đồ thị có thể mở ra cách giải nhanh hơn rất, rất nhiều.
All right, let's look at some problem structures we can actually use.
Được rồi, hãy xem vài cấu trúc bài toán mà ta thực sự dùng được.
One of the main ones is you can look at your graph and notice, not that it's in pieces — that almost never happens — but that it's sort of not highly connected.
Một trong những cấu trúc chính là nhìn đồ thị và nhận ra, không phải là nó tách thành các mảnh, điều đó hầu như không bao giờ xảy ra, mà là nó không liên kết dày đặc.
So an extreme case of that is that it's a tree structure. So you look at your graph, and you notice that there's a bunch of constraints.
Trường hợp cực đoan là nó có cấu trúc cây. Bạn nhìn đồ thị của mình, và bạn thấy có một loạt ràng buộc.
But the way they connect up the variables forms a tree. So here is a simple example of a 6-node CSP that forms a tree.
Nhưng cách chúng nối các biến lại tạo thành một cái cây. Đây là ví dụ đơn giản về một CSP 6 nút tạo thành cây.
And there's a theorem, which we're going to show by giving an algorithm, that says that if the constraint graph has no loops, then the CSP can be solved in polynomial time, in particular, linear in the number of variables.
Và có một định lý, mà ta sẽ chứng minh bằng cách đưa ra một thuật toán, nói rằng nếu đồ thị ràng buộc không có chu trình, thì CSP có thể được giải trong thời gian đa thức, cụ thể là tuyến tính theo số biến.
That's way better than exponential number of variables. And again, there's the small term where it's quadratic in the size of the domains.
Tốt hơn nhiều so với số mũ theo số biến. Và lại có thêm một thành phần nhỏ là bậc hai theo kích thước miền giá trị.
That's much better than the d to the n that you get in general. And it's not crazy to think you'll find graphs which are tree-structured or close to tree-structured.
Tốt hơn nhiều so với d mũ n trong trường hợp tổng quát. Và không phải là viển vông khi nghĩ rằng bạn sẽ gặp các đồ thị có cấu trúc cây hoặc gần như cây.
And we'll talk in a minute about how to take something that's almost a tree and tree-ify it, arborize it. I don't actually know what the word is.
Và lát nữa ta sẽ nói về cách biến thứ gần giống cây thành cây, "cây hóa" nó. Thật ra tôi không biết từ đúng là gì.
But you can do it, and then things are efficient. So this property is also going to apply when we talk about the base nets and probabilistic reasoning.
Nhưng làm được thì mọi thứ sẽ hiệu quả. Tính chất này cũng sẽ áp dụng khi ta nói về mạng Bayes và suy luận xác suất.
It's sort of a deep example of how you can have syntactic or structural restrictions on your problem which change the complexity of doing reasoning within that problem even across different ways of posing the problem itself.
Đây là một ví dụ sâu sắc về việc các hạn chế về cú pháp hay cấu trúc của bài toán có thể thay đổi độ phức tạp của việc suy luận trong bài toán đó, ngay cả khi ta đặt bài toán theo những cách khác nhau.
Here's the algorithm for tree-structured CSPs. We'll see how fast it is, and we'll see if it works. And if it's fast and it works, we will have proven our theorem.
Đây là thuật toán cho CSP có cấu trúc cây. Ta sẽ xem nó nhanh đến đâu và xem nó có chạy đúng không. Và nếu nó nhanh và đúng, ta sẽ chứng minh xong định lý.
So step 1, order. So you have your three. You give it an order. That means you pick an arbitrary node to be the root.
Bước 1, sắp thứ tự. Bạn có cái cây của mình. Bạn cho nó một thứ tự. Nghĩa là bạn chọn tùy ý một nút làm gốc.
Because the CSPs aren't directed to begin with. You pick a node to be the root. You pick the tree up by the node. You shake it like this.
Vì ban đầu các CSP không có hướng. Bạn chọn một nút làm gốc. Bạn nhấc cái cây lên bằng nút đó. Bạn lắc nó như thế này.
Pick it up by the ankle. This induces an ordering on everything else. That is the first node, and everything else follows according to the ordering along the topological ordering of the tree.
Xách nó lên bằng cổ chân. Điều này tạo ra một thứ tự cho mọi nút còn lại. Đó là nút đầu tiên, và mọi thứ còn lại theo sau theo thứ tự sắp xếp topo của cây.
There's not just one ordering. But it doesn't matter which one you pick. Just pick one. Linearize the thing.
Không chỉ có một thứ tự. Nhưng chọn cái nào cũng không quan trọng. Cứ chọn một cái. Tuyến tính hóa nó.
So here' s a linearization of this graph. Notice everything's gone directed, because it's now been linearized, and I'm talking about the ordering here. So the underlying CSP is not ordered.
Đây là một cách tuyến tính hóa của đồ thị này. Để ý là mọi thứ giờ đều có hướng, vì nó đã được tuyến tính hóa, và ở đây tôi đang nói về thứ tự. Vậy CSP gốc bên dưới thì không có thứ tự.
But this directed linearization is. And it starts at A. I could have started it anywhere. The same algorithm would work just fine. So let's do an example.
Nhưng bản tuyến tính hóa có hướng này thì có. Nó bắt đầu từ A. Tôi có thể bắt đầu từ bất kỳ nút nào. Thuật toán vẫn chạy tốt như vậy. Ta làm một ví dụ nhé.
Let's imagine this was, again, map coloring. And so all the constraints that you see are inequality constraints. Remember in general, they won't be.
Giả sử đây lại là bài toán tô màu bản đồ. Và mọi ràng buộc mà các em thấy đều là ràng buộc khác nhau. Nhớ là nói chung thì không phải vậy.
And let's assume, perhaps because of unary constraints, that the colors that are shown here are the only ones that are allowed.
Và giả sử, có thể do các ràng buộc đơn biến, rằng các màu được hiển thị ở đây là những màu duy nhất được phép.
And so we can take those domains, and we can draw them underneath each of the nodes. So here, A has to be blue or red.
Vậy ta lấy các miền giá trị đó, và vẽ chúng bên dưới từng nút. Ở đây, A phải là xanh dương hoặc đỏ.
B has to be green or blue and so on. OK, so that's ordering. Here's the algorithm. Once you've ordered it, we do a backwards pass.
B phải là xanh lá hoặc xanh dương, v.v. Rồi, đó là phần thứ tự. Đây là thuật toán. Khi đã sắp thứ tự, ta làm một lượt duyệt ngược.
So we start at F, and we go leftward. And for each node in this pass, we are going to make the arc pointing to that node consistent.
Ta bắt đầu từ F và đi sang trái. Với mỗi nút trong lượt này, ta sẽ làm cho cung trỏ vào nút đó trở nên nhất quán.
So let's do F. We're going to do F. That means the arc that points to F is D to F. So we're looking at this arc right here.
Ta làm F. Ta sẽ làm F. Nghĩa là cung trỏ tới F là D tới F. Ta đang xét cung này đây.
And we want to make it consistent. Maybe I should pick a color that's not one of my magic colors, like purple. And so I look at D to F. I pull it over.
Và ta muốn làm cho nó nhất quán. Có lẽ tôi nên chọn một màu không phải màu đã dùng, như màu tím. Tôi xét D tới F. Tôi kéo nó sang.
I look in the trunk. The trunk is at D. And I'm going to cross off anything in D which can not be extended to F without violating a constraint.
Tôi nhìn vào gốc cung. Gốc là D. Và tôi sẽ gạch bỏ mọi giá trị trong D không thể mở rộng sang F mà không vi phạm một ràng buộc.
Red's OK, because I'll pick blue. Green's OK. Blue is not. And so I will eliminate that, because that's what it means to run this removing consistent values.
Đỏ thì được, vì tôi sẽ chọn xanh dương. Xanh lá được. Xanh dương thì không. Nên tôi sẽ loại nó, vì đó là ý nghĩa của việc loại bỏ các giá trị không nhất quán.
Next is E. I look at the arc that points to E — that's D to E — and I make it consistent. Is it consistent already? Look at it.
Tiếp theo là E. Tôi xét cung trỏ vào E, tức D tới E, và làm cho nó nhất quán. Nó đã nhất quán chưa? Nhìn thử xem. Đỏ được.
Red works. I can pick anything I want. Green work, because I can pick blue. So that one's already consistent.
Tôi chọn gì cũng được. Xanh lá được, vì tôi có thể chọn xanh dương. Nên cung đó đã nhất quán rồi. Giờ sang D. Cung đi vào D là cung B tới D.
Now I'll go to D. Incoming to D is the B to D arc. Is there anything that has to go, or is it already consistent? Already consistent.
Có giá trị nào phải bỏ không, hay nó đã nhất quán? Đã nhất quán.
Now we do C. B to C — is there anything in there that needs to go? Now B to D left B untouched.
Giờ tới C. B tới C có giá trị nào trong đó cần bỏ không? B tới D không đụng gì tới B.
But B to C will not, because if you assign green at B, you don't have an extension to C. So we'll delete that there. So we processed C's incoming arc.
Nhưng B tới C thì có, vì nếu gán xanh lá cho B, thì không có cách mở rộng sang C. Nên ta xóa nó ở đó. Vậy ta đã xử lý cung đi vào C. Giờ ta xử lý cung đi vào B.
Now we'll process B's incoming arc. That's the last one. We look at A to B. And we realize that blue just does not have a future here.
Đó là cung cuối cùng. Ta xét A tới B. Và nhận ra xanh dương không có tương lai ở đây. Vậy là ta xong lượt này.
And now, we've done this pass. Who knows what has happened? I executed the algorithm as specified. I have removed inconsistent values going from right to left.
Ai biết chuyện gì đã xảy ra? Tôi đã chạy thuật toán đúng như quy định. Tôi đã loại các giá trị không nhất quán từ phải sang trái.
SINH VIÊN
Now I kept saying things like the arc pointing to F. How do we know there's not seven arcs pointing to F. Let me add some arcs.
Tôi cứ nói kiểu "cung trỏ vào F". Làm sao biết không có bảy cung trỏ vào F. Để tôi thêm vài cung. Làm sao biết không có nút nào đó trỏ vào F. Vâng. [KHÔNG NGHE RÕ] GIÁO SƯ: Đúng, nó là cây.
How do I know there's not nodes somewhere pointing to F. Yep.
STUDENT
[INAUDIBLE] PROFESSOR: Yeah. it's a tree. So this is the first time we've used the tree property, as we know that there's going to be one arc pointing to each thing.
Đây là lần đầu ta dùng tính chất cây, vì ta biết sẽ chỉ có một cung trỏ vào mỗi nút. Được rồi, giờ làm bước hai. Ta đã kéo hết mọi thứ sang.
All right, now it's time to do step two. We've pulled over everything. We've pulled everything out of the trunk. Our arc-consistency phase is done.
Ta đã lấy hết mọi thứ ra khỏi gốc cung. Pha nhất quán cung đã xong. Giờ đến phần vui, đó là gán giá trị xuôi.
And now, we get to do the fun part, which is assigning forward. So we're going to start at A, and we're just going to go on an assignment spree.
Ta bắt đầu từ A, và cứ gán một mạch. Ta sẽ chọn giá trị không vi phạm các lựa chọn trước đó.
We're going to pick stuff that doesn't violate our choices to date. So let's do it. For A, let's pick one of the remaining values. Easy choice.
Làm thôi. Với A, chọn một trong các giá trị còn lại. Dễ. Với B, ta phải chọn một giá trị còn lại. Sao biết chắc có giá trị ở B?
B, we have to pick our remaining value. How do I know there even is one at B? I picked something at A. Maybe I picked the wrong thing at A.
Tôi đã chọn gì đó ở A. Biết đâu chọn sai ở A. Không sao, vì A tới B đã nhất quán cung. Cung đó nhất quán.
No worries, because A to B is arc-consistent. That arc is consistent.
And because A to B is a consistent arc, whatever I pick at A, there's something that's going to work out at B. Doesn't mean everything's going to work out.
Và vì A tới B là cung nhất quán, dù tôi chọn gì ở A, cũng sẽ có giá trị phù hợp ở B. Không có nghĩa là mọi thứ đều ổn. Nhưng sẽ có giá trị phù hợp, và tôi sẽ chọn một trong số đó.
But something's going to work out, and I'm going to pick one of the things that works out. Could I be messing up my whole future? Maybe. Let's not stress out about that yet.
Liệu tôi có phá hỏng cả tương lai không? Có thể. Giờ chưa cần lo chuyện đó.
All right, time to pick C. I look at C, and I say, is it guaranteed that I can take my existing assignment and extend it to C?
Được rồi, tới lượt C. Tôi nhìn C và hỏi, liệu có chắc là tôi mở rộng được phép gán hiện tại sang C không? Cha của C là B. Tôi đã chọn gì đó ở B. Và B tới C nhất quán, nghĩa là tôi chọn gì ở B, cũng có cách mở rộng sang C. Ở đây là xanh lá.
Well, C's parents is B. I picked something at B. And B to C was consistent, which means whatever I pick at B, there is an extension to C. In this case, it's green.
Rồi, cuối cùng cũng có chỗ thực sự có lựa chọn. Giờ gán D. D có các giá trị.
OK, finally, there's one where there's actually a choice. So it's time to assign D. D has values. Will they all work out? We don't know.
Chúng đều ổn không? Ta chưa biết.
But we know we made an assignment at B. And we know, because B to D was consistent, something at D is a legal extension. In fact, two things at D are legal extensions.
Nhưng ta biết đã gán ở B. Và ta biết, vì B tới D nhất quán, nên có giá trị ở D là một mở rộng hợp lệ. vì B tới D đã nhất quán, nên một giá trị nào đó ở D là một phần mở rộng hợp lệ. Thực ra có hai giá trị ở D là phần mở rộng hợp lệ.
Which one do I choose? Whatever you want. Who wants red? Who wants green?
Tôi chọn cái nào? Tùy các bạn. Ai muốn đỏ? Ai muốn xanh lá?
Well, that's surprisingly lopsided for green. Go, green. OK, so we're going to pick green. Oh, you're making it hard for me.
Chà, xanh lá áp đảo bất ngờ. Cố lên, xanh lá. Được, vậy ta chọn xanh lá. Ôi, các bạn làm khó tôi rồi.
That's why you want green. So now, we go to D to E. And thank you, class. You made it hard.
Đó là lý do các bạn chọn xanh lá. Giờ ta đi từ D sang E. Cảm ơn cả lớp. Các bạn làm khó tôi đấy.
So when I look at D to E, there are two values at E. One of them doesn't actually work.
Khi nhìn D sang E, E có hai giá trị. Một trong hai giá trị thực ra không dùng được.
But D to E was consistent, which means even if I pick green at D, something is going to work. And in this case, the something is blue.
Nhưng D tới E là nhất quán, nghĩa là dù chọn xanh lá ở D, vẫn có một giá trị nào đó dùng được. Và trong trường hợp này, đó là xanh dương.
And then when I get to F, I only have one choice. And because of consistency, it's fine. So it sure looked like, in this case, I could go from left to right doing assignments.
Rồi tới F, tôi chỉ có một lựa chọn. Và nhờ tính nhất quán, nó ổn. Vậy là trong trường hợp này, tôi có thể gán giá trị từ trái sang phải.
And I wouldn't have to backtrack. It doesn't mean I can choose arbitrarily. There are still things here that won't work.
Và không cần quay lui. Điều đó không có nghĩa là chọn tùy ý được. Vẫn có những giá trị ở đây không dùng được.
It's just that as long as I consistently extend one step at a time, it seemed to work out. And that's going to be true in general.
Chỉ là miễn là ta mở rộng nhất quán từng bước một thì mọi thứ đều ổn. Và điều này đúng trong trường hợp tổng quát.
Run time on this — I'm going to step by step right to left, and then step by step left to right. It's linear in n. There's no complication in n.
Thời gian chạy của việc này — tôi đi từng bước từ phải sang trái, rồi từng bước từ trái sang phải. Nó tuyến tính theo n. Không có gì phức tạp theo n.
And then where does the d squared come from?
Vậy d bình phương từ đâu ra?
That comes from the fact that whenever I visit an arc, I have to look at all the things in the head and all the things in the tail, and check them against the constraint.
Nó đến từ việc mỗi khi duyệt một cung, tôi phải xét mọi giá trị ở đầu và mọi giá trị ở đuôi, rồi kiểm tra chúng với ràng buộc.
And all those pairs, there's d squared. Every time you see a d squared in CSPs, it's usually that you're doing some checking of a cross-product of a domain.
Tất cả các cặp đó có d bình phương. Mỗi khi thấy d bình phương trong CSP, thường là ta đang kiểm tra tích Descartes của một miền giá trị.
So there we are. Let's prove it. Let's prove that this works. So the claim is, after the backward pass — so remember, we enforced the consistency of these arcs in a various particular pattern.
Vậy là xong. Giờ ta chứng minh. Ta chứng minh cách này đúng. Khẳng định là: sau lượt đi ngược — nhớ rằng ta đã áp dụng tính nhất quán cho các cung này theo một thứ tự cụ thể.
It wasn't like arc-consistency for the whole graph, where we do it, and we do it again and again and again and again and again. We just did one pass.
Không như nhất quán cung cho cả đồ thị, nơi ta làm đi làm lại nhiều lần. Ta chỉ làm một lượt.
The claim is that after you do that, all root-to-leaf arcs are consistent. Why is that? Well, each arc was made consistent at one point. We know that because we visited each one.
Khẳng định là sau đó, mọi cung từ gốc đến lá đều nhất quán. Tại sao? Mỗi cung đã được làm nhất quán tại một thời điểm. Ta biết vì ta đã duyệt từng cung.
And when we visited it, it was consistent when we were done. It is entirely possible that after that point, we screwed things up. So for example, let's take B to D here.
Và khi duyệt xong, nó nhất quán. Có thể hoàn toàn xảy ra là sau đó, ta làm hỏng nó. Ví dụ, xét cung B tới D.
We visited this arc when we processed D. We made it consistent. It was consistent for that brief moment in time. And then we did some computation.
Ta duyệt cung này khi xử lý D. Ta làm nó nhất quán. Nó nhất quán trong khoảnh khắc ngắn đó. Rồi ta tính toán tiếp.
But all the computation we did was on this side.
Nhưng mọi tính toán đều ở phía bên này.
So what could make this arc that was once consistent, what could ruin it? What could ruin the beautiful consistency of B pointing to D?
Vậy điều gì có thể phá cung từng nhất quán này, điều gì làm hỏng nó? Điều gì phá được tính nhất quán đẹp đẽ của B trỏ tới D?
Well, consistency says, for everything in B, there's an extension to D. So deleting stuff from B is not going to make anything worse. That's just going to make our life easier.
Nhất quán nghĩa là với mọi giá trị ở B, có một phần mở rộng sang D. Nên xóa giá trị khỏi B không làm mọi thứ tệ đi. Nó chỉ làm mọi thứ dễ hơn.
The problem comes if we delete stuff out of D. But we won't, because we're headed in the other direction.
Vấn đề xảy ra nếu ta xóa giá trị khỏi D. Nhưng ta sẽ không xóa, vì ta đi theo hướng ngược lại.
So provided we do them in this order, it will be consistent when you visit the arc. And that consistency will never be messed up, because we will never delete anything else from D.
Nên miễn là làm theo thứ tự này, cung sẽ nhất quán khi ta duyệt nó. Và tính nhất quán đó sẽ không bao giờ bị phá, vì ta sẽ không xóa thêm gì khỏi D.
Claim two — if root-to-leaf arcs — as we just saw that they are — are consistent, the forward assignment will not backtrack. Well, we're going to have to do an induction on position.
Khẳng định hai: nếu các cung gốc đến lá — như ta vừa thấy là chúng — nhất quán, thì lượt gán xuôi sẽ không quay lui. Ta sẽ phải quy nạp theo vị trí.
And I'm not going to do it, but let's look at why it's true.
Tôi sẽ không làm, nhưng hãy xem tại sao nó đúng.
So we assign something at A. We know we can extend it to B. Whatever we assign to B, we know we can extend it to C here.
Ta gán một giá trị ở A. Ta biết có thể mở rộng sang B. Gán gì cho B, ta biết cũng mở rộng được sang C.
And that's because each thing, whenever we go to some node — to let's say we go to F here.
Đó là vì mỗi khi ta đến một nút nào đó — giả sử ta đến F ở đây.
D to F is consistent.
D tới F là nhất quán.
Provided we've made it all the way up to D and E, whatever we did at D has a consistent extension to F, and therefore, we can assign to F. That's the core of the induction.
Miễn là ta đã đi tới D và E, thì giá trị ta gán ở D có một phần mở rộng nhất quán sang F, nên ta gán được cho F. Đó là cốt lõi của phép quy nạp.
But how could this be? Why doesn't this work on an arbitrary graph? Where did I use the fact that this is a tree?
Nhưng sao lại thế được? Sao cách này không chạy trên đồ thị tùy ý? Tôi đã dùng tính chất cây ở đâu?
Because all I really need to know to know that F is going to be OK is that whatever I assign to D, because of the consistency of D to F, whatever I assign to D extends to F.
Vì điều tôi thực sự cần biết để chắc F ổn là gán gì cho D, nhờ tính nhất quán của D tới F, thì cũng mở rộng được sang F.
Let's say it wasn't a tree. It's not a tree anymore. F has two parents. It's still fine, right?
Giả sử nó không phải cây. Không còn là cây nữa. F có hai nút cha. Vẫn ổn, đúng không?
Whatever I assign to D, there's an extension to F. That doesn't break the constraints. And whatever I assigned at C, there's an extension to F. So I'm good, right?
Gán gì cho D, cũng có phần mở rộng sang F. Điều đó không vi phạm ràng buộc. Và gán gì ở C, cũng có phần mở rộng sang F. Vậy là ổn, đúng không?
STUDENT
[INAUDIBLE] PROFESSOR: Yes, that's exactly right. Let me repeat that.
[KHÔNG NGHE RÕ] GIÁO SƯ: Đúng, chính xác. Để tôi nhắc lại.
I'm going to repeat it and modify it. But it is exactly right.
Tôi sẽ nhắc lại và chỉnh một chút. Nhưng bạn nói hoàn toàn đúng.
So yes, the consistency of these arcs tells me that whatever I assigned at D has an extension to F. Whatever I assigned at C has an extension to F. But there's no guarantee that they have an extension in common.
Đúng vậy, tính nhất quán của các cung này cho tôi biết gán gì ở D cũng có phần mở rộng sang F. Gán gì ở C cũng có phần mở rộng sang F. Nhưng không đảm bảo là chúng có chung một phần mở rộng.
So this consistency only lets me go without backtracking if there's only one parent. Because if I had two parents, they might not have a joint extension.
Nên tính nhất quán này chỉ cho phép đi mà không quay lui nếu chỉ có một nút cha. Vì nếu có hai nút cha, chúng có thể không có một phần mở rộng chung.
A joint extension would be 3-consistency for two parents, and we don't have that. So for a tree, you only need r-consistency.
Phần mở rộng chung sẽ là 3-nhất quán cho hai nút cha, và ta không có điều đó. Vậy với một cây, bạn chỉ cần r-nhất quán.
If you have more parents than that, you would need higher order consistency, and we don't have that. So we just said why that is. And we'll see the same thing with base nodes.
Nếu có nhiều nút cha hơn thế, bạn sẽ cần nhất quán bậc cao hơn, và ta không có điều đó. Vậy là ta vừa giải thích lý do. Và ta sẽ thấy điều tương tự với các nút cơ sở.
There's an equivalent algorithm for tree structure for base nodes. All right, so we talked about two kinds of structures that are helpful.
Có một thuật toán tương đương cho cấu trúc cây với các nút cơ sở. Được rồi, ta đã nói về hai loại cấu trúc hữu ích.
There is independent sub-problems, which is extremely helpful and correspondingly rare. There's tree-structured CSPs, which are not that rare, and they're still efficient.
Một là các bài toán con độc lập, cực kỳ hữu ích và tương ứng là rất hiếm. Hai là CSP có cấu trúc cây, không hiếm đến thế, và vẫn hiệu quả.
But most of the time, you don't have a tree either. You've got something that's tree-ish.
Nhưng phần lớn thời gian, bạn cũng không có một cây. Bạn có thứ gì đó gần giống cây.
And so most of exploiting structure is looking at the graph you have and figuring out if there's a good way to turn it into one of the efficient patterns.
Vì vậy khai thác cấu trúc chủ yếu là nhìn vào đồ thị bạn có và xem có cách nào hay để biến nó thành một trong các dạng hiệu quả đó không.
So we'll talk about two ways to do this. One way to deal with things that are nearly tree-structured is to make them tree-structured.
Ta sẽ nói về hai cách. Một cách xử lý thứ gần như có cấu trúc cây là biến nó thành có cấu trúc cây.
And we do that by deleting nodes until the thing is tree-structured. How do we delete nodes? If we could delete nodes, we'd just start deleting nodes. So there's an algorithm called cutset conditioning.
Ta làm vậy bằng cách xóa các nút cho đến khi nó có cấu trúc cây. Làm sao xóa nút? Nếu xóa được thì ta cứ xóa thôi. Có một thuật toán gọi là cutset conditioning.
Here's how it works. Conditioning in a CSP is when you instantiate a variable. So in this case, I can take my full CSP on the left.
Nó hoạt động như sau. Conditioning trong CSP là khi bạn gán giá trị cho một biến. Ở đây, tôi lấy CSP đầy đủ bên trái.
I can instantiate southern Australia to some value. It now has a particular value. As soon as I give it a value, I can then consider its effect on its neighbor's domains.
Tôi gán southern Australia một giá trị nào đó. Giờ nó có một giá trị cụ thể. Ngay khi gán giá trị, tôi có thể xét ảnh hưởng của nó lên miền giá trị của các nút lân cận.
So maybe I assign it red. And that means there is going to be an impact on all of its neighbors as a consequence.
Giả sử tôi gán màu đỏ. Điều đó nghĩa là sẽ có tác động lên tất cả các nút lân cận.
But once I have assigned SA, and I've seen its impact, the remaining problem looks like this and is now tree-structured. Is it the same problem?
Nhưng khi đã gán SA và thấy tác động của nó, bài toán còn lại trông như thế này và giờ có cấu trúc cây. Nó có phải cùng một bài toán không?
No, because I just assigned SA to red. In the original problem, I didn't know what to assign SA to.
Không, vì tôi vừa gán SA là đỏ. Trong bài toán gốc, tôi không biết nên gán SA là gì.
So what we can do is we can pick a node, and we can assign it, not once, but in every possible way and then solve the residual graph.
Vậy ta có thể chọn một nút, và gán nó không phải một lần mà theo mọi cách có thể, rồi giải đồ thị còn lại.
And any of those solutions concatenated with the cutset assignment is a solution to the original problem. Why is this helpful? Well, let's imagine you don't just have SA here.
Bất kỳ nghiệm nào trong số đó ghép với phép gán của cutset đều là nghiệm của bài toán gốc. Tại sao điều này hữu ích? Hãy tưởng tượng không chỉ có SA ở đây.
But you've got a cutset of size C. There's going to be C nodes that were going to delete from the graph by instantiating them.
Mà bạn có một cutset kích thước C. Sẽ có C nút mà ta xóa khỏi đồ thị bằng cách gán giá trị.
Well, when you instantiate them, you have to be prepared to instantiate them in all ways. Because you don't know which is going to be the one that leads to a solution.
Khi gán chúng, bạn phải sẵn sàng gán theo mọi cách. Vì bạn không biết cách nào sẽ là cách dẫn đến nghiệm.
So if I want to delete C nodes, I have to do D to the C instantiations and solve D to the C residual graphs. Is that bad?
Nên nếu muốn xóa C nút, tôi phải thử D mũ C phép gán và giải D mũ C đồ thị còn lại. Có tệ không?
It kind of depends on D and C. But mostly, it's OK if C is small.
Còn tùy vào D và C. Nhưng nhìn chung ổn nếu C nhỏ.
OK, so cutsets that are small can give you a fast algorithm if the residual graph, for example, is a tree or is independent.
Vậy cutset nhỏ có thể cho thuật toán nhanh nếu đồ thị còn lại, chẳng hạn, là một cây hoặc là độc lập.
And so you can look at your graph, and you can delete nodes until it's either independent or a tree or something you know how to handle efficiently.
Và bạn có thể nhìn vào đồ thị, xóa nút cho đến khi nó độc lập hoặc là cây hoặc thứ gì đó bạn biết xử lý hiệu quả.
That problem is efficient, but you have to solve it over and over again once for every value of the cutset. You actually don't have to do every value.
Bài toán đó hiệu quả, nhưng bạn phải giải đi giải lại, mỗi lần cho một giá trị của cutset. Thực ra bạn không phải thử mọi giá trị.
Because if the first value you try works, then you don't have to do the rest.
Vì nếu giá trị đầu tiên bạn thử chạy được, thì không cần làm phần còn lại.
OK, so this is fast for small C. And so that means you ask questions, like great, can I find the smallest cutset that will turn my graph into a tree, like NP-hard, right?
Vậy nó nhanh với C nhỏ. Và điều đó khiến bạn hỏi: tuyệt, tìm cutset nhỏ nhất biến đồ thị thành cây được không? Nó là NP-hard đấy. Nhưng đây là lớp AI.
This is AI class. Everything we do is NP-hard. But if you happen to have a cut set that's small that achieves this, you get to speed up. So here's the algorithm.
Cái gì ta làm cũng NP-hard. Nhưng nếu bạn tình cờ có một cutset nhỏ đạt được điều này, bạn sẽ được tăng tốc. Đây là thuật toán. Thật ra bạn đã biết thuật toán này rồi.
You actually already know the algorithm. But let's lay it out. You choose a cutset.
Nhưng ta cứ trình bày ra. Bạn chọn một cutset.
In this case, a good cutset choice would be SA, because when you delete it, the residual graph is a tree. It's, in fact, a chain. You instantiate the cutset in all possible ways.
Ở đây, một lựa chọn cutset tốt là SA, vì khi xóa nó, đồ thị còn lại là một cây. Thực ra nó là một chuỗi. Bạn gán cutset theo mọi cách có thể.
So instead of having one problem, you now have three problems or, in general, D to the C problems. But if the residuals are really efficient, that's OK. Because you compute the residual graphs.
Thay vì một bài toán, giờ bạn có ba bài toán, hoặc tổng quát là D mũ C bài toán. Nhưng nếu các đồ thị còn lại giải rất hiệu quả thì không sao. Vì bạn tính các đồ thị còn lại.
And then you solve them crazy fast with your special algorithm, like with a tree-structured algorithm. So you have more problems. But each one is simple. That's cutset conditioning.
Rồi giải chúng cực nhanh bằng thuật toán chuyên biệt, như thuật toán cho cấu trúc cây. Vậy bạn có nhiều bài toán hơn. Nhưng mỗi bài đều đơn giản. Đó là cutset conditioning. Câu đố: tôi nói là nói chung nó NP-hard.
Quiz — I know I told it was NP-hard in general. But find the smallest cutset for the graph below.
Nhưng hãy tìm cutset nhỏ nhất cho đồ thị bên dưới. Được rồi, thế này nhé?
All right, how about this? Take a two-minute break. And when you're back, we'll begin with two letters.
Nghỉ hai phút. Khi quay lại, ta sẽ bắt đầu với hai chữ cái. Được, cutset nhỏ nhất.
OK, smallest cutset. I guess I need a quadratic clicker or something like that. Anybody want to throw something out?
Chắc tôi cần một cái clicker bậc hai hay gì đó. Ai muốn đưa ra đáp án không? Tôi nghe có người nói AB.
I heard some ABs. Who thinks AB? All right. That's at least the majority opinion.
Ai nghĩ là AB? Ai nghĩ là AB? Được rồi. Ít nhất đó là ý kiến của đa số.
That's also correct. OK, good. So if you delete AB, what's left? Well, remember, A's got a constraint against G.
Cái đó cũng đúng. Tốt. Vậy nếu xóa AB thì còn lại gì? Hãy nhớ A có một ràng buộc với G.
So something will happen when you instantiate A on G. It'll delete some values on G and so on. But yeah, once you delete A and B, you're left with a nice tree-structured graph.
Nên sẽ có chuyện xảy ra khi ta gán giá trị cho A trên G. Nó sẽ xóa một số giá trị của G, v.v. Nhưng đúng vậy, khi đã xóa A và B, ta còn lại một đồ thị có cấu trúc cây rất đẹp.
It's kind of a trick question. I guess the smallest cutset is the empty set. But that is the smallest cutset that gives you a tree. So thanks for doing the pragmatics.
Đây hơi là câu hỏi mẹo. Tập cắt nhỏ nhất có lẽ là tập rỗng. Nhưng đó là tập cắt nhỏ nhất cho ra một cây. Cảm ơn các em đã tính đến chuyện thực tế.
All right, I'm going to tell you something a little more advanced that we're not going to go into as much depth or which you'll be responsible for in the material that takes a little further this idea of how you can take something that's almost a tree and make it a tree.
Giờ thầy sẽ nói một điều nâng cao hơn một chút, mà ta sẽ không đi sâu nhiều và các em cũng không phải chịu trách nhiệm về phần này, nó đưa ý tưởng này đi xa hơn một chút: làm sao lấy một thứ gần như là cây và biến nó thành cây.
So cutset conditioning is a way. It's delete nodes until you have a tree left. That is one way.
Cutset conditioning là một cách. Xóa các nút cho đến khi còn lại một cây. Đó là một cách.
But another way to do it is to do grouping, to look at your graph and say, it's almost a tree. Maybe there's nothing I want to delete.
Nhưng cách khác là gom nhóm, nhìn đồ thị và nói: nó gần như là cây. Có thể ta không muốn xóa gì cả.
But I can decompose it into something that is tree-structured over larger variable. So the idea here is that we're going to create a tree-structured graph. But it's not going to be the same variables.
Nhưng ta có thể phân rã nó thành thứ có cấu trúc cây trên các biến lớn hơn. Ý tưởng ở đây là ta sẽ tạo ra một đồ thị có cấu trúc cây. Nhưng các biến sẽ không còn như cũ.
They're going to be mega variables. And the variables here are going to be little clumps or clicks of variables in the original graph.
Chúng là các biến khổng lồ (mega variable). Và các biến ở đây sẽ là những cụm biến nhỏ, các clique trong đồ thị gốc.
So each mega variable is going to encode part of the original CSP. And the sub-problems, the outer CSP is going to be something that coordinates them.
Mỗi mega variable sẽ mã hóa một phần của CSP gốc. Còn CSP bên ngoài sẽ là thứ điều phối các bài toán con đó.
So for example, here is, again, our favorite example of map coloring in Australia.
Ví dụ, đây lại là ví dụ quen thuộc về tô màu bản đồ nước Úc.
One thing I could notice is if I'm going to solve that whole graph with all of its inequality constraints, I also will have a solution to the smaller CSP, which just describes what's going on the WA and T and SA nodes.
Có một điều ta nhận ra: nếu ta giải cả đồ thị với mọi ràng buộc khác nhau, thì ta cũng có lời giải cho CSP nhỏ hơn, chỉ mô tả chuyện xảy ra ở các nút WA, T và SA.
This is a little fragment of the graph. So a solution to the whole thing is a solution to this.
Đây là một mảnh nhỏ của đồ thị. Vậy lời giải của toàn bộ cũng là lời giải của phần này.
Another thing that I have to solve to solve the whole thing is I have to solve the NTSAQ region of the graph and so on.
Một việc khác cần giải để giải toàn bộ là vùng NT, SA, Q của đồ thị, v.v.
So I can break this graph into little pieces and say, instead of solving the whole graph, I'll just solve the little pieces. Great. I have independent sub-problems. I lied to you.
Vậy ta có thể chia đồ thị thành các mảnh nhỏ và nói: thay vì giải cả đồ thị, ta chỉ giải các mảnh nhỏ. Tuyệt. Ta có các bài toán con độc lập. Thầy nói dối đấy.
They're all over the place. It's all tractable. So what's the problem with solving these independently?
Chúng chồng chéo lung tung. Nhưng tất cả đều giải được. Vậy giải độc lập chúng có vấn đề gì?
What's the problem with solving, let's call this one, A and this one B. What's the problem with solving A and B separately? I'll give you A. I'll give you B. Yeah.
Có vấn đề gì khi giải, gọi cái này là A và cái này là B. Vấn đề gì khi giải A và B riêng rẽ? Thầy cho các em A. Thầy cho B. Mời em.
STUDENT
[INAUDIBLE] PROFESSOR: Exactly.
[KHÔNG NGHE RÕ] GIÁO SƯ: Chính xác.
To repeat that back, if you solve them independently, the solutions to the sub-problems may not actually be coherent.
Nhắc lại ý em: nếu giải độc lập, lời giải của các bài toán con có thể không nhất quán với nhau.
So you might, in problem A, color the Northern Territories red and, in problem B, color it green. So you can't just solve them separately. You need to solve them separately subject to some constraints.
Ở bài A, ta có thể tô Northern Territory màu đỏ, còn ở bài B lại tô màu xanh lá. Nên không thể giải riêng rẽ được. Ta cần giải riêng từng bài nhưng phải thỏa một số ràng buộc.
It's going to get meta, right? So the constraints are going to say do these sub-problems, but make sure that any variables they have in common are assigned in the same way.
Nó sẽ thành kiểu "meta" đấy. Các ràng buộc sẽ nói: hãy giải các bài toán con, nhưng mọi biến chung giữa chúng phải được gán giống nhau.
So here's mega variable one, which represents this part of the problem, and mega variable two represents the next, and so on. They're going to be nodes. These nodes have domains.
Đây là mega variable một, biểu diễn phần này của bài toán, mega variable hai biểu diễn phần kế tiếp, v.v. Chúng sẽ là các nút. Các nút này có miền giá trị.
Except what are the domains of a mega variable? It's the assignments to that mega variable, the legal ones. Well, what is that? That's all the legal assignments to that piece of the CSP.
Vậy miền giá trị của một mega variable là gì? Là các phép gán hợp lệ cho mega variable đó. Vậy đó là gì? Là mọi phép gán hợp lệ cho mảnh đó của CSP.
It's going to be triples, which are OK. It's going to be an enumeration of the solutions to the sub-problem. And then you go to M2, and it's going to have its solutions numerator.
Nó sẽ là các bộ ba thỏa mãn. Nó là việc liệt kê các lời giải của bài toán con. Rồi sang M2, nó cũng có các lời giải được liệt kê.
And then there's going to be for M3 and M4, these are the mega nodes. And then there's going to be constraints between them, which say they have to agree on shared variables.
Rồi tương tự cho M3 và M4, đây là các nút mega. Và sẽ có các ràng buộc giữa chúng, nói rằng chúng phải khớp nhau trên các biến chung.
And that means that if they were explicit, they would say things like, WA — red, SA — green, NTB and NTB, SA — green, q — whatever.
Nghĩa là nếu viết tường minh, nó sẽ nói những thứ như WA đỏ, SA xanh lá, NT và NT, SA xanh lá, Q thế nào cũng được.
That is OK, because it's consistent. And then if you solve this, you'll have a solution to the whole thing. Because each little piece is happy.
Như vậy là ổn, vì nó nhất quán. Và nếu giải được bài này, ta có lời giải cho toàn bộ. Vì mỗi mảnh nhỏ đều thỏa mãn.
And they're all coherent, which means the whole thing is happy all at once, and you have a solution.
Và chúng đều nhất quán, nghĩa là toàn bộ cùng thỏa mãn một lúc, và ta có lời giải.
I more or less implied that this mega graph is now going to be a tree. But it's only going to be a tree if you set it up right.
Thầy đã ngầm nói rằng đồ thị mega này giờ sẽ là một cây. Nhưng nó chỉ là cây nếu ta thiết lập đúng.
And we're not going to talk about the exact details. There's a property the pieces have to have so that it will be a tree and that consistency is actually guaranteed.
Ta sẽ không nói chi tiết cụ thể. Các mảnh phải có một tính chất để nó thành cây và tính nhất quán thực sự được đảm bảo.
And it's called the running intersection property. And in particular, it has to be the case that, say, if Victoria appears here and it appears here, it appears everywhere in between.
Đó gọi là running intersection property. Cụ thể, phải đảm bảo rằng nếu Victoria xuất hiện ở đây và xuất hiện ở đây, thì nó xuất hiện ở mọi chỗ ở giữa.
So it can't change its mind partway through. But provided you set this up in the right way, this mega problem can be efficiently solved.
Nên nó không thể đổi ý giữa chừng. Nhưng nếu thiết lập đúng cách, bài toán mega này có thể giải hiệu quả.
But it's sufficiently solvable over variables that are very, very big. So again, there's no free lunch. But you can sort of push your lunch around the plate as some of us like to do.
Nó giải được trên các biến rất, rất lớn. Vậy nên, một lần nữa, không có bữa trưa miễn phí. Nhưng bạn có thể đẩy bữa trưa của mình quanh cái đĩa như một số người trong chúng ta vẫn hay làm.
All right, something totally different now. All of the things that we've talked about so far are ways of solving CSPs that basically boil down to search.
Được rồi, bây giờ là một thứ hoàn toàn khác. Tất cả những gì ta đã nói đến giờ đều là các cách giải CSP mà về cơ bản quy về tìm kiếm.
And the search got smarter and smarter and smarter about look ahead in that search — that's what filtering was — and about structuring the exploration. That's what ordering was and so on.
Và việc tìm kiếm ngày càng thông minh hơn trong việc nhìn trước khi tìm kiếm, đó là việc lọc, và trong việc cấu trúc hóa quá trình khám phá. Đó là việc sắp thứ tự, và còn nhiều nữa.
Iterative improvement is the first time we're going to see a randomized algorithm. And it works in a very, very different way and actually generalizes to local search methods in general.
Cải thiện lặp là lần đầu tiên ta thấy một thuật toán ngẫu nhiên. Nó hoạt động theo một cách rất khác và thực ra khái quát hóa thành các phương pháp tìm kiếm cục bộ nói chung.
So local search iterative algorithm for CSPs is our first example of a local search. These methods work with complete states rather than partial assignment, partial assignment.
Thuật toán lặp tìm kiếm cục bộ cho CSP là ví dụ đầu tiên của tìm kiếm cục bộ. Các phương pháp này làm việc với trạng thái đầy đủ thay vì phép gán một phần.
And then at the end, if you've survived that long, and you have a complete assignment, an iterative algorithm starts with a complete state.
Và cuối cùng, nếu bạn sống sót đến lúc đó, và có một phép gán đầy đủ, thuật toán lặp bắt đầu từ một trạng thái đầy đủ.
For example, here's a 2-node graph coloring problem with an inequality constraint where they have both been colored red. It is a complete assignment. It is not a legal one.
Ví dụ, đây là bài toán tô màu đồ thị 2 nút với ràng buộc khác nhau, mà cả hai nút đều được tô màu đỏ. Đó là một phép gán đầy đủ. Nhưng nó không hợp lệ.
But that's OK. Local search methods don't necessarily have legal assignments, but they are complete. That's different than what we used to do, which was legal but not necessarily complete.
Nhưng không sao. Tìm kiếm cục bộ không nhất thiết có phép gán hợp lệ, nhưng chúng đầy đủ. Điều đó khác với cách ta làm trước đây, là hợp lệ nhưng không nhất thiết đầy đủ.
Now, they're complete, but not necessarily legal. If we want to apply this kind of algorithm to a CSP it works like this. You take an assignment with unsatisfied constraint.
Giờ thì chúng đầy đủ, nhưng không nhất thiết hợp lệ. Nếu muốn áp dụng loại thuật toán này cho một CSP thì nó chạy như sau. Bạn lấy một phép gán còn ràng buộc chưa thỏa.
You're going to have operators. Instead of a successor function, which gives you the next state, you're going to have operators, which reassign variable values. So you change the state in some way.
Bạn sẽ có các toán tử. Thay vì hàm kế tiếp cho ra trạng thái tiếp theo, bạn có các toán tử gán lại giá trị biến. Vậy là bạn thay đổi trạng thái theo một cách nào đó.
It goes from one complete state to another. So I might go to the state. This state's a lot better. It's complete and it's legal.
Nó đi từ một trạng thái đầy đủ sang trạng thái đầy đủ khác. Nên tôi có thể chuyển sang trạng thái này. Trạng thái này tốt hơn nhiều. Nó đầy đủ và hợp lệ.
And these methods have no fringe. You live on the edge. There is no backup plan.
Và các phương pháp này không có biên (fringe). Bạn sống trên lằn ranh. Không có phương án dự phòng.
Normally, when you do search, there's a whole backup plan of all of these things you're going to try if your current plan A doesn't work out.
Thông thường, khi tìm kiếm, có cả một kế hoạch dự phòng gồm mọi thứ bạn sẽ thử nếu kế hoạch hiện tại A không thành công.
That backup plan, that queue, the fringe can get exponentially large. Here, it does not exist. You've got your current thing, and you're going to keep tweaking it until it works or you give up.
Kế hoạch dự phòng đó, hàng đợi đó, biên (fringe) có thể lớn theo cấp số mũ. Ở đây, nó không tồn tại. Bạn chỉ có cái hiện tại, và bạn sẽ tiếp tục chỉnh nó cho đến khi chạy được hoặc bạn bỏ cuộc.
Here's the algorithm. While you have not solved the problem — in this case, it's a CSP. So there's a notion of solution. You're going to pick a variable.
Đây là thuật toán. Trong khi bạn chưa giải xong bài toán, ở đây là một CSP. Nên có khái niệm về lời giải. Bạn sẽ chọn một biến.
And here, you're going to select something that's conflicted. Don't mess with something that's already working. So you pick a variable that's already conflicted. Meaning it participates in a violated constraint.
Và ở đây, bạn chọn một biến đang xung đột. Đừng đụng vào thứ đang ổn. Nên bạn chọn một biến đang xung đột. Nghĩa là nó tham gia vào một ràng buộc bị vi phạm.
Then you're going to reassign its value. There's something called the minimum conflicts heuristic, which says choose a value that violates the fewest constraints. So get rid of as many conflicts as you can.
Rồi bạn gán lại giá trị cho nó. Có thứ gọi là hàm heuristic xung đột tối thiểu, nói rằng hãy chọn giá trị vi phạm ít ràng buộc nhất. Tức là loại bỏ càng nhiều xung đột càng tốt.
Basically, this means hill climb on the function of the total number of violated constraints.
Về cơ bản, nghĩa là leo đồi trên hàm tổng số ràng buộc bị vi phạm.
So for 4-queens, for example — or in any queens problem — you would have the queens just lying on the board in a bad state, where everybody is threatening everybody else or whatever the random state you start with is.
Ví dụ với bài 4 quân hậu, hay bất kỳ bài toán quân hậu nào, các quân hậu nằm trên bàn cờ ở trạng thái xấu, nơi ai cũng đe dọa nhau, hoặc là trạng thái ngẫu nhiên nào bạn bắt đầu. Còn các toán tử có thể là chọn một quân hậu và di chuyển nó trong cột hoặc hàng của nó.
And the operators might be, pick a queen and move it within that column or within that row. The goal test would be there's no attacks.
Kiểm tra đích là không còn quân nào tấn công nhau.
And then the function you would use to count the number of constraints violated might be the number of attacks. So that's it. That's the whole algorithm. Let's see it run twice.
Còn hàm dùng để đếm số ràng buộc bị vi phạm có thể là số lượt tấn công. Vậy thôi. Đó là toàn bộ thuật toán. Hãy xem nó chạy hai lần. Đây là nó chạy với n quân hậu.
Here it is running with n queens.
Đây rồi.
There it is. OK, it's five queens now. Here is the initial state. Each of these queens is conflicted.
Được, giờ là năm quân hậu. Đây là trạng thái ban đầu. Quân hậu nào cũng đang xung đột. Nên tôi chọn một biến đang xung đột.
So I'm going to pick a conflicted variable. Not the least conflicted one, not the most one, just pick one at random. I'll pick this one.
Không phải ít xung đột nhất hay nhiều nhất, cứ chọn ngẫu nhiên một cái. Tôi chọn cái này.
And then you pick a minimum of conflicts, which in this case, is to reassign it over here. This is my new state. It's a local search procedure. This is my only state.
Rồi bạn chọn vị trí xung đột tối thiểu, trong trường hợp này là gán lại nó sang đây. Đây là trạng thái mới của tôi. Đây là thủ tục tìm kiếm cục bộ. Đây là trạng thái duy nhất của tôi. Tôi làm lại lần nữa.
I'm going to do it again. I'm going to look at my successors informally. But I'm going to look at the ways I can modify this state.
Tôi xem các trạng thái kế tiếp một cách không chính thức. Tức là xem các cách tôi có thể sửa trạng thái này.
And I'm going to pick a conflicted variable, and I'm going to put it in a place that minimizes its conflicts. Then I'm going to pick a conflicted variable.
Và tôi chọn một biến đang xung đột, rồi đặt nó vào chỗ giảm thiểu xung đột của nó. Rồi tôi chọn một biến đang xung đột. Tôi đặt nó vào chỗ giảm thiểu xung đột.
I'm going to put it in a place that minimizes conflicts. I'm going to do it again. And actually, I broke something. But that's OK, because I have no memory.
Tôi làm lại lần nữa. Và thực ra tôi vừa làm hỏng một thứ. Nhưng không sao, vì tôi không có bộ nhớ. Tôi cứ làm tiếp cho đến khi giải xong.
I'm going to keep doing this until now I solved it. That's it.
Xong rồi. Đây là ví dụ tô màu bản đồ trên bài toán lớn.
This was our map coloring example on the big problem. Remember, we did filtering to make sure we didn't mess anything up? You see all the domains. Let's switch to iterative improvement.
Nhớ không, ta đã lọc để chắc là không làm hỏng gì? Bạn thấy tất cả các miền giá trị. Giờ ta chuyển sang cải thiện lặp. Bùm, phép gán đầy đủ.
Boom, complete assignment. It's terrible. Look at all those greens. It's not a good assignment, but it's complete.
Tệ thật. Tệ thật. Nhìn toàn màu xanh lá kìa. Đây không phải phép gán tốt, nhưng nó đầy đủ.
What am I going to do now instead of assigning new things? I'm going to pick up a node that participates in a conflict.
Giờ thay vì gán thêm giá trị mới, em sẽ làm gì? Tôi sẽ chọn một nút đang tham gia vào xung đột.
And I'm going to assign it in a way that minimizes its conflicts. So here's the next step. OK, I re-assign that one. Our conflict disappeared.
Và tôi sẽ gán lại cho nó theo cách giảm thiểu số xung đột của nó. Đây là bước tiếp theo. Được rồi, tôi gán lại nút đó. Xung đột biến mất.
Step 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, done.
Bước 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, xong.
That's it. This works really well sometimes. Yeah.
Thế thôi. Đôi khi cách này hiệu quả thật sự. Vâng, em hỏi đi.
STUDENT
Do you risk introducing a new conflict problem?
Có nguy cơ tạo ra xung đột mới không ạ?
PROFESSOR
Do you risk introducing a new conflict? Yep. Can this thing run forever? Yep.
Có nguy cơ tạo ra xung đột mới không? Có. Nó có thể chạy mãi không dừng không? Có.
Will it give you an optimal solution if there are waits? No. Do you have any guarantee whatsoever? No.
Nó có cho nghiệm tối ưu nếu có chi phí không? Không. Có bảo đảm nào không? Không.
But it's very fast very often. So how do you feel about that? Yeah, it's OK to have complex feelings about that. All right, in practice, these things are really fast.
Nhưng rất thường xuyên nó chạy rất nhanh. Vậy các em thấy sao? Cảm xúc lẫn lộn về chuyện này cũng bình thường. Thực tế thì những thứ này chạy rất nhanh.
Min-conflicts, sometimes it's amazing. So given a random initial state, you can solve — remember we were like, we can solve n-queens of size 5, of size 20, of size 300 with these other methods.
Min-conflicts đôi khi tuyệt vời. Với một trạng thái ban đầu ngẫu nhiên, các em nhớ không, trước đó ta giải n-queens cỡ 5, cỡ 20, cỡ 300 bằng các phương pháp khác.
You can solve basically n-queens of size anything with this method in basically constant time. Because you randomize it and most of the board is fine. And you fix a couple problems, and you're done.
Với phương pháp này, n-queens cỡ nào cũng giải được trong thời gian gần như hằng số. Vì ta khởi tạo ngẫu nhiên và phần lớn bàn cờ đã ổn. Sửa vài lỗi là xong.
That's great. So far, it's looking pretty good. There's going to be some bad news, right?
Tuyệt vời. Cho đến giờ trông khá tốt. Sẽ có tin xấu đấy, đúng không?
OK, let's hear some more news It also seems to be true that for almost any randomly generated CSP, you can solve it instantly.
Được rồi, nghe thêm tin nữa. Dường như hầu như mọi CSP sinh ngẫu nhiên đều giải được ngay lập tức.
Here's an important quantity — the ratio of number of constraints to number of variables, broadly speaking. If there's a lot of variables but almost no constraint, this ratio is small.
Có một đại lượng quan trọng: tỉ số giữa số ràng buộc và số biến, nói một cách tổng quát. Nếu có nhiều biến nhưng gần như không có ràng buộc, tỉ số này nhỏ.
And would you describe this problem as easy or hard? Tons of variables, no constraints. It's easy, right? Compared to the variables, there's barely any constraints at all.
Bài toán này dễ hay khó? Rất nhiều biến, không có ràng buộc. Dễ, đúng không? So với số biến thì gần như chẳng có ràng buộc nào.
You just assign whatever you want. And therefore, iterative improvement works great. That's over here. What happens over here?
Muốn gán gì thì gán. Nên cải thiện lặp hoạt động rất tốt. Đó là ở bên này. Còn bên này thì sao?
Over here, there's just tons of constraints. The variables have constraints all over them. Is this easy or hard? Think.
Bên này có cực nhiều ràng buộc. Các biến bị ràng buộc chằng chịt. Dễ hay khó? Nghĩ đi.
It's a trick question. So the answer must be — easy. Why is this easy? Well, if you have a solution, and there's constraints everywhere, there's probably not a lot of wiggle room.
Câu hỏi mẹo đấy. Nên đáp án phải là dễ. Tại sao dễ? Nếu có nghiệm mà ràng buộc ở khắp nơi, thì có lẽ không còn nhiều chỗ để xoay xở.
And it turns out that very quickly, you can chase your solution down really quickly.
Và hóa ra rất nhanh chóng, ta có thể truy ra nghiệm rất nhanh.
Now of course, there's this middle ground here, where there's just the right balance of constraints and variables, where it's hard to find solutions, but it's kind of hard to tell if you're on the wrong track.
Tất nhiên còn vùng giữa này, nơi ràng buộc và biến cân bằng vừa vặn, khó tìm nghiệm, mà cũng khó biết mình có đang đi sai hướng không.
And there's this spike in how long you have to run these iterative improvement algorithms. So here's a map. There's this whole world of places where CSPs will be solved instantly.
Và có một đỉnh nhọn về thời gian phải chạy các thuật toán cải thiện lặp này. Đây là một bản đồ. Có cả một vùng rộng nơi CSP được giải ngay lập tức.
And then there's this bad area of hard problems, where the critical ratio is like the right balance, where it's not over-constrained and not under-constrained. Is that good news?
Rồi có vùng xấu gồm các bài toán khó, nơi tỉ số tới hạn cân bằng vừa vặn, tức là không quá nhiều và không quá ít ràng buộc. Đó có phải tin tốt không?
Where are you? Where's the problems that you see in daily life? Right there. That's it.
Các em đang ở đâu? Những bài toán trong đời sống thường nằm ở đâu? Ngay chỗ đó. Đúng vậy.
So it turns out that this constraint for hard problems that we actually want to solve, very often, you are in this bad ratio here. And queens is a little weird, because it's pretty under-constrained.
Hóa ra với những bài toán khó mà ta thực sự muốn giải, rất thường xuyên ta rơi vào tỉ số xấu này. Còn bài queens hơi lạ, vì nó khá ít ràng buộc.
OK, in summary, and then we're going to do a quick intro to local search. In summary, CSPs are a special kind of search problem.
Được rồi, tóm tắt, rồi ta sẽ giới thiệu nhanh về tìm kiếm cục bộ. Tóm lại, CSP là một dạng bài toán tìm kiếm đặc biệt.
The states are partial assignments, and the goal test is defined by constraints. Because the goal test can be broken into pieces, we could smear that goal all the way through the backtracking search.
Các trạng thái là phép gán từng phần, và kiểm tra đích được định nghĩa bằng các ràng buộc. Vì kiểm tra đích có thể tách thành nhiều phần, ta rải việc kiểm tra đó suốt quá trình tìm kiếm quay lui.
And that gave us a faster way of using something like DFS to find solutions. We sped it up by being smart about the order that we attacked the variables in the problem.
Nhờ vậy ta có cách nhanh hơn để dùng thứ như DFS tìm nghiệm. Ta tăng tốc bằng cách khéo chọn thứ tự xử lý các biến của bài toán.
We sped it up by filtering and looking at the consequences of our assignments before we made the next assignment.
Ta tăng tốc bằng lọc, và xem xét hệ quả của các phép gán trước khi thực hiện phép gán kế tiếp.
And then we sped it up by looking for or creating special structures within our CSP in order to have specialized algorithms or better performance from our existing algorithms.
Rồi ta tăng tốc bằng cách tìm hoặc tạo ra các cấu trúc đặc biệt trong CSP để dùng thuật toán chuyên biệt hoặc cải thiện hiệu năng của các thuật toán sẵn có.
We also have an iterative algorithm called min-conflicts that is very effective in practice for many cases, though, you have almost no guarantees.
Ta cũng có một thuật toán lặp gọi là min-conflicts, rất hiệu quả trong thực tế ở nhiều trường hợp, dù gần như không có bảo đảm nào.
That's CSPs. We're going to talk about something very, very related that uses basically the same ideas. We're going to talk about local search here. You can think about local search as you're this robot.
Đó là CSP. Giờ ta sẽ nói về thứ rất liên quan, dùng về cơ bản cùng những ý tưởng đó. Ta sẽ nói về tìm kiếm cục bộ. Có thể hình dung bạn là con robot này.
You're in a mountain range, and you're trying to find the top, because you're an optimizer. You're searching. You're trying to find the best solution here.
Bạn đang ở trong dãy núi, và cố tìm đỉnh, vì bạn là một bộ tối ưu hóa. Bạn đang tìm kiếm. Bạn đang cố tìm lời giải tốt nhất.
So you want to go up there to that golden summit. But what does it look like to you? Well, you're a robot. And you can see about this far ahead of you.
Vậy là bạn muốn leo lên đỉnh vàng đằng kia. Nhưng bạn nhìn thấy gì? Bạn là một con robot. Và bạn chỉ nhìn thấy được xa chừng này phía trước.
So you go uphill, and you can see about this far ahead of you. And so you go uphill, and you go uphill, and you go uphill. And you get to here.
Thế là bạn đi lên dốc, và bạn chỉ thấy được xa chừng này phía trước. Nên bạn cứ đi lên, đi lên, rồi lại đi lên. Và bạn đến đây.
And then what happens? You look around and everything's downhill. You do your little victory dance. Because as far as you can tell, you've just won.
Rồi chuyện gì xảy ra? Bạn nhìn quanh và đâu đâu cũng là dốc xuống. Bạn nhảy điệu ăn mừng nho nhỏ. Vì theo những gì bạn thấy, bạn vừa thắng rồi.
You said, what about this thing up here? What about that much better solution? You've no idea that's there. In local search, you have an operating point.
Bạn đâu biết có cái đỉnh ở trên kia. Còn lời giải tốt hơn nhiều kia thì sao? Bạn hoàn toàn không biết nó ở đó. Trong local search, bạn có một điểm đang xét.
You look around you and things either look like there's an uphill or there isn't. And if there's uphill, you go uphill. Iterative improvement was an example of that.
Bạn nhìn quanh và thấy hoặc có dốc lên, hoặc không. Nếu có dốc lên thì bạn đi lên. Cải thiện lặp là một ví dụ của điều đó.
More generally, to phrase that, tree search keeps a queue of unexplored alternatives. And that's what ensures its completeness.
Nói tổng quát hơn, tìm kiếm trên cây giữ một hàng đợi các lựa chọn chưa được khám phá. Và đó là điều đảm bảo tính đầy đủ của nó.
The reason why things like breadth for search and a-star, and uniform cost, and all of that are complete is because if what you're doing right now doesn't work out, you've got this possibly exponentially large list of other things you're going to try one by one until finally, something works.
Lý do các thuật toán như tìm kiếm theo chiều rộng, A*, và uniform cost đều đầy đủ là vì nếu cách đang làm không hiệu quả, bạn còn một danh sách có thể lớn theo cấp số mũ các lựa chọn khác để thử lần lượt cho đến khi có cái chạy được.
And in the worst case, you're going to try everything. So it's going to be complete. These algorithms tend to be complete.
Và trong trường hợp xấu nhất, bạn sẽ thử tất cả. Nên nó sẽ đầy đủ. Những thuật toán này thường đầy đủ.
But they're going to be pretty slow, because you're going to try everything in the worst case. Local search, you start with a single option. You try to make it better.
Nhưng chúng khá chậm, vì trong trường hợp xấu nhất bạn phải thử tất cả. Với local search, bạn bắt đầu với một lựa chọn duy nhất. Bạn cố làm nó tốt hơn.
And when you can't make it better, you stop. Then what happens? You're done. Is it a good solution?
Và khi không thể tốt hơn nữa, bạn dừng. Rồi chuyện gì xảy ra? Xong. Đó có phải lời giải tốt không?
Who knows. You're just done. So the new successor functionality is that you make local changes to an existing state. And this is usually much faster and more memory efficient.
Ai mà biết. Bạn cứ thế là xong. Vậy chức năng hàm kế thừa mới là bạn thực hiện các thay đổi cục bộ trên một trạng thái có sẵn. Cách này thường nhanh hơn nhiều và tiết kiệm bộ nhớ hơn.
But you have no guarantees, no completeness, no optimality. We talked about the general idea. Start wherever, move to the best neighboring state. If nothing is better than your current state, then you stop.
Nhưng bạn không có đảm bảo nào: không đầy đủ, không tối ưu. Chúng ta đã nói về ý tưởng chung. Bắt đầu từ đâu cũng được, chuyển sang trạng thái lân cận tốt nhất. Nếu không có gì tốt hơn trạng thái hiện tại thì dừng.
We already talked about why it's bad. It's not complete. It's not optimal. But what's good about it is it's really easy to apply in a lot of problems.
Chúng ta đã nói vì sao nó tệ. Nó không đầy đủ. Nó không tối ưu. Nhưng điểm tốt là nó rất dễ áp dụng cho nhiều bài toán.
It's really fast to come up with a solution. It may be a bad solution. But maybe that's OK. Depends on your problem.
Tìm ra lời giải rất nhanh. Có thể đó là lời giải tệ. Nhưng có khi vậy cũng được. Tùy vào bài toán của bạn.
It will at least be a better solution than the ones around it. So you can feel relatively good. So that's hill climbing.
Ít nhất nó cũng là lời giải tốt hơn những lời giải xung quanh. Nên bạn có thể yên tâm phần nào. Đó là hill climbing.
Here is basically the diagram of what your life in cartoon when you hill climb. Why is this cartoon? In general, any space research is very large and very high dimensional.
Đây là sơ đồ minh họa cuộc đời bạn dưới dạng hoạt họa khi leo đồi. Tại sao lại là hoạt họa? Nói chung, mọi không gian tìm kiếm đều rất lớn và có số chiều rất cao.
High dimensional spaces are very hard to visualize. They have all kinds of corners and high dimensional effects. And they definitely do not look like line drawings on a PowerPoint slide.
Không gian nhiều chiều rất khó hình dung. Chúng có đủ loại góc cạnh và hiệu ứng của nhiều chiều. Và chắc chắn chúng không giống những nét vẽ đường trên một slide PowerPoint.
But here's a line drawing on a PowerPoint slide. So schematically, you might be searching. Here's your current state right here.
Nhưng đây là một nét vẽ đường trên slide PowerPoint. Nên minh họa là bạn đang tìm kiếm. Đây là trạng thái hiện tại của bạn.
And you look around, and your operators might be nudged to the left or nudged to the right. Let me find another color. So you can go downhill. You can go uphill.
Bạn nhìn quanh, và các toán tử của bạn có thể là nhích sang trái hoặc nhích sang phải. Để tôi tìm màu khác. Bạn có thể đi xuống dốc. Bạn có thể đi lên dốc.
And so, at that current state, you'll go uphill. And you'll go uphill again and uphill again in hill climbing.
Vậy ở trạng thái hiện tại, bạn sẽ đi lên. Rồi lại đi lên và lại đi lên trong hill climbing.
And in general, you will stop when you get to a point that looks like this, where everything to your left and right or whatever operator you have is downhill.
Và nói chung, bạn sẽ dừng khi đến một điểm như thế này, nơi mọi hướng bên trái, bên phải hay bất kỳ toán tử nào cũng đều đi xuống.
That's called a local maximum. You've almost certainly heard this terminology used informally. Up here is the global maximum. What is the sign that you have a local maximum, instead of a global maximum?
Đó gọi là cực đại cục bộ. Chắc chắn bạn đã nghe thuật ngữ này được dùng một cách không chính thức. Trên kia là cực đại toàn cục. Dấu hiệu nào cho biết bạn đang ở cực đại cục bộ chứ không phải cực đại toàn cục?
No sign. They look exactly the same.
Không có dấu hiệu nào. Chúng trông hệt nhau.
Only from looking from the outside or knowing something special or comparing two maxima can you tell that this is not, in fact — it's like you're climbing Mt.
Chỉ khi nhìn từ bên ngoài hoặc biết điều gì đặc biệt hoặc so sánh hai cực đại thì bạn mới biết đây thực ra không phải — Giống như bạn leo núi Everest.
Everest. You get to here, and you think you're done. You're not done. You barely even started.
Bạn đến đây và nghĩ là xong rồi. Chưa xong đâu. Bạn gần như chưa bắt đầu.
But you can't tell from your local environment. Global maximum, local maximum, you can sometimes see these flat situations — either a flat local optimum or a shoulder — where things have leveled off.
Nhưng bạn không thể biết từ môi trường cục bộ quanh mình. Cực đại toàn cục, cực đại cục bộ, đôi khi bạn còn thấy những tình huống bằng phẳng — cực trị cục bộ phẳng hoặc một vai đồi (shoulder) — nơi mọi thứ đã đi ngang.
But they're not going to level off forever. But you can't tell. This thing could go off to infinity as far as you know. This is what it looks like to be hill climbing.
Nhưng chúng sẽ không đi ngang mãi. Nhưng bạn không thể biết. Theo những gì bạn biết, nó có thể tiếp tục lên đến vô cực. Đây là hình ảnh của việc leo đồi.
Here's a quiz. All right, starting from x where do you end up? b, OK. I agree.
Đây là một câu đố. Được rồi, bắt đầu từ x thì bạn kết thúc ở đâu? b, đúng rồi. Tôi đồng ý.
Starting from y — where is y? There's y. Where do you end up? d.
Bắt đầu từ y thì y ở đâu? y đây. Bạn kết thúc ở đâu? d.
That's sort of a bummer, because you feel like you should at least roll. That's not a thing. That's a metaphor that you might get from some combination of two dimensions in physics.
Hơi buồn nhỉ, vì bạn cảm thấy rằng ít nhất mình cũng nên lăn xuống tiếp chứ. Nhưng không có chuyện đó. Đó là một phép ẩn dụ bạn có thể lấy từ sự kết hợp nào đó của hai chiều trong vật lý.
There are notions of momentum, where you keep trying things and you keep moving in directions that have been successful. So I shouldn't say there's no such thing.
Có khái niệm động lượng, tức là bạn cứ thử và cứ tiếp tục di chuyển theo những hướng đã thành công. Nên tôi không nên nói là không có thứ như vậy.
But in general, with simple hill climbing, you do just stop whenever you can't see which direction is uphill. Starting from z — that's here — where do you end up?
Nhưng nói chung, với hill climbing đơn giản, bạn dừng lại ngay khi không thấy hướng nào đi lên dốc. Xuất phát từ z, ở đây, bạn kết thúc ở đâu?
e. And how do you feel about that? Well, you feel about the same as when you stop at b.
e. Và bạn thấy thế nào? Cũng gần giống như khi dừng ở b.
But if you had multiple restarts, and one stopped at b and one stopped at e, you can certainly tell them apart.
Nhưng nếu bạn có nhiều lần khởi động lại, một lần dừng ở b và một lần dừng ở e, thì chắc chắn bạn phân biệt được chúng.
And so that's why when people do local search, they often have many restarts running in parallel.
Và đó là lý do khi làm local search, người ta thường chạy song song nhiều lần khởi động lại.
Couple other ideas that are out there. Hill climbing is super powerful. Restarts on top of hill climbing where you start in a bunch of different places and you just swarm, that's pretty powerful.
Còn vài ý tưởng khác nữa. Hill climbing rất mạnh. Thêm khởi động lại lên trên hill climbing, tức là bạn bắt đầu từ nhiều chỗ khác nhau rồi cho chạy như một bầy, cách đó khá mạnh.
There are a couple of other ideas that I'm just going to cover very briefly the ideas. One is simulated annealing. You may have heard of. So simulated annealing basically says it's basically local search.
Còn một vài ý tưởng khác mà tôi chỉ nói rất ngắn gọn. Một là simulated annealing. Có thể bạn đã nghe tên. Simulated annealing về cơ bản vẫn là local search.
It's designed for problems that look like this, where you're here, and you look around you. And hill climbing would say, to my left is downhill, to my right is downhill, I'm done.
Nó được thiết kế cho các bài toán như thế này, khi bạn đang ở đây và nhìn quanh. Hill climbing sẽ nói: bên trái là xuống dốc, bên phải cũng xuống dốc, xong.
Simulated annealing is like hill climbing search with a lot of caffeine. So it's going to bounce around. And sometimes it's going to bounce out of these local optima.
Simulated annealing giống như hill climbing uống thật nhiều cà phê. Nó sẽ nảy lung tung. Và đôi khi nó nảy ra khỏi các cực trị cục bộ này.
That's the core idea. In particular, the algorithm goes like this. You start with an initial state. And then you do the following forever.
Đó là ý tưởng cốt lõi. Cụ thể, thuật toán như sau. Bạn bắt đầu với một trạng thái ban đầu. Rồi bạn làm các bước sau mãi mãi.
You're never actually done. You just decide to shut it off at some point. You get a temperature schedule. What's a temperature?
Thực ra không bao giờ xong. Bạn chỉ quyết định tắt nó ở một lúc nào đó. Bạn có một lịch trình nhiệt độ. Nhiệt độ là gì?
A temperature is just a physics analogy. And there's some mathematics to back it up. But it's a physics analogy that has to do with how much you're bouncing around.
Nhiệt độ chỉ là một phép tương tự với vật lý. Và có một chút toán học đằng sau. Nhưng đó là phép tương tự vật lý liên quan đến mức độ bạn nảy lung tung.
And over time, you bounce around less. If your temperature hits 0, you just stop. Otherwise, you look at a successor. So instead of picking the best successor, you just pick one at random.
Và theo thời gian, bạn nảy ít đi. Nếu nhiệt độ về 0, bạn dừng. Nếu không, bạn xét một trạng thái kế tiếp. Thay vì chọn trạng thái kế tiếp tốt nhất, bạn chọn ngẫu nhiên một cái.
And you say, you, am I going to do it, or am I going to not do it? And then you look at the change in value, and you look at the temperature.
Rồi tự hỏi: mình có đi theo nó không, hay không đi? Sau đó bạn xem độ thay đổi giá trị, và xem nhiệt độ.
And so you compute the change in energy. And if it's better, you just do it. Go in that random direction. But even if it's worse, you do it with some probability.
Bạn tính độ thay đổi năng lượng. Nếu tốt hơn thì bạn cứ đi. Đi theo hướng ngẫu nhiên đó. Nhưng kể cả khi tệ hơn, bạn vẫn đi với một xác suất nào đó.
And the probability you do it has to do with how much worse it is. The worse it is, the less likely you are going to do it.
Và xác suất bạn đi phụ thuộc vào mức độ tệ hơn. Càng tệ thì càng ít khả năng bạn đi.
And the temperature — the hotter it is, the more likely you are to do it. And so at the beginning, you're just moving around randomly.
Còn nhiệt độ thì càng nóng, bạn càng dễ đi theo. Nên lúc đầu, bạn chỉ di chuyển ngẫu nhiên.
If the temperature is really high, you're just totally moving randomly. If the temperature is very low, you're doing hill climbing. And in between, you're hill climbing with some caffeine.
Nếu nhiệt độ rất cao, bạn di chuyển hoàn toàn ngẫu nhiên. Nếu nhiệt độ rất thấp, bạn đang làm hill climbing. Ở giữa, bạn làm hill climbing có thêm cà phê.
And so you can often bounce your way out of little local optima. And that can be effective. Yeah.
Nhờ vậy bạn thường nảy thoát khỏi các cực trị cục bộ nhỏ. Và điều đó có thể hiệu quả. Vâng.
STUDENT
[INAUDIBLE] PROFESSOR: Oh, what is annealing about this? That has to do with a physics analogy of metal cooling.
[KHÔNG NGHE RÕ] GIÁO SƯ: À, annealing ở đây nghĩa là gì? Nó liên quan đến phép tương tự vật lý với việc kim loại nguội đi.
I won't push the analogy on this or on genetic algorithms or neural nets or anything like that. They're techniques. They have math.
Tôi sẽ không đào sâu phép tương tự này, hay với thuật toán di truyền hay mạng nơ-ron hay những thứ tương tự. Chúng là các kỹ thuật. Chúng có toán học.
Their names often come from some analogy to something else that I, in general, will not push too far.
Tên của chúng thường đến từ một phép so sánh với thứ khác mà nói chung tôi sẽ không đi quá xa.
Amazingly, this is one of the few search processes that has a guarantee. It has a theoretical guarantee of optimality.
Đáng ngạc nhiên là đây là một trong số ít quá trình tìm kiếm có bảo đảm. Nó có bảo đảm lý thuyết về tính tối ưu.
So it basically says that if you decrease your temperature slowly enough, you will eventually converge to the optimal state. Why is that? Well, it's a really interesting guarantee, right?
Cụ thể là nếu bạn giảm nhiệt độ đủ chậm, cuối cùng bạn sẽ hội tụ về trạng thái tối ưu. Tại sao vậy? Đây là một bảo đảm rất thú vị, đúng không?
Why is that? It says, you're bouncing around, and you maybe bounce less and less over time. What do you do when you're bouncing around?
Tại sao vậy? Bạn cứ nảy lung tung, và nảy ít dần theo thời gian. Khi nảy lung tung thì bạn làm gì?
You get to this good part of the state, and you bounce around. And eventually, you bounce out of it, and you bounce in some less good part.
Bạn đến phần tốt của không gian trạng thái và nảy quanh đó. Rồi cuối cùng bạn nảy ra khỏi đó, và rơi vào phần kém tốt hơn.
And you bounce back to the good part. And you bounce back to the less good part. And the higher the hill is, the more time you spend there in the limit of infinity.
Rồi bạn nảy lại về phần tốt. Rồi lại nảy về phần kém tốt. Và đồi càng cao thì bạn càng dành nhiều thời gian ở đó khi tiến tới vô hạn.
You'll spend a lot of time there. You'll spend less time on the smaller hill. And the taller the hill, the longer you're going to be there.
Bạn sẽ ở đó rất lâu. Bạn sẽ ở ít hơn trên ngọn đồi nhỏ hơn. Đồi càng cao thì bạn ở đó càng lâu.
So if you run this thing forever, you can actually turn this into a guarantee of optimality. But it's not magic. In reality, that guarantee does not hold on any actual finite time scale.
Nên nếu chạy mãi mãi, bạn có thể biến nó thành một bảo đảm về tính tối ưu. Nhưng nó không phải phép màu. Trên thực tế, bảo đảm đó không đúng trong bất kỳ khoảng thời gian hữu hạn thực tế nào.
And basically, it boils down to the more downhill steps you have to take to escape a local optimum, the less likely you are to do them all in a row.
Về cơ bản, bạn càng phải đi nhiều bước xuống dốc để thoát khỏi một cực trị cục bộ, thì càng khó làm hết các bước đó liên tiếp.
And so you're pretty much going to be stuck unless it's just one downhill step or two and then you're escaped.
Nên về cơ bản bạn sẽ bị kẹt, trừ khi chỉ cần một hay hai bước xuống dốc là bạn đã thoát ra được.
So people think really hard not just about how to jitter around, but how to create what are called ridge operators, which let you jump around the space in better ways.
Vì vậy người ta nghĩ rất kỹ, không chỉ về cách dao động xung quanh, mà còn cách tạo ra cái gọi là toán tử ridge, giúp bạn nhảy khắp không gian theo những cách tốt hơn.
One example of a very extreme ridge operator — to give you an example of what it would mean to do more than just jittering around — would be something like a genetic algorithm.
Một ví dụ về toán tử ridge rất cực đoan — để cho các bạn thấy làm nhiều hơn là chỉ dao động xung quanh nghĩa là gì — là một thứ như thuật toán di truyền.
There's an evolutionary metaphor here that I won't, again, not push too far. It's really just a method here. Using the natural selection metaphor that has basically two parts.
Ở đây có một phép ẩn dụ tiến hóa mà tôi sẽ không đẩy đi quá xa. Thực ra nó chỉ là một phương pháp. Dùng phép ẩn dụ chọn lọc tự nhiên, nó về cơ bản có hai phần.
You have a bunch of candidates. They have fitness. But you're keeping a bunch of candidates, like, a bunch of restarts. They have fitness.
Bạn có một nhóm các ứng viên. Chúng có độ thích nghi. Bạn giữ cả một nhóm ứng viên, giống như nhiều lần khởi động lại. Chúng có độ thích nghi.
So you select some of them. And some of them duplicate because they're good. And some of them didn't get selected. And so they're off.
Vậy bạn chọn một số trong chúng. Một số được nhân đôi vì chúng tốt. Một số không được chọn. Thế là chúng đi.
They're gone. And then of the pairs that are left, you do something called crossover. This is the important part. You take partial hypotheses and you recombine them.
Biến mất. Rồi với các cặp còn lại, bạn thực hiện cái gọi là lai ghép (crossover). Đây là phần quan trọng. Bạn lấy các giả thuyết từng phần và tổ hợp lại.
So what would that mean for real? Well, it might mean something like this. I have two pretty good n-queen solutions. Neither is actually a solution.
Vậy thực tế nghĩa là gì? Có thể là như thế này. Tôi có hai lời giải n-queen khá tốt. Cả hai thực ra đều chưa phải lời giải.
But they both have a small number of conflicts. So I'm going to slice my board down the middle, and I'm going to take part of a and part of b and slam them together.
Nhưng cả hai đều có ít xung đột. Nên tôi sẽ cắt bàn cờ ở giữa, lấy một phần của a và một phần của b rồi ghép chúng lại.
I feel like it's trying to tell me something. All right, let's restart now. Just kidding.
Hình như nó đang muốn nói gì với tôi. Được rồi, giờ khởi động lại nhé. Đùa thôi.
So why does this make sense? Well, if you formulated the problem just right, your left quadrant and your right quadrant have the right number of queens.
Vậy tại sao cách này hợp lý? Nếu bạn biểu diễn bài toán đúng cách, phần tư bên trái và phần tư bên phải có đúng số quân hậu.
And maybe one's good on the left, and one's good on the right. And when you smash them together, they'll work. Or maybe not. Maybe you'll get the worst of both.
Có thể bên trái tốt, và bên phải cũng tốt. Ghép lại thì chúng sẽ hoạt động. Hoặc không. Có thể bạn nhận được cái tệ nhất của cả hai.
And you'll get some terrible thing with lots of conflicts. And so you do need to still do a bunch searches, a bunch of restarts, and a bunch of rounds of these.
Và ra một thứ rất tệ với đầy xung đột. Nên bạn vẫn cần thực hiện nhiều lần tìm kiếm, nhiều lần khởi động lại, và nhiều vòng như vậy.
But this is an example of not just nudging your thing locally, but just taking entirely different ways of traversing the space, which is why I bring it up.
Nhưng đây là ví dụ về việc không chỉ nhích nhẹ cục bộ, mà dùng những cách hoàn toàn khác để duyệt không gian, đó là lý do tôi nhắc đến.
OK, that's it for today.
Được rồi, hôm nay đến đây.
Next time, you and Peter will talk about adversarial search, which is how you think about planning forward in computation when not just you, but also other agents who are trying to ruin your day, are taking action.
Lần tới, bạn và Peter sẽ nói về tìm kiếm đối kháng, tức là cách suy nghĩ lập kế hoạch về phía trước trong tính toán khi không chỉ bạn, mà cả các tác tử khác, đang tìm cách phá hỏng ngày của bạn, cùng hành động.
[AUDIO OUT]
[MẤT ÂM THANH]
Đă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.