zjffun blog

算法概论

更新于 写于 算法

序言

Fibonacci 数列

多项式时间算法：

js
var fib_arr = [0, 1];
function fib(n) {
  if (n == 0) {
    return 0;
  } else if (n == 1) {
    return 1;
  }
  for (var i = 0; i < n - 2; i++) {
    fib_arr[n + 2] = fib_arr[n + 1] + fib_arr[n];
  }
  return fib_arr[n];
}
var start = new Date().getTime();
console.log(fib(30));
var end = new Date().getTime();
console.log("运行时间：" + (end - start));
// 运行时间：24

指数时间算法：

js
function fib(n) {
  if (n == 0) {
    return 0;
  } else if (n == 1) {
    return 1;
  } else {
    return fib(n - 1) + fib(n - 2);
  }
}
var start = new Date().getTime();
console.log(fib(30));
var end = new Date().getTime();
console.log("运行时间：" + (end - start));
// 运行时间：50

渐进

  • 上界：Ο
  • 下界：Ω
  • 紧确界：Θ

数字的算法

基础算数

基数和对数

  • b 为基数的 k 位数字最大为 b^k-1
  • b 为基数表示 N 需要 ⌈log(b)(N+1)⌉ 位（应该是向上取整）

乘法（Al Khwarizmi 乘法规则）

类似使用二进制进行乘法

y（每次整除 2） z（结果，由底至顶）
11 13+(13+(13*2)*2)*2
5 13+(13*2)*2
2 13*2
1 13
0 0
js
// 类似使用二进制进行乘法（当y>=0时可用）
function multiply(x, y) {
  if (0 == y) {
    return 0;
  }
  var z = multiply(x, Math.floor(y / 2));
  // y为偶数，y为奇数加到x上
  return y % 2 == 0 ? 2 * z : x + 2 * z;
}
console.log(multiply(13, 11));

除法

类似使用二进制进行除法

x（每次整除 2） z（结果，由底至顶）
13 [0+1, ((((0+1)*2+1)*2)*2+1)-11]
6 [0, ((0+1)*2+1)*2]
3 [0, (0+1)*2+1]
1 [0, (0+1)]
0 [0, 0]
js
// 类似使用二进制进行除法（当y>=1时可用，q：quotient，r：remainder）
function divide(x, y) {
  if (0 == x) {
    return [0, 0];
  }
  var z = divide(Math.floor(x / 2), y);
  var q = 2 * z[0];
  var r = 2 * z[1];
  if (x % 2 == 1) {
    // 被除数为奇数除二余数为1
    r++;
  }
  if (r >= y) {
    // 余数大于除数，余数变为余数减去除数，商+1
    r -= y;
    q++;
  }
  console.log(q, r);
  return [q, r];
}
console.log(divide(13, 11));

模运算

定义：x=qN+r，且0<=r<N，则 x 模 N 等于 r。

  • x 与 y 模 N 同余 <=> x≡y(mod N) <=> N 整除 (x-y)
  • 模运算准守结合律、分配率、交换律

模的指数运算

x:10, y:6, N:17

y（指数，每次整除 2） z（结果，由底至顶）
6 ((10*((10*1*1)%17)*((10*1*1)%17))%17)*((10*((10*1*1)%17)*((10*1*1)%17))%17)%17
3 (10*((10*1*1)%17)*((10*1*1)%17))%17
1 (10*1*1)%17
0 0
js
// 求模的指数运算（y>=1）
function modexp(x, y, N) {
  if (0 == y) {
    return 1;
  }
  var z = modexp(x, Math.floor(y / 2), N);
  if (y % 2 == 0) {
    return (z * z) % N;
  } else {
    return (x * z * z) % N;
  }
}
console.log(modexp(11, 11, 2)); //1
console.log(modexp(10, 11, 2)); //0
console.log(modexp(10, 6, 17)); //9

Euclid 最大公因数（greatest common divisor）算法

  • Euclid 规则：如果 x，y 是正整数，且有 X>=y，那么 gcd(x, y) = gcd(x mod y, y)
js
// Euclid求最大公约数方法（a>=b>=0）
function euclid(a, b) {
  if (0 == b) return a;
  return euclid(b, a % b);
}
console.log(euclid(11, 11)); //11
console.log(euclid(33, 22)); //11
console.log(euclid(97, 79)); //1
  • Euclid 拓展：用来求gcd(a, b) = d = ax + by的 x 和 y
