数据结构与算法笔记

拼搏现实的明天。 2022-12-25 04:59 150阅读 0赞

### 文章目录 ###

*   *  0.序言
     *   *  0.1数据结构
         *  0.2斐波那契数列（递归）
         *  0.3距离
     *  1.排序
     *   *  1.1冒泡排序
         *  1.2选择排序
         *  1.3插入排序
         *  1.4快速排序
         *  1.5希尔排序
         *  1.6归并排序
         *  1.7总结
     *  2.搜索算法
     *   *  2.1线性搜索（Linear search）
         *  2.2二分搜索（Binary search）
         *  2.3深度优先搜索（Depth-first search）
         *  2.4广度优先搜索（Breadth-first search）
         *  2.5A\*搜索
         *  2.6总结
     *  3.约束满足问题（Constraint-satisfaction problem）
     *  4.图问题
     *   *  4.1贪婪算法
         *  4.2Jarnik算法
         *  4.3Dijkstra算法
     *  5.遗传算法（Genetic algorithm）
     *  6.K均值聚类（K-means clustering）
     *  7.对抗搜索（adversarial search）
     *   *  7.1极小化极大算法
         *  7.2α-β剪枝算法（alpha-beta pruning）优化极小化极大算法

看了《算法精粹——经典计算机科学问题的Python实现》这本书，记录了一些笔记，整理了此篇文章，持续更新…

## 0.序言 ##

### 0.1数据结构 ###

> 参考文章：[最全的数据结构归纳总结][Link 1]

### 0.2斐波那契数列（递归） ###

斐波那契序列（Fibonacci sequence）是一系列数字，后面的数字是前两个数字之和。 f i b ( n ) = f i b ( n − 1 ) + f i b ( n − 2 ) fib(n)=fib(n-1)+fib(n-2) fib(n)=fib(n−1)\+fib(n−2)

一般用递归编写fib函数，递归包括基线条件和递归条件。

""" 利用字典对象作为结果缓存 """
    from typing import Dict
    memo: Dict[int, int] = { 0: 0, 1: 1}  # base cases
    
    def fib3(n: int) -> int:
        if n not in memo:
            memo[n] = fib3(n - 1) + fib3(n - 2)     # memoization
        return memo[n]

### 0.3距离 ###

*  欧氏距离（Euclidean distance）：对角线距离， d = Δ x 2 + Δ y 2 d=\\sqrt\{\\Delta x^2+\\Delta y^2\} d=Δx2\+Δy2
 *  曼哈顿距离（Manhattan distance）：绝对值距离， d = ∣ x ∣ + ∣ y ∣ d=|x|+|y| d=∣x∣\+∣y∣

## 1.排序 ##

### 1.1冒泡排序 ###

def bubble_sort(alist):
        for j in range(len(alist) - 1, 0, -1):
            # j表示每次遍历需要比较的次数，是逐渐减小的
            for i in range(j):
                if alist[i] > alist[i + 1]:
                    alist[i], alist[i + 1] = alist[i + 1], alist[i]
    
    li = [54, 26, 93, 17, 77, 31]
    bubble_sort(li)
    print(li)

### 1.2选择排序 ###

def selection_sort(alist):
        n = len(alist)
        # 需要进行n-1次选择操作
        for i in range(n - 1):
            min_index = i
            for j in range(i + 1, n):
                if alist[j] < alist[min_index]:
                    min_index = j
            # 如果选择出的数据不在正确位置，进行交换
            if min_index != i:
                alist[i], alist[min_index] = alist[min_index], alist[i]
    
    li = [54, 26, 93, 17, 77, 31]
    selection_sort(li)
    print(li)

### 1.3插入排序 ###

def insert_sort(alist):
        for i in range(1, len(alist)):
            # 从第i个元素开始向前比较，若小于前一个元素则交换位置
            for j in range(i, 0, -1):
                if alist[j] < alist[j - 1]:
                    alist[j], alist[j - 1] = alist[j - 1], alist[j]
    
    li = [54,26,93,17,77,31]
    insert_sort(li)
    print(li)

### 1.4快速排序 ###

简单版本的：

def quicksort(array):
        # 基线条件
        if len(array) < 2:
            return array
        # 递归条件
        else:
            pivot = array[0]
            less = [i for i in array[1:] if i <= pivot]
            greater = [i for i in array[1:] if i > pivot]
            return quicksort(less) + [pivot] + quicksort(greater)
            
    print (quicksort([10, 5, 2, 3]))

### 1.5希尔排序 ###

