Материал готовится,

пожалуйста, возвращайтесь позднее

пожалуйста, возвращайтесь позднее

OPERATOR: — The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseWare continue to offer high quality educational resources for free. To make a donation, or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu.

PROFESSOR: At the end of the lecture on Tuesday, a number of people asked me questions, asked Professor Grimson questions, which made it clear that I had been less than clear on at least a few things, so I want to come back and revisit a couple of the things we talked about at the end of the lecture.

You'll remember that I had drawn this decision tree, in part because it's an important concept I want you to understand, the concept of decision trees, and also to illustrate, I hope, visually, some things related to dynamic programming. So we had in that decision tree, is we had the weight vector, and I just given a very simple one [5,3,2], and we had a very simple value vector, [9,7,8]. And then the way we drew the tree, was we started at the top, and said all right, we're going to first look at item number 2, which was the third item in our list of items, of course, and say that we had five pounds left of weight that our knapsack that could hold, and currently had a value of 0. And then we made a decision, to not put that last item in the backpack, and said if we made that decision, the next item we had to consider was item 1, we still had five pounds available, and we still had a weight available.

Now I, said the next item to consider is item 1, but really what I meant is, 1 and all of the items proceeding it in the list. This is my shorthand for saying the list up to and including items sub 1, kind of a normal way to think about it. And then we finish building the tree, left first step first, looking at all the no branches, 0,5,0 and then we were done, that was one branch. We then backed up, and said let's look at a yes, we'll include item number 1. Well, what happens here, if we've included that, it uses up all the available weight, and gave us the value of 9.

STUDENT: [UNINTELLIGIBLE]

PROFESSOR: Pardon?

STUDENT: — want to be off the bottom branch.

PROFESSOR: Yup, Off by 1. Yeah, I wanted to come off this branch, because I've backtrack just 1, thank you. And then I backtrack up to this branch, and from here we got 0,2,7. And I'm not going to draw the rest of the tree for you here, because I drew it last time, and you don't need to see the whole tree. The point I wanted to make is that for every node, except the leaves, the leaves are the bottom of a tree in this case, computer scientists are weird, right, they draw trees where the root is at the top, and the leaves are at the bottom. And I don't know why, but since time immemorial that is the way computer scientists have drawn trees. That's why we're not biologists, I guess. We don't understand these things.

But what I want you to notice is that for each node, except the leaves, the solution for that node can be computed from the solutions from it's children. So in order to look at the solution of this node, I choose one of the solutions of it's children, a or b, is the best solution if I'm here, and of course this is the better of the 2 solutions. If I look at this node, I get to choose its solution as the better of the solution for this node, and this node.

PROFESSOR: At the end of the lecture on Tuesday, a number of people asked me questions, asked Professor Grimson questions, which made it clear that I had been less than clear on at least a few things, so I want to come back and revisit a couple of the things we talked about at the end of the lecture.

You'll remember that I had drawn this decision tree, in part because it's an important concept I want you to understand, the concept of decision trees, and also to illustrate, I hope, visually, some things related to dynamic programming. So we had in that decision tree, is we had the weight vector, and I just given a very simple one [5,3,2], and we had a very simple value vector, [9,7,8]. And then the way we drew the tree, was we started at the top, and said all right, we're going to first look at item number 2, which was the third item in our list of items, of course, and say that we had five pounds left of weight that our knapsack that could hold, and currently had a value of 0. And then we made a decision, to not put that last item in the backpack, and said if we made that decision, the next item we had to consider was item 1, we still had five pounds available, and we still had a weight available.

Now I, said the next item to consider is item 1, but really what I meant is, 1 and all of the items proceeding it in the list. This is my shorthand for saying the list up to and including items sub 1, kind of a normal way to think about it. And then we finish building the tree, left first step first, looking at all the no branches, 0,5,0 and then we were done, that was one branch. We then backed up, and said let's look at a yes, we'll include item number 1. Well, what happens here, if we've included that, it uses up all the available weight, and gave us the value of 9.

STUDENT: [UNINTELLIGIBLE]

PROFESSOR: Pardon?

STUDENT: — want to be off the bottom branch.

PROFESSOR: Yup, Off by 1. Yeah, I wanted to come off this branch, because I've backtrack just 1, thank you. And then I backtrack up to this branch, and from here we got 0,2,7. And I'm not going to draw the rest of the tree for you here, because I drew it last time, and you don't need to see the whole tree. The point I wanted to make is that for every node, except the leaves, the leaves are the bottom of a tree in this case, computer scientists are weird, right, they draw trees where the root is at the top, and the leaves are at the bottom. And I don't know why, but since time immemorial that is the way computer scientists have drawn trees. That's why we're not biologists, I guess. We don't understand these things.

But what I want you to notice is that for each node, except the leaves, the solution for that node can be computed from the solutions from it's children. So in order to look at the solution of this node, I choose one of the solutions of it's children, a or b, is the best solution if I'm here, and of course this is the better of the 2 solutions. If I look at this node, I get to choose its solution as the better of the solution for this node, and this node.

Загрузка...

Выбрать следующее задание

Ты добавил

Выбрать следующее задание

Ты добавил