js
// Euclid拓展（a>=b>=0）
function extend_euclid(a, b) {
  if (0 == b) return [1, 0, a];
  var result = extend_euclid(b, a % b),
    x = result[0],
    y = result[1],
    d = result[2];
  return [y, x - Math.floor(a / b) * y, d];
}
console.log(extend_euclid(11, 11)); //[ 0, 1, 11 ]
console.log(extend_euclid(33, 22)); //[ 1, -1, 11 ]
console.log(extend_euclid(97, 79)); //[ 22, -27, 1 ]

注：a mod b = a - ⌊a/b⌋*b

模的除法运算

不确定！！！

例，求 100/27 mod 97

求乘法逆元：
97*22 + 79*-27 = 1
=> 79*-27 = 1 mod 97
=> -79 = 1/27 mod 97

乘法逆元带入：
100/27 mod 97
= 100 * 1/27 mod 97
= 100 * -79 mod 97
= 54

素性测试

  • 费马小定理：p 为素数，任意对于任意 1<=a<p 有a^(p-1) = 1 mod p
js
// 素数测试算法（对于合数N，a的大多数无法通过测试）
function primality(N) {
  var a = Math.floor(2 + Math.random() * (N - 3));
  if (modexp(a, N - 1, N) == 1) {
    return true;
  } else {
    return false;
  }
}

// 求模的指数运算（y>=1），前面的算法
function modexp(x, y, N) {
  if (0 == y) {
    return 1;
  }
  var z = modexp(x, Math.floor(y / 2), N);
  if (y % 2 == 0) {
    return (z * z) % N;
  } else {
    return (x * z * z) % N;
  }
}
console.log(primality(11027));
console.log(primality(11026));
js
// 素数测试算法（对于合数N，a的大多数无法通过测试）
function primality(N) {
  // 降低出错概率到(2^-100)
  for (var i = 0; i < 100; i++) {
    var a = Math.floor(2 + Math.random() * (N - 3));
    if (modexp(a, N - 1, N) != 1) {
      return false;
    }
  }
  return true;
}

// 求模的指数运算（y>=1），前面的算法
function modexp(x, y, N) {
  if (0 == y) {
    return 1;
  }
  var z = modexp(x, Math.floor(y / 2), N);
  if (y % 2 == 0) {
    return (z * z) % N;
  } else {
    return (x * z * z) % N;
  }
}
console.log(primality(11027));
console.log(primality(11026));

密码学

一次一密乱码本（one-time pad）和 AES

使用密钥 r 进行异或加密解密

  • 加密：er(x) = x ⊕ r
  • 解密：er(er(x)) =(x ⊕ r) ⊕ r = x ⊕ (r ⊕ r) = x

一次一密乱码本

r 与发送信息长度一样

js
const r = "101011100";

function encrypt(x) {
  return (parseInt(x, 2) ^ parseInt(r, 2)).toString(2);
}

function unencrypt(x) {
  return (parseInt(x, 2) ^ parseInt(r, 2)).toString(2);
}

// test
var msg = "111110000";
var encrypted = encrypt(msg);
console.log(`encrypted: ${encrypted}`);
var unencrypted = unencrypt(encrypted);
console.log(`unencrypted: ${unencrypted}`);

AES

  1. r 通常定为 128 位（也有定为 192 位或 256 位的情况）
  2. 定义一种双向映射机制 er
  3. 信息分成片段，每个片段用 er 加密

RSA

生成密钥

  1. 找大整数 p,q（素数测试算法）
  2. 根据 N=pq，求 N（乘法）
  3. 找任意与 (p-1)(q-1) 互素的数 e
  4. 根据 ed≡(1 mod (p-1)(q-1))，求 d（拓展 Euclid 算法）

此时公钥为 (N,e)，私钥为 (N,d)

js
class rsa {
  static genrsa() {
    let p, q, N, e, d;
    // 产生两个大素数
    p = this._genpri(4);
    q = this._genpri(4);
    // 求N
    N = p * q;
    // 求e和d
    [e, d] = this._get_eexp_and_inv((p - 1) * (q - 1));
    return {
      // 公钥
      pub_key: {
        N: N,
        e: e,
      },
      // 私钥
      pri_key: {
        N: N,
        d: d,
      },
    };
  }

