Features
Features:

Product Tour >

Edraw AI >

Paid Plans:

Individuals >

Business >

Eduaction >
Resources
Blog

History

How-tos & Tips

Discovery

Biography

Business Analysis

Examples

AI concept Map

Free AI Mind Map Generator

Onenote Mind Map

Bcg Matrix Examples

Nike Marketing Strategy

Unilever SWOT Analysis

Make Mind Maps in Google Docs

Guide

FAQs

What's New

Resource Center
Templates
All Templates

Brain Storming Templates

Strategy and Planning Templates

Project Management Templates

Product Management Templates

Human Resources Templates

Agile Workflow Templates

Marketing Templates

Education Templates

Fun and Games Templates

User Gallery
Download
Pricing
Enterprise

MindMap Gallery General knowledge of algorithms

General knowledge of algorithms

Share the complete version of Algorithm General Knowledge! The content includes understanding algorithms, designing algorithms, algorithm strategies and algorithm preface. The map is rich and detailed, friends, let’s start learning~

Edited at 2023-03-14 21:49:53

PlotWizard

Recent works View more works>>

General knowledge of algorithms

PlotWizard

Recent works View more works>>

Recommended to you
Outline

General knowledge of algorithms

Understanding algorithms

Nature

Algorithms have extremely stringent requirements for clarity

eg. Matchmaker’s experience: Live close – how close is considered close? close to home? Close to work? Prioritization between multiple locations...

Algorithms solve problems with deterministic guarantees

Modeling is the essence of algorithm advantage

eg. When shopping for a thermos kettle online, the thermos kettle is always recommended; when searching for "The Wind", various spy movies are recommended.

Modeling: treat different problems in the same way and solve them with the same set of algorithms

Algorithms are not good or bad, they are all human thoughts behind them

the complexity

Difficulties in evaluating algorithm efficiency: using absolute time to evaluate efficiency is not applicable

Hardware dependencies

gigantic

time complexity

"Functional relationship" in which the "total number of basic operations" grows with the "input size" of the algorithm

eg. To build a 10-meter-high pyramid, the design drawing determines whether 100,000 stones or 500,000 stones should be built: Stone base = basic operation; 10 meters = input scale; drawing = total amount of stone base; the functional relationship between the total amount of stone base and the height of the pyramid is the time complexity

Ways to reduce time complexity

space for time

Space complexity: a functional relationship in which the space resources occupied by the algorithm increase as the input size increases.

It is very cost-effective to sacrifice some storage space (hard disk/memory) in exchange for faster search speed.

divide and conquer thinking

eg. From Fourier transform to fast Fourier transform, compressing audio takes from 1 day to 1 second

Inspire

Utility choice model: approximating reality while maintaining solvability

Utility: Satisfaction

eg. Whether American voters vote or not is affected by many factors such as gender, ethnicity, education level, occupation, etc. There are too many factors that affect utility, and some factors even have complex correlations.

If the model is too complex, the solution cannot be obtained; in this case, the model must be simplified; it is assumed that the relationship between all factors is only linear superposition without complex interactions; this is called a linear effect model

Texas Hold'em Poker: Problem Size Reduction

The scale is too large for computers to handle, so you have to find a way to throw away some information.

eg. Texas Hold'em: Merge similar states

Explore and exploit: iterate to get results

eg. The video website will initially recommend various contents to you, and after a while it will start to recommend the contents you watch most often.

Reflection: Algorithms can only execute and cannot be held responsible; if there is a problem with the algorithm, we have to go back to humans to find the answer.

Algorithms cannot be held responsible for problems

eg. Both bookstores set their own prices at multiples of the other’s prices, resulting in unusually high prices.

Algorithms cannot be responsible for data

eg. I took iced black tea for a urine test and found that the sugar level exceeded the standard, indicating that I was suspected of having diabetes.

Algorithms cannot be held accountable for interpretation

eg. IBM builds Watson medical diagnosis system, but the algorithm cannot provide explanations

design algorithm

Algorithm blueprint

clarify the problem

clear purpose

eg. Match all taxi passengers or match as many passengers as possible as quickly as possible

Clear restrictions

eg. The waiting time for passengers in urban areas cannot exceed 1 minute.

Clarify evaluation criteria

eg. time or cost benefit

Modeling

It is the process of converting real problems into algorithmic problems, and it is also the process of abstracting away a lot of details.

Before designing an algorithm, a mathematical model must be established

Model iteration is very important

Algorithm selection

Determined by the level of achieving the goal and the time complexity

Iterate

algorithms, hardware

Modeling

Determine the hypothesis

Determine the accuracy requirements for prediction results, discard unimportant details, and clarify and quantify fuzzy issues

Validate model

Use common sense to verify; use historical data to verify

Weigh feasibility

It should be close to reality and easy to solve.

Algorithm selection

Relationship: Models and algorithms are not one-to-one correspondence

eg. knapsack problem

Choice: The trade-off between quality and efficiency

eg. The decision to place online ads needs to be done instantly and uses a greedy algorithm;

eg. When planning to protect wild animals, we must find the optimal solution as much as possible and use the branch and bound algorithm.

Advanced: More considerations for algorithm engineers

