图论补充内容
图论补充内容
图论的基本知识汇总已以PDF形式上传至科大个人主页链接，此部分补充内容主要记录图论在实际算法问题方面的知识学习，部分内容来源于网络。
计算复杂性问题
P问题、NP问题、不可判定问题
P问题：能够在多项式时间内可用算法求解的问题。举例：找到Euler回路
NP问题：非确定型多项式时间（nondeterministic polynomial-time）问题，指不确定是否存在多项式时间的求解算法，但可以在多项式时间内验证一个猜测解的正确性的问题。举例：找Hamilton回路（实际上是NPC问题，尚且未知有限性算法）。
不可判定问题(undecidable problem)：”不可能“解出的问题。举例：让C编译器找出所有的语法错误和无限循环。
与NP相关的问题有P，NP，NP Hard ，NPC问题，其中NP Hard 与NPC问题的具体描述为：
NP hard问题：Non-deterministic Polynomial hard problem(NPH)问题，如果所有NP问题可在多项式时间内转化（归约，意思是解决了后者也就相应的解决了前者）成某个问题，则该问题称为NP难问题。
这里规约的意思是将一个特殊问题一般化，即将原问题推广为一个最一般的、最有概括性、也更难的、计算复杂度更高的问题，这个问题具有最高的计算复杂度，如果这个最一般的问题也能有多项式时间求解算法，那么那些特殊的原问题也能有多项式时间求解算法。
解决了这个NP hard问题，所有NP问题都能够被解决了。NP hard问题不一定是NP问题，有可能是不可判定问题。这时候说明原问题也是不可判定的。
NPC问题：Non-deterministic Polynomial complete problem ，如果所有NP问题可在多项式时间内归约成某个NP问题，则该NP问题称为NP完全问题。NPC包含了NP中最难的问题。
解决了这个NPC问题。所有NP问题都能够被解决了。NPC问题相当广泛，包括来自操作系统（调度和安全）、数据库系统、运筹学、逻辑学、特别是图论等不同领域的问题。
可满足性问题、哈密顿圈问题、巡回售货员问题、最长路径问题都是NPC问题。 装箱(bin packing)问题、背包(knapsack)问题、图的着色(graph coloring)问题以及团(clique)的问题都是著名的NPC问题。NPC问题相当广泛，包括来自操作系统（调度和安全）、数据库系统、运筹学、逻辑学、特别是图论等不同领域的问题。
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkel和Hellman提出的。背包问题已经研究了一个多世纪，早期的作品可追溯到1897年数学家托比亚斯·丹齐格（Tobias Dantzig，1884-1956）的早期作品 ，并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。
NPC算法的复杂度更倾向于$O(e^n)$,NP Hard 算法的时间复杂度甚至可能达到$O(n^n)$.
在本课程里出现的NPC问题：
- 图着色（边/顶点/面着色）
- Hamilton圈算法
- …?
随机游走Random Walk
随机游走（英语：Random Walk，缩写为 RW），是一种数学统计模型，它是一连串的轨迹所组成，其中每一次都是随机的。[1][2]它能用来表示不规则的变动形式，如同一个人酒后乱步，所形成的随机过程记录。1905年，由卡尔·皮尔逊首次提出。
——来自维基百科
靠随机游走解出来了tx的自定义阴间一笔画红包
——来自群友
算法思想：
- 该算法要实现的是搜索，从起始点s开始找到目的地t。
- 给定一个图，从起点开始走的每一步都让其有一定的概率$\alpha$跳转到图中的任意一个点上，还有$ 1-\alpha$的概率会行走到任意一个与该点相连的点上。不断的重复上述过程，直到找到目的地中。
步骤
- 将实际问题抽象为图的形式，并用临接表、邻接矩阵等存图方式将图存储在计算机中；
- 用一个变量记录当前所处的位置（图中点的标号），每次随机一个[0, 1]之间的数，若其小于等于随机跳跃概率$\alpha $则随机一个[1, n]的数字并跳转，否则随机一个$x,x\in S$，其中S为与当前点相连的点的集合；
- 不断重复第二步并记录路径，直到找到目的地t.
该算法的思想也被应用到了PageRank算法中，作为Google等搜索引擎的网页检索算法。（PageRank中心性算法的本质就是随机游走（详见课本中心型算法部分，考试不考）。