  static encrypt(x, N, e) {
    return this._modexp(x, e, N);
  }

  static unencrypt(y, N, d) {
    return this._modexp(y, d, N);
  }

  // 生成素数
  static _genpri(size) {
    while (true) {
      let n = Math.floor((1 << size) - 1 + Math.random() * (1 << size));
      if (this._primality(n)) {
        return n;
      }
    }
  }

  // 获取加密指数和乘法余元（encryption exponent and multiplicative inverse）
  static _get_eexp_and_inv(N) {
    while (true) {
      let e = this._genpri(2);
      let d = this._extend_euclid(N, e)[1];
      // d > 1：乘法余元非负，且与N互素（模的指数运算无法使用负数）
      if (d > 1) {
        return [e, d];
      }
    }
  }

  // 模的指数运算
  static _modexp(x, y, N) {
    if (0 == y) {
      return 1;
    }
    // static模式下arguments.callee失效
    var z = this._modexp(x, Math.floor(y / 2), N);
    if (y % 2 == 0) {
      return (z * z) % N;
    } else {
      return (x * z * z) % N;
    }
  }

  // 素数测试算法（对于合数N，a的大多数无法通过测试）
  static _primality(N) {
    // 降低出错概率到(2^-100)
    for (var i = 0; i < 100; i++) {
      var a = Math.floor(2 + Math.random() * (N - 3));

      if (this._modexp(a, N - 1, N) != 1) {
        return false;
      }
    }
    return true;
  }

  // Euclid拓展（a>=b>=0）
  static _extend_euclid(a, b) {
    if (0 == b) return [1, 0, a];
    var result = this._extend_euclid(b, a % b),
      x = result[0],
      y = result[1],
      d = result[2];
    return [y, x - Math.floor(a / b) * y, d];
  }
}

// test
let msg = 123;
let test_rsa = rsa.genrsa();
console.log(`test_res：`, test_rsa);
let encrypted = rsa.encrypt(msg, test_rsa.pub_key.N, test_rsa.pub_key.e);
console.log(`encrypted: ${msg} -> ${encrypted}`);
let unencrypted = rsa.unencrypt(
  encrypted,
  test_rsa.pri_key.N,
  test_rsa.pri_key.d
);
console.log(`unencrypted: ${encrypted} -> ${unencrypted}`);

加密解密

  1. 加密：y=x^e mod N
  2. 解密：x=y^d mod N

破解？

  • 方法 1：尝试所有可能的 x 判断x^e = y mod N是否成立
  • 方法 2：对 N 因式分解，得到 p 和 q，进而计算出 d

散列表

散列表大小设为素数冲突概率小！

例：IP 地址的散列

js
// 未做解决冲突
function hash_IP(num) {
  var a = [],
    ip_table = new Array(num);
  for (let i = 0; i < 4; i++) {
    a[i] = Math.floor(Math.random() * num);
  }
  return function (IP) {
    let d,
      sum = 0;
    d = IP.split(".");
    for (let i = 0; i < 4; i++) {
      sum += +d[i] * a[i];
    }
    ip_table[Math.floor(sum % num)] = {
      ip: IP,
      data: IP,
    };
    return ip_table;
  };
}
var hi = hash_IP(100);
console.log(hi("127.0.0.1"));
console.log(hi("60.59.44.33"));
console.log(hi("192.110.119.115"));

分治算法

乘法

递归将乘数分为两段，并将 T(n) = 4T(n/2) + O(n) 的方法优化为 T(n) = 3T(n/2) + O(n) 的方法

效率：

由普通的 O(n^2) 提高到 O(3^log2(n))（约为 O(n^1.59)）

PS: O(3^log2(n)) = O(n^log2(3)) 指数对数一顿推就出来了

算法：

js
/**
 * 分治整数乘法算法
 * @param  {number} x 被乘数，整数，大于等于0
 * @param  {number} y 乘数，整数，大于等于0
 * @returns {number} 结果
 */