Prefer algorithms with low data sensitivity, few restrictions, and little dependence on data

algorithm strategy

Iterate

Iterative algorithm: An algorithm that repeats a fixed operation through a loop, with each step starting from the result of the previous step and gradually approaching the answer.

The conditions for the iterative algorithm to be effective: first, the algorithm must converge; second, the fixed point must be unique

The iterative strategy allows for errors in the process of finding the solution, and this error decreases very quickly, so the iterative algorithm is also very fast.

eg. Searching Chicago to find a car is very slow. This is called a brute force algorithm.

eg. Use the iterative algorithm to find a car. In the first step, the distance from the car is 10 kilometers. When you turn the first turn and enter the second iteration, the distance becomes 1 kilometer. After another iteration, it becomes 100 meters. This distance is called " "residual"

divide and conquer

Divide-and-conquer algorithm: a backtracking algorithm that splits large problems into small ones; through backtracking, the same problem is continuously decomposed until the problem is small enough to be solved directly, and then the solutions to the small problems are merged into the original problem solution.

eg. The chief referee of a tennis match subcontracts the refereeing work at different levels.

Traceback: nested loop calls its own procedure

Conditions for the effectiveness of the divide-and-conquer algorithm

Can it be used? Make sure that the problem can be decomposed into sub-problems that are similar to the original problem and that these sub-problems are independent of each other.

Is the solution fast or not?

The two important operations in divide and conquer - decomposition and merging, are not free

eg. Collision detection: To calculate which of the 100 moving balls in the space have collided with each other, the distance between the two is calculated, a total of 4950 times; by dividing the space into two parts and detecting them independently, the number is reduced to 2450 times. Finding suitable division positions when dividing space requires additional computational costs. When merging, it is found that some balls are cut in the middle. To determine whether a collision has occurred, additional calculations are required. This is the cost of the merging result.

If the decomposition problem & the calculation of the merged results are not complex, the divide-and-conquer strategy can reduce the complexity of the algorithm.

The divide-and-conquer algorithm can be calculated in parallel with multiple CPUs, while the iterative algorithm requires that each step should be based on the result of the previous step and calculated in sequence, so it cannot be calculated in parallel with multiple CPUs.

dynamic programming

Solution: Start with the end in mind, build from the small to the big

eg. Candy taking game: Whoever faces 4 candies in the end loses

eg. Rocket vertical soft landing: the final position must be very close to the designated position, the angle between the rocket and the ground must be very close to 90 degrees, and the landing speed must be very close to 0

When facing a multi-step decision-making problem, the optimal decision of a certain step includes and depends on the optimal strategy for smaller-scale problems. This is the optimal substructure.

eg. Candy-taking game: The optimal strategy should be to take two candies at the beginning; but if you do not follow the optimal strategy when facing fewer candies in the future, you will not win if you take two candies now.

The efficiency of dynamic programming is affected by the circumference explosion. At this time, the algorithm engineer may not necessarily solve all the sub-problems accurately, but may only solve a part of them, and it is an inexact solution. Only one estimate is made for the solution of other sub-problems.

branch and bound

Portfolio Optimization

It is not difficult to find a feasible solution, but it is particularly difficult to find the optimal solution.

eg. Find the biggest apple on the tree: cut off the branches that are obviously smaller than the apples, leaving a small number of branches for comparison.

branch and bound

eg. Find the tallest student in middle school

Branch: Junior High School/High School

Delimitation: The spring outing cave of the junior high school is 1.8 meters high, no one needs to bend down - "1.8 meters" is the upper limit of this branch of the junior high school

Pruning: If there is one tree in the senior high school that is over 1.8 meters tall, the entire junior high school can be eliminated.

When the target that can be obtained in a certain sub-search space is not as good as a known feasible solution, this sub-space will be eliminated directly.

How to make branch-and-bound method efficient

It depends on how effectively you can prune; if you only branch without pruning, there is no difference from counting them all.

"Early stopping" strategy: If the obtained temporary optimal dissociation is very close to the real optimal solution, early stopping can greatly save time.

heuristic

When encountering a particularly complex combinatorial optimization problem, if you cannot find the optimal solution, you can turn to heuristic algorithms to find a good feasible solution.

Heuristic algorithms: either consistent with human intuition or natural laws

Monte Carlo

Applicable: Too many possibilities to count

Monte Carlo: Sampling random events in the problem, performing independent calculations for a limited number of samples, and finally statistics of the sample results

It relies heavily on the correctness of the parameters and is not very helpful in revealing the nature of the problem.

Algorithm Frontier

machine learning

Machine learning algorithms are a series of algorithms that allow computers to learn autonomously. They are most suitable for problems that humans cannot solve using clear rules.

Machine learning has learned many details that humans have not been taught and do not understand.

Machine learning learns the complex relationships between things

Learning strategy: How machine learning algorithms learn

K neighbor algorithm, based on memory, finally expresses a bunch of historical data

eg. Case law in the common law system

The decision tree model summarizes the conditional judgments through data induction, and finally expresses some complex conditional judgments.

The neural network model simulates the transmission of nerve signals and the process of nerve responses to different external information, and finally expresses a series of parameter values.