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ả.
[SIDE CONVERSATIONS] PROFESSOR: All right, let's get started.
[NÓI CHUYỆN RIÊNG] GIÁO SƯ: Được rồi, chúng ta bắt đầu nhé.
Welcome to the third lecture of 188. Today's topic is Informed Search. Couple of announcements first.
Chào mừng các bạn đến bài giảng thứ ba của môn 188. Chủ đề hôm nay là Tìm kiếm có thông tin (Informed Search). Trước hết là vài thông báo.
Homework One Search has been released. It's due on Tuesday. But keep in mind that typically homework will be due on Mondays.
Bài tập về nhà số Một, Search, đã được đăng. Hạn nộp là thứ Ba. Nhưng lưu ý là thông thường bài tập về nhà sẽ có hạn nộp vào thứ Hai.
So don't fall into the pattern of thinking it's going to be due on Tuesdays. It's pretty much always going to be Mondays. But because of Labor Day, it's on Tuesday next week.
Nên đừng nghĩ theo thói quen rằng hạn nộp sẽ là thứ Ba. Hầu như lúc nào cũng là thứ Hai. Nhưng vì có ngày Lễ Lao động nên tuần sau là thứ Ba.
There's two components, electronic and written. You should do both. It's not a choice, one or the other, both are for you to do. Electronic is on Gradescope.
Có hai phần: phần điện tử và phần viết. Các bạn nên làm cả hai. Không phải chọn một trong hai, mà làm cả hai. Phần điện tử nằm trên Gradescope.
You solve things. And you can try as many times as you like until we get it right and until the deadline hits. The written component is an exam style two-pager.
Các bạn giải bài. Và có thể thử bao nhiêu lần tùy thích cho đến khi đúng hoặc đến khi hết hạn. Phần viết là hai trang theo kiểu đề thi.
We highly recommend you print it out, try to work it on your own.
Chúng tôi rất khuyên các bạn in ra, tự làm một mình trước.
And then after you've done that for let's say, half an hour, or an hour on your own, feel free to discuss with other students and so forth to try to get a better understanding.
Sau khi đã tự làm khoảng nửa tiếng hoặc một tiếng, các bạn cứ thoải mái thảo luận với các bạn khác và vân vân để hiểu rõ hơn.
But then still, you have to submit your own work not some other students' work of course.
Nhưng bạn vẫn phải nộp bài của chính mình, tất nhiên không phải bài của bạn khác.
These will be graded on effort/completion, which means that we will check if you — it looks like you tried as hard as you would try on an exam to solve these problems.
Bài sẽ được chấm theo nỗ lực/mức hoàn thành, nghĩa là chúng tôi sẽ kiểm tra xem bạn có cố gắng giải như khi làm bài thi hay không. Ý nghĩa là như vậy.
That's what it means. And the next week, you'll get to make corrections to anything you got wrong by grading it yourself.
Ý nghĩa là như vậy. Tuần sau, các bạn sẽ tự chấm và sửa lại những chỗ mình làm sai.
And again, grading yourself will be graded on whether you did it precisely, not on whatever grades you would have given yourself. Project One Search has been released.
Và việc tự chấm cũng sẽ được chấm xem bạn có làm chính xác hay không, chứ không dựa vào điểm bạn tự cho mình. Project Một, Search, đã được đăng.
It's due next week, Friday at 4 PM. You might wonder why 4 PM. It seems pretty arbitrary. We picked PM because a good fraction of students like to work last minute.
Hạn nộp là thứ Sáu tuần sau, lúc 4 giờ chiều. Có thể các bạn thắc mắc sao lại là 4 giờ chiều. Nghe có vẻ khá tùy tiện. Chúng tôi chọn giờ chiều vì khá nhiều sinh viên thích làm sát giờ.
And if we pick 4 PM, then — I mean we don't recommend working last minute, but if we pick 4 PM, the students who do work until the last minute still have a Friday evening free for doing something else and weekend.
Và nếu chọn 4 giờ chiều thì, tôi không khuyến khích làm sát giờ đâu, nhưng nếu chọn 4 giờ chiều, những bạn làm đến phút cuối vẫn còn tối thứ Sáu rảnh để làm việc khác, và cả cuối tuần nữa.
So that's our rationale here to try to help you have Friday evening free.
Đó là lý do của chúng tôi, để các bạn có tối thứ Sáu rảnh.
One important thing is that Project One is representative of the projects we'll have throughout the remainder of the course. Project Zero is not.
Một điều quan trọng là Project Một mang tính đại diện cho các project trong phần còn lại của môn học. Project Không thì không.
So if you thought Project Zero is easy, you got it done very quickly, Project One is different, and it's representative of everything that follows.
Nên nếu bạn thấy Project Không dễ, làm xong rất nhanh, thì Project Một khác đấy, và nó đại diện cho tất cả những project sau.
If you're worried about your coding skills, your coding background, Project One will tell you how ready you are. The entire teaching staff is there to help you if you have questions.
Nếu bạn lo về kỹ năng lập trình, nền tảng lập trình của mình, Project Một sẽ cho bạn biết mình sẵn sàng đến đâu. Toàn bộ đội ngũ giảng dạy luôn sẵn sàng giúp các bạn nếu có thắc mắc.
Post on Piazza, come to office hours. We want you to solve these problems. You can work in a team of two. We recommend that you pair code, or in some other way work together.
Hãy đăng lên Piazza, đến giờ tiếp sinh viên. Chúng tôi muốn các bạn giải được các bài này. Các bạn có thể làm theo nhóm hai người. Chúng tôi khuyên nên lập trình cặp, hoặc bằng cách nào đó cùng làm việc với nhau.
We don't recommend you just split the work. Because you'll only learn half of the material that way.
Không khuyến khích chỉ chia đôi công việc. Vì như vậy bạn chỉ học được một nửa kiến thức.
When you submit into Gradescope, one person submits and has to mark the other student their partner, if you work with a partner to make sure that they get a grade too.
Khi nộp lên Gradescope, một người nộp và phải đánh dấu người kia là bạn cùng nhóm, nếu bạn làm với một bạn khác, để bảo đảm bạn ấy cũng có điểm.
So don't forget to mark your partner if you had one or they will not get that grade.
Nên đừng quên đánh dấu bạn cùng nhóm nếu có, nếu không bạn ấy sẽ không có điểm.
Section started this week, as I mentioned before, you can go to any BF priority and the one you signed up for on Piazza. Any questions about logistics? Yes?
Buổi section đã bắt đầu từ tuần này, như tôi đã nói trước đây, các bạn có thể đến bất kỳ buổi nào, ưu tiên buổi mình đã đăng ký trên Piazza. Có câu hỏi nào về các vấn đề hậu cần không? Bạn nào?
There's only — so there's only one type of discussion per week. There isn't many, many that are meant to be the same.
Mỗi tuần chỉ có một loại buổi thảo luận. Không có nhiều buổi khác nhau, chúng giống nhau.
But they're at different times and different GSI's so there will always be a little bit of variation in exactly how each GSI will do things.
Nhưng giờ khác nhau và GSI khác nhau nên sẽ luôn có chút khác biệt về cách mỗi GSI làm.
And also on Fridays, we will try to record a webcast of the material covered in the section that week. So you'll also have a webcast coverage of whatever was that week's section.
Và vào các thứ Sáu, chúng tôi sẽ cố gắng ghi lại một webcast về nội dung đã học trong buổi section của tuần đó. Vậy các bạn cũng sẽ có webcast về buổi section của tuần đó.
Any other questions about logistics?
Còn câu hỏi nào khác về hậu cần không?
Over there.
Bạn ở đằng kia.
STUDENT
Can homework be submitted as a picture [? or letter? ?]
Em có thể nộp bài tập bằng ảnh chụp [? hoặc thư? ?] được không ạ?
PROFESSOR
So for homework, we want you to submit something that matches the template that we have. If you want to relay ticket, that's fine.
Với bài tập về nhà, chúng tôi muốn các bạn nộp bài khớp với mẫu mà chúng tôi có. Nếu bạn muốn gõ lại thì cũng được.
But we want it to match up with a template that we have. Because that's important for our grading. We recommend you print it out and write on it.
Nhưng phải khớp với mẫu của chúng tôi. Vì điều đó quan trọng cho việc chấm bài. Chúng tôi khuyên bạn in ra và viết lên đó.
Because that's most similar to exams. But ultimately if you prefer to type it up, that's fine too. But follow the template structure that is in our PDF. Other questions about logistics?
Vì như vậy giống với bài thi nhất. Nhưng nếu bạn thích gõ thì cũng được. Nhưng hãy theo cấu trúc mẫu trong file PDF của chúng tôi. Còn câu hỏi nào khác về hậu cần không?
OK. Today's topic is Informed Search.
Được rồi. Chủ đề hôm nay là Tìm kiếm có thông tin.
What that means, we're going to cover something called the heuristics, Greedy Search, A Star Search and then we'll see something called Graph Search, which will be an improvement to the Tree Search we've already seen towards the end of lecture.
Nghĩa là chúng ta sẽ học về hàm heuristic, Greedy Search, A Star Search, rồi sau đó sẽ thấy một thứ gọi là Graph Search, là bản cải tiến của Tree Search mà chúng ta đã học, vào cuối bài giảng.
Let's first recap what is search. Well, in Search, what we're typically interested in is somehow capturing something about the real world inside a computer.
Trước hết nhắc lại tìm kiếm là gì. Trong tìm kiếm, điều chúng ta thường quan tâm là bằng cách nào đó nắm bắt một phần của thế giới thực bên trong máy tính.
So, and the way we'll do that is by defining a search problem.
Và cách làm là định nghĩa một bài toán tìm kiếm.
The search problem is defined by a set of states, which corresponds to the configurations of the world, not necessarily all details of the configurations of the world, but the abstraction of the world that is relevant for the agent's decision making.
Một bài toán tìm kiếm được định nghĩa bởi một tập các trạng thái, tương ứng với các cấu hình của thế giới, không nhất thiết là mọi chi tiết của cấu hình của thế giới, mà là phần trừu tượng hóa của thế giới có liên quan đến việc ra quyết định của tác tử.
There are actions that can be taken. And there are typically costs associated with those actions.
Có các hành động có thể thực hiện. Và thường có chi phí gắn với các hành động đó.
There is a successor function, which defines for each state and each action that's available in that state, where you would end up, and also the cost associated with it.
Có một hàm kế tiếp, nó xác định với mỗi trạng thái và mỗi hành động khả dụng ở trạng thái đó, bạn sẽ đến trạng thái nào, và cả chi phí đi kèm.
So that's modeling how the world works, again, at some level of abstraction that you choose as right for your problem. And then there's a start state. That's where the agent starts.
Vậy đó là mô hình hóa cách thế giới vận hành, ở một mức trừu tượng hóa nào đó mà bạn chọn là phù hợp cho bài toán của mình. Rồi có một trạng thái bắt đầu. Đó là nơi tác tử xuất phát.
And there is a gold test, which allows you to check if a current state that you feed into that test satisfies the goal condition or not.
Và có một phép kiểm tra đích, cho phép bạn kiểm tra xem trạng thái hiện tại đưa vào phép kiểm tra đó có thỏa điều kiện đích hay không.
If it does, it's a goal state and you can declare success if you get there. That's the problem structure.
Nếu có, đó là trạng thái đích và bạn có thể tuyên bố thành công khi đến được đó. Đó là cấu trúc của bài toán.
The computation we tend to do is building up a search tree, not fully, but partially hopefully. The nodes in a search area correspond to paths to states.
Phép tính ta thường làm là xây dựng một cây tìm kiếm, không phải toàn bộ, hy vọng chỉ một phần. Các nút trong cây tìm kiếm tương ứng với các đường đi đến trạng thái.
We'll see some examples again soon. And these paths or plans have costs associated with them, which is the sum of all the costs of all the actions you took along that path.
Chúng ta sẽ sớm xem lại vài ví dụ. Và các đường đi hay kế hoạch này có chi phí đi kèm, là tổng chi phí của mọi hành động bạn đã thực hiện dọc đường đi đó.
A search algorithm is an algorithm that systematically builds out the search tree, hopefully only a fraction of the entire search tree, but maybe worst case the entire search tree.
Một thuật toán tìm kiếm là thuật toán xây dựng cây tìm kiếm một cách có hệ thống, hy vọng chỉ một phần nhỏ của toàn bộ cây tìm kiếm, nhưng trường hợp xấu nhất là toàn bộ cây.
And it has to choose an ordering of what to currently expand. This is what is — ready to be expanded is called the fringe. But you have to choose which one to expand first.
Và nó phải chọn thứ tự mở rộng các nút hiện có. Cái này là — những nút sẵn sàng để mở rộng gọi là biên (fringe). Nhưng bạn phải chọn mở rộng nút nào trước.
Then a optimal search algorithm is one that finds least cost plans. So not all search is about pathing. So we'll use a slightly different example here. Pancake flipping.
Một thuật toán tìm kiếm tối ưu là thuật toán tìm ra kế hoạch có chi phí thấp nhất. Không phải bài toán tìm kiếm nào cũng là tìm đường. Nên ở đây ta dùng một ví dụ hơi khác. Lật bánh pancake.
What is the setup here? This is a setup where there is four pancakes. They have different sizes.
Thiết lập ở đây là gì? Đây là thiết lập có bốn cái bánh pancake. Chúng có kích thước khác nhau.
And the goal is to get the pancakes stacked with the biggest one at the bottom, second biggest one on top of that, and so forth, smallest one at the top.
Và mục tiêu là xếp chồng các bánh với cái to nhất ở dưới cùng, cái to thứ hai nằm trên nó, và cứ thế, cái nhỏ nhất ở trên cùng.
Your action space is you can put your spatula between two pancakes or underneath the bottom one and then decide to flip everything that's above your spatula.
Không gian hành động là bạn đặt cái xẻng giữa hai cái bánh hoặc dưới cái dưới cùng rồi quyết định lật mọi thứ nằm phía trên cái xẻng.
For example, if the spatula goes right there where it's shown, it would flip the top two and the bottom two would stay in place.
Ví dụ, nếu xẻng đặt đúng chỗ như hình, nó sẽ lật hai cái trên và hai cái dưới giữ nguyên vị trí.
So for a stack of four pancakes here, you effectively have three actions available to you. You can go between number 2 and number 3, between number 3 and number 4, or below number 4.
Vậy với chồng bốn cái bánh này, thực chất bạn có ba hành động khả dụng. Bạn có thể xen giữa cái số 2 và số 3, giữa số 3 và số 4, hoặc dưới số 4.
Going between 1 and 2 doesn't do anything for you. Because you're just keeping the top one on top. So that's the successor states from this particular state.
Xen giữa 1 và 2 thì chẳng có tác dụng gì. Vì bạn chỉ giữ cái trên cùng ở nguyên trên cùng. Đó là các trạng thái kế tiếp từ trạng thái cụ thể này.
You might wonder who might care about pancakes? Well, the cost will be the number of pancakes as well. Pancake flipping robots is one type of species that cares a lot about this.
Bạn có thể thắc mắc ai quan tâm đến bánh pancake? Chi phí cũng sẽ là số bánh được lật. Robot lật bánh pancake là một loại rất quan tâm đến chuyện này.
But there are actually other people who cared about this. And people you, unless you looked at the slides ahead of time, definitely wouldn't guess.
Nhưng thực ra còn có những người khác cũng quan tâm. Và những người mà, nếu không xem slide trước, chắc chắn bạn sẽ không đoán ra.
Bill Gates and Christos Papadimitriou wrote a paper this past Tuesday exactly 40 years ago about pancake flipping as an abstraction for sorting things.
Bill Gates và Christos Papadimitriou đã viết một bài báo vào thứ Ba tuần trước, đúng 40 năm trước, về lật bánh pancake như một sự trừu tượng hóa của việc sắp xếp.
So now back to the problem. Here is the state space graph, well, part of the state space graph. There is more states.
Giờ quay lại bài toán. Đây là đồ thị không gian trạng thái, à, một phần của đồ thị không gian trạng thái. Còn nhiều trạng thái nữa.
How many states are there, you think in the state space total if we drew the entire graph? Any thoughts?
Theo bạn có tổng cộng bao nhiêu trạng thái trong không gian trạng thái nếu ta vẽ toàn bộ đồ thị? Có ý kiến nào không?
anyone? Over there. Did you say 24? 24?
có ai không? Bạn đằng kia. Bạn nói 24 phải không? 24?
OK, how do you get to that?
Được, bạn tính ra nó thế nào?
STUDENT
Oh, [INAUDIBLE] anywhere and then the [INAUDIBLE].
À, [KHÔNG NGHE RÕ] ở bất kỳ đâu rồi [KHÔNG NGHE RÕ].
PROFESSOR
Exactly. So let me say that again just because of the acoustics. It may be hard for people behind you to hear you. The answer was 24 total.
Chính xác. Để tôi nhắc lại vì âm thanh trong phòng. Có thể các bạn phía sau khó nghe được bạn. Câu trả lời là tổng cộng 24.
So you can see, we're not showing them all on this slide. And how do we get to that? Well, you first have four choices as to what goes at the bottom.
Như bạn thấy, trên slide này ta không hiển thị hết. Và làm sao ra được con số đó? Đầu tiên bạn có bốn lựa chọn cho cái nằm dưới cùng.
Then you have three choices left for what goes on top of that. Two choices left what goes on top of that.
Rồi còn ba lựa chọn cho cái nằm trên nó. Còn hai lựa chọn cho cái nằm trên nữa.
And then one choice left before it goes in the top and that multiplication is 24. So part of the state space graph, the costs here correspond to how many pancakes you're flipping.
Rồi còn một lựa chọn trước khi nó lên trên cùng và phép nhân đó bằng 24. Đây là một phần của đồ thị không gian trạng thái, chi phí ở đây tương ứng với số bánh bạn lật.
And we can imagine that maybe the robot has some energy costs depending on how many pancakes it has to lift and expends energy.
Ta có thể hình dung robot tốn năng lượng tùy theo số bánh nó phải nhấc lên.
And it prefers to lift us as few as possible and get to a goal. And the goal is to get into this configuration here where they're nicely lined up.
Và nó muốn nhấc càng ít càng tốt để đến đích. Và mục tiêu là đạt được cấu hình này, khi các bánh xếp gọn gàng.
So not all Search is padding. It could be pancake flipping. And there will be other examples in the future. How does Tree Search work.
Vậy không phải tìm kiếm nào cũng là tìm đường. Nó có thể là lật bánh pancake. Và sau này sẽ còn các ví dụ khác. Tree Search hoạt động thế nào?
I've illustrated with that pancake flipping problem. Tree Search goes through a loop. It initializes before going into the loop with putting on the fringe the start state, the current situation in the world.
Tôi đã minh họa bằng bài toán lật bánh pancake. Tree Search chạy qua một vòng lặp. Trước khi vào vòng lặp, nó khởi tạo bằng cách đặt vào biên trạng thái bắt đầu, tức tình huống hiện tại của thế giới.
Then it checks. Are there any candidates for expansion? That is, is there anything on the fringe? And the answer is yes.
Rồi nó kiểm tra. Có ứng viên nào để mở rộng không? Tức là, có gì trong biên không? Và câu trả lời là có.
This is our fringe. Then it decides to expand that. Well, it'll first check if it's the goal. If it's not the goal, then it will decide to expand it.
Đây là biên của chúng ta. Rồi nó quyết định mở rộng nút đó. Trước tiên nó sẽ kiểm tra xem đó có phải đích không. Nếu không phải đích, nó sẽ quyết định mở rộng nút đó.
This will be our new fringe. And then it'll go back around. It'll check is there anything left on the fringe? The answer is yes.
Đây sẽ là biên mới của chúng ta. Rồi nó quay lại vòng lặp. Nó kiểm tra xem trên biên còn gì không? Câu trả lời là có.
Then pick something with some strategy, one of those three. Then it will check, does it achieve the goal condition? The answer will be no. It will then expand and this process repeats.
Rồi chọn một nút theo một chiến lược nào đó, một trong ba nút này. Sau đó nó kiểm tra: nút này có thỏa điều kiện đích không? Câu trả lời sẽ là không. Nó sẽ mở rộng nút và quá trình này lặp lại.
And then at some point, we might expand this one over here and declare success.
Và đến một lúc nào đó, ta có thể mở rộng nút ở đây và tuyên bố thành công.
This algorithm is underneath all the search arguments we've seen so far, Depth-first, Breadth-first, uniform cost. Today we'll see Greedy and A star. They will still use this.
Thuật toán này nằm bên dưới tất cả các thuật toán tìm kiếm mà ta đã thấy: Depth-first, Breadth-first, uniform cost. Hôm nay ta sẽ học Greedy và A star. Chúng vẫn dùng khung này.
The only difference is the choice of strategy used to expand things from the fringe.
Khác biệt duy nhất là cách chọn chiến lược để mở rộng các nút từ biên.
And at the end of lecture, we'll see a modification to this called Graph Search where we'll put in one extra check here. But otherwise, it will be the same.
Và cuối bài, ta sẽ thấy một cải tiến gọi là Graph Search, trong đó ta thêm một bước kiểm tra ở đây. Ngoài ra thì mọi thứ giống nhau.
And we'll also apply it to all the other — all the strategies that we've seen.
Và ta cũng sẽ áp dụng nó cho tất cả các chiến lược đã thấy.
So in this case, the total cost would be 7 to achieve the goal state if this is how you got there.
Vậy trong trường hợp này, tổng chi phí để đến trạng thái đích sẽ là 7 nếu đi theo đường này.
The way you can implement this, no matter what the strategy is you can implement this with a priority queue. Your fringe is stored as a priority queue.
Về cách cài đặt, dù chiến lược là gì, bạn đều có thể cài đặt bằng hàng đợi ưu tiên. Biên được lưu dưới dạng hàng đợi ưu tiên.
When you pick something from priority queue, your strategy determines what the priorities are. And you pick based on whoever is highest priority.
Khi chọn một nút từ hàng đợi ưu tiên, chiến lược của bạn quyết định các mức ưu tiên. Và bạn chọn nút có ưu tiên cao nhất.
Now if you specifically are interested in Depth-first search, you could also use a stack instead of a priority queue.
Còn nếu bạn chỉ quan tâm đến Depth-first search, bạn cũng có thể dùng ngăn xếp thay cho hàng đợi ưu tiên.
If you're specifically interested in Breadth-first search, you could also use a regular queue instead of a priority queue, which will make it slightly more efficient but will make your implementation less unified.
Nếu bạn chỉ quan tâm đến Breadth-first search, bạn có thể dùng hàng đợi thông thường thay cho hàng đợi ưu tiên, như vậy sẽ hiệu quả hơn một chút nhưng cài đặt sẽ kém thống nhất hơn.
For project purposes either way is fine. You can choose whether you want to do it in a unified way or have slightly special purpose versions for Depth-first, then Breadth-first.
Với project thì cách nào cũng được. Bạn có thể chọn làm theo cách thống nhất hoặc viết các phiên bản chuyên biệt cho Depth-first, rồi Breadth-first.
So last lecture what we covered was Uninformed Search.
Bài trước ta đã học về Uninformed Search.
And what that meant, let's say, it was Uniform Cost Search but the strategy correspondent to expand the lowest path cost from what's currently on the fringe.
Ví dụ, Uniform Cost Search có chiến lược là mở rộng nút có chi phí đường đi thấp nhất trong số các nút hiện có trên biên.
The good news, it's complete and optimal, which means if a solution exists, it will find it. And it will actually find the optimal solution meaning the way to achieve the goal at lowest cost.
Tin tốt: nó đầy đủ và tối ưu, nghĩa là nếu có lời giải, nó sẽ tìm ra. Và nó sẽ tìm ra lời giải tối ưu, tức là cách đến đích với chi phí thấp nhất.
The bad news, it searches in every direction equally hard. For example, in this 2D space over here, it would expand in all directions at equal pace, even though the goal is on this side.
Tin xấu: nó tìm kiếm đều nhau theo mọi hướng. Ví dụ, trong không gian 2D này, nó sẽ mở rộng theo mọi hướng với tốc độ như nhau, dù đích nằm ở phía này.
It doesn't have any information about the goal. All it does with the goal is every now and then check, do I satisfy the goal condition?
Nó không có thông tin gì về đích. Với đích, nó chỉ thỉnh thoảng kiểm tra: mình có thỏa điều kiện đích không?
But nothing else about the goal is used, so it doesn't know that it's going in the right or wrong direction.
Ngoài ra không dùng gì khác về đích, nên nó không biết mình đang đi đúng hay sai hướng.
So pictorially what this corresponds to is, let's say we run uniform cost search on a empty grid.
Minh họa trực quan là thế này: giả sử ta chạy uniform cost search trên một lưới trống.
Then it would look — and so the way we visualize this whenever a state gets expanded for the first time, we show it highlighted here, uniform cost would just equally radiate out in all directions and then finally finds the goal.
Khi đó nó sẽ trông như thế này... Cách ta trực quan hóa là mỗi khi một trạng thái được mở rộng lần đầu, ta tô sáng nó ở đây. Uniform cost sẽ lan đều ra mọi hướng rồi cuối cùng mới tìm thấy đích.
And then if we have a — if we have a maze that runs so fast that we didn't see it in action.
Và nếu ta có một... mê cung mà chạy nhanh đến mức ta không kịp thấy nó diễn ra.
So what happened here is uniform cost search was run. And it highlighted in red nodes that are expanded during uniform cost search. You are bright red if you're expanded early on.
Ở đây, uniform cost search đã được chạy. Các nút được mở rộng được tô đỏ trong quá trình uniform cost search. Mở rộng sớm thì màu đỏ sáng.
You're darker red if you're expanded later on. So the last one expanded would be around here where — does that cursor show up over there? Let's see, yeah.
Mở rộng muộn hơn thì đỏ sẫm hơn. Nút mở rộng cuối cùng sẽ ở quanh đây... con trỏ có hiện ra ở đó không? Để xem, có.
So it would be around here. That's the goal state. That's the last one expanded and declare success.
Vậy nó ở quanh đây. Đó là trạng thái đích. Đó là nút cuối cùng được mở rộng và tuyên bố thành công.
But what you see here in this maze is that it actually expanded every single reachable state, except for just one of them over here. Why did it do that?
Nhưng điều bạn thấy trong mê cung này là nó đã mở rộng gần như mọi trạng thái có thể đến được, trừ đúng một trạng thái ở đây. Tại sao lại thế?
Well, Uniform Cost Search doesn't know where the goal's going to be since they uniformly explore in all directions.
Uniform Cost Search không biết đích ở đâu, vì nó khám phá đều theo mọi hướng.
And if you want to know, will it have expanded the state or not, and you want to quickly guess that for a maze like this, you would say, OK, let me eyeball what's the shortest path to the goal.
Nếu muốn biết một trạng thái có bị mở rộng hay không, và muốn đoán nhanh với mê cung thế này, bạn chỉ cần ước lượng bằng mắt đường ngắn nhất tới đích.
I find the shortest path to the goal from Pac-Man to the go. I measure the length.
Tìm đường ngắn nhất từ Pac-Man đến đích. Đo độ dài của nó.
And I know that Uniform Cost Search will expand every state that is at less than that distance from the start, which in this case means every state except for this loner over here, which is actually further away from the start than the goal.
Và bạn biết Uniform Cost Search sẽ mở rộng mọi trạng thái cách điểm xuất phát ít hơn khoảng cách đó, trong trường hợp này là mọi trạng thái trừ cái đứng lẻ loi ở đây, vì nó thật ra xa điểm xuất phát hơn cả đích.
But everything else gets expanded.
Còn mọi thứ khác đều bị mở rộng.
So we're hoping to make that more efficient today.
Hôm nay ta hy vọng làm cho việc này hiệu quả hơn.
The way we're going to make it more efficient is by infusing information about where the goal is while the search algorithm is running. These are called heuristics.
Cách để làm hiệu quả hơn là đưa thông tin về vị trí của đích vào trong lúc thuật toán tìm kiếm đang chạy. Đó gọi là các hàm heuristic.
Heuristics is a function that estimates how close the state is to a goal. And it will be designed for a particular search problem.
Hàm heuristic là hàm ước lượng một trạng thái gần đích đến mức nào. Và nó được thiết kế cho một bài toán tìm kiếm cụ thể.
Everything we've seen so far, you build a search problem abstraction and you can run your algorithm. If you want a heuristic, we have to take one additional step.
Với mọi thứ đã thấy từ đầu đến giờ, bạn xây dựng một trừu tượng hóa bài toán tìm kiếm rồi chạy thuật toán của mình. Nếu muốn có hàm heuristic, ta phải làm thêm một bước.
We have to come up with a heuristic function for the current problem we're trying to solve. So we'll build the heuristic function.
Ta phải nghĩ ra một hàm heuristic cho bài toán hiện tại mà ta đang cố giải. Vậy ta sẽ xây dựng hàm heuristic.
There are some different choices that you can make for these heuristic functions. So we'll dive into that a little bit today.
Bạn có thể đưa ra nhiều lựa chọn khác nhau cho các hàm heuristic này. Hôm nay ta sẽ đi sâu một chút vào chuyện đó.
So for example for Pac-Man needing to find the one pallet here in this maze, what could be a reasonable heuristic function? A reasonable way of measuring how close am I to the goal?
Ví dụ, với Pac-Man cần tìm một viên thức ăn duy nhất trong mê cung này, hàm heuristic hợp lý có thể là gì? Một cách hợp lý để đo mình còn cách đích bao xa?
Any thoughts? Over there.
Có ý kiến nào không? Bạn ở đằng kia.
STUDENT
Is it Manhattan distance?
Có phải khoảng cách Manhattan không ạ?
PROFESSOR
So the suggestion was, Manhattan distance. Why would that make sense? Well, you can only move North, East, South, West, so your motion is always along that grid pattern.
Ý kiến là khoảng cách Manhattan. Tại sao nó hợp lý? Vì bạn chỉ có thể đi Bắc, Đông, Nam, Tây, nên chuyển động luôn theo dạng lưới.
And so Manhattan distance is, well, in this case, Manhattan distance, of course, measures the distance that to achieve that path to the goal, you'd have to go through walls.
Và khoảng cách Manhattan thì, trong trường hợp này, tất nhiên, nó đo quãng đường mà để đi tới đích, bạn sẽ phải xuyên qua tường.
But it gives you an estimate. And that's what heuristics are about. It's way of quickly getting an estimate of how far away the goal might be. And Manhattan distance is quick to compute.
Nhưng nó cho ta một ước lượng. Và heuristic chính là như vậy. Đó là cách nhanh chóng ước lượng đích có thể cách bao xa. Khoảng cách Manhattan tính rất nhanh.
And it's very much tied into how you move in this space, except that it ignores the walls. You can also use Euclidean distance. So there's Manhattan distance, Euclidean distance would look like this.
Và nó gắn chặt với cách bạn di chuyển trong không gian này, chỉ trừ việc nó bỏ qua các bức tường. Bạn cũng có thể dùng khoảng cách Euclid. Ngoài khoảng cách Manhattan, khoảng cách Euclid sẽ trông như thế này.
It's probably not as good a fit for this problem. Because Pac-Man cannot move diagonally. And so it doesn't measure as well how far away you are from the goal.
Có lẽ nó không phù hợp bằng với bài toán này. Vì Pac-Man không thể đi chéo. Nên nó đo không tốt bằng việc bạn cách đích bao xa.
How about for this pathing problem we saw last time, finding a path in Romania from Iran to Bucharest? Well, again heuristic is something you want to be able to compute easily.
Còn với bài toán tìm đường mà ta thấy lần trước, tìm đường ở Romania từ Iran đến Bucharest thì sao? Một lần nữa, heuristic là thứ bạn muốn tính toán dễ dàng.
And it gives us a guess of how close we are to the goal. So straight line distance could be something. Because all we need for that is the GPS coordinates of each city.
Và nó cho ta phỏng đoán mình gần đích đến đâu. Vậy khoảng cách đường thẳng có thể dùng được. Vì ta chỉ cần tọa độ GPS của mỗi thành phố.
From that we can compute the straight line distance to other cities. And that's a good measure of how far we are away.
Từ đó ta tính được khoảng cách đường thẳng đến các thành phố khác. Và đó là thước đo tốt cho việc ta còn cách bao xa.
If we want to go to Bucharest, then it would be all straight line distances to Bucharest. And this would be our heuristic function.
Nếu muốn đến Bucharest, thì đó sẽ là mọi khoảng cách đường thẳng đến Bucharest. Và đây sẽ là hàm heuristic của ta.
And this is in a tabular format what it could look like.
Đây là dạng bảng của nó.
Like heuristic function, if there's only a finite set of states assigns a number to each state, which is how far you think that state is or how much cost do you think you'll still incur from that state to get to the goal.
Hàm heuristic, nếu chỉ có một tập hữu hạn trạng thái, gán một số cho mỗi trạng thái, là bạn nghĩ trạng thái đó còn xa bao nhiêu hay bạn nghĩ mình vẫn sẽ phải chịu bao nhiêu chi phí từ trạng thái đó để tới đích.
How about for pancake flipping ? Any thoughts on heuristics for that?
Còn bài toán lật bánh kếp thì sao? Có ý kiến nào về heuristic cho bài này không?
Here.
Bạn ở đây.
STUDENT
Make a number of pancakes that aren't in correct position.
Đếm số bánh không ở đúng vị trí.
PROFESSOR
So this the suggestion was the number of pancakes not in the correct position.
Ý kiến là số bánh không ở đúng vị trí.
And the reason that could be a good heuristic is because every pancake not in the correct position has to be flipped at some point, at least once.
Lý do đó có thể là heuristic tốt là vì mỗi cái bánh không đúng vị trí đều phải được lật ít nhất một lần.
And whenever you do an action, the cost is the number of pancakes flipped.
Và mỗi khi thực hiện một hành động, chi phí là số bánh được lật.
So number of pancakes out of place is definitely an estimate of how much cost you're going to encounter before you can get everything in place. So that's one choice.
Nên số bánh sai vị trí chắc chắn là ước lượng cho chi phí bạn sẽ gặp trước khi đặt được mọi thứ vào đúng chỗ. Đó là một lựa chọn.
Number of pancakes out of place. Any other thoughts on other heuristics? This has to be an art. For many problems there is many, many heuristic you can come up with.
Số bánh sai vị trí. Còn heuristic nào khác không? Việc này đúng là một nghệ thuật. Với nhiều bài toán, có rất nhiều heuristic bạn có thể nghĩ ra.
STUDENT
Longest chain of correct, like ordered pancakes.
Chuỗi bánh dài nhất được sắp đúng thứ tự.
PROFESSOR
Say it again.
Bạn nói lại đi.
STUDENT
Longest chain of correctly ordered pancakes.
Chuỗi bánh dài nhất được sắp đúng thứ tự.
PROFESSOR
Longest chain of correctly ordered pancakes. And so can you say a little more about how that measures, how far we are away from achieving the goal?
Chuỗi bánh dài nhất được sắp đúng thứ tự. Bạn nói rõ hơn một chút được không, nó đo việc ta còn cách đích bao xa như thế nào?
STUDENT
So if you have 1, 2, 3 together, that would be like four 3's. But if you have 1, 3, 5 that gets 0. So your final case would be 1,2, 3, 4.
Nếu có 1, 2, 3 nằm cạnh nhau, thì tính như ba số 3. Nhưng nếu là 1, 3, 5 thì được 0. Trạng thái cuối sẽ là 1, 2, 3, 4.
PROFESSOR
Mm-hm.
Ừ.
STUDENT
So if you have 1 — like 2, 3, 4 somewhere in there, but not closer to the [INAUDIBLE]..
Nếu có 1, hay 2, 3, 4 ở đâu đó trong đó, nhưng không gần [KHÔNG NGHE RÕ]...
PROFESSOR
So the idea here is that you look at a essentially subset of the pancakes and see how many are already in the right order.
Ý tưởng ở đây là bạn xét một tập con các cái bánh và xem có bao nhiêu cái đã đúng thứ tự.
Because that means they are ready for whatever we need to achieve at the end. Now one subtlety here is that usually we measure heuristics measured in a similar unit as cost.
Vì điều đó nghĩa là chúng đã sẵn sàng cho thứ ta cần đạt được ở cuối. Có một điểm tinh tế là thường thì ta đo heuristic theo đơn vị tương tự chi phí.
So instead of measuring how many are already ordered nicely, which in case of the goal state would be all four. When we're at the goal state, we want the heuristic to be 0.
Nên thay vì đo bao nhiêu cái đã được sắp đẹp, mà ở trạng thái đích sẽ là cả bốn. Khi ở trạng thái đích, ta muốn heuristic bằng 0.
So we want to do maybe something like 4 minus the function that you proposed to make sure that it measures distance from the goal, not higher when closer to the goal.
Nên có lẽ ta làm kiểu 4 trừ đi hàm bạn đề xuất, để chắc rằng nó đo khoảng cách tới đích, chứ không phải càng gần đích càng cao.
But it's a good suggestion with that small caveat. Any other thoughts?
Nhưng đó là gợi ý tốt, với lưu ý nhỏ đó. Còn ý kiến nào khác không?
Here's another one, one that we put on the slides is the number that is the ID number of the largest pancake that is still out of place. How does that work?
Đây là một cái khác, cái mà ta để trên slide: số ID của cái bánh lớn nhất vẫn còn sai vị trí. Nó hoạt động thế nào?
Well, which is the largest pancake still out of place here, it's the one at the top there. It's pancake number three. So then this heuristic would say 3.
Cái bánh lớn nhất còn sai vị trí ở đây là cái trên cùng này. Đó là bánh số ba. Vậy heuristic này sẽ cho 3.
Why does that make sense? Well, that pancake is still out of place. That means that everything 3 up still needs to undergo some flipping operation in the stack.
Tại sao nó hợp lý? Vì cái bánh đó vẫn còn sai vị trí. Nghĩa là mọi thứ từ 3 trở lên vẫn cần trải qua một thao tác lật nào đó trong chồng bánh.
Otherwise there's no way to get this one in place. It measures something about how deep you'll need to go into the stack for some operation before you could ever complete.
Nếu không thì không cách nào đặt cái này vào đúng chỗ. Nó đo phần nào việc bạn sẽ cần đi sâu bao nhiêu vào chồng bánh cho một thao tác trước khi có thể hoàn thành.
So this what we're showing here. Later we'll also look at what might make one heuristic better than another heuristic. And, of course, a lot of it has to do with accuracy.
Đây là điều ta đang minh họa ở đây. Sau này ta cũng sẽ xem điều gì khiến một hàm heuristic tốt hơn so với một hàm heuristic khác. Và tất nhiên, phần lớn liên quan đến độ chính xác.
And so in this case, let's compare the one that's on the slide with the one that was proposed earlier about how many pancakes still out of place. So we'll look at this one here.
Vậy trong trường hợp này, hãy so sánh hàm trên slide với hàm đã được đề xuất lúc trước, là đếm số bánh pancake vẫn còn sai vị trí. Ta xem hàm này.
How many pancakes still out of place? That is 2.
Còn bao nhiêu bánh pancake sai vị trí? Là 2.
So what we see is that these are different numbers. And that's going to happen often with different heuristics. One of them may be more precise than the other one.
Vậy ta thấy hai con số này khác nhau. Và điều đó thường xảy ra với các hàm heuristic khác nhau. Một hàm có thể chính xác hơn hàm kia.
Because actually there is an action here that takes you straight to the goal state. And it has a cost of 3. And so this heuristic here is more precise than this one.
Vì thực ra ở đây có một hành động đưa bạn thẳng tới trạng thái đích. Và nó có chi phí là 3. Nên hàm heuristic này chính xác hơn hàm kia.
Now there are other trade-offs in heuristics at times related to not just precision but also speed of finding your heuristic.
Còn có những đánh đổi khác ở heuristic, đôi khi không chỉ là độ chính xác mà còn là tốc độ tính ra hàm heuristic của bạn.
But what we see here is that in this case, we might prefer number of the largest pancake that is still out of place over number of pancakes still out of place.
Nhưng ở đây ta thấy rằng trong trường hợp này, ta có thể thích dùng số hiệu của chiếc bánh lớn nhất còn sai vị trí hơn là số bánh còn sai vị trí.
So mostly with heuristics we can start doing something called Greedy Search.
Với heuristic, ta có thể bắt đầu làm một thứ gọi là Greedy Search.
In Greedy Search what we're going to do is a strategy to pick something from the fringe is to pick the thing that looks like it's already closest to the goal.
Trong Greedy Search, chiến lược để chọn một nút từ biên (fringe) là chọn nút trông như đã gần đích nhất.
So it's like you're searching, and you look in your fringe and you say, oh, well this one's already pretty close, closest of everything on the fringe. Let me pick that one.
Giống như bạn đang tìm kiếm, nhìn vào biên và nói: ồ, cái này đã khá gần rồi, gần nhất trong mọi nút trên biên. Để mình chọn cái đó.
So what does that look like? On this map of Romania, well, we still start with the start state. Then we expand. At this point we have three nodes on the fringe.
Vậy nó trông thế nào? Trên bản đồ Romania này, ta vẫn bắt đầu từ trạng thái đầu. Rồi ta mở rộng. Lúc này biên có ba nút.
And the number shown are the straight line distances to Bucharest, our heuristic function. And Sibiu has the shortest straight line distance to Bucharest. So we started here in Iran.
Các con số hiển thị là khoảng cách đường chim bay đến Bucharest, tức hàm heuristic của ta. Và Sibiu có khoảng cách đường chim bay ngắn nhất đến Bucharest. Ta bắt đầu từ đây ở Iran.
Sibiu is over here, shortest straight line distance. So Greedy will say expand that one. Then we have now a fringe with 6 members.
Sibiu ở đằng này, khoảng cách đường chim bay ngắn nhất. Nên Greedy sẽ mở rộng nút đó. Giờ biên có 6 nút.
We again look at which one of these is closest to the goal. It's Fagaras over here with a heuristic of 176. We expand that one. Now we have a fringe of 7.
Ta lại xem nút nào gần đích nhất. Là Fagaras ở đây với heuristic 176. Ta mở rộng nút đó. Giờ biên có 7 nút.
And in that fringe of 7, one of them actually has a heuristic of 0. That's as good as it gets. It's actually the goal.
Và trong 7 nút đó, có một nút thực ra có heuristic bằng 0. Không thể tốt hơn được nữa. Nó chính là đích.
We would pick this one, expand it, and declare a success. And we would have found this path over here.
Ta chọn nút này, mở rộng nó, và tuyên bố thành công. Và ta sẽ tìm được đường đi này ở đây.
What can go wrong here? And we might already have gone wrong. Over there.
Điều gì có thể sai ở đây? Có thể ta đã sai rồi. Bạn ở đằng kia.
STUDENT
You might choose a path that's a local optimum but not a global optimal.
Có thể bạn chọn một đường tối ưu cục bộ nhưng không tối ưu toàn cục.
PROFESSOR
So the answer was you might use a path that's a local optimum, not a global optimal, or maybe to rephrase it a little bit into terminology we're using here, you might, and for this specific example, you see Fagaras here.
Câu trả lời là bạn có thể dùng một đường tối ưu cục bộ, không tối ưu toàn cục, hoặc diễn đạt lại một chút theo thuật ngữ ta đang dùng, với ví dụ cụ thể này, bạn thấy Fagaras ở đây.
And you expand it. And you end up at the goal. And you found the path. But it turns out that this other path is actually better.
Bạn mở rộng nó. Và bạn đến đích. Và bạn đã tìm được đường đi. Nhưng hóa ra đường kia mới tốt hơn.
The lower path is the better path. And you didn't find that. Why did we not find that?
Đường phía dưới là đường tốt hơn. Và bạn đã không tìm ra nó. Tại sao ta không tìm ra?
Well, we didn't find it because from Sibiu we compared Fagaras and Ramnicu Valcea and with Fagaras we kind of took a very big action. We covered a lot of ground.
Vì từ Sibiu ta so sánh Fagaras và Ramnicu Valcea, và với Fagaras ta đã thực hiện một hành động rất lớn. Ta đi được một quãng đường dài.
It was a bit off to the side. But we covered a lot of ground. And we ended up closer to Bucharest after that action. But it was a costly action.
Hơi lệch sang một bên. Nhưng ta đi được rất xa. Và sau hành động đó ta gần Bucharest hơn. Nhưng đó là một hành động tốn kém.
But Greedy Search ignores that this was a costly action. It doesn't pay attention to how much cost has already been incurred. It just looks at what's left.
Nhưng Greedy Search bỏ qua việc đó là hành động tốn kém. Nó không chú ý đến chi phí đã phải bỏ ra. Nó chỉ nhìn vào phần còn lại.
And so when you take a costly action like this that brings you closer to the goal, you're likely to go for that node again and then maybe again and ignore maybe something that could have been more promising, which is go this route, which was a cheaper option and you could have found a cheaper path to the goal.
Và khi bạn thực hiện một hành động tốn kém như vậy mà đưa bạn gần đích hơn, bạn có khả năng lại chọn nút đó, rồi có thể lại nữa, và bỏ qua thứ có thể triển vọng hơn, là đi theo lộ trình này, vốn rẻ hơn, và bạn có thể đã tìm được đường rẻ hơn tới đích.
So what go wrong is that you kind of go down a rabbit hole that looks good and keep going, rather than carefully considering other opportunities that might still exist.
Vậy điều sai là bạn như chui vào một cái hang thỏ trông có vẻ tốt và cứ đi tiếp, thay vì cân nhắc kỹ những cơ hội khác vẫn có thể còn tồn tại.
So Greedy Search is trying to expand the node that you think is closest to a goal state. The heuristic is the thing that measures the distance to nearest goal for each state.
Vậy Greedy Search cố mở rộng nút mà bạn nghĩ là gần trạng thái đích nhất. Hàm heuristic là thứ đo khoảng cách đến đích gần nhất cho mỗi trạng thái.
A common case is that this best first approach takes you straight down some path, possibly to the wrong goal, but often to a goal still.
Trường hợp thường gặp là cách tốt-nhất-trước này đưa bạn đi thẳng xuống một đường, có thể tới sai đích, nhưng thường vẫn tới một đích.
Worst case is that it behaves like a badly guided Depth-first search.
Trường hợp xấu nhất là nó hoạt động như tìm kiếm theo chiều sâu được dẫn dắt tồi.
And the heuristic sends you the wrong way, wrong way, wrong way and makes you explore everything except for where you need to be. Of course, this depends on your heuristic and so forth.
Hàm heuristic đưa bạn đi sai hướng, sai hướng, sai hướng và bắt bạn khám phá mọi thứ trừ nơi bạn cần đến. Tất nhiên, điều này phụ thuộc vào hàm heuristic của bạn, v.v.
But with a poor heuristic this can absolutely happen. Now let's take a look at how well this works on our two examples.
Nhưng với một hàm heuristic kém thì chắc chắn có thể xảy ra. Giờ hãy xem nó hoạt động tốt đến đâu trên hai ví dụ của ta.
So think for a moment. What do you think Greedy Search will do in this scenario?
Hãy nghĩ một chút. Bạn nghĩ Greedy Search sẽ làm gì trong tình huống này?
STUDENT
Straight line.
Đi thẳng một đường.
PROFESSOR
Straight line. I think so too. Now there's a slight caveat there. It really depends on the heuristic it's using.
Đi thẳng một đường. Tôi cũng nghĩ vậy. Có một lưu ý nhỏ ở đây. Nó thực sự phụ thuộc vào hàm heuristic nó dùng.
All right? So if I don't tell you what heuristic it's using, you can't know for sure what it's going to be doing.
Được chứ? Nên nếu tôi không nói nó dùng hàm heuristic nào, thì bạn không thể biết chắc nó sẽ làm gì.
But here are the heuristic is measuring straight line distance to the goal. And so what we expect to happen is that then it'll keep expanding towards the goal.
Nhưng ở đây hàm heuristic đo khoảng cách đường thẳng đến đích. Và vì vậy ta kỳ vọng nó sẽ liên tục mở rộng về phía đích.
Let's see if it actually happens. It does and finds a solution very quickly, very low compute cost, and actually the optimal path in this case.
Xem thử có đúng vậy không. Đúng thế, nó tìm ra lời giải rất nhanh, chi phí tính toán rất thấp, và trong trường hợp này còn là đường đi tối ưu.
Now let's take a look at Pac-Man in the small maze. Let's — actually this is a uniform cost. We need Greedy.
Bây giờ ta xem Pac-Man trong mê cung nhỏ. À, đây đang là uniform cost. Ta cần Greedy.
So again, this runs so fast we don't see it highlight.
Lại một lần nữa, nó chạy quá nhanh nên ta không thấy phần tô sáng.
But what happened here is that as we run the search, whenever we expand a state for the first time, code successor function, we color that corresponding square red.
Nhưng chuyện xảy ra là khi chạy tìm kiếm, mỗi khi ta mở rộng một trạng thái lần đầu, tức gọi hàm successor, ta tô đỏ ô vuông tương ứng.
The brighter red you are, the earlier that happened. The darker red you are, the later that happened. And black means it never happened.
Màu đỏ càng sáng thì nó xảy ra càng sớm. Màu đỏ càng sẫm thì nó xảy ra càng muộn. Còn màu đen nghĩa là chưa từng xảy ra.
So Greedy did not expend nearly as much as Uniform Cost Search. So it was a faster calculation. But the path it finds is actually suboptimal.
Vậy Greedy mở rộng ít hơn nhiều so với Uniform Cost Search. Nên tính toán nhanh hơn. Nhưng đường đi nó tìm được thực ra không tối ưu.
It goes off to the left, down, back to the right, it comes down, and then off to the left again. It's a suboptimal path, but it was found quickly.
Nó đi sang trái, xuống dưới, quay lại sang phải, rồi đi xuống, rồi lại sang trái. Đó là đường đi dưới tối ưu, nhưng tìm được nhanh.
You might wonder, why does it not try to move to the right? Why is that never being expanded?
Bạn có thể thắc mắc, sao nó không thử đi sang phải? Sao ô đó không bao giờ được mở rộng?
It's because the heuristic tells us then from that spot one to the right from where Pac-Man started, the heuristic value, which in this case is Manhattan distance, is higher than for any of the nodes we did expand.
Đó là vì hàm heuristic cho ta biết rằng tại ô bên phải vị trí xuất phát của Pac-Man, giá trị heuristic, ở đây là khoảng cách Manhattan, cao hơn mọi nút mà ta đã mở rộng.
And so it's still on the fringe waiting to be up next. But it never gets its turn. We expand the goal before we get to it. It's on that fringe.
Nên nó vẫn nằm trên biên (fringe) chờ đến lượt. Nhưng nó không bao giờ được đến lượt. Ta mở rộng đích trước khi tới nó. Nó nằm trên biên đó.
It's waiting but just never got called upon.
Nó cứ chờ nhưng không bao giờ được gọi.
So now we're going to see something that hopefully can bring together the best of both worlds. Let's think about this a little bit pictorially.
Bây giờ ta sẽ xem một thứ hy vọng có thể kết hợp ưu điểm của cả hai. Ta hãy hình dung một chút bằng hình ảnh.
Who knows about the fable of the tortoise and the hare? Most of you, not everybody? Who doesn't know about the fable of the tortoise and the hare? You don't know about it.
Ai biết truyện ngụ ngôn rùa và thỏ? Phần lớn các bạn, không phải tất cả? Ai chưa biết truyện rùa và thỏ? Bạn chưa biết.
OK, great. Or do you have a question? Or you don't know about it. It's a great fable.
Được rồi, tuyệt. Hay bạn có câu hỏi? Hay là bạn chưa biết. Đó là một truyện ngụ ngôn hay.
Let's see if I can do it justice explaining in here. But the gist is that the tortoise and the hare are in a race.
Để xem tôi kể có trọn vẹn được không. Đại ý là rùa và thỏ đang thi chạy.
And they have to get to a destination before the other.
Và phải đến đích trước đối phương.
And the hare runs off, and it's way ahead of the tortoise early on but then gets off on a side track, takes a nap, does all kinds of things.
Thỏ chạy vọt đi, dẫn trước rùa rất xa lúc đầu, nhưng rồi rẽ sang đường khác, đi ngủ trưa, làm đủ thứ chuyện.
Because it feels like it's winning anyway.
Vì nó thấy dù sao mình cũng thắng.
And in the meantime, the tortoise just slow and steady slow and steady, slow and steady keeps moving, keeps moving, keeps moving and actually gets to the destination first.
Trong lúc đó, rùa cứ chậm mà chắc, chậm mà chắc, cứ tiến lên, tiến lên, tiến lên và thực sự đến đích trước.
It's meant to be — the fable is about teaching people a lesson. But we're going to do some analogies here. Uniform Cost Search is our tortoise. It's slow and steady.
Truyện nhằm dạy người ta một bài học. Nhưng ở đây ta sẽ dùng nó để so sánh. Uniform Cost Search là con rùa. Chậm mà chắc.
It tries out every single thing that might be cheaper than what we've considered, that might be cheap enough, and only will declare success when it's tried everything that's cheaper than the cheapest path to the goal.
Nó thử mọi thứ có thể rẻ hơn những gì ta đã xét, có thể đủ rẻ, và chỉ tuyên bố thành công khi đã thử mọi thứ rẻ hơn đường đi rẻ nhất tới đích.
Greedy is like the hare. It just goes off, tries to find a path to the goal. But it might go down wrong rabbit hole and might not do so well after all.
Greedy giống con thỏ. Nó cứ lao đi, cố tìm đường tới đích. Nhưng nó có thể chui nhầm hang thỏ và rốt cuộc không làm tốt lắm.
Now, well, wouldn't it be beautiful if we could have something like this?
Vậy, chẳng phải sẽ tuyệt nếu có được thứ như thế này sao?
So we're bringing together slow and steady with greedy and fast. So it's one thing to make a cartoon. Now we need to put an algorithm behind this cartoon.
Ta kết hợp sự chậm mà chắc với sự tham lam và nhanh. Vẽ một bức tranh hoạt hình thì dễ. Giờ ta cần một thuật toán đứng sau bức tranh này.
It's called A Star Search, the topic of this lecture, main topic of this lecture. So let's start comparing Uniform Cost, Greedy, and then A Star on a simple example here.
Nó gọi là A Star Search, chủ đề của bài giảng này, chủ đề chính của bài giảng này. Ta bắt đầu so sánh Uniform Cost, Greedy, rồi A Star trên một ví dụ đơn giản.
And again, keep in mind, these examples are not meant to be representative of problems you would really want to solve, it's just to illustrate the algorithms.
Và nhớ rằng, các ví dụ này không đại diện cho những bài toán bạn thực sự muốn giải, chúng chỉ để minh họa các thuật toán.
So what does it mean to run Uniform Cost Search? Well, on the left we have the states based graph. On the right here, we have the Search Tree.
Vậy chạy Uniform Cost Search nghĩa là gì? Bên trái ta có đồ thị trạng thái. Bên phải là cây tìm kiếm.
I have shown the Search Tree here. What will Uniform Cost do? It will go in tiers through that Search Tree, initially S is on the fringe, then a, and s is off.
Tôi đã vẽ cây tìm kiếm ở đây. Uniform Cost sẽ làm gì? Nó đi qua cây tìm kiếm theo từng tầng, ban đầu S nằm trên biên, rồi a, và S ra khỏi biên.
Then a will go off and we'll have b, d, e on the fringe. And then what will happen next, we now have choices to make. There's three options.
Rồi a ra khỏi biên và ta có b, d, e trên biên. Tiếp theo sẽ ra sao, giờ ta phải chọn. Có ba lựa chọn.
We will go by lowest cost so far. To get to b cost is 2. To get to d cost is 4. To get to e cost is 9.
Ta chọn theo chi phí tới hiện tại thấp nhất. Để tới b chi phí là 2. Để tới d chi phí là 4. Để tới e chi phí là 9.
So then Uniform Cost will go here, 2 is lowest. Expand b and we'll have found this path to c and so forth.
Vậy Uniform Cost sẽ đi vào đây, 2 là thấp nhất. Mở rộng b và ta sẽ tìm ra đường tới c, v.v.
Now what we see here, if we look at the graph, it start state a, b, c. That's kind of going off in the wrong direction. But Uniform Cost Search doesn't know.
Giờ nếu nhìn vào đồ thị, trạng thái đầu rồi a, b, c. Như vậy là đang đi sai hướng. Nhưng Uniform Cost Search không biết.
It does not have access to any information about the goal, except for a Boolean check, am I at the goal or not? So it doesn't know. And so it doesn't do so well.
Nó không có thông tin nào về đích, ngoại trừ phép kiểm tra Boolean: tôi đã tới đích chưa? Nên nó không biết. Và vì thế nó làm không tốt lắm.
Now, it's slow and steady and ultimately will explore that search Tree until it finds the shortest path to the goal.
Nó chậm mà chắc và cuối cùng sẽ khám phá cây tìm kiếm đó cho đến khi tìm ra đường đi ngắn nhất tới đích.
But it's going to waste a lot of time on things that are not promising. Greedy, how about Greedy? Well, Greedy orders by forward cost, the heuristic function.
Nhưng nó sẽ lãng phí rất nhiều thời gian vào những thứ không triển vọng. Còn Greedy thì sao? Greedy sắp xếp theo chi phí tiến, tức hàm heuristic.
So Greedy would also start with the start state, expand that, get just a on the fringe, expand that. Now there are options.
Vậy Greedy cũng sẽ bắt đầu từ trạng thái đầu, mở rộng nó, được a trên biên, rồi mở rộng a. Giờ có các lựa chọn.
And it would check H. H is 1 here, 2 here, 6 here. It would say 1 is best. Let me expand this one. Now we have this.
Và nó kiểm tra H. H là 1 ở đây, 2 ở đây, 6 ở đây. Nó sẽ bảo 1 là tốt nhất. Mở rộng nút này. Giờ ta có cái này.
Now we have 2, 2, and 6. There's some tie-breaking there. It would pick one of them. And then next it finds one of those two goals and declares success.
Giờ ta có 2, 2 và 6. Ở đây có chọn ngẫu nhiên khi hòa. Nó sẽ chọn một trong số đó. Rồi tiếp theo nó tìm thấy một trong hai đích đó và tuyên bố thành công.
But so what happens with Greedy is that you might end up finding this longer path to the goal that you would find if you were more careful about how you expand.
Vậy điều xảy ra với Greedy là bạn có thể tìm ra đường dài hơn tới đích so với đường bạn tìm được nếu cẩn thận hơn trong cách mở rộng.
How about A Star Search? A Star Search will consider both G and H. And keep in mind here, g is the cumulative cost so far.
Còn A Star Search thì sao? A Star Search xét cả G và H. Lưu ý ở đây, g là chi phí tích lũy cho đến hiện tại.
The reason g is 2 here, it's 1 plus 1 to get our 2.
Lý do g bằng 2 ở đây là 1 cộng 1 ra 2.
So A Star means you do it by g plus h so how will it expand? Well, we'll start with s. No choice there, expand then a, no choice there, expand.
A Star nghĩa là xét theo g cộng h, vậy nó mở rộng thế nào? Ta bắt đầu với s. Không có lựa chọn, mở rộng a, cũng không có lựa chọn, mở rộng.
Now we have b, d, e. That's our fringe. Which has the lowest g plus h? It would be this one here for 6 total, expand d.
Giờ ta có b, d, e. Đó là biên của ta. Nút nào có g cộng h thấp nhất? Là nút này, tổng 6, mở rộng d.
Then it would be over here. It would not declare success yet. Remember, we don't declare success just when we put something on the fringe, it's when we pop it off.
Rồi sẽ sang bên này. Nó chưa tuyên bố thành công. Nhớ rằng, ta không tuyên bố thành công khi vừa đưa một nút vào biên, mà là khi lấy nó ra.
Now we'll look at what's lowest. G plus h, this one has 8. This one has 6. This one has 10.
Giờ ta xem cái nào thấp nhất. G cộng h, cái này là 8. Cái này là 6. Cái này là 10.
This one is lowest, we declare success. Because we popped a state — a path that ends up in the goal state.
Cái này thấp nhất, ta tuyên bố thành công. Vì ta lấy ra một trạng thái — một đường đi kết thúc ở trạng thái đích.
So that's A Star Search and we'd expand less nodes than Uniform Cost Search expands, yet still in this case, at least, find the optimal path.
Đó là A Star Search, và ta mở rộng ít nút hơn so với Uniform Cost Search, mà vẫn, ít nhất trong trường hợp này, tìm được đường tối ưu.
So question, when should A Star terminate? Can we stop when we enqueue a goal?
Câu hỏi: khi nào A Star nên dừng? Có thể dừng khi đưa đích vào hàng đợi không?
No we can't. And I've tried to emphasize this a few times. This is the most commonly occurring bug in Project One. We have to wait until we dequeue.
Không. Tôi đã nhấn mạnh điều này vài lần rồi. Đây là lỗi hay gặp nhất trong Project One. Ta phải đợi đến khi lấy ra khỏi hàng đợi.
Now if you want to show something like that, if you want to say, I want to show to you that you have to wait until dequeueing.
Giờ nếu bạn muốn chứng minh điều như vậy, nếu bạn muốn nói, tôi muốn chứng minh là phải đợi đến khi lấy ra.
It's not enough to declare success when you enqueue. The way to prove that is by showing a counterexample, showing that if you do it wrong on this example, things go wrong.
Tuyên bố thành công lúc đưa vào hàng đợi là không đủ. Cách chứng minh là đưa ra một phản ví dụ, cho thấy nếu làm sai trên ví dụ này, thì mọi thứ hỏng.
You get the wrong solution. That shows that your algorithm then is wrong, and you should change it. So here's a small example showcasing that we can not stop when we enqueue a goal.
Bạn ra lời giải sai. Điều đó cho thấy thuật toán của bạn sai, và bạn nên sửa nó. Đây là một ví dụ nhỏ cho thấy ta không thể dừng khi đưa đích vào hàng đợi.
Because what happens in this example is we start with s on our fringe. Then next we have a and b on our fringe.
Vì trong ví dụ này điều xảy ra là ta bắt đầu với s trên biên. Tiếp theo ta có a và b trên biên.
Then what would be next? Well, t plus h, we have 4 here total. We have 3 here total. So we would expand b first.
Rồi tiếp theo là gì? Ta có t cộng h, ở đây tổng là 4. Ở đây tổng là 3. Nên ta mở rộng b trước.
We then queue g. If we declare success at this point, we'd found the path of length 5. But there is actually a path of length 4. We need to wait.
Rồi ta đưa g vào hàng đợi. Nếu ta tuyên bố thành công ngay lúc này, ta tìm được đường dài 5. Nhưng thực ra có đường dài 4. Ta cần đợi.
We have now a and g on the queue. G has a score of g equals 5, h equals 0. So 5 a has 2 plus 2, which is 4.
Giờ hàng đợi có a và g. G có điểm g bằng 5, h bằng 0. Vậy là 5, còn a có 2 cộng 2, là 4.
We need to expand a. And now we'll get — we have on the fringe at this point is s to a to g as well as s to a, s to b to g.
Ta cần mở rộng a. Và giờ ta sẽ có — trên biên lúc này có s đến a đến g cũng như s đến a, s đến b đến g.
This one has 4. This one has 5, both plus 0, because the heuristic of the goal is 0. And then we pop this one, then we can declare success.
Cái này là 4. Cái này là 5, cả hai cộng 0, vì heuristic của đích bằng 0. Rồi ta lấy cái này ra, lúc đó mới tuyên bố thành công.
So only stop when we dequeue. Is A Star guaranteed to find the optimal solution?
Vậy chỉ dừng khi lấy ra khỏi hàng đợi. A Star có đảm bảo tìm ra lời giải tối ưu không?
Let's do a raise of hands. Who thinks yes? OK. Who thinks no?
Giơ tay nào. Ai nghĩ là có? Được. Ai nghĩ là không?
So it's a bit of a mix. So it's kind of a mixed answer also. But in general, it's not guaranteed to be optimal.
Khá lẫn lộn. Nên câu trả lời cũng là lẫn lộn. Nhưng nói chung, nó không đảm bảo tối ưu.
Some extra conditions have to be met before that guarantee is satisfied. So we will have that guarantee with extra conditions. Now, why is it not generally true?
Phải thỏa thêm một số điều kiện thì mới có đảm bảo đó. Vậy ta sẽ có đảm bảo khi có thêm điều kiện. Vậy tại sao nói chung nó không đúng?
Well, the way to show it is by, again, showing a counter-example. Come up with a graph where A Star Search finds a suboptimal solution.
Cách chứng minh, một lần nữa, là đưa ra một phản ví dụ. Tìm một đồ thị mà A Star Search tìm ra lời giải không tối ưu.
And then that's your proof right there that is not guaranteed to be optimal. Here's an example of such graph. If you're run A Star Search on this graph, what do we get?
Thế là đó chính là chứng minh rằng nó không đảm bảo tối ưu. Đây là một ví dụ về đồ thị như vậy. Nếu chạy A Star Search trên đồ thị này, ta được gì?
We start with s on the — with a 0 plus 7. Comes off the fringe.
Ta bắt đầu với s trên — với 0 cộng 7. Nó ra khỏi biên.
We have s to a with a 1 plus 6.
Ta có s đến a với 1 cộng 6.
We have s to g with a 5 plus 0. What's next? This one is next.
Ta có s đến g với 5 cộng 0. Tiếp theo là gì? Là cái này.
Sorry about those vertical lines, not sure why. This one is next. And that would mean we declare success. And we found this path here, the bottom one.
Xin lỗi về những đường dọc này, không rõ vì sao. Cái này là tiếp theo. Và nghĩa là ta tuyên bố thành công. Và ta tìm được đường này, đường phía dưới.
Why did that happen?
Vì sao lại xảy ra vậy?
STUDENT
Because the heuristic is not on there.
Vì heuristic không có ở trên đó.
PROFESSOR
So the answer is this heuristic here is a very poorly chosen heuristic. It says that it thinks it's still 6 away from the goal, but it's only 3 away.
Câu trả lời là hàm heuristic này được chọn rất tệ. Nó cho rằng vẫn còn cách đích 6, nhưng thực ra chỉ cách 3.
And so because it thinks 6, well, it's on the fringe. And it has to wait its turn much longer than it really should.
Và vì nó nghĩ là 6, nên nút đó nằm trên biên. Và nó phải chờ đến lượt lâu hơn nhiều so với mức cần thiết.
And it doesn't get its turn soon enough for us to find it before we declare success. So that's also the intuition about what goes wrong when A Star is suboptimal on this specific problem.
Và nó không được đến lượt đủ sớm để chúng ta tìm ra nó trước khi ta tuyên bố thành công. Đó cũng là trực giác về việc điều gì sai khi A Star không tối ưu trên bài toán cụ thể này.
It's whenever the heuristic is too pessimistic and forces things are actually promising to stay on the fringe for too long and you find something else in the meantime, and you declare success.
Đó là bất cứ khi nào hàm heuristic quá bi quan và buộc những nút thực sự đầy hứa hẹn phải nằm trên biên quá lâu và trong lúc đó bạn tìm được thứ khác, rồi bạn tuyên bố thành công.
So the actual cost was smaller than the estimated cost from the heuristic. That's not a good thing. We need to do it the other way around. So this is called an Admissible Heuristic.
Tức là chi phí thực tế nhỏ hơn chi phí ước lượng từ hàm heuristic. Đó không phải là điều tốt. Chúng ta cần làm theo chiều ngược lại. Cái này gọi là hàm heuristic chấp nhận được.
If you're heuristic satisfies the property, then it's optimistic, meaning than it estimates how much more cost you're going to get before reaching the goal from the state as a lower number or equal to what it really is.
Nếu hàm heuristic của bạn thỏa mãn tính chất này, thì nó lạc quan, nghĩa là nó ước lượng chi phí còn phải trả để đi tới đích từ trạng thái đó là một số nhỏ hơn hoặc bằng giá trị thực.
That's an optimistic heuristic, which is admissible, then A Star Search will be optimal. If you're heuristics are too pessimistic and they are inadmissible, A Star Search optimality guarantees will break.
Đó là hàm heuristic lạc quan, tức là chấp nhận được, thì A Star Search sẽ tối ưu. Nếu hàm heuristic của bạn quá bi quan và không chấp nhận được, thì đảm bảo tối ưu của A Star Search sẽ bị phá vỡ.
Because good plans, good partial plans will be trapped on the fringe and not expanded on. Because the heuristic is holding it back.
Vì các kế hoạch tốt, các kế hoạch từng phần tốt sẽ bị kẹt trên biên và không được mở rộng. Vì hàm heuristic đang kìm chúng lại.
So formal definition, h star n is the optimal cost with which you can get from this node m to the goal.
Định nghĩa hình thức: h star n là chi phí tối ưu để đi từ nút này tới đích.
Typically we don't have access to that. But mathematically it exists.
Thường thì ta không có giá trị đó. Nhưng về mặt toán học thì nó tồn tại.
And a heuristic h is admissible if for every node it estimates something that's lower than or equal to the exact cheapest way to get to the goal from that state.
Và hàm heuristic h là chấp nhận được nếu với mọi nút nó ước lượng một giá trị nhỏ hơn hoặc bằng chi phí rẻ nhất chính xác để đi tới đích từ trạng thái đó.
What are some examples? Manhattan distance. It's lower or equal to the actual cost. If there's no walls, it would be the actual cost.
Ví dụ nào? Khoảng cách Manhattan. Nó nhỏ hơn hoặc bằng chi phí thực. Nếu không có tường, nó chính là chi phí thực.
And when there are walls, it might be an optimistic estimate of the actual cost. Pancake flipping.
Và khi có tường, nó có thể là một ước lượng lạc quan của chi phí thực. Lật bánh kếp.
What we had there, number of the ID of the largest one that's still out of place is optimistic.
Cái ta có ở đó, số ID của chiếc lớn nhất vẫn còn sai vị trí là lạc quan.
Because at the very least, you need to still go as deep as that one to rearrange things, which means flip at least that many pancakes to get to the goal.
Vì ít nhất, bạn vẫn cần đi sâu tới chiếc đó để sắp xếp lại, nghĩa là lật ít nhất từng ấy chiếc bánh để tới đích.
So it's, again, and Admissible Heuristic. Come up with Admissible Heuristics is actually a lot of what's involved in using A Star in practice. Because once you've coded up A Star it's there.
Nên, một lần nữa, đây là hàm heuristic chấp nhận được. Nghĩ ra các hàm heuristic chấp nhận được thực ra là phần lớn công việc khi dùng A Star trong thực tế. Vì một khi bạn đã code xong A Star thì nó có sẵn đó.
You can use it. But when you now want to solve a new problem, you need to think about what's a good heuristic for this new problem.
Bạn dùng được. Nhưng khi giờ bạn muốn giải một bài toán mới, bạn cần nghĩ xem hàm heuristic nào tốt cho bài toán mới này.
So let's now formally prove that if we have a Admissible Heuristic, again, which means that for every node we estimate the cost to the goal as less than or equal to what it really would be, then A Star Tree Search will be optimal.
Giờ ta hãy chứng minh chặt chẽ rằng nếu có hàm heuristic chấp nhận được, nghĩa là với mọi nút ta ước lượng chi phí tới đích nhỏ hơn hoặc bằng giá trị thực, thì A Star Tree Search sẽ tối ưu.
Assume A is an optimal goal node. So we hope to find this one in the Search Tree. Assume B is a suboptimal goal node.
Giả sử A là một nút đích tối ưu. Ta hy vọng tìm thấy nút này trong cây tìm kiếm. Giả sử B là một nút đích không tối ưu.
So failure would be if we expand b and then we would declare success before we get to a. And let's assume h is admissible.
Vậy thất bại là nếu ta mở rộng b và tuyên bố thành công trước khi tới a. Và giả sử h là chấp nhận được.
Our claim is that a will exit the fringe before b. If we can prove that claim we're done.
Khẳng định của ta là a sẽ rời biên trước b. Nếu chứng minh được khẳng định này là xong.
Because if for — this is we have an optimal goal node, any optimal on goal node a, any suboptimal goal node b and if we can show that a will be guaranteed to exit the fringe before b, then that is true for any such optimal and suboptimal goal nodes.
Vì nếu, ở đây ta có một nút đích tối ưu, bất kỳ nút đích tối ưu a nào, bất kỳ nút đích không tối ưu b nào và nếu ta chỉ ra được a chắc chắn rời biên trước b, thì điều đó đúng với mọi cặp nút đích tối ưu và không tối ưu như vậy.
And that means we'll always first expand the optimal one before we might consider expansion of the suboptimal one. So this claim is what we need to prove to as a result get optimality.
Và điều đó nghĩa là ta luôn mở rộng nút tối ưu trước khi có thể xét mở rộng nút không tối ưu. Vậy khẳng định này là điều ta cần chứng minh để từ đó có được tính tối ưu.
How do you prove a pops off first from the fringe? Let's see, imagine a's on the fringe. If b's never on the fringe, we have no trouble anyway.
Làm sao chứng minh a được lấy ra khỏi biên trước? Hãy xem, tưởng tượng a đang ở trên biên. Nếu b không bao giờ lên biên thì ta chẳng có vấn đề gì.
But imagine b makes it on the fringe.
Nhưng tưởng tượng b lên được biên.
This might be our fringe. What do we know? We know that when b's on the fringe then also some ancestor n of a is on the fringe. Maybe it's A itself, maybe an ancestor.
Đây có thể là biên của ta. Ta biết gì? Ta biết rằng khi b ở trên biên thì cũng có một tổ tiên n nào đó của a ở trên biên. Có thể chính là A, có thể là một tổ tiên.
How do we know that? If no ancestor of a is on the fringe anymore, then it means we already expanded a.
Làm sao ta biết? Nếu không còn tổ tiên nào của a trên biên nữa, thì nghĩa là ta đã mở rộng a rồi.
Like, when all your ancestors are gone, you mean you've — and you're gone, you've been expanded. There's no other way around it. So we know this will — this condition to be true.
Giống như khi mọi tổ tiên của bạn đã mất hết, nghĩa là bạn đã được mở rộng rồi. Không có cách nào khác. Vậy ta biết điều này là đúng.
Some ancestor or a itself be on the fringe too. Then our claim will be that n will be expanded before b.
Một tổ tiên nào đó hoặc chính a ở trên biên. Rồi khẳng định của ta là n sẽ được mở rộng trước b.
So let's see how we can show that. F of N is less or equal then f of a.
Hãy xem ta chứng minh điều đó thế nào. f của n nhỏ hơn hoặc bằng f của a.
Why is that? Well, let's expand this. F of n is the backward cost plus the heuristic forward cost.
Vì sao vậy? Ta hãy khai triển ra. f của n là chi phí lùi cộng với chi phí tiến heuristic.
F of n is smaller than t of a.
f của n nhỏ hơn f của a.
Because that's what it means to be an Admissible Heuristic, it's the heuristics — to be admissible means that it underestimates how much it will cost to get to the goal, the optimal goal that you can reach from there.
Vì đó là ý nghĩa của hàm heuristic chấp nhận được, hàm heuristic chấp nhận được nghĩa là nó đánh giá thấp hơn chi phí để tới đích, đích tối ưu mà bạn có thể đạt từ đó.
So that's using the condition of admissibility. This is where we use it. If it was not admissible, we could not take this step. So we need the admissibility to take this step.
Đó là dùng điều kiện chấp nhận được. Đây là chỗ ta dùng nó. Nếu nó không chấp nhận được, ta không thể làm bước này. Nên ta cần tính chấp nhận được để làm bước này.
t of a equals f of a because a is a goal node. So h is 0. The only way to be admissible at a goal node is by a heuristic that's 0.
f của a bằng g của a vì a là nút đích. Nên h bằng 0. Cách duy nhất để chấp nhận được tại một nút đích là một hàm heuristic bằng 0.
Heuristics need to be positive. So this is now true. Then next thing we'll claim is that f of a is less than f of b. Why is that the case?
Heuristic phải không âm. Vậy điều này giờ đã đúng. Điều tiếp theo ta khẳng định là f của a nhỏ hơn f của b. Tại sao lại như vậy?
Well, the cost to get to A is less than the cost to get to b. Because that's what we said at the beginning. A is the optimal way of achieving the goal.
Chi phí để đến A nhỏ hơn chi phí để đến b. Vì đó là điều ta đã nói ngay từ đầu. A là cách tối ưu để đạt được đích.
B is a suboptimal way of achieving the goal. That's exactly what this is. B is suboptimal. That also means f of a smaller than f of b.
B là cách không tối ưu để đạt được đích. Đó chính xác là ý nghĩa của nó. B không tối ưu. Điều đó cũng có nghĩa là f của a nhỏ hơn f của b.
Because the heuristic h is 0 at all goal states so including a and b. Now, we have f of n small label to f of a.
Vì hàm heuristic h bằng 0 tại mọi trạng thái đích, kể cả a và b. Giờ ta có f của n nhỏ hơn hoặc bằng f của a.
F of a smaller than f of b which means f of n smaller than f of b, which means n will be expanded before b.
F của a nhỏ hơn f của b, nghĩa là f của n nhỏ hơn f của b, nghĩa là n sẽ được mở rộng trước b.
Since n expands before b and this was for an arbitrary ancestor n of a, we can repeat this argument for the next ancestor on the fringe, next one, next one.
Vì n được mở rộng trước b, và điều này đúng cho một tổ tiên n bất kỳ của a, ta có thể lặp lại lập luận này cho tổ tiên kế tiếp trên biên, rồi cái tiếp theo, rồi tiếp theo nữa.
This will keep happening. Ancestors of a will continue to be expanded before f until finally it's a itself on the fringe, which will also be expanded before b.
Điều này cứ tiếp diễn. Các tổ tiên của a sẽ tiếp tục được mở rộng trước b cho đến khi cuối cùng chính a nằm trên biên, và a cũng sẽ được mở rộng trước b.
And we've found a before b, hence, we found the optimal path to the goal, not the suboptimal one at b. So a expands before b.
Ta tìm thấy a trước b, do đó ta tìm được đường đi tối ưu đến đích, chứ không phải đường không tối ưu ở b. Vậy a được mở rộng trước b.
A Star Tree Search with Admissible Heuristics, remember we needed that condition somewhere in our proof, is optimal.
Tìm kiếm cây A Star với heuristic chấp nhận được, nhớ là ta cần điều kiện đó ở đâu đó trong chứng minh, là tối ưu.
I'll leave this up for you to maybe think over during a small break and we'll start again in two minutes.
Tôi để slide này lại để các bạn suy nghĩ thêm trong giờ nghỉ ngắn, và hai phút nữa ta bắt đầu lại.
[SIDE CONVERSATIONS] STUDENT: Do you consider A Star to be a Greedy algorithm?
[NÓI CHUYỆN RIÊNG] SINH VIÊN: Thầy có coi A Star là thuật toán Greedy không ạ?
PROFESSOR
No. So terminology wise Greedy for us is when you use the heuristic as the only thing to have your — to determine your strategy of what to expect next.
Không. Về thuật ngữ, Greedy với chúng ta là khi bạn chỉ dùng heuristic để quyết định chiến lược của mình, tức là mở rộng nút nào tiếp theo.
STUDENT
Oh.
À.
PROFESSOR
You could think of it may be Greedy in some way and kind of how many people use the terminology greedy in everyday world.
Bạn có thể coi nó hơi greedy theo một nghĩa nào đó, giống như nhiều người dùng từ greedy trong đời sống hằng ngày. Nhưng không phải nghĩa đó.
But not the terminology, the technical terminology we use here, Greedy means something very, very specific.
Thuật ngữ kỹ thuật ở đây, Greedy có nghĩa rất cụ thể.
It means you just look at the heuristic and expand based on whoever has the lowest heuristic value and repeat.
Nghĩa là bạn chỉ nhìn vào heuristic và mở rộng nút có giá trị heuristic thấp nhất rồi lặp lại.
STUDENT
So it's like specific to them, like, AI in the [INAUDIBLE] field?
Vậy nó là thuật ngữ riêng của lĩnh vực AI [KHÔNG NGHE RÕ] ạ?
PROFESSOR
Yes.
Đúng.
STUDENT
OK.
Vâng.
PROFESSOR
Hey.
Chào em.
STUDENT
Hi. Just had a question on, I think, one of the previous slides.
Chào thầy. Em có câu hỏi về một slide trước đó ạ.
GIÁO SƯ
So you said the — so f is the total like value received for n, like — PROFESSOR: F is g plus h.
Thầy nói là... f là tổng giá trị nhận được cho n, kiểu như... F là g cộng h.
STUDENT
F is g plus h.
F là g cộng h.
GIÁO SƯ
G is — PROFESSOR: Backward cost, so the cost of all the actions so far to get you to n.
G là... Chi phí lùi, tức là chi phí của tất cả các hành động cho đến nay để đưa bạn đến n.
STUDENT
Right.
Vâng.
PROFESSOR
Accumulated together, summed together. And then h is the heuristic function that you choose to use.
Cộng dồn lại, lấy tổng. Còn h là hàm heuristic mà bạn chọn dùng.
STUDENT
OK.
Vâng.
PROFESSOR
It's the estimate of the cost to get to the goal.
Nó là ước lượng chi phí để đến đích.
STUDENT
Right, right, right.
Vâng, vâng.
GIÁO SƯ
So then when you say f of n is less than or equal to g of a, for the cost all the way to get to a, we're saying that — PROFESSOR: So this step here, from here to here, that's what you're asking about right?
Vậy khi thầy nói f của n nhỏ hơn hoặc bằng g của a, tức chi phí để đến a, nghĩa là... Bước này, từ đây sang đây, là bước em đang hỏi đúng không?
STUDENT
Yeah.
Vâng.
PROFESSOR
That is saying that this heuristic is admissible.
Nó nói rằng heuristic này là chấp nhận được.
STUDENT
Like this — PROFESSOR: That's the definition of admissible is we're saying then, f of n, which is how much we estimate it takes from n to get to the goal, and we know a is the optimal goal right?
Tức là... Đó là định nghĩa của chấp nhận được: f của n, là ước lượng từ n đến đích mất bao nhiêu, và ta biết a là đích tối ưu, đúng không? A là đích tối ưu.
STUDENT
A's the optimal goal.
PROFESSOR
So we're saying then, it's the cost encountered so far plus our estimates. And we know that that estimate is less than what is really going to be.
Vậy ta đang nói chi phí đã phát sinh cho đến giờ cộng với ước lượng của ta. Và ta biết ước lượng đó nhỏ hơn chi phí thực sự. Còn g của a chính là chi phí thực sự.
SINH VIÊN
And g of a is what it's really going to be.
Vâng, tính từ điểm xuất phát.
STUDENT
OK, from start.
Tổng chi phí, từ điểm xuất phát.
PROFESSOR
For total, from start.
Vâng.
STUDENT
OK.
Nên tổng hai thành phần này nhỏ hơn g của a.
PROFESSOR
So that's why some of these two is less than g of a.
Vâng, em hiểu rồi.
STUDENT
OK, OK, yeah.
Nên xem lại vài lần.
PROFESSOR
It's good to go through this a few times.
Tôi đã xem lại ít nhất 100 lần rồi.
SINH VIÊN
I've gone through it at least 100 times by now.
Vâng, em cảm ơn thầy.
STUDENT
OK, thank you.
Câu hỏi hay.
PROFESSOR
Good question.
STUDENT
So we've proved that there are two goals, and we were going to use the optimal one — PROFESSOR: Mm-hm. STUDENT: --before it comes. But I don't think we have to prove that.
Vậy ta đã chứng minh có hai đích, và ta sẽ dùng đích tối ưu... Ừm. SINH VIÊN: ...trước khi nó đến. Nhưng em nghĩ ta không cần chứng minh điều đó. Ta sẽ đi theo đường tối ưu để đạt a.
GIÁO SƯ
We were going to the optimal path to achieve a.
Được, đây có thể là chuyện thuật ngữ nhỏ.
PROFESSOR
OK, so that's maybe a slight terminology thing.
Vâng.
STUDENT
Yes.
PROFESSOR
So when we're looking at the search history, A corresponds to a path, a is the — is a node, which corresponds to a sequence of actions and a sequence of states you traverse that ends in the goal.
Khi ta nhìn vào lịch sử tìm kiếm, A tương ứng với một đường đi, a là một nút, tương ứng với một chuỗi hành động và một chuỗi trạng thái ta đi qua, kết thúc ở đích. Và nó là cái mà...
SINH VIÊN
And it's one that — STUDENT: Oh, yeah, that's right. PROFESSOR: --corresponds to the shortest — STUDENT: OK.
À, đúng rồi. GIÁO SƯ: ...tương ứng với đường đi SINH VIÊN: Vâng. GIÁO SƯ: ...ngắn nhất đến bất kỳ đích nào.
SINH VIÊN
PROFESSOR: --path to any goal.
À, em hiểu rồi.
STUDENT
Oh, I see.
Vậy...
GIÁO SƯ
So — PROFESSOR: So that's why we're trying — STUDENT: --just one goal in the original search graph, whereas in the Search Tree that same graph node — PROFESSOR: It could be that the — STUDENT: [INAUDIBLE] different branch.
Đó là lý do ta đang cố... SINH VIÊN: ...chỉ có một đích trong đồ thị tìm kiếm ban đầu, SINH VIÊN: — chỉ có một đích trong đồ thị tìm kiếm ban đầu, trong khi ở cây tìm kiếm thì cùng nút đồ thị đó — GIÁO SƯ: Có thể là — SINH VIÊN: [KHÔNG NGHE RÕ] nhánh khác.
PROFESSOR
Yeah, it could be that it's on a and b. Or there could be multiple states to satisfy goal and a and b correspond to different ones.
Đúng, có thể nó nằm ở a và b. Hoặc có thể có nhiều trạng thái thỏa mãn mục tiêu, và a với b ứng với các trạng thái khác nhau.
STUDENT
Right.
Vâng.
PROFESSOR
Either way could be true. But the proof holds for when a is the one that is the cheapest goal you can get to from the start state. m encodes the path to get here.
Trường hợp nào cũng có thể đúng. Nhưng chứng minh vẫn đúng khi a là mục tiêu rẻ nhất mà bạn có thể đến được từ trạng thái xuất phát. m mã hóa đường đi để đến đây.
STUDENT
And the tree cannot convert [INAUDIBLE]..
Và cây không thể chuyển đổi [KHÔNG NGHE RÕ].
PROFESSOR
Correct, mm-hm.
Đúng rồi, ừm.
STUDENT
Hi.
Chào thầy.
PROFESSOR
Hey.
Chào em.
STUDENT
I was wondering how necessary the C70 pre-req is for the course.
Em muốn hỏi môn tiên quyết C70 cần thiết đến mức nào cho môn này.
I took [INAUDIBLE] class — PROFESSOR: So I think you will find out by doing the math cell diagnostic, which covers some of the essentially that's a way of measuring, do you have the math background?
Em đã học lớp [KHÔNG NGHE RÕ] — GIÁO SƯ: Tôi nghĩ em sẽ biết được khi làm bài chẩn đoán toán, bài này bao gồm một số phần cơ bản, về cơ bản đó là cách đo xem em có đủ nền tảng toán hay không.
STUDENT
The first homework?
Là bài tập đầu tiên ạ?
PROFESSOR
Homework 0, yeah.
Bài tập 0, đúng.
STUDENT
OK, I did that one.
Vâng, em làm bài đó rồi.
PROFESSOR
So if that goes well, then you should be fine.
Nếu làm tốt thì em ổn thôi.
STUDENT
OK.
Vâng.
PROFESSOR
Yeah.
Ừ.
STUDENT
OK, cool, awesome. Thank you.
Vâng, tuyệt quá. Em cảm ơn thầy.
STUDENT
What's the — what do you mean by suboptimal over there? Suboptimal — PROFESSOR: Suboptimal means that you get to the goal.
Thầy nói suboptimal ở đó nghĩa là gì ạ? Suboptimal — GIÁO SƯ: Suboptimal nghĩa là em đến được mục tiêu.
But the path you follow has higher costs than another path to a goal that has lower cost.
Nhưng đường đi em theo có chi phí cao hơn một đường khác đến một mục tiêu có chi phí thấp hơn.
STUDENT
This is is a little bit unrelated question but what do you think of the significance of memory networks [INAUDIBLE].
Câu này hơi lạc đề nhưng thầy nghĩ các mạng bộ nhớ quan trọng thế nào [KHÔNG NGHE RÕ].
Because like use tools [INAUDIBLE] memory — PROFESSOR: Absolutely. So memory will play a big role in everything we do as humans and in AI.
Vì ví dụ dùng các công cụ [KHÔNG NGHE RÕ] bộ nhớ — GIÁO SƯ: Chắc chắn rồi. Bộ nhớ đóng vai trò lớn trong mọi việc con người làm, và cả trong AI.
It's the second half of the class, not this lecture, but the second half of the semester.
Đó là nửa sau của môn, không phải bài này, mà là nửa sau của học kỳ.
STUDENT
OK.
Vâng.
PROFESSOR
We'll look at those things.
Chúng ta sẽ xem những thứ đó.
STUDENT
But, like, in terms of newer network and, you know, gradient based optimization — PROFESSOR: I might have to restart. And this is not — STUDENT: Yeah. PROFESSOR: --too into this lecture.
Nhưng về mạng nơ-ron mới, và tối ưu hóa dựa trên gradient thì sao ạ — GIÁO SƯ: Tôi có thể phải bắt đầu lại rồi. Và cái này không — SINH VIÊN: Vâng. GIÁO SƯ: — đi quá sâu vào bài này.
But having to talk about it in office hours — STUDENT: Yeah. PROFESSOR: --or in the second half of the semester.
Nhưng ta có thể nói trong giờ hỏi đáp — SINH VIÊN: Vâng. GIÁO SƯ: — hoặc trong nửa sau của học kỳ.
STUDENT
OK. Thank you.
Vâng. Em cảm ơn.
PROFESSOR
Hi everyone, let's restart.
Chào mọi người, ta bắt đầu lại nhé.
So one quick clarification that ties into some of the questions that came up during the break. When we talk about a is a optimal goal node, what does that mean?
Có một điểm làm rõ nhanh liên quan đến vài câu hỏi xuất hiện trong giờ nghỉ. Khi nói a là nút đích tối ưu, điều đó nghĩa là gì?
Remember, this is a Search Tree. So what is a?
Nhớ rằng đây là cây tìm kiếm. Vậy a là gì?
A encodes a sequence of actions as well as a sequence of states that you traverse that get you from s to, in this case we've assumed it achieved the goal, to a goal state.
A mã hóa một chuỗi hành động cũng như chuỗi trạng thái mà bạn đi qua, đưa bạn từ s đến, ở đây ta giả sử là đạt mục tiêu, một trạng thái đích.
And we said a is an optimal goal node, which means that it encodes of all paths to all possible goals in your state space, A encodes the shortest path to any goal.
Và ta nói a là nút đích tối ưu, nghĩa là trong mọi đường đi đến mọi mục tiêu khả dĩ trong không gian trạng thái, A mã hóa đường đi ngắn nhất đến một mục tiêu bất kỳ.
That's what a is. That's what it means to be an optimal node in the Search Tree. There could be many goals states. And there could be many paths to each of the goals states.
A là như vậy. Đó là ý nghĩa của nút tối ưu trong cây tìm kiếm. Có thể có nhiều trạng thái đích. Và có thể có nhiều đường đến mỗi trạng thái đích.
The optimal one is the one that is shortest from the start to any of the goal states.
Đường tối ưu là đường ngắn nhất từ trạng thái xuất phát đến một trạng thái đích bất kỳ.
Like, the goal state that's closest to the start state and the shortest path to that particular goal state.
Tức là trạng thái đích gần nhất với trạng thái xuất phát và là đường ngắn nhất đến trạng thái đích cụ thể đó.
To be suboptimal means you are a path to a goal state that is not as sure as the path encoded in a.
Suboptimal nghĩa là đó là đường đến một trạng thái đích mà không ngắn bằng đường được mã hóa trong a.
Any questions about the first half?
Có câu hỏi nào về nửa đầu không?
Yes?
Có bạn nào không?
STUDENT
When we were writing [INAUDIBLE]..
Khi mình viết [KHÔNG NGHE RÕ].
PROFESSOR
Mm-hm.
Ừm.
STUDENT
Then [INAUDIBLE].
Rồi [KHÔNG NGHE RÕ].
PROFESSOR
So he's saying, so your question is, once we're here, why are we not done yet?
Bạn ấy hỏi là khi đã đến đây thì sao ta chưa xong?
STUDENT
Right.
Đúng ạ.
PROFESSOR
The reason we're not done yet with the proof, even though at this point intuitively it's clear that we're going to get there, and I agree with you on that, that once we know that, we expect it to be true.
Lý do ta chưa xong phần chứng minh, dù đến đây về trực giác đã rõ là ta sẽ tới đích, và tôi đồng ý, một khi ta biết điều đó thì ta kỳ vọng nó đúng.
The reason we're not done yet is because we need to show that the process of how we pop things from the fringe will also get a before b.
Lý do chưa xong là vì ta cần chứng minh rằng quá trình lấy các nút ra khỏi biên cũng sẽ lấy a trước b.
And essentially what this is showing here, this entire reasoning is showing, if you look at it carefully, it's showing that you go in order of f cost.
Về bản chất, những gì được chỉ ra ở đây, toàn bộ lập luận này, nếu nhìn kỹ, là ta đi theo thứ tự chi phí f.
Right? And you keep expanding in order of f cost. And anything lower at F cost will happen before things that are higher F cost.
Đúng không? Và ta tiếp tục mở rộng theo thứ tự chi phí f. Cái nào có chi phí f thấp hơn sẽ xảy ra trước cái có chi phí f cao hơn.
And as a consequence, I mean, those are the kind of ideas that are at play here. And that's why, when you look at this, you might say, oh, maybe we're already there.
Và do đó, đó là những ý tưởng đang vận hành ở đây. Vì vậy khi nhìn vào đây, bạn có thể nghĩ, có lẽ ta đã xong rồi.
But it turns out that we actually need to carefully look at the process. Because this is not actually enough. Well, there are some subtleties to think about.
Nhưng hóa ra ta thực sự cần xem xét kỹ quá trình. Vì thế này thực ra chưa đủ. Có một vài điểm tinh tế cần suy nghĩ.
And we'll get to some of those later in lecture. And it is important to step through the algorithm and see what happens.
Và ta sẽ bàn một số điểm đó sau trong bài. Và điều quan trọng là đi từng bước qua thuật toán và xem điều gì xảy ra.
And so the reason at this point then we say this is not enough is that a might not be on the fringe when b is on the fringe.
Vậy lý do ở thời điểm này mà ta nói như vậy là chưa đủ, là vì a có thể không nằm trên biên khi b đang nằm trên biên.
So we need to say, while when a is not on the fringe, we know an ancestor of a has to be on the fringe.
Nên ta cần nói: khi a không nằm trên biên, ta biết một tổ tiên của a chắc chắn đang nằm trên biên.
And then we say, well, are we guaranteed that that ancestor will be expanded before b such that we can get a on the fringe before b gets expanded?
Rồi ta hỏi: liệu có đảm bảo tổ tiên đó sẽ được mở rộng trước b, để a kịp vào biên trước khi b được mở rộng không?
And so that is what we still need to do.
Và đó chính là điều ta vẫn cần chứng minh.
STUDENT
Thanks.
Em cảm ơn.
PROFESSOR
Another question there.
Còn câu hỏi nào khác không?
STUDENT
And it assumes that the heuristic is accurate?
Vậy nó giả định hàm heuristic là chính xác ạ?
PROFESSOR
It does not assume it's accurate. It assumes that it's admissible.
Không giả định là chính xác. Nó giả định là chấp nhận được.
And admissible is this very kind of specific mathematical condition that the heuristic value at each node is lower than or equal to the cheapest cost path to the nearest by goal from that node.
Và chấp nhận được là một điều kiện toán học rất cụ thể: giá trị heuristic tại mỗi nút nhỏ hơn hoặc bằng chi phí của đường đi rẻ nhất từ nút đó đến đích gần nhất.
And that's what it means to be admissible. You can be admissible without being accurate. And then you might not be very informative.
Đó là ý nghĩa của chấp nhận được. Có thể chấp nhận được mà không chính xác. Khi đó heuristic có thể không mang nhiều thông tin.
You might not help the A Star Search much in terms of being computationally efficient. But you will still have it be optimal. In fact, special case. What if I said h equals 0?
Nó có thể không giúp A Star Search nhiều về mặt hiệu quả tính toán. Nhưng kết quả vẫn tối ưu. Thật ra có một trường hợp đặc biệt. Nếu h bằng 0 thì sao?
If I said h equals 0, this condition is satisfied. We can still run A Star Search. But it actually becomes equivalent to Uniform Cost Search.
Nếu h bằng 0, điều kiện này vẫn thỏa. Ta vẫn chạy được A Star Search. Nhưng nó trở thành tương đương với Uniform Cost Search.
And so the proof we just showed here also proves that Uniform Cost Search is optimal. Because this is a special case of this.
Vì vậy chứng minh vừa rồi cũng chứng minh Uniform Cost Search là tối ưu. Vì đây là một trường hợp đặc biệt của nó.
But it's not as efficient than a more accurate heuristic might be.
Nhưng nó kém hiệu quả hơn so với một heuristic chính xác hơn. .
Other questions? Over there.
Còn câu hỏi nào không? Bạn ở đằng kia.
STUDENT
If we prove that our heuristics is admissible, then wouldn't we already know, like, h star n?
Nếu đã chứng minh heuristic chấp nhận được, thì chẳng phải ta đã biết h star n rồi sao ạ?
PROFESSOR
How do we know our heuristics is admissible? Let me see if you still have that question as well we're a little further down this lecture.
Làm sao biết heuristic chấp nhận được? Lát nữa em xem còn thắc mắc không nhé, ta sẽ đến phần đó ở phía sau bài giảng.
But right, you don't want to have to rely on knowing h star n.
Nhưng đúng, ta không muốn phải dựa vào việc biết h star n.
Because if you know n star n everywhere, and you're going to explicitly check against that, you might as well use h star n. So that's not what we want to do.
Vì nếu biết h star n ở mọi nơi và kiểm tra trực tiếp với nó, thì ta dùng luôn h star n là xong. Nên đó không phải điều ta muốn làm.
We'll get to that, what we actually want to do. Over there.
Ta sẽ đến phần ta thật sự muốn làm. Bạn ở đằng kia.
STUDENT
So how do we know when reading the first part of the claim that f of n is less than or equal to t of a?
Làm sao ta biết, khi đọc phần đầu của khẳng định, rằng f của n nhỏ hơn hoặc bằng t của a ạ?
PROFESSOR
How do we know in the first part that f of n is less than or equal to t of a? That's the definition of admissibility.
Làm sao biết ở phần đầu f của n nhỏ hơn hoặc bằng t của a? Đó là định nghĩa của tính chấp nhận được.
That's the key place where we need the assumption that the heuristic is admissible.
Đó là chỗ then chốt cần giả thiết rằng heuristic là chấp nhận được.
H being admissible means that from n the cheapest way to get to goal has to cost less than h of n.
H chấp nhận được nghĩa là từ n cách rẻ nhất đến đích phải tốn không ít hơn h của n.
And so we know that this thing here, t of a is the cost to get to the goal encoded in node a.
Và ta biết t của a ở đây là chi phí đến đích được mã hóa trong nút a.
And so we know that the cost encountered so far to get to n plus our heuristic, which underestimates the extra costs still yet to come, together should be smaller than the actual cost.
Vậy chi phí đã phát sinh để đến n cộng với heuristic, vốn ước lượng thấp phần chi phí còn lại sắp tới, gộp lại phải nhỏ hơn chi phí thực tế.
That's what this is, and that's the admissibility. And if we don't assume admissibility, we cannot go through with this proof. And that's also, I mean, we expect that, that we need it somewhere.
Đó là ý nghĩa của nó, và đó là tính chấp nhận được. Nếu không giả định tính chấp nhận được, ta không thể hoàn thành chứng minh này. Và điều đó cũng dễ hiểu, vì ta cần nó ở đâu đó.
Because we've seen counterexamples. When heuristics are not admissible, we can have counterexamples where A Star Tree Search doesn't find the optimal solution. Yes.
Bởi ta đã thấy các phản ví dụ. Khi heuristic không chấp nhận được, có phản ví dụ mà A Star Tree Search không tìm ra lời giải tối ưu. Mời bạn.
STUDENT
So if [INAUDIBLE] heuristics [INAUDIBLE] put 0 rather than [INAUDIBLE].
Vậy nếu [KHÔNG NGHE RÕ] heuristic [KHÔNG NGHE RÕ] đặt 0 thay vì [KHÔNG NGHE RÕ].
PROFESSOR
So how to choose heuristic, we'll see more of that soon. OK.
Còn cách chọn heuristic thì sẽ sớm học thêm. Được rồi.
So what are some properties Uniform Cost Search versus A Star Search, Uniform Cost goes equally fast in terms of the expansion in all directions whereas A Star will zone in towards the goal if you have a reasonably good heuristic.
Vậy Uniform Cost Search so với A Star Search có tính chất gì? Uniform Cost mở rộng đều nhau theo mọi hướng, còn A Star sẽ tập trung về phía đích nếu heuristic khá tốt. .
Pictorially looks like this, and looks at — let's also take a look on the maze environments. So we'll do demo one and five. So remember this is Uniform Cost Search.
Hình minh họa như thế này, và ta cũng xem thử trên các môi trường mê cung. Ta chạy demo một và năm. Nhớ rằng đây là Uniform Cost Search.
What do we expect for A Star Search. It will, again, depend on the exact heuristic we're using.
Ta kỳ vọng gì ở A Star Search? Nó lại phụ thuộc vào heuristic cụ thể được dùng.
Here we're using a heuristic that is saying, take the straight line distance to the goal and then take half of that value as my heuristic.
Ở đây ta dùng heuristic là lấy khoảng cách đường thẳng đến đích rồi lấy một nửa giá trị đó làm heuristic.
So things that are closer to the goal get favored, but maybe not favored as much as you might want. And here is the result in action.
Nên những ô gần đích hơn được ưu tiên, nhưng có thể chưa được ưu tiên nhiều như ta muốn. Và đây là kết quả khi chạy.
So it still expands a bit in all directions but favors the direction towards the goal and doesn't need to expand as much as Uniform Cost Search.
Nó vẫn mở rộng ít nhiều theo mọi hướng nhưng ưu tiên hướng về đích và không cần mở rộng nhiều như Uniform Cost Search.
Remember Uniform Cost expands this many nodes compared to A Star this may nodes. How about the Pac-Man environment? Well, here is the result of A Star Search.
Nhớ rằng Uniform Cost mở rộng chừng này nút, so với A Star chỉ chừng này nút. Còn môi trường Pac-Man thì sao? Đây là kết quả của A Star Search.
We see that it expanded again. The coding is red means expanded at some point. The brighter red, the earlier we're expanding, the darker red the later. Black means never expanded.
Ta thấy nó lại mở rộng. Mã màu: màu đỏ nghĩa là đã được mở rộng vào lúc nào đó. Đỏ càng sáng thì mở rộng càng sớm, đỏ càng đậm thì càng muộn. Màu đen nghĩa là chưa bao giờ được mở rộng.
We see, and we'll — let's do a comparison with other things we've seen.
Ta hãy so sánh với những thuật toán đã thấy.
Greedy expanded very little. But the path found was suboptimal. Uniform Cost expands everything below cheapest path cost to the goal, which was everything but one square.
Greedy mở rộng rất ít. Nhưng đường đi tìm được không tối ưu. Uniform Cost mở rộng mọi thứ dưới chi phí đường đi rẻ nhất đến đích, tức là gần như mọi ô trừ một ô.
And then A Star Search is somewhat in the middle. It does a bit more work than Greedy but as a result also finds the optimal path.
Còn A Star Search nằm ở khoảng giữa. Nó làm việc nhiều hơn Greedy một chút, nhờ vậy cũng tìm ra đường đi tối ưu.
How to know what will get expanded by A Star Search if you look at this. Can you just, like, eyeball what will be expanded? Well, it depends on the heuristic.
Làm sao biết A Star Search sẽ mở rộng những nút nào khi nhìn hình này? Có thể chỉ cần nhìn bằng mắt là biết sẽ mở rộng gì không? Điều đó còn phụ thuộc vào hàm heuristic.
What if the heuristic is the Manhattan heuristic? Then you can say, well, what is the shortest path to the goal? What's the length of the shortest path to the goal?
Nếu hàm heuristic là khoảng cách Manhattan thì sao? Thì bạn hỏi: đường đi ngắn nhất tới đích là gì? Độ dài đường đi ngắn nhất tới đích là bao nhiêu?
And then you can say every state that I can reach with F cost, lower than that will need to be expanded first.
Rồi bạn nói mọi trạng thái mà tôi có thể đạt tới với chi phí F thấp hơn mức đó thì đều phải được mở rộng trước.
So anything that has cost plus heuristic lower than cheapest path to the goal will be expanded. And that's exactly what we're seeing here.
Tức là bất cứ nút nào có chi phí cộng heuristic thấp hơn chi phí của đường đi ngắn nhất tới đích sẽ được mở rộng. Và đó đúng là những gì ta thấy ở đây.
This is used in many, many applications. A Star is typically the go-to planning algorithm, whether it's for video games or routing or decoding in speech recognition, machine translation, and so forth.
Thuật toán này được dùng trong rất nhiều ứng dụng. A Star thường là thuật toán lập kế hoạch được chọn đầu tiên, dù là cho trò chơi điện tử, định tuyến, hay giải mã trong nhận dạng giọng nói, dịch máy, v.v.
Let's take a look at this in action on the tiny maze first, 6 and 7.
Hãy xem nó chạy thực tế trên mê cung nhỏ trước, hình 6 và 7.
So let's run Uniform Cost Search. Look at the console here to see how many nodes are being expanded, the work that's being done.
Chạy Uniform Cost Search trước. Hãy nhìn vào console để xem có bao nhiêu nút được mở rộng, tức là khối lượng công việc phải làm.
The starting expands over 9,000 nodes before it finds a path. With Uniform Cost we'll find the optimal path clears the board optimally.
Nó mở rộng hơn 9.000 nút trước khi tìm ra đường đi. Với Uniform Cost ta sẽ tìm được đường đi tối ưu, dọn sạch bàn một cách tối ưu.
Now, so remember over 9,000 nodes expanded. Now let's take a look at A Star Search. How many nodes does it expand?
Nhớ nhé, hơn 9.000 nút được mở rộng. Giờ xem A Star Search. Nó mở rộng bao nhiêu nút?
It expanded, well, less than 1,000. Only 175 nodes expanded to find the optimal solution.
Chưa đến 1.000. Chỉ 175 nút được mở rộng để tìm ra lời giải tối ưu.
So thanks to this heuristic, it could find a solution a lot more quickly. Now let's do a few demos of different algorithms in action. This is our water maze.
Nhờ hàm heuristic này, nó tìm ra lời giải nhanh hơn rất nhiều. Giờ ta xem vài demo của các thuật toán khác nhau. Đây là mê cung nước.
Dark blue means more expensive to traverse. Light blue is cheaper to traverse. Let's guess all algorithms. So how about this one?
Màu xanh đậm nghĩa là đi qua tốn kém hơn. Màu xanh nhạt là đi qua rẻ hơn. Hãy đoán xem thuật toán nào. Còn cái này thì sao?
Anyone? Breadth-first because it goes out in every direction equally fast and finds the shortest number of steps path. How about this one?
Ai trả lời? Breadth-first, vì nó lan ra mọi hướng với tốc độ như nhau và tìm đường đi có số bước ít nhất. Còn cái này?
STUDENT
Greedy.
Greedy.
PROFESSOR
Greedy. It finds the thing that's closest to the goal based on the heuristic and keeps expanding that and doesn't have to do much work but doesn't find the best path either.
Greedy. Nó tìm nút gần đích nhất dựa trên hàm heuristic và cứ mở rộng nút đó, không phải làm nhiều việc nhưng cũng không tìm ra đường tốt nhất.
How about this one?
Còn cái này?
STUDENT
Uniform cost [INAUDIBLE]..
Uniform cost [KHÔNG NGHE RÕ].
PROFESSOR
Uniform cost. How do we know? Well, it moves forward more quickly in regions where the cost is slower. But it does expand everywhere.
Uniform cost. Làm sao biết? Nó tiến nhanh hơn ở những vùng có chi phí thấp. Nhưng nó mở rộng ra khắp nơi.
And it actually does not orient itself much towards the goal. How about this one?
Và thực ra nó không hướng nhiều về phía đích. Còn cái này?
STUDENT
[LAUGHTER] PROFESSOR: Depth-first search. Yes. How about this one?
[CƯỜI] GIÁO SƯ: Depth-first search. Đúng. Còn cái này?
STUDENT
A Star.
A Star.
PROFESSOR
That's A Star. It pays attention to costs incurred so far, also what's looking like it's getting closer to the goal, and can do a relatively small amount of work to find the optimal path.
Đúng, A Star. Nó chú ý đến chi phí đã phát sinh, cũng như nút nào có vẻ đang tiến gần đích hơn, và chỉ làm một lượng việc tương đối nhỏ để tìm ra đường đi tối ưu.
OK. So part of the art is creating good heuristics. We saw straight line distance as one, Manhattan distance as one for Pac-Man. And Admissible Heuristics can be useful at times.
Được rồi. Một phần của nghệ thuật là tạo ra các hàm heuristic tốt. Ta đã thấy khoảng cách đường thẳng là một ví dụ, khoảng cách Manhattan là một ví dụ cho Pac-Man. Và các hàm heuristic không chấp nhận được đôi khi cũng hữu ích.
You might lose optimality. But there might be informative and just like Greedy market, your solution is faster but not the right solution, not the optimal one.
Bạn có thể mất tính tối ưu. Nhưng chúng có thể nhiều thông tin, giống như Greedy, lời giải đến nhanh hơn nhưng không đúng không phải lời giải tối ưu.
You might sometimes just want to find a solution fast. Let's do some kind of practice here in designing heuristics. OK, this is the 8 Puzzle. What are the states in the 8 Puzzle?
Đôi khi bạn chỉ muốn tìm ra một lời giải thật nhanh. Giờ ta thực hành một chút việc thiết kế hàm heuristic. Đây là bài 8 Puzzle. Các trạng thái trong 8 Puzzle là gì?
Well, it corresponds to all possible configurations of the board. How many states are there?
Đó là mọi cấu hình có thể có của bàn cờ. Có bao nhiêu trạng thái?
Well, there's 9 positions for the first tile, 8 for the next one, 7 for the next one and so forth. Then there is 9 factorial states. What are the actions?
Có 9 vị trí cho ô đầu tiên, 8 cho ô tiếp theo, 7 cho ô kế tiếp, và cứ thế. Vậy có 9 giai thừa trạng thái. Các hành động là gì?
You can move a tile onto the empty spot. Or another way to think of it, you can move the empty spot around. How many successors from the start state?
Bạn có thể dời một ô vào chỗ trống. Hoặc nghĩ theo cách khác, bạn di chuyển chỗ trống. Từ trạng thái đầu có bao nhiêu trạng thái kế tiếp?
Well, there are 4 tiles you can move into that, so 4 successors. What should the cost be? Well, that's — you as the designer choose.
Có 4 ô bạn có thể dời vào đó, nên có 4 trạng thái kế tiếp. Chi phí nên là bao nhiêu? Điều đó do bạn, người thiết kế, chọn.
But maybe you don't want to put too much effort into sliding these things into place. And so every time we have to move a tile, that's a cost of one.
Nhưng có thể bạn không muốn tốn quá nhiều công sức để trượt các ô vào đúng chỗ. Nên mỗi lần phải dời một ô, chi phí là một.
So, now let's think about heuristics. What would be a possible heuristic for this problem?
Giờ hãy nghĩ về hàm heuristic. Hàm heuristic nào có thể dùng cho bài này?
So an estimate of how many more actions, how many more steps you need to get to the goal in this case. Any thoughts?
Tức là ước lượng cần thêm bao nhiêu hành động, bao nhiêu bước nữa để tới đích trong trường hợp này. Ai có ý kiến không?
Over there.
Bạn ở đằng kia.
STUDENT
The number of tiles that are in the wrong position.
Số ô nằm sai vị trí.
PROFESSOR
So number of tiles in the wrong position. Why could that be a reasonable heuristic. Let's think about it. Might it be admissible?
Số ô nằm sai vị trí. Tại sao đó có thể là một hàm heuristic hợp lý? Hãy cùng suy nghĩ. Nó có chấp nhận được không?
Yeah, it is admissible. Because every tile in the wrong place will need to undergo an action.
Có, nó chấp nhận được. Vì mỗi ô nằm sai chỗ đều cần ít nhất một hành động.
And likely more actions will be needed so it's a underestimate of the cost you'll incur to achieve the goal state.
Và nhiều khả năng sẽ cần nhiều hành động hơn, nên nó ước lượng thấp hơn chi phí thực tế bạn phải trả để đạt trạng thái đích.
So we've reasoned through the fact that it is admissible without having to compute what the actual optimal cost is to the goal state.
Vậy ta đã lập luận được rằng nó chấp nhận được mà không cần tính chi phí tối ưu thực sự tới trạng thái đích.
So we just had an abstract reasoning that told us this is indeed admissible. For example, what's the heuristic for the start state here? Well, looks like all 8 are out of place, so 8.
Vậy là ta vừa có một lập luận trừu tượng cho thấy hàm heuristic này đúng là chấp nhận được. Ví dụ, giá trị heuristic của trạng thái xuất phát ở đây là bao nhiêu? Có vẻ cả 8 ô đều sai vị trí, nên là 8.
If you run Uniform Cost Search and we have a problem where the goal is four steps away, it expands 112 nodes, eight steps away to get the to go from start state, 6,300 nodes expanded, 12 steps away, 3.6 million nodes expanded with Uniform Cost Search, A Star with this heuristic only 227.
Nếu chạy Uniform Cost Search với bài toán mà đích cách bốn bước, nó mở rộng 112 nút; cách tám bước tính từ trạng thái xuất phát thì mở rộng 6.300 nút, cách 12 bước thì Uniform Cost Search mở rộng 3,6 triệu nút, còn A Star với hàm heuristic này chỉ có 227.
So a lot of time saved. Another way to think of this heuristic is that it's a relaxed problem heuristic. What do I mean with that?
Vậy là tiết kiệm được rất nhiều thời gian. Một cách khác để nhìn hàm heuristic này là xem nó như hàm heuristic của bài toán nới lỏng. Ý tôi là gì?
One way to ensure that your heuristic is admissible is to introduce new actions. You take your original problem, you add new actions, and in this new hypothetical problem space, you find the optimal solution.
Một cách để đảm bảo hàm heuristic chấp nhận được là thêm các hành động mới. Bạn lấy bài toán gốc, thêm các hành động mới, và trong không gian bài toán giả định mới này, bạn tìm lời giải tối ưu.
And because this is the optimal solution, in a new space, we have more actions available to you, the optimal solution there will be cheaper or same as the optimal solution in the real scenario.
Vì đây là lời giải tối ưu trong không gian mới, nơi bạn có nhiều hành động hơn, lời giải tối ưu ở đó sẽ rẻ hơn hoặc bằng lời giải tối ưu trong tình huống thực.
So you know optimal in this new relaxed space is an admissible heuristic. How is this — how can we relax this? Well, like this.
Như vậy, giá trị tối ưu trong không gian nới lỏng này là một hàm heuristic chấp nhận được. Vậy nới lỏng bài này bằng cách nào? Như thế này.
Essentially what we think of here is that if every acti — if you have as an action available to just grab a tile and place onto the destination, in that space number of actions you need is equal to number of misplaced tiles.
Về cơ bản, ta nghĩ rằng nếu bạn có một hành động là lấy một ô và đặt thẳng vào vị trí đích, thì trong không gian đó số hành động cần thiết bằng số ô sai vị trí.
And it's an easier problem than the original one. It's a relaxed problem. So optimal solution in the relaxed problem is an admissible heuristic for real problem. Let's see, can we do better than this?
Và đó là bài dễ hơn bài gốc. Đó là một bài toán nới lỏng. Nên lời giải tối ưu của bài toán nới lỏng là hàm heuristic chấp nhận được cho bài toán thật. Ta có thể làm tốt hơn thế này không?
Can we have an even better heuristic meaning something that's closer to the true cost?
Có hàm heuristic nào tốt hơn nữa, tức là gần chi phí thật hơn không?
STUDENT
It's the largest number [INAUDIBLE] PROFESSOR: So one suggestion is the largest number that's misplaced. Any other suggestions? Over there.
Là số lớn nhất [KHÔNG NGHE RÕ] GIÁO SƯ: Một gợi ý là số lớn nhất trong các ô sai vị trí. Còn gợi ý nào khác không? Ở đằng kia.
STUDENT
Some of what happens [INAUDIBLE]..
Tổng của những gì xảy ra [KHÔNG NGHE RÕ].
PROFESSOR
So some of Manhattan distances for each of the tiles from where they are at the beginning to where they need to end up.
Tức là tổng các khoảng cách Manhattan của từng ô, từ vị trí ban đầu đến vị trí cuối cùng nó cần đến.
That is heuristic we have on this slide here. And how does that correspond to a relaxed problem? It's as if you can slide the tiles without them constraining each other.
Đó chính là hàm heuristic trên slide này. Nó tương ứng với bài toán nới lỏng nào? Như thể bạn trượt các ô mà chúng không cản nhau.
So it's a relaxed problem, less constrained. For Pac-Man, a relaxed would be something like ignore the walls. Here it's ignore the other tiles. It's a relaxed problem.
Vậy là bài toán nới lỏng, ít ràng buộc hơn. Với Pac-Man, nới lỏng có thể là bỏ qua các bức tường. Ở đây là bỏ qua các ô khác. Đó là một bài toán nới lỏng.
We call it total Manhattan distance. It is admissible because it's a relaxed problem solution. Another way to think of it is through more abstract reasoning.
Ta gọi nó là tổng khoảng cách Manhattan. Nó chấp nhận được vì là lời giải của bài toán nới lỏng. Một cách khác để nghĩ là qua lập luận trừu tượng hơn.
It's admissible because every tile has to undergo at least that many steps before you can achieve the goal. H for start.
Nó chấp nhận được vì mỗi ô phải đi ít nhất chừng đó bước trước khi bạn đạt được đích. Còn H của trạng thái xuất phát.
Well, we need to look at every one of these pieces and see how far they're away and sum it up.
Ta cần xét từng ô này xem nó cách đích bao xa rồi cộng lại.
And this brings it from 227 expansions for the tiles heuristic from the previous slide to only 73. Remember Uniform Cost Search was 3.6 million?
Và điều này giảm từ 227 lần mở rộng với heuristic đếm ô ở slide trước xuống chỉ còn 73. Nhớ Uniform Cost Search là 3,6 triệu không?
Having a good heuristic allows A Star Search to be much more effective than Uniform Cost Search. Of course you can A Star Search with the heuristic that's always 0.
Có hàm heuristic tốt giúp A Star Search hiệu quả hơn nhiều so với Uniform Cost Search. Tất nhiên bạn có thể chạy A Star Search với hàm heuristic luôn bằng 0.
It'll, again, have to expand 3.6 million nodes. Because it's just like Uniform Cost. How about using the actual cost as a heuristic? Would it be admissible?
Nó lại phải mở rộng 3,6 triệu nút. Vì nó giống hệt Uniform Cost. Còn dùng chính chi phí thực làm hàm heuristic thì sao? Nó có chấp nhận được không?
STUDENT
Yes.
Có.
PROFESSOR
Yes, actual cost is less than or equal to the actual cost. So that's satisfied. Would we save on nodes expanded?
Có, chi phí thực nhỏ hơn hoặc bằng chi phí thực. Vậy điều kiện được thỏa. Ta có tiết kiệm được số nút mở rộng không?
STUDENT
Yeah.
Có.
PROFESSOR
Yes, a lot. What's wrong with it?
Có, rất nhiều. Vậy nó có vấn đề gì?
STUDENT
We don't know that.
Ta không biết giá trị đó.
PROFESSOR
We don't know it. If you know it, you're done. You have already solved the problem.
Ta không biết nó. Nếu biết rồi thì xong luôn. Bạn đã giải xong bài toán rồi.
So there's a trade-off here between the amount of computational cost required to compute your heuristic and the resulting number of nodes expanded, which also takes time.
Nên ở đây có sự đánh đổi giữa lượng chi phí tính toán để tính hàm heuristic và số nút phải mở rộng, điều này cũng tốn thời gian.
So the closer heuristic gets to the true cost, the fewer nodes you tend to expand.
Hàm heuristic càng gần chi phí thật thì càng ít nút phải mở rộng.
But usually the closer you want to get to the true cost, the more work you have to do to compute the heuristic. And so that's the trade-off.
Nhưng thường càng muốn gần chi phí thật, bạn càng phải tính toán nhiều để có hàm heuristic. Đó là sự đánh đổi.
You can actually define a semilattice of heuristics. So earlier we were talking about is one heuristic better than the other one and so forth, for example, for pancake flipping.
Thực ra ta có thể định nghĩa một semilattice các hàm heuristic. Lúc nãy ta nói về việc hàm heuristic này có tốt hơn hàm kia không, v.v., ví dụ với bài lật bánh kếp.
Well, you can define this as follows. You have two heuristics.
Bạn có thể định nghĩa như sau. Có hai hàm heuristic.
And we say h (a) is dominating h(c) if for all nodes h(a) is higher than h(c). Now not all heuristics can be compared this way.
Ta nói h(a) trội hơn h(c) nếu với mọi nút h(a) lớn hơn h(c). Không phải hàm heuristic nào cũng so sánh được như vậy.
Sometimes the heuristic is higher in one node, lower in another node. Then they will live kind of next to each other like here.
Đôi khi hàm này cao hơn ở nút này, thấp hơn ở nút khác. Khi đó chúng nằm cạnh nhau như ở đây.
But if you are strictly higher in all nodes, you can put yourself above another node. For example, a is above c, and they're all above 0.
Nhưng nếu bạn cao hơn hẳn ở mọi nút, bạn có thể đặt mình ở trên hàm kia. Ví dụ, a nằm trên c, và tất cả đều nằm trên 0.
And you can build this partial ordering shown in this graph here that at the bottom has the all 00 heuristic, at the top has the exact.
Bạn có thể xây dựng thứ tự bộ phận này như trong đồ thị ở đây, dưới đáy là hàm heuristic toàn 0, trên đỉnh là hàm chính xác.
And the further you go to the top, the more informative your heuristic is but possibly more expensive to compute.
Càng lên cao, hàm heuristic càng nhiều thông tin nhưng có thể tốn kém hơn để tính.
And one last little trick is that if you have two heuristics, you take the max, double dominate them.
Và một mẹo nhỏ cuối cùng là nếu bạn có hai hàm heuristic, bạn lấy max, nó sẽ trội hơn cả hai.
And so if you have two heuristics that are both admissible, the max will be admissible and will be more informative than either one of them.
Vậy nếu bạn có hai hàm heuristic đều chấp nhận được, thì max cũng chấp nhận được và có nhiều thông tin hơn từng hàm riêng lẻ.
In the last kind of 10 minutes that we have here, I want to switch up the algorithm that's powering all of this.
Trong khoảng 10 phút cuối còn lại, tôi muốn chuyển sang thuật toán đứng đằng sau tất cả những điều này.
So, so far we've done Tree Search and what's been different across approaches is the strategy of what to expect next from the fringe. Now we're going to change Tree Search into Graph Search.
Cho đến giờ ta đã làm Tree Search, và điểm khác nhau giữa các cách tiếp cận là chiến lược chọn nút tiếp theo để mở từ biên. Bây giờ ta sẽ biến Tree Search thành Graph Search.
Why? Well, on the left this is state graph. And on the right there's a Search Tree for this. If you look at this, well, b appears multiple times, c appears multiple times.
Tại sao? Bên trái đây là đồ thị trạng thái. Còn bên phải là cây tìm kiếm của nó. Nhìn vào đây, b xuất hiện nhiều lần, c cũng xuất hiện nhiều lần.
There will be exponential growth in terms of how often a node appears. And do we really need that?
Số lần một nút xuất hiện sẽ tăng theo cấp số mũ. Và ta có thực sự cần điều đó không?
Do we really need to keep track of all past a00 from a to b to c and so forth or might it be that just one of them is enough?
Ta có thực sự cần theo dõi mọi đường đi từ a đến b đến c, v.v. không, hay chỉ cần một trong số chúng là đủ?
Like, might it be that just this c is enough. And once we've looked here, we don't need to look here or here or here anymore.
Ví dụ, có thể chỉ cần c này là đủ. Và khi đã xét ở đây rồi, ta không cần xét ở đây, đây hay đây nữa.
Because if we could do that, we could save a lot of time. And that's exactly with Graph Search proposes.
Vì nếu làm được vậy, ta tiết kiệm được rất nhiều thời gian. Và đó chính xác là điều Graph Search đề xuất.
Graph Search will keep track of a list of nodes you've expanded and not expand them again.
Graph Search theo dõi danh sách các nút đã mở và không mở lại chúng.
For example, in Breadth-first search you have — this is the Search Tree and we should not expand these nodes. Why not?
Ví dụ, trong Breadth-first search bạn có — đây là cây tìm kiếm và ta không nên mở các nút này. Tại sao không?
Why should we not expand this one over here? E is also over here. And if it's Breadth-first search, this way of getting to e is better than this way.
Tại sao không nên mở nút này ở đây? E cũng nằm ở đây. Và với Breadth-first search, cách đến e này tốt hơn cách này.
Because this one takes one step. This one takes two steps. So we already got there in one step. We should not later, again, see what's underneath e.
Vì cách này mất một bước. Cách này mất hai bước. Ta đã đến đó trong một bước rồi. Sau này ta không nên xem lại những gì bên dưới e.
Because we got there in a worse way. So anything we find underneath here is worse than anything we find underneath here. Because we got to be e with more cost.
Vì ta đã đến đó bằng cách tệ hơn. Nên bất cứ thứ gì tìm thấy bên dưới đây đều tệ hơn thứ gì tìm thấy bên dưới đây. Vì ta đến e với chi phí lớn hơn.
And what's underneath is the same anyway. We're not going to find anything new here. We're just going to have gotten there in a worse way. There's no point in doing all that work again.
Mà phần bên dưới thì vốn giống nhau. Ta sẽ không tìm thấy gì mới ở đây. Ta chỉ đến đó theo cách tệ hơn thôi. Không có lý do gì làm lại tất cả công việc đó.
So the idea in Graph Search is you never expand a state twice. How do implement this? It's just like Tree search.
Vậy ý tưởng của Graph Search là không bao giờ mở một trạng thái hai lần. Cài đặt thế nào? Giống hệt Tree Search.
But you have a set of expanded states, which we'll call the closed set.
Nhưng bạn có một tập các trạng thái đã mở, gọi là closed set.
The closed set, whenever you expand, whenever you call a successor function on a state, you first do a quick sanity check. Have I already called a successor function on this state?
Với closed set, mỗi khi bạn mở, mỗi khi bạn gọi hàm kế tiếp trên một trạng thái, trước tiên bạn kiểm tra nhanh. Mình đã gọi hàm kế tiếp trên trạng thái này chưa?
The closed set will tell you. If you have, skip it. Just you don't do it. If you haven't, you do call your successor function.
Closed set sẽ cho bạn biết. Nếu rồi, bỏ qua. Đơn giản là không làm. Nếu chưa, bạn gọi hàm kế tiếp.
But then you add the state to the closed set.
Rồi thêm trạng thái đó vào closed set.
It's important to store it is as a set, not a list. Some literature even calls it closed list. When they call it closed list, same thing. But it's not great terminology.
Quan trọng là lưu nó dưới dạng tập hợp, không phải danh sách. Một số tài liệu còn gọi là closed list. Khi họ gọi là closed list thì vẫn là một thứ. Nhưng thuật ngữ đó không hay.
Because if you store it as a list, the time it takes to traverse the list and find whether you're in there or not is much worse than when it's stored as a set.
Vì nếu bạn lưu nó dưới dạng danh sách, thời gian duyệt danh sách để tìm xem có trong đó hay không tệ hơn nhiều so với khi lưu dưới dạng tập hợp.
And your algorithm will be really slow. So that's why we call it explicitly closed set. And you should code it up as a set. Then it [? right ?] completeness.
Và thuật toán của bạn sẽ rất chậm. Vì vậy ta gọi rõ ràng là closed set. Và bạn nên cài đặt nó dưới dạng tập hợp. Còn tính đầy đủ (completeness) thì sao?
Well, let's think about it. So what does it mean to be complete? It means that if a solution exists, you'll find it. What do we not do?
Ta hãy nghĩ thử. Đầy đủ nghĩa là gì? Nghĩa là nếu có lời giải thì bạn sẽ tìm ra. Ta bỏ qua cái gì?
Which part of a Search Tree do we exclude here? It's parts of the Search Tree that we already have expansions for.
Ta loại phần nào của cây tìm kiếm ở đây? Đó là những phần của cây tìm kiếm mà ta đã có sự mở rộng rồi.
So if we exclude something by doing Graph Search, it's something we already have somewhere else anyway, so we're not losing access to the goal by what we're excluding in our expansions.
Nên nếu ta loại bỏ thứ gì bằng Graph Search, thì đó là thứ ta vốn đã có ở chỗ khác, nên ta không mất khả năng đến đích do những gì ta loại khỏi các lần mở rộng.
So still complete. How about optimality? Oh, that one's trickier. So let's look at A Star Graph Search gone wrong suggesting that it's not always optimal.
Vậy vẫn đầy đủ. Còn tính tối ưu thì sao? À, cái đó khó hơn. Hãy xem một trường hợp A Star Graph Search bị sai, cho thấy nó không phải lúc nào cũng tối ưu.
So here are some heuristics. Here is some costs. Search Tree, expand, expand, expand, expand. We build our Search Tree.
Đây là một số hàm heuristic. Đây là một số chi phí. Cây tìm kiếm, mở, mở, mở, mở. Ta xây dựng cây tìm kiếm.
What do we do now? Well, we found the bad path to the goal. But luckily we don't expand yet. We're going to expand this one first.
Giờ ta làm gì? Ta đã tìm thấy đường đi tệ đến đích. Nhưng may là ta chưa mở nó. Ta sẽ mở nút này trước.
And now we've gotten here and here. But what will Graph Search say? My closed set already has c on it. So I'm not expanding this.
Và giờ ta đã đến đây và đây. Nhưng Graph Search sẽ nói gì? Closed set của tôi đã có c rồi. Nên tôi không mở cái này.
And now the only thing that's left is this thing here. And we declare success. So what happened here is that we first expanded along this path.
Và giờ chỉ còn lại cái này ở đây. Và ta tuyên bố thành công. Vậy chuyện xảy ra là ta mở theo đường này trước.
And then later when we found the better path to c, we said, we already expanded from c. Let's skip it this time.
Rồi sau đó khi tìm thấy đường tốt hơn đến c, ta nói, ta đã mở từ c rồi. Lần này bỏ qua đi.
So we need to be careful in Graph Search, the first time we expand, it's actually when we were there in an optimal way. Because if not, we might never do the optimal way.
Nên ta phải cẩn thận trong Graph Search: lần đầu ta mở một nút, thực ra phải là lúc ta đến đó theo cách tối ưu. Vì nếu không, ta có thể không bao giờ đi theo cách tối ưu.
In fact, we will never do it the optimal way. So the issue here is some kind of poor choice of heuristics in some sense guiding us down the wrong path at that time.
Thực tế, ta sẽ không bao giờ đi theo cách tối ưu. Vậy vấn đề ở đây là một kiểu chọn heuristic kém theo nghĩa nào đó đã dẫn ta đi sai đường lúc đó.
So what we need is more than Admissible Heuristics. We need consistent heuristics.
Vậy ta cần nhiều hơn heuristic chấp nhận được. Ta cần heuristic nhất quán.
The main idea is that the estimate heuristic costs are not just more than actual cost to the goal, but everywhere things need to be representative.
Ý chính là chi phí ước lượng của heuristic không chỉ lớn hơn chi phí thực tế đến đích, mà ở mọi nơi các giá trị đều phải phản ánh đúng.
So admissibility was just about cost to the goal and heuristic. And that's what we have here. Consistency will be about locally checking that things are consistent within the heuristic and the actual cost.
Vậy tính chấp nhận được chỉ liên quan đến chi phí tới đích và hàm heuristic. Và đó là những gì ta có ở đây. Tính nhất quán là kiểm tra cục bộ rằng hàm heuristic có nhất quán với chi phí thực tế.
So here in that graph we just looked at, we have h of 4 over here, h of 1 over here, and a cost of 1 here. That is inconsistent.
Trong đồ thị vừa xem, ta có h bằng 4 ở đây, h bằng 1 ở đây, và chi phí là 1 ở đây. Như vậy là không nhất quán.
If we think from 8 is going to be 4, but then after one step, at a cost of 1, we think it's 1, that doesn't make sense.
Nếu từ a ta ước lượng là 4, nhưng sau một bước với chi phí 1 mà ta lại ước lượng là 1 thì vô lý.
If we really think it's 1 from c, we should think it's 2 from a. There's an inconsistency in our heuristic choices there. If we make it 2, it becomes consistent.
Nếu ta thực sự nghĩ từ c là 1, thì từ a ta phải nghĩ là 2. Có sự không nhất quán trong cách chọn heuristic ở đó. Nếu đặt là 2, nó sẽ nhất quán.
And if we revisit the previous example, it'll find the optimal solution. Consequence of consistency, the f value along a path never decreases. Why is that?
Và nếu xét lại ví dụ trước, nó sẽ tìm ra lời giải tối ưu. Hệ quả của tính nhất quán: giá trị f dọc theo một đường đi không bao giờ giảm. Tại sao vậy?
We have a heuristic value. And the heuristic value is smaller than — this is consistency. So consistency means this. Then we just add backward cost on both sides.
Ta có một giá trị heuristic. Và giá trị heuristic này nhỏ hơn... đây chính là tính nhất quán. Tức là nhất quán nghĩa là như vậy. Rồi ta cộng chi phí ngược vào cả hai vế.
Together that makes for f.
Cộng lại ta được f.
And what we see here is that f of a, the node we started from, and c, the node we got after the expansion, f of a is smaller than f of c.
Và ta thấy f của a, nút xuất phát, và c, nút có được sau khi mở rộng, thì f của a nhỏ hơn f của c.
So what we see is consistency implies as we expand, f will go up and up and up and up.
Vậy nhất quán kéo theo khi ta mở rộng, f sẽ tăng lên mãi.
And that goes back to some of the original intuition in one of the questions said, if we have consistency, which is a stronger condition than admissibility, f will keep going up as we expand.
Điều này quay lại trực giác ban đầu ở một câu hỏi: nếu có tính nhất quán, vốn là điều kiện mạnh hơn tính chấp nhận được, thì f sẽ liên tục tăng khi ta mở rộng.
And that means then if we have consistency, whenever we expand the goal state, we know we're done. And we found the optimal path.
Và như vậy, nếu có tính nhất quán, khi nào mở rộng trạng thái đích là ta biết đã xong. Và ta đã tìm được đường đi tối ưu.
Because everything else will have a higher f cost on the fringe. Because otherwise we would have done it first. Whenever we expand the goal, everything else is a higher f.
Vì mọi thứ khác trên biên đều có chi phí f cao hơn. Vì nếu không thì ta đã mở rộng nó trước rồi. Khi mở rộng đích, mọi thứ khác đều có f cao hơn.
And thanks to consistency, we see that after we expand the node, f goes up. So in the future, every f will be even higher.
Và nhờ tính nhất quán, ta thấy sau khi mở rộng nút, f tăng lên. Nên về sau mọi f sẽ còn cao hơn.
And so consistency implies f costs keep going up as we run the search, which in terms implies that when we expand the goal, there is no option left for us to ever encounter something with lower f cost.
Vậy nhất quán kéo theo chi phí f liên tục tăng khi chạy tìm kiếm, điều này lại kéo theo rằng khi ta mở rộng đích, sẽ không còn khả năng nào gặp được nút có chi phí f thấp hơn.
There is a more formal proof on this in the slides here. But since we only have two minutes left, I'm just going to leave you with that main intuition that's really important.
Trong slide có một chứng minh hình thức hơn. Nhưng vì chỉ còn hai phút, tôi chỉ để lại cho các bạn trực giác chính, rất quan trọng này.
If you have a consistent heuristic, f cost will keep going up, which in turn means when you expand the goal, nothing else could ever be lower again in the future.
Nếu có hàm heuristic nhất quán, chi phí f sẽ liên tục tăng, nghĩa là khi bạn mở rộng đích, sẽ không còn gì khác thấp hơn nữa trong tương lai.
These are the optimality properties for both Tree Search and Graph Search, different conditions. One implies the other.
Đây là các tính chất tối ưu của Tree Search và Graph Search, với các điều kiện khác nhau. Điều này kéo theo điều kia.
That's just applying the consistency to the path to the goal. And here's a summary, A Star uses both backward and forward cost.
Đó chỉ là áp dụng tính nhất quán lên đường đi tới đích. Và đây là tóm tắt: A Star dùng cả chi phí ngược và chi phí xuôi.
It's optimal for Tree Search for the admissible heuristics, for Graph Search with consistent heuristics. Heuristic design is key to make it good.
Nó tối ưu với Tree Search khi heuristic chấp nhận được, và với Graph Search khi heuristic nhất quán. Thiết kế heuristic là chìa khóa để nó hiệu quả.
And in your Project One you'll do a lot of heuristic design to make your algorithm go fast. Often you'll use relaxed problems to get there.
Và trong Project One bạn sẽ thiết kế heuristic khá nhiều để thuật toán chạy nhanh. Thường bạn sẽ dùng các bài toán nới lỏng để làm được vậy.
The slides have pseudocodes for you, which will be useful for your project and a more formal proof of optimality of A Star Graph Search, which you can do in your own time.
Slide có mã giả cho các bạn, sẽ hữu ích cho project và có chứng minh hình thức hơn về tính tối ưu của A Star Graph Search, các bạn có thể tự xem khi rảnh.
Thank you.
Cảm ơn các bạn.
[SIDE CONVERSATIONS]
[CÁC CUỘC TRÒ CHUYỆN RIÊNG]
Đă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.