export default (x, y) => {
  function multiply(x, y) {
    var xl, xr, yl, yr, p1, p2, p3, n, nl, nr;
    n = Math.max(x.toString(2).length, y.toString(2).length);

    // 一位的时候x*y和x&y一样
    if (n == 1) return x & y;

    nl = Math.ceil(n / 2);
    nr = Math.floor(n / 2);

    xl = x >> nr;
    xr = x - (xl << nr);
    yl = y >> nr;
    yr = y - (yl << nr);
    p1 = multiply(xl, yl);
    p2 = multiply(xr, yr);
    p3 = multiply(xl + xr, yl + yr);

    /**
     * 左移的位数要在纸上写几遍把握一下（书上p1左移n位当n为偶数才能成立）
     * 算数运算符优先级大于位移运算符
     * 如：110 * 111 = ((11 << 1) + 0) * ((11 << 1) + 1)
     *  = [(11 * 11 << 2)] + [11 * 1 + 11 * 0 << 1]                 + [0 * 1]
     *  = [p1 << 2]        + [((11 + 0) * (11 + 1) - p1 - p2) << 1] + [p2]
     *  = [p1 << 2]        + [(p3 - p1 - p2) << 1]                  + [p2]
     * 这个式子中n为3，nr为Math.floor(3 / 2)等于1
     */
    return (p1 << (nr << 1)) + ((p3 - p1 - p2) << nr) + p2;
  }

  return multiply(x, y);
};

注：书中最后左移的位数只有偶数位才正确

主定理

T(n) = aT(n/b) + O(n^d)

  • d > logb(a) : T(n) = O(n^d)
  • d = logb(a) : T(n) = O((n^d)*log(n))
  • d < logb(a) : T(n) = O(n^(logb(a)))

递归树宽 a^logb(n)，高logb(n)

合并排序

T(n) = 2T(n/2) + O(n) = O(nlogn)

递归：

js
test_arr = [10, -1, 2, 3, 9, 10, 9];
function mergesort(arr) {
  if (arr.length > 1) {
    // 将两个排序好的数组进行连接
    return merge(
      mergesort(arr.slice(0, Math.floor(arr.length / 2))),
      mergesort(arr.slice(Math.floor(arr.length / 2), arr.length))
    );
  } else {
    return arr;
  }
}
function merge(arr1, arr2) {
  if (arr1.length == 0) return arr2;
  if (arr2.length == 0) return arr1;
  if (arr1[0] > arr2[0]) {
    return [arr1[0]].concat(merge(arr1.slice(1, arr1.length), arr2));
  } else {
    return [arr2[0]].concat(merge(arr2.slice(1, arr2.length), arr1));
  }
}
console.log(mergesort(test_arr));

迭代：

js
test_arr = [10, -1, 2, 3, 9, 10, 9];
function interative_mergesort(arr) {
  var temp_arr = test_arr.map((d) => {
    return [d];
  });
  while (temp_arr.length > 1) {
    temp_arr.push(merge(temp_arr.pop(), temp_arr.pop()));
  }
  return temp_arr[0];
}
function merge(arr1, arr2) {
  if (arr1.length == 0) return arr2;
  if (arr2.length == 0) return arr1;
  if (arr1[0] > arr2[0]) {
    return [arr1[0]].concat(merge(arr1.slice(1, arr1.length), arr2));
  } else {
    return [arr2[0]].concat(merge(arr2.slice(1, arr1.length), arr1));
  }
}
console.log(interative_mergesort(test_arr));

寻找中项（选择有序数组的某项）

用快速排序的思想，递归找出 SL（小于 v 的数）、SV（等于 v 的数）、 SR（大于 v 的数）缩小范围

代码

效率：

最好：T(n) = T(n/2) + O(n) = O(n)

最坏：T(n) = T(n - 1) + O(n) = O(n^2)

PS：快速排序是超大文件排序算法的基础

矩阵乘法

使用T(n) = 7T(n/2) + O(n^2)的分治算法可以从传统的 O(n^3) 优化到 O(n^log2(7))

留坑以后写

快速傅里叶变换（FFT）

预备知识

一个 d 次多项式被其在任意 d+1 个不同点出的取值所唯一确定

d+1 个不同点处的取值可以列出 d+1 个方程，解出系数 a0, a1, ..., ad（共 d+1 个）

多项式A(x)=a0*(x^0) + a1*(x^1) + ... + ad*(x^d)的两种表示

  1. 系数：a0, a1, ..., ad
  2. 值：A(x0), A(x1), ..., A(xd)

系数与值的关系

系数 -> 计算 -> 值

值 -> 插值 -> 系数

问题转化

