COMPSCI 188 - 2018-08-30 - A* Search and Heuristics

Рет қаралды 50,054

Күн бұрын

COMPSCI 188, LEC 001 - Fall 2018
COMPSCI 188, LEC 001 - Pieter Abbeel, Daniel Klein
Copyright @2018 UC Regents; all rights reserved
"Slides (from 2018): inst.eecs.berkeley.edu/~cs188...
Latest website: inst.eecs.berkeley.edu/~cs188
More resources: ai.berkeley.edu
00:00 Setup [no content]
02:57 Announcements [outdated]
07:50 Recap: Search
15:54 Uninformed Search
18:56 Heuristics
25:40 Greedy Search
31:56 A* Search
39:34 Admissibility of Heuristics
44:09 Optimality of A*
49:09 Break [no content]
54:17 A* Q&A
1:01:15 Properties of A*
1:06:45 Creating Heuristics
1:14:08 Graph Search
1:18:53 Consistency of Heuristics
1:22:33 End [no content]"

Пікірлер: 21

@michaelj7677 5 жыл бұрын

2:57 Start 7:50 Begin of content 54:11 After break

@quiteSimple24 5 жыл бұрын

Thanks

@peteleyden6507 3 жыл бұрын

Not all heroes wear capes

@sridharbabumudhangulla2430 3 жыл бұрын

Dr. Pieter Abbeel, you are the best. Your explanation is very intuitive.

@pedramsafari3869 3 жыл бұрын

It's amazing that this course is for free. Thanks! One little mistake I found @ 1:00:04 : "from n the cheapest way to get to a goal has to cost *less* than h(n)" should be "from n the cheapest way to get to a goal has to cost *more* than h(n)"

@rita9651 2 жыл бұрын

Great lecture!

@jatinsaini7790 3 жыл бұрын

Best lecture, the way you structured the flow of topics is just the best I ever seen for this topic!! Great sir! Awesome

@user-fc9hs2hg2n 5 жыл бұрын

Where can we(non-ucb students) find the electronic homework? The 2014 version of cs188 on edx always shows "This XML file does not appear to have any style information associated with it. The document tree is shown below" when clicking on any of the python files or "zip archive". Please help us because most stuff can only be learnt through exercises.

@binxuwang4960 3 жыл бұрын

1:09:54 is great point, heuristic comes from relexing constraint or solving a easier problem, but not comes by being greedy since you can be inoptimal that way

@yulogs. 2 жыл бұрын

Hopefully have a chance study in UC Berkeley and under supervised by Prof. Pieter Abbeel

@alexandre-ob1nf 3 жыл бұрын

who dares to dislike this video?

@Nu2526 4 жыл бұрын

how can I find the slides of this lecture?

@devmahad 4 ай бұрын

00:00 Setup [no content] 02:57 Announcements [outdated] 07:50 Recap: Search 15:54 Uninformed Search 18:56 Heuristics 25:40 Greedy Search 31:56 A* Search 39:34 Admissibility of Heuristics 44:09 Optimality of A* 49:09 Break [no content] 54:17 A* Q&A 1:01:15 Properties of A* 1:06:45 Creating Heuristics 1:14:08 Graph Search 1:18:53 Consistency of Heuristics 1:22:33 End [no content]"

@sanjanachopra2100 4 жыл бұрын

Topic: A* Search and admissibility and consistency of heuristics

@siruili7924 11 ай бұрын

The graph in 1:18:49. I changed the h(A)=2 to make the heuristic consistent but the solution is still S-B-C-G in A* graph search because B(1+1)

@SaurabhKumar-lu7su 3 жыл бұрын

@43:50, he says that taking id of the largest cake still out of place is optimistic but it doesn't satisfy the heuristic condition. Consider (3,1,2,4) with 3 at top and 4 at bottom. h(n) = 3 as it's the biggest cake out of place but actually it is only 2 steps away from goal as (3,1,2,4) -> (2,1,3,4) -> (1,2,3,4). what am I getting wrong?

@pedramsafari3869 3 жыл бұрын

The cost of a step/flip is not 1 but rather the number of pancakes flipped (see @11:25).

@kellyzhang6012 4 жыл бұрын

Every course materials you want: inst.eecs.berkeley.edu/~cs188/fa18/

@smolllee3818 5 жыл бұрын

why not let the definition of admissible be h(n)-h(Goal)

@quiteSimple24 5 жыл бұрын

h(Goal) is always 0

@smolllee3818 5 жыл бұрын

@@quiteSimple24oh, I was thinking the heuristic just need to be smaller when it is closer to the goal. now I watched it again, and it's always h(goal) = 0. I still think it doesn't have to be, but keep it to 0 sure is more convenient.