How to Solve It�1. Prologue

Cong Li

Feb. 27th ~ Mar. 6th, 2021

Prologue of the Prologue

How to Solve It: 1. Prologue

I am not talking on algorithms only, though I will talk quite a lot of algorithms …

I would like to talk on how to frame problems, and solve them effectively and creatively …

Based on the book

Zbigniew Michalewicz and David B. Fogel (2000). How to Solve it: Modern Heuristics, Springer-Verlag.

Problem Solving (1)

• Examples of Real World Problems
• Big problem: minimizing cost in containing COVID-19 breakout
• Small problem: the best path to go back to your home from a place
• Compute problem: a complex neural network fitting the training data
• Problems
• Exist in peoples’ life and work
• A great deal to be gained from solving problem, but a great deal to be lost in solving problem poorly

How to Solve It: 1. Prologue

Problem Solving (2)

• Problem Solving
• To solve real world problems
• Sometimes (not always) under the aids of computers when the problems are large
• In Nowadays
• Advanced science and technologies
• We know more information
• We may change and affect more things
• (We have more computing power)
• Problem solving becomes more difficult

​

How to Solve It: 1. Prologue

Algorithm

• Definitions of Algorithm
• A precise rule (or set of rules) specifying how to solve some problems
• A finite set of well-defined instructions for accomplishing some tasks
• Classical Algorithm Characteristics
• Given an initial state, will result in a corresponding recognizable end-state

How to Solve It: 1. Prologue

Problem Solving ≠ Algorithms (1)

• Misunderstanding
• People would like to frame the problem (which can be solved with existing tools) simply without deep considerations
• People would like to have a universal algorithm which can solve all the problems like a magic
• Results
• Such solutions are simply not reliable

How to Solve It: 1. Prologue

Problem Solving ≠ Algorithms (2)

• Problem Solving and Algorithms
• Algorithms are used in problem solving
• Algorithms only are not all of problem solving
• Other than Algorithm Itself
• Formulate a mathematical representation of the problem
• Choose an appropriate algorithm

How to Solve It: 1. Prologue

Problem Formulation (1)

• Mathematical Models
• A representation of real world problem
• Make it feasible to be solved on computer (using some algorithms)
• Abstraction
• Only some (important), not all the factors can be included in models
• We don’t know all the factors
• We cannot consider too many (hundreds of thousands of) factors

How to Solve It: 1. Prologue

Problem Formulation (2)

• Simple Models
• Lead to an easy application of classical and reliable algorithms
• Result in greater difference between realistic and abstractions
• In some cases the difference makes the solution unreliable
• Complex Models
• Closer gap between realistics and abstractions
• Difficult (sometimes intractable) to solve

How to Solve It: 1. Prologue

Solutions

• Win or Loss
• May be concluded by a slight advantage
• Precise Algorithms
• Result in precise results
• May be slower in solving
• Approximated Algorithms
• Result in approximated results
• May be much faster

How to Solve It: 1. Prologue

Decision Making

• Decisions
• Trade-off between model complexity and model precision
• Trade-off between quality of solutions and difficulty of methods
• To Make a Good Decision
• One should know the assumptions, complexities, and reliabilities of different methods

How to Solve It: 1. Prologue

Common Mistakes (1)

• Tuning Problems to a Method
• Treat everything as a nail when holding an hammer, even it is a screw
• Example
• Modify the problems or objectives to fit to classical problem solving methods
• All the models are linear or smooth
• Solution looks perfect, but not practical

How to Solve It: 1. Prologue

Common Mistakes (2)

• Choosing Algorithms
• Algorithms are introduced independently
• Simply look up algorithms in books to solve the problem
• Effective Problem Solving
• Not only know the characteristics of algorithms, but creatively use or combine them as well

How to Solve It: 1. Prologue

Unfortunate Things

• In Our Early Educations
• Learn to decompose and solve small problems independently
• Example
• In mathematical books, after introducing how to solve quadratic equations, we have an exercise:
• The perimeter of a farm is 110m, and the area of it is 700m², then what is the length of each edge?

How to Solve It: 1. Prologue

Results

• Lessons Learned
• Relations between methods and problems should not be discussed focusing on the methods, but on the problems
• Otherwise
• Students do not get accustomed to think of the problems independently

How to Solve It: 1. Prologue

A Problem

How to Solve It: 1. Prologue

Try to prove AB + AC > DB + DC

About the Course (1)

• Prerequisites
• Knowledge and skills on mathematics
• Knowledge on data structure
• Programming skills
• Preparation
• Select a programming language and its corresponding development environment
• Notice
• The result demanded by me is the answer, not the program you write

​

How to Solve It: 1. Prologue

About the Course (2)

• What I will Talk
• Various problems
• Classical algorithms and modern heuristics
• How to construct and solve problems
• Notice
• I am not a top expert on problem solving, but I would like to share my knowledge in problem solving
• You are expected to be active in solving problems by yourselves

How to Solve It: 1. Prologue

The End

Backup

Another Problem

How to Solve It: 1. Prologue

h = ?