计算 A(x)\*B(x) = C(x) 的问题转化成计算A(x) 和B(x) 在 2d+1（d 为多项式次数）个不同点处的取值的乘积，然后对这些乘积插值获取C(x) 的系数

从直接计算和插值开始

下面有一个直接进行计算和插值求多项式乘积的算法，可以看出问题有：

  1. 计算：计算增广矩阵的时间复杂度是O(n^2)（这里和直接乘起来一样复杂了）
  2. 插值：求非齐次线性方程组的时间复杂度是O(n^3)（反而更加复杂了）

原本以为用 0,2,4,8... 这些点是不可以简化计算和插值，结果发现想多了简化不了，就用了 0,1,2,3... 这种取值。

FFT 正是巧妙地选择了计算的点使算法效率提高。

js
/**
 * 使用未经优化的计算和插值方法，计算多项式A(x)*B(x)的系数
 * @param  {Array<number>} Ax 多项式A(x)的系数
 * @param  {Array<number>} Bx 多项式B(x)的系数
 * @returns {Array<number>} 多项式A(x)*B(x)的系数
 */
export default (Ax, Bx) => {
  let d,
    am = [], //增广矩阵 augmented matrix
    Cx = [];

  if (Ax.length > Bx.length) {
    d = Ax.length - 1;
    Bx[Ax.length - 1] = 0;
    while (Bx.push(0) != Ax.length);
  } else if (Bx.length > Ax.length) {
    d = Bx.length - 1;
    while (Ax.push(0) != Bx.length);
  } else {
    d = Ax.length - 1;
  }

  // 计算增广矩阵（O(n^2)）
  for (let i = 0; i < 2 * d + 1; i++) {
    // 循环2*d + 1次
    let x = 1,
      Av = 0,
      Bv = 0;
    am[i] = [];
    for (var j = 0; j < 2 * d + 1; j++) {
      // 循环2*d + 1次
      if (j < d + 1) {
        Av += Ax[j] * x;
        Bv += Bx[j] * x;
      }
      am[i][j] = x;
      x *= i;
    }

    am[i][j] = Av * Bv;
  }

  // 之后就是用增广矩阵求非齐次线性方程组了（O(n^3)，比直接乘都复杂了）

  // 1.三角阵
  for (let i = 0; i < 2 * d; i++) {
    for (let j = i + 1; j < 2 * d + 1; j++) {
      let ratio = am[j][i] / am[i][i];
      am[j] = am[j].map((v, index) => {
        return v - ratio * am[i][index];
      });
    }
  }

  // 2.对角阵
  for (let i = 2 * d; i > 0; i--) {
    for (let j = i - 1; j > -1; j--) {
      let ratio = am[j][i] / am[i][i];
      am[j] = am[j].map((v, index) => {
        return v - ratio * am[i][index];
      });
    }
  }

  // 3.单位阵（思想）
  for (let i = 0; i < 2 * d + 1; i++) {
    Cx[i] = Math.round(am[i][2 * d + 1] / am[i][i]);
  }

  return Cx;
};

开始 FFT

计算：点的选取

多项式A(x)可以变为Ae(x^2) + x * Ao(x^2)（也就是A(x) = Ae(x^2) + x * Ao(x^2)），例如：

A(x) = 1*x^0 + 2*x^1 + 3*x^2 + 4*x^3 = (1*x^0 + 3*x^2) + x * (2*x^0 + 4*x^2)

这时如果选取的点为正负的数对进行计算，就可以简化将近一半的计算量，例如：

x1取1，x2取-1

这时计算：
A(x1) = Ae(x1^2) + x1 * Ao(x1^2)
A(x2) = Ae(x2^2) + x2 * Ao(x2^2)

只需计算：P1 = Ae(1) 和 P2 = 1 * Ao(1)
A(x1) = P1 + P2
A(x2) = P1 - P2

这里的Ae(x) 和Ao(x) 也是可以再分的，这样就可以使用分治了，但选取的正负的数对的平方还得是正负的数对这样才可以简化运算，这样的数存在么？当然存在那就是复数（这里得补点课），例如：

取4个点：
x1取1，x2取-1，x3取i，x4取-i
平方   1             -1
平方           1

取8个点：
取复数 1+0, -1+0, 0+i, 0-i, √2+√2i, -√2-√2i, √2-√2i, -√2+√2i
平方       1+0      -1+0         0+i              0-i
平方             1                         -1
平方                           1