def shell_sort(alist):
        n = len(alist)
        gap = n // 2     # 初始步长
        while gap > 0:
            # 按照步长进行插入排序
            for i in range(gap, n):
                j = i
                # 插入排序
                while j >= gap and alist[j - gap] > alist[j]:
                    alist[j - gap], alist[j] = alist[j], alist[j - gap]
                    j -= gap
            # 得到新的步长
            gap = gap // 2
    
    li = [54, 26, 93, 17, 77, 31]
    shell_sort(li)
    print(li)

### 1.6归并排序 ###

def merge_sort(alist):
        if len(alist) <= 1:
            return alist
        # 二分分解
        num = len(alist) // 2
        left = merge_sort(alist[: num])
        right = merge_sort(alist[num :])
        # 合并
        return merge(left, right)
    
    def merge(left, right):
        # 合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组
        l, r = 0, 0     # left和right的下下标指针
        result = []
        while l < len(left) and r < len(right):
            if left[l] < right[r]:
                result.append(left[l])
                l += 1
            else:
                result.append(right[r])
                r += 1
        result += left[l:]
        result += right[r:]
        return result
    
    li = [54,26,93,17,77,31]
    print(merge_sort(li))

### 1.7总结 ###

> 这里有一个贼nb的总结：[十大经典排序算法（动图演示）][Link 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlaXZlbl8_size_16_color_FFFFFF_t_70]

## 2.搜索算法 ##

### 2.1线性搜索（Linear search） ###

按照原始数据结构的顺序遍历搜索空间（search space）中的每个元素。时间复杂度为 O ( n ) O(n) O(n)。

### 2.2二分搜索（Binary search） ###

查看一定范围内有序元素的中间位置的元素，将其与所查找的元素进行比较，根据比较结果将搜索范围缩小一半，重复上述过程。

### 2.3深度优先搜索（Depth-first search） ###

DFS深度优先搜索：搜索尽可能深深入，碰到障碍就回溯到最后一次的决策位置。栈作为基本数据结构。

### 2.4广度优先搜索（Breadth-first search） ###

BFS广度优先搜索：寻找最短路径，离起点位置最近的元素最先被搜索。队列作为基本数据结构。

### 2.5A\*搜索 ###

A\*搜索结合运用代价函数与启发函数。优先队列作为基本数据结构。

### 2.6总结 ###

> 参考文章：[搜索算法总结][Link 3]

## 3.约束满足问题（Constraint-satisfaction problem） ##

CSP约束满足问题由一组变量构成，变量可能的取值范围是值域（domain）,要求解决约束满足问题需要满足变量之间的约束。CSP是变量、值域和约束的汇聚点。

> 参考文章：[人工智能 一种现代方法 第6章 约束满足问题][_ _6_]

## 4.图问题 ##

### 4.1贪婪算法 ###

每一步都寻找最优解，最终解不一定是最优解。

> 参考文章：[【算法】贪婪算法（贪心算法）][Link 4]

### 4.2Jarnik算法 ###

一种贪婪算法，不适用于有向图和非连通图

> 参考文章：[最小生成树之Prim（普里姆）算法][Prim]

### 4.3Dijkstra算法 ###

通过更新的方式寻找起点到终点的最短路径。

> 参考文章：[最短路径问题—Dijkstra算法详解][Dijkstra]

## 5.遗传算法（Genetic algorithm） ##

遗传算法包含了名为染色体（chromosome）的个体组成的种群。所有染色体都要竞争解决一些问题，每条染色体都由定义其特性的基因组成。染色体解决问题的能力由适应度函数（fitness function）定义。遗传算法要经历很多代（generation）。每一代中适应力较强的染色体更有可能被选中进行繁殖。每一代中还有可能发生两条染色体的基因合并，即交换（crossover）。染色体的基因可能会随机发生变异（mutate）。所以染色体必须实现以下功能：

*  确定自己的适应度
 *  创建一个携带了随机选中基因的实例（用于填充第一代个体的数据）
 *  实现交换，让自己与另一个同类结合并创建后代
 *  变异，让自己体内的数据发生相当随机的小变化

常见的两种遗传算法的选择方法：

*  轮盘式选择法（Roulette-wheel selection）：有时被称为适应度比例选择法（Fitness proportionate selection），让每一条染色体都有机会被选中，与其适应度成正比。
 *  锦标赛选择法（Tournament selection）：一定数量的随机染色体会相互挑战，适应度最佳的那个染色体将会被选中。

> 参考文章：[遗传算法详解（GA）（个人觉得很形象，很适合初学者）][GA]

