Name: 21.TSPアルゴリズムのチューニング (21. Tuning a TSP Algorithm)
Uploaded: 2021-01-14T10:27:04.000Z
Duration: 1 h 20 min 53 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

基礎受動態

The following content is provided under a Creative

Your support will help MIT OpenCourseWare

continue to offer high-quality educational resources for free.

To make a donation or to view additional materials

from hundreds of MIT courses, visit MIT OpenCourseWare

CHARLES LEISERSON: It is my great pleasure

to welcome Jon Bentley, now retired from Bell Labs.

Jon was my PhD thesis supervisor at Carnegie Mellon.

The other one was HT Kung, who is now at Harvard.

I guess people flee Carnegie Mellon like the plague

studied some of his work, is a pioneer in software performance

And he's going to talk today about a particularly neat piece

centers around the so-called traveling salesperson problem,

And so, without further ado, Jon, why don't you

I want to tell you a story about a cool problem.

This is a problem that I first heard when I was a young nerd--

not much older than this little pile of nerds in front of me--

in high school, the traveling salesperson problem.

Who here has heard of the TSP at some point?

I heard about this in high school, one of the things

And a few years later, I had a chance to work on it.

and I said, well, what you need to do is solve a TSP.

of the stuff that I learned about it was sort of relevant

So I've been hooked for coming up on 40 years now.

And I want to tell you one story about a really cool program I

I've been paid to be a computer programmer for coming up

on 50 years, since I've been doing it for 48 years now.

This is probably the most fun, the coolest program

Start off with what recursive generation is.

and we'll make it faster and faster and faster.

Again, I spend my whole life squeezing performance.

We'll start, though, with how do you enumerate

enumerate the guys between 1 and a hundred, I just count.

all subsets of the set from the integers from 1 to 5?

How many subsets are there of integers from 1 to 5?

Well, you have to decide how you represent it.

You guys know all about set representations.

We'll stick with bit vectors for the time being.

An iterative solution is you just count--

What does it mean to go from one integer to the next?

How do you go from a given integer to the next one?

You just scan over all the 0's, turning the-- you start

at the right-hand side, the least significant digit,

You scan over all the 1's, turning them to 0

This one goes-- that one becomes 0, that one becomes 0.

字幕リスト動画再生

21.TSPアルゴリズムのチューニング (21. Tuning a TSP Algorithm)

sort

approach

effective

audience