以此类推，取16个点，取32个点。。。

插值：用计算的算法就可解决

用计算的算法就可解决插值问题，那么原理是什么呢？计算相当于n 阶的方阵 M * n 个系数，插值相当于n 阶的方阵 M 的逆矩阵 * n 个计算出来的值，且这个方阵满足M(w)^-1 = 1/n * M(w^-1)，证明如下：

证明：略

图的分解

对图进行深度优先搜索得到森林

代码

Algorithms-JS/dfs.js at master · 1010543618/Algorithms-JS

有向图分解为强连通部件

步骤

  1. 找到出度为 0 的强连通部件（汇点强连通部件）
  2. 删去该强连通部件
  3. 重复执行 1 和 2，直到没有顶点

如何找到汇点强连通部件

因为对图 G 进行深度优先搜索得到的 post 最大的点（最后一个出栈的点）一定位于源点强连通部件中，

PS：注意对图进行深度优先搜索得到森林，而不是仅遍历可以达到的节点。这样从非源点强连通部件的节点开始遍历其 post 的值会加到下一个开始遍历的强连通部件中。例如：

(强连通部件C)--->---(强连通部件C')

若是从C开始遍历post最大的点（最后一个出栈的点）是C中的点

若是从C'开始遍历，post最大的点（最后一个出栈的点）还是C中的点

这样将图 G 翻转得到 GR，对 GR 进行深度优先搜索得到的 post 最大的点（最后一个出栈的点）一定位于汇点强连通部件中。

算法

  1. 将图 G 翻转得到 GR
  2. 对 GR 进行深度优先搜索，按出栈顺序（post 的值）降序排列顶点
  3. 依次从排序后的顶点开始进行深度优先搜索，找到汇点强连通部件
  4. 删除该汇点强连通部件
  5. 重复执行 3 和 4，直到没有顶点

代码

Algorithms-JS/get_strongly_connected_component.js at master · 1010543618/Algorithms-JS

图中的路径

广度优先搜索关注某一顶点的所有能达到的顶点的搜索深度。

贪心算法

最小生成树

Huffman 编码

Hron 公式

SAT 的一种特殊形式，可在线性时间求解。

Horn-satisfiability - Wikipedia

动态规划

最长递增子序列

编辑距离

问题：给字符串x[1...m]与y[1...n]，求使两个字符串对齐的最小代价（不同的列数）。

子问题：E(i,j)，字符串x[1...m]与y[1...n]的前缀x[1...i]与y[1...j]的编辑距离。

子问题间关系：E(i,j) = min{1+E(i-1,j), 1+E(i,j-1)， diff(i,j) + E(i-1,j-1)}

x\y \0 P O L Y N
\0 0 E(0, 0) 1 E(0, 1) 2 3 4 5
E 1 1 diff(1,1) = 1 2 3 4 5
X 2 2 2 3 4 5
P 3 2 diff(3,1) = 0 3 3 4 5
O 4 3 2 3 4 5

背包问题

多副本背包问题

背包容量递增，对每个物品判断加入后是否最优。（要保存先前每个背包容量最优状态下的价值）

单副本背包问题

物品数递增，判断加入当前物品是否最优。（要保存先前每个物品数最优状态下的重量和价值）

矩阵链式相乘

注意：求解方向如下表

j\i 1 2 3 4 5
1 1 最先求解
2 2 其次求解 1 最先求解
3 3 2 其次求解 1 最先求解
4 4 3 2 其次求解 1 最先求解
5 5 最后求解 4 3 2 其次求解 1 最先求解

最短路径

最短可靠路径

Dijkstra 算法：从起点出发，每次将一个最短路径长度最小的点加入已经找到最短路径的节点集合。

  • 类型：贪心算法 + 动态规划 dist(s,j) = min(dist(s,j),dist(s,i)+dist(i,j))
  • 时间复杂度：O(n^2)

所有节点间的最短路径

Floyd-Warshall 算法：取 i 直接去 j 或者 i 去 k 再去 j 的较小值最为最短路径。

  1. 初始两点间路径为两点间的距离 dist(i,j,0) = l(i,j)；
  2. 依次加入顶点 k，计算加入顶点后的最短路径 dist(i,j,k) = min(dist(i,k,k-1)+dist(k,j,k-1),dist(i,j,k-1))。
  • 类型：动态规划
  • 时间复杂度：O(n^3)

无需三维数组，二维即可 dist(i,j) = min(dist(i,k)+dist(k,j),dist(i,j))。因为每次加入点都会计算所有节点间的最短距离，所以和加入点的顺序无关。

c
for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++) {
                if(d[i][k]+d[k][j]<d[i][j]) {
                    d[i][j]=d[i][k]+d[k][j];
                }
            }

