pczebra

算法笔记

2023/06/19

分而治之(divide and conquer，D&C) – 一种递归式问题解决方法

  • 使用分而治之解决问题的过程包括两个步骤： (1) 找出基线条件(递归退出)，这种条件必须尽可能简单； (2) 不断将问题分解(或者说缩小规模)，直到符合基线条件。  

  • 代表算法：欧几里得算法和快速排序算法。 欧几里得算法：The Euclidean Algorithm for finding GCD(A,B) is as follows:  

    • If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, and we can stop;  
    • If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop;  
    • Write A in quotient remainder form (A = B⋅Q + R);  

    • Find GCD(B,R) using the Euclidean Algorithm since GCD(A,B) = GCD(B,R);   算法实例:

        int calculator(int A, int B) {
    if (A == 0) {
      return B;
    }
    if (B == 0) {
      return A;
    }
    if (A >= B) {
      A = A % B;
      return calculator(A, B);
    } else {
      B = B % A;
      return calculator(A, B);
    }
  }

贪婪算法 – 每步都选择局部最优解，最终得到的就是全局最优解

  • 贪心算法适合解决集合覆盖问题(NP完全问题)。面临NP完全问题时，最佳的做法是使用近似算法；贪婪算法易于实现、运行速度快，是不错的近似算法。
  • 判断 NP完全问题 的依据：
    • 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢；
    • 涉及“所有组合”的问题通常是NP完全问题；
    • 不能将问题分成小问题，必须考虑各种可能的情况，这可能是NP完全问题；
    • 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能是NP完全问题；
    • 如果问题涉及集合（集合覆盖问题）且难以解决，它可能就是NP完全问题；
    • 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。

