Basic algorithm

/ Fl0w3r

Original link: https://yousazoe.top/archives/ce5da845.html

introduction

Briefly introduce some basic algorithms, including: search, greedy, binary search and third search, sequence divide and conquer, and sorting.

search

what is search

search tree

  • Taking the starting state as the root, each state connects directed edges to its successor states, and a rooted tree can be obtained
    • The terminal state corresponds to the leaves of this tree
  • The search process can be abstracted into the process of traversing the search tree
  • If you need to traverse the entire search tree, the complexity is at least proportional to the number of nodes in the search tree
  • The size of a rooted tree can be estimated by the number of leaf nodes if all nodes other than leaf nodes have at least two leaf nodes
    • why?
  • If all states except the terminal state have at least two successor states, the number of terminal states can be used to estimate the complexity of the search
  • If there is a lower bound on the number of successor states of states other than the terminal state, the number of terminal states can be estimated with the number of layers

search complexity

Depth First vs Breadth First

Depth-First Search ( Depth-First Search ) first traverses all nodes in the subtree of a successor node

  • One way to go to black first, then go back to the previous fork point

Breadth-First Search ( Breadth-First Search ) first traverses all the successor nodes, and then traverses the successor of the successor node

  • Clone at the bifurcation point, and eventually each termination node has a clone

Depth-First Search

Breadth-First Search

Choice of search strategy

Depth First Search DFS

  • Just store a path from the initial state to the current state
  • When the recursion level is deep, the stack may burst
  • Need to consider the issue of retroactive revocation, the details may be troublesome
    • Can cause problems when the number of search layers is uncertain: infinite expansion
  • Move the piece and make a big circle back to the starting point
  • Nodes in the subtree are consecutively numbered

Breadth First Search BFS

  • Need to store all the states to be expanded, the space overhead is large
  • Heap memory can be used dynamically
  • One-way expansion of the state, the implementation is relatively simple
  • It is possible to know the minimum number of steps from the initial state to each state
    • Applies to shortest paths with edge weights of 1
  • Node numbers on the same layer are consecutive

Further reading: Iteratively deepen the search

Search for Pruning

Fruit tree pruning is done to make the tree look better and produce higher quality fruit

The search tree can also be pruned to make the search more efficient; be careful not to prune the optimal solution

Feasibility Pruning

  • If the current state does not meet the requirements of the title, do not continue to expand
  • Can be used for optimization problems as well as statistical solutions

optimal pruning

  • can only be used for optimization problems
  • If starting from the current state, the optimal solution that can be obtained must not be better than the optimal solution that has been obtained, then do not continue to expand

In addition, there are other pruning ideas, such as Alpha-beta pruning in two-player games, etc., which will not be detailed here.

classic problem

Eight Queens
egyptian score
Pruning ideas
  • Zoom!
  • If you can’t save it, you should give up
    • If the subsequent state must be illegal, do not continue to search further
  • Take the minimization problem as an example
    • Estimate the lower bound of the solution for all successors of the current state, and prune if the lower bound is greater than (or greater than or equal to, depending on the specific topic) the current minimum
  • Extended reading:Branch and bound method solution

heuristic search

greedy

Greedy Algorithm

The difference between greedy and dynamic programming

change money problem

  • Suppose you have several banknotes of $1, $5, $10, $20, $50, and $100
  • Use these banknotes to represent a given positive integer amount so that the minimum number of banknotes is used
  • Greedy approach: each time the banknote with the largest denomination that does not exceed the amount not yet expressed is selected
    • 127 → 100 + 20 + 5 + 1 + 1
    • correctness?
  • Suppose the denominations of the banknotes are 1 yuan, 2 yuan, 4 yuan, 8 yuan, 16 yuan, …, is it still correct to be greedy?
  • Assuming the denominations of banknotes are $1, $5, $10, $20, and $25, is greed still correct?
    • Counter example: 40 → 25 + 10 + 5, but 20 + 20 is better

Common Ideas for Proving Greedy Correctness

Huffman coding

Twos and threes

Binary Search

a little story

three points

Recursion and divide and conquer

recursion

divide and conquer

sort

sort

Bubble Sort

Insertion sort

selection sort

merge sort

quick sort

This article is reprinted from: https://yousazoe.top/archives/ce5da845.html
This site is for inclusion only, and the copyright belongs to the original author.