旅行商问题（TSP）

子问题：由起点出发经过城市集合S 终点为j经过S集合中每个顶点各一次的最短路径C(S,j)。

树中的独立集

树的独立集可以利用线性规划在线性时间求解。

子问题：子树的最大独立规模。

线性规划（LPs）与归约

单纯形法

线性规划都可以用单纯形法求解

步骤：从一个顶点开始，不断寻找目标函数值较高的顶点，当找不到目标函数值更高的顶点，则当前顶点为最优解。

归约（reduce）

将复杂的问题转化为同等具有代表性的问题

如：求解 dag 的最长路径可以归约到求解最短路径。（取倒数求最短路径即可得到最长路径）

网络流

最大流

步骤：

  1. 寻找一条还有剩余流量的路径；
  2. 找到该路径所有边的剩余流量的最大值m；
  3. 对路径所有边正向减去m，反向加上m；
  4. 重复 1、2、3，直到找不到有剩余流量的路径。

最小分割

得到最大流后，搜索起点能达到的顶点集合L，令R=V-L，集合R和集合L即为最小分割

二部图的匹配

可以被归约到最大流问题。（通过添加起点，终点并对所有边容量都设置为 1）

对偶

LP 的最大问题都有对偶的最小问题。

对偶定理：如果一个线性规划的最优目标函数值有界，则其对偶的最优目标函数值也有界，并且二者相等

零和博弈（游戏）

单纯形算法

  • 顶点：由 n 个不等式定义。
  • 邻居：两个顶点对应的所有不等式有 n-1 个相同

算法

  1. 坐标变换将顶点移动到原点
  2. 判断是否最优
    • 非最优：原点移动到邻居 u，并使 u 成为新的坐标原点
    • 最优：返回结果
  3. 重复 2 直到找到最优

电路值

电路值问题可以归约到线性规划。

如果算法的复杂度是多项式的，则它就能被视为一个包含了多项式数量的计算机电路拷贝的布尔电路。

NP - 完全问题

搜索问题

搜索问题是由一个算法C描述的，以问题实例I和一个可能的解S为输入，运行在关于|I|的多项式时间内。我们说S是I的一个解，当且仅当C(I,S)=true。

根据摩尔定律，时间复杂度为指数的算法的能力将以多项式速度提高，时间复杂度为多项式的算法的能力将以指数熟读提高。

可满足性问题（STA）

Horn 公式和 2SAT 可在线性时间求得。

旅行商问题（TSP)

给定一个实例，寻找一个总费用在预算内的可行路线。

Euler 问题和 Rudrata 问题

Euler 问题（七桥问题）：给定一个图，求一条恰好包含每条边一次的路径。

Rudrata 问题（马踏棋盘问题）：给定一个图，求一条经过每个顶点恰好一次的环路。

Euler 问题和 Rudrata 问题复杂度存在巨大差异的原因在于一个是关注的是边，另一个关注的是顶点。

最小分割和平衡分割

最小分割：给定图和整数 g，求最多包含 g 条边的分割。

平衡分割：给定图和整数 g，将所有顶点分割为S和T，使得|S|>=3，|T|>=3，且S和T之间最多包含 g 条边。

3D 匹配

二部图匹配的推广。

独立集、顶点覆盖和团

独立集：给定图和整数 g，求图中 g 个相互独立的顶点。

顶点覆盖：给定图和整数 g，求图中 g 个能覆盖到每条边的顶点。

团：给定图和整数 g，求图中 g 个两两相连的顶点。

最长路径问题

给定图和整数 g，s 到 t 总权重最少为 g 的路径（不包含重复的顶点）。

背包问题与子集合

子集合：设背包问题的物品价值都等于重量，求最大收益（使带走物品总重量等于负重）。

NP - 完全问题