动态规划 – 将问题分解成小问题，并先着手解决这些小问题，再逐步解决大问题

  • 动态规划，
    • 动态规划找到给定约束条件下的最优解（如背包问题中，必须在背包容量给定的情况下，偷到总价值最高的物品）；
    • 在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决；
    • 每种动态规划解决方案都涉及网格；
    • 单元格中的值通常就是要优化的值。（背包问题中，单元格的值为物品的价值）；
    • 每个单元格都是一个子问题，需要思考如何将问题分成子问题，有助于找出网格的坐标轴。
  • 当且仅当每个子问题都是离散的、整体的（不可划分，不依赖于其它子问题），动态规划才管用。  
  • 动态规划的实际应用：
    • 最长公共子串或子序列；
    • git diff等比较文件差异；
    • 字符串相似程度。编辑距离(levenshtein distance),指出两个字符串的相似程度，用来拼写检查、判断用户上传的资料是否为盗版等；
       

  • 使用动态规划解决旅行商问题  

    假设从顶点s出发，令 $d(i, {V})$ 表示从顶点i出发经过 ${V}$ (城市点的集合)中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。

    推导：(分情况来讨论)

    ①当 ${V}$ 为空集，那么 $d(i, {\phi})$ 表示直接从i回到s了，此时 $d(i,{\phi})=C_{is}$ 且 $(i\not ={s})$;

    ②如果 ${V}$ 不为空，那么就是对子问题的最优求解。你必须在 ${V}$ 这个城市集合中，尝试每一个，并求出最优解。

    \[d(i,V) = min\{C_{ik}+d(k,\{V-k\})\}\]

    其中：$C_{ik}$ 表示选择的城市k和城市i的距离，$d(k,{V-k})$是一个子问题。

    综上所述，TSP问题的动态规划方程为：

    \(d(i,V) = \left\{ \begin{array}{rcl} C_{is} & & { \{V\}=\phi, i \not ={s} }\\ min\{C_{ik}+d(k,\{V-k\})\} & & { k \epsilon \{ V \}, \{ V \} \not ={\phi} } \end{array} \right.\) 其中，s为起点。如图是TSP问题求动态规划网格的实例： 动态规划数组 其中，点到自身的距离设为 $\infty$(最大16位int)。

散列表

  • 为避免冲突，散列表需要有 (1)较低的填装因子；(2)良好的散列函数。
    • 填装因子：散列表包含的元素数 / 位置总数。一旦填装因子大于0.7，就调整散列表的长度，通常是翻倍。
    • 良好的散列函数使数组中的值呈均匀分布，如：SHA函数。
    • 处理冲突的方法：开放定址法（线性探测法，二次探测法，随机探测法），再散列函数法（直接定址法，数字分析法，平方取中法，折叠法，除留余数法，随机数法），链地址法（将所有关键字同义的记录存储在一个单链表中），公共溢出区法（冲突的关键字存储到溢出表中）。

图

  • 广度优先搜索 解决两类问题：（1）从节点A出发，有前往节点B的路径吗？（2）从节点A出发，前往节点B的哪条路径最短？
  • 广度优先搜索通过队列 (先进先出 First In First Out, FIFO) 实现。
  • 图的表示：邻接表，邻接矩阵

    • 邻接矩阵

      typedef char VertexType;         /*顶点类型由用户定义*/
typedef int EdgeType;            /*边上权值类型由用户定义*/
#define MAXVEX 100               /*最大顶点数*/
#define INFINITY  65535          /*用65535表示无限大，即边不相连*/

struct MGraph{
  VertexType vexs[MAXVEX];       //顶点表
  EdgeType arc[MAXVEX][MAXVEX];  //邻接矩阵，可看作边表
  int  numVertexes, numEdges;    //图中当前的顶点数和边数
}

    • 邻接表

      using std::string;
const int MAXVEX = 100;

// 边表节点
struct EdgeNode {
  int              adjvex; /*邻接点域，存储该顶点对应的下标*/
  int              weight; /*用于存储权值，非网图不需要*/
struct EdgeNode* next;   /*链域，指向下一个邻接点*/
};

// 顶点表节点
struct VertexNode {
  string    value;     /*顶点域，存储顶点信息*/
  EdgeNode* firstEdge; /*边表头指针*/
};
typedef VertexNode AdjList[MAXVEX];

struct Graph {
  AdjList AdjList;
  int     vertexNum, edgeNum; /*图中当前顶点数和边数*/
};

    • 广度优先搜索算法

      void BreadthFirstSearch(Graph& graph) {
  std::queue<VertexNode> queue;
  bool                   visited[graph.vertexNum]{false};
  for (int i = 0; i < graph.vertexNum; i++) {
    if (!visited[i]) {
        visited[i] = true;
        std::cout << graph.adjList[i].value << std::endl;
        queue.push(graph.adjList[i]);
        while (!queue.empty()) {
            queue.pop();
            auto p = graph.adjList[i].firstEdge;
            while (p) {
                if (!visited[p->adjvex]) {
                    visited[p->adjvex] = true;
                    queue.push(graph.adjList[p->adjvex]);
                    std::cout << graph.adjList[p->adjvex].value << std::endl;
                }
                p = p->next;
            }
        }
    }
  }
}

    • Dijkstra算法求最短路径

      // 计算两点之间的权值
int GetWeight(Graph& graph, int start, int end) {
  auto edge = graph.adjList[start].firstEdge;
  while (edge) {
    if (edge->adjvex == end) {
        return edge->weight;
    }
    edge = edge->next;
  }
  return **INT16_MAX**;
}
    
/// @brief 最短路径--迪杰斯特拉算法
/// @param graph 邻接表
/// @param v0 起始结点
/// @param pathMatrix 最短路径下标数组
/// @param shortPathTable 存储到各点最短路径的权值和
void Dijkstra(Graph& graph, int v0, int*pathMatrix, int* shortPathTable) {
  int  i, j, k, min;
  bool IsShortest[graph.vertexNum]{false};
  for (i = 0; i < graph.vertexNum; i++) {
    shortPathTable[i] = GetWeight(graph, v0, i);  // 全部顶点初始化为未知最短路径状态
    pathMatrix[i]     = v0;
  }
  shortPathTable[v0] = 0;  // v0至v0路径为0
  IsShortest[v0]     = true;
  /*开始主循环，每次求得v0到某个v顶点的最短路径*/
  for (i = 1; i < graph.vertexNum; i++) {
    min = **INT16_MAX**;  // 当前所知离v0顶点的最近距离
    for (j = 0; j < graph.vertexNum; j++) {
        // 寻找离v0最近的顶点
        if (!IsShortest[j] && shortPathTable[j] < min) {
            k   = j;
            min = shortPathTable[j];  // j顶点离v0顶点更近
        }
    }
    IsShortest[k] = true;  // 将目前找到的最近的顶点记录为true
    for (j = 0; j < graph.vertexNum; j++) {
        // 修正当前最短路径及距离
        int p = GetWeight(graph, k, j);
        if (!IsShortest[j] && (min + p) < shortPathTable[j]) {
            // 说明找到两两更短的路径，修改
            shortPathTable[j] = min + p;
            pathMatrix[j]     = k;
        }
    }
  }
}

K最邻近(k-nearest neighbours, KNN)算法

  • 特征抽取，计算元素间的欧式距离、余弦相似度等，选择最邻近的k个特征点。
  • KNN的两项基本工作–分类和回归。分类就是编组，回归就是预测结果（如一个数字）。

Post Directory