## 6.K均值聚类（K-means clustering） ##

K均值聚类算法：根据每个点与聚类簇中心的相对距离，将聚类点分组到某个聚类簇中。是一种非监督学习方法。

kmeans++算法：不是完全随机选择形心，而是基于到各点距离的概率分布选择形心。

> 参考文章：[Kmeans聚类算法详解][Kmeans]

## 7.对抗搜索（adversarial search） ##

### 7.1极小化极大算法 ###

极小化极大算法通常采用递归实现，两个玩家要么是极大化玩家，要么是极小化玩家。极大化玩家目标是找到能获得最大收益的走法，但是必须考虑极小化玩家的走法，即需要求得对手的回手：让极大化玩家的收益最小化的走法。这个过程一直进行（求最大值、求最小值），直到达到递归函数的基线条件。对于搜索空间太深而无法抵达终局的游戏，极小化极大函数minimax()会在达到一定深度后停止。

### 7.2α-β剪枝算法（alpha-beta pruning）优化极小化极大算法 ###

在搜索时将不会生成更优结果的棋局排除，由此来增加搜索的深度。跟踪记录递归调用minimax()间的两个值 α \\alpha α和 β \\beta β， α \\alpha α表示搜索树当前找到的最优极大化走法的评分， β \\beta β表示当前找到的对手的最优极小化走法的评分，如果 β ≤ α \\beta \\leq\\alpha β≤α，则不值得对该搜索分支进一步搜索。这种启发式算法能显著缩小搜索空间。

> 参考文章：[极小化极大算法][Link 5]

[Link 1]: https://blog.csdn.net/huwenxing0801/article/details/85057602
[Link 2]: https://www.cnblogs.com/onepixel/p/7674659.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tlaXZlbl8_size_16_color_FFFFFF_t_70]: /images/20221120/c857247fbe0e4b398650bc7633106d8d.png
[Link 3]: https://blog.csdn.net/Holyang_1013197377/article/details/41978833?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160681535719724816623417%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=160681535719724816623417&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-1-41978833.pc_search_result_no_baidu_js&utm_term=%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93&spm=1018.2118.3001.4449
[_ _6_]: https://blog.csdn.net/yyl424525/article/details/95308201?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160681572719725222440033%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=160681572719725222440033&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_v2~rank_v28-12-95308201.pc_search_result_no_baidu_js&utm_term=%E7%BA%A6%E6%9D%9F%E6%BB%A1%E8%B6%B3%E9%97%AE%E9%A2%98&spm=1018.2118.3001.4449
[Link 4]: https://blog.csdn.net/HelloZEX/article/details/81093385?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160681590519721940261125%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=160681590519721940261125&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-1-81093385.pc_search_result_no_baidu_js&utm_term=%E8%B4%AA%E5%A9%AA%E7%AE%97%E6%B3%95&spm=1018.2118.3001.4449
[Prim]: https://blog.csdn.net/aa793336532/article/details/71680311?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160681624719724838543354%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=160681624719724838543354&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-3-71680311.pc_search_result_no_baidu_js&utm_term=Prim%E7%AE%97%E6%B3%95&spm=1018.2118.3001.4449
[Dijkstra]: https://blog.csdn.net/qq_35644234/article/details/60870719?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160681644819725222467302%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=160681644819725222467302&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-1-60870719.pc_search_result_no_baidu_js&utm_term=Dijkstra%E7%AE%97%E6%B3%95&spm=1018.2118.3001.4449
[GA]: https://blog.csdn.net/u010451580/article/details/51178225?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160681670919725271091233%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=160681670919725271091233&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_v2~hot_rank-5-51178225.pc_search_result_no_baidu_js&utm_term=%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95&spm=1018.2118.3001.4449
[Kmeans]: https://blog.csdn.net/qq_32892383/article/details/80107795?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160681681719724827637182%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=160681681719724827637182&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_v2~hot_rank-1-80107795.pc_search_result_no_baidu_js&utm_term=K%E5%9D%87%E5%80%BC%E8%81%9A%E7%B1%BB&spm=1018.2118.3001.4449
[Link 5]: https://blog.csdn.net/joshualiunsw/article/details/52131507?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160681705119724848176526%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=160681705119724848176526&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-5-52131507.pc_search_result_no_baidu_js&utm_term=%E6%9E%81%E5%B0%8F%E5%8C%96%E6%9E%81%E5%A4%A7%E7%AE%97%E6%B3%95&spm=1018.2118.3001.4449