困难的问题（NP - 完全） 容易的问题（P）
3SAT 2SAT、HORN SAT
旅行商问题 最小生成树
3D 匹配 二部图匹配
背包问题 一元数背包问题
独立集 树的独立集
整数线性规划 线性规划
Rudrata 路径 Euler 路径
平衡分割 最小分割

任意两个困难的问题可以相互归约。

P = NP？

P：多项式的时间（polynomial time）

NP：不确定多项式的时间（nondeterministic polynomial time）

另一种说法：是否存在不能在多项式时间求解的问题？

归约

称一个搜索问题是 NP - 完全的，是指其他所有搜索问题都可以归约到它。

A 归约为 B，B 的难度大于 A。问题的难度沿着归约方向移动，NP - 完全问题是最难的（其他所有搜索问题都可以归约到它）。

NP 问题：

  • ZOE：给定 0-1 值得 M*N 矩阵 A，求一个 0-1 列向量 x 使得Ax = 1,1 表示所有分量都为 1 的行向量（书中貌似有误）。

  • ILP：求满足 Ax <= b 的整数向量 x。

  • 含有成对边的 Rudrata 环路：给定一个图G=(V, E) 和一个集合C（C 属于 E*E），求经过所有顶点一次（Rudrata 环路的要求），且对C中的每个边对(e,e')只能用其一（用了 e 就不能用 e‘）（成对边的要求）的环路。

    所有 NP 问题
    SAT（将所有 NP 问题转化为电路）
    3SAT（给 SAT 增加变量）
    独立集（将 3SAT 变量作为顶点，条件作为边）
    顶点覆盖（|V|-g 个节点的顶点覆盖）
    团问题（图 G 的补集的团）
    3D 匹配（使用四个三元组模拟布尔变量）
    ZOE（将 3D 匹配的图 转化为邻接矩阵求解）
    子集合（将 ZOE 的列视为二进制整数）
    ILP（将 ZOE 的约束方程重写为两个不等式，对每个变量增加新约束）
    Rudrata 环路（ZOE -> 含有成对边的 Rudrata 环路 -> Rudrata 环路）
    TSP（Rudrata 环路的实例视为” 城市间距离为 1，预算等于顶点个数 “的 TSP 的解）

NP - 完全问题的处理

智能穷举搜索

回溯

将问题展开成子问题，通过判断子问题的状态决定下一步操作，子问题的状态有：

  1. 子问题有解：找到问题的一个解
  2. 子问题无解：问题无解，停止继续展开
  3. 不确定：将该子问题继续展开

对于 2SAT 问题，如果存在可满足的赋值，则总可以利用回溯在多项式时间内找到她。

分支定界

将问题展开成子问题，通过判断通过该子问题解决问题的代价是否超过界限（已经计算出来的解）来决定下一步操作，子问题的状态有：

  1. 子问题未超过界限：继续展开
  2. 子问题超过界限：停止展开

计算 “通过该子问题解决问题的代价” 通常也没有高效算法，可以使用能够高速计算的 “通过该子问题解决问题的代价” 的下界来代替。

近似算法

对于实例I，记OPT(I)为最优解目标值，记A(I)为近似算法解的值，最坏情况下的偏离程度为max(i)(A(I)/OPT(I))。

顶点覆盖

利用贪心算法可以在O(logn) 的范围内逼近最优解。

顶点覆盖的更好的近似算法是基于匹配的概念构造的，寻找没有公共端点的边组成的集合。（偏离程度 <= 2）

聚类

k - 聚类（k-clustering）：空间中有 n 个点，给出 k 个大小相等的圆将她们完全覆盖，求这些圆的最小直径。（max(j)max(xa,xb 属于 Cj)d(xa,xb)最小）

k - 聚类的逼近算法：选择 k 个点作为中心，然后将剩余点中与中心点靠近的都划分为一组。选取中心点时遵循 “每次选取的中心点都是距离已选取的中心点最远的点” 的原则。（偏离程度 \<= 2）

TSP

如果城市距离满足三角不等式，则有近似算法：先构造 MST，然后修改访问不止一次的路径。（偏离程度 <= 2）

背包问题

近似算法：将物品价值按比例缩小到n/ε的范围内。算法复杂度由O(nV)提高到O(n^3/ε)。（偏离程度 <= 1-ε）

注：这里书中说的应该是单副本背包问题（这样最高价值才不会超过每个物品的价值之和）。因为该问题是最大问题所以偏离程度小于 1。