EXHAUSTIVE ENUMERATION IMPRACTICAL

• CONSIDER TRAVELLING SALESPERSON PROBLEM

• ASSUME

20-CITY PROBLEM TAKES ABOUT 1 HOUR

• THEN

21-CITY PROBLEM TAKES ABOUT 20 HOURS

22-CITY PROBLEM TAKES ABOUT 20 DAYS

•

•

25-CITY PROBLEM TAKES ABOUT 6 CENTURIES!!

Previous slide

Next slide

Back to first slide

View graphic version