ES6的JavaScript算法思想实现之分而治之，动态规划，贪心算法和回溯算法

目的：ES6标准下的JS算法的一些实现代码。（作为记录和启发）

内容：分而治之，动态规划，贪心算法，回溯算法及其著名算法问题。（未完成，待继续）

所有源码在我的Github上（如果觉得不错记得给星鼓励我哦）：ES6的JavaScript算法思想实现之分而治之，动态规划，贪心算法和回溯算法（分别在divide and rule、dynamic programming、greedy、backtracking目录下）

一、基础算法

1、分而治之

概念：分而治之算法可以分为三个部分。1、分解原问题为多个子问题（原问题的多个小实例）；2、解决子问题，用返回解决子问题的方式的递归算法。递归算法的基本情形可以用来解决子问题；3、组合这些子问题的解决方式，得到原问题的解。

分而治之的二分搜索算法如下：

 1 const Compare = {
 2   LESS_THAN: -1,
 3   BIGGER_THAN: 1,
 4   EQUALS: 0
 5 };
 6 
 7 const DOES_NOT_EXIST = -1;
 8 
 9 function defaultCompare(a, b) {
10   if (a === b) {
11     return Compare.EQUALS;
12   }
13   return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
14 }
15 
16 function swap(array, a, b) {
17   /* const temp = array[a];
18   array[a] = array[b];
19   array[b] = temp; */
20   [array[a], array[b]] = [array[b], array[a]];
21 }
22 function partition(array, left, right, compareFn) {
23   const pivot = array[Math.floor((right + left) / 2)];
24   let i = left;
25   let j = right;
26 
27   while (i <= j) {
28     while (compareFn(array[i], pivot) === Compare.LESS_THAN) {
29       i++;
30     }
31     while (compareFn(array[j], pivot) === Compare.BIGGER_THAN) {
32       j--;
33     }
34     if (i <= j) {
35       swap(array, i, j);
36       i++;
37       j--;
38     }
39   }
40   return i;
41 }
42 function quick(array, left, right, compareFn) {
43   let index;
44   if (array.length > 1) {
45     index = partition(array, left, right, compareFn);
46     if (left < index - 1) {
47       quick(array, left, index - 1, compareFn);
48     }
49     if (index < right) {
50       quick(array, index, right, compareFn);
51     }
52   }
53   return array;
54 }
55 function quickSort(array, compareFn = defaultCompare) {
56   return quick(array, 0, array.length - 1, compareFn);
57 }
58 
59 function binarySearchRecursive(array, value, low, high, compareFn = defaultCompare) {
60   if (low <= high) {
61     const mid = Math.floor((low + high) / 2);
62     const element = array[mid];
63     if (compareFn(element, value) === Compare.BIGGER_THAN) {
64       return binarySearchRecursive(array, value, low, mid -1, compareFn);
65     }
66     if (compareFn(element, value) === Compare.LESS_THAN) {
67       return binarySearchRecursive(array, value, mid + 1, high, compareFn);
68     }
69     return mid;
70   }
71   return DOES_NOT_EXIST;
72 }
73 
74 function binarySearch(array, value, compareFn = defaultCompare){
75   const sortedArray = quickSort(array);
76   const low = 0;
77   const high = sortedArray.length - 1;
78   return binarySearchRecursive(array, value, low, high, compareFn);
79 }
80 
81 
82 const array = [8,7,6,5,4,3,2,1];
83 console.log(array);
84 console.log(binarySearch(array,2));
85 console.log(binarySearch(array,16));

binarySearch

2、动态规划

概念：动态规划（dynamic programming，DP）是一种将复杂问题分解成更小的子问题来解决的优化技术（分而治之方法是把问题分解成相互独立的子问题，然后组合它们的答案；而动态规划是将问题分解成相互依赖的子问题）。用动态规划解决问题时，要遵循三个重要步骤：1、定义子问题；2、实现要反复执行来解决子问题的部分（考虑递归）；3、识别并求解出基线条件。

动态规划能解决一些著名算法问题：

2.1 背包问题

描述：给出一组项，各自有值和容量，目标是找出总值最大的项的集合。这个问题的限制是，总容量必须小于等于“背包”的容量。

 1 function knapSack(capacity, weights, values, n) {
 2   const kS = [];
 3   for (let i = 0; i <= n; i++) {
 4     kS[i] = [];
 5   }
 6   for (let i = 0; i <= n; i++) {
 7     for (let w = 0; w <= capacity; w++) {
 8       if ( i === 0 || w === 0) {
 9         kS[i][w] = 0;
10       } else if (weights[i - 1] <= w) {
11         const a = values[i - 1] + kS[i - 1][w - weights[i - 1]];
12         const b = kS[i - 1][w];
13         kS[i][w] = a > b ? a : b;
14       } else {
15         kS[i][w] = kS[i - 1][w];
16       }
17     }
18   }
19   findValues(n, capacity, kS);
20   return kS[n][capacity];
21 }
22 
23 function findValues(n, capacity, kS) {
24   let i = n;
25   let k = capacity;
26    console.log('Items that are part of the solution:');
27   while (i > 0 && k > 0) {
28     if (kS[i][k] !== kS[i - 1][k]) {
29        console.log(
30         'item ' + i + ' can be part of solution w,v: ' + weights[i - 1] + ',' + values[i - 1]
31         );
32       i--;
33       k -= kS[i][k];
34     } else {
35       i--;
36     }
37   }
38 }
39 
40 
41 const values = [3,4,5];
42 const weights = [2,3,4];
43 const capacity = 5;
44 const n = values.length;
45 
46 console.log(knapSack(capacity, weights, values, n));

knapSack

2.2 最长公共子序列

描述：找出一组序列的最长公共子序列（可由另一序列删除元素但不改变余下元素的顺序而得到）。最长子序列是指，在两个字符串序列中以相同顺序出现，但不要求连续（非字符串子串）的字符串序列。

 1 function printSolution(solution, wordX, m, n) {
 2   let a = m;
 3   let b = n;
 4   let x = solution[a][b];
 5   let answer = '';
 6   while (x !== '0') {
 7     if (solution[a][b] === 'diagonal') {
 8       answer = wordX[a - 1] + answer;
 9       a--;
10       b--;
11     } else if (solution[a][b] === 'left') {
12       b--;
13     } else if (solution[a][b] === 'top') {
14       a--;
15     }
16     x = solution[a][b];
17   }
18   return answer;
19 }
20 export function lcs(wordX, wordY) {
21   const m = wordX.length;
22   const n = wordY.length;
23   const l = [];
24   const solution = [];
25   for (let i = 0; i <= m; i++) {
26     l[i] = [];
27     solution[i] = [];
28     for (let j = 0; j <= n; j++) {
29       l[i][j] = 0;
30       solution[i][j] = '0';
31     }
32   }
33   for (let i = 0; i <= m; i++) {
34     for (let j = 0; j <= n; j++) {
35       if (i === 0 || j === 0) {
36         l[i][j] = 0;
37       } else if (wordX[i - 1] === wordY[j - 1]) {
38         l[i][j] = l[i - 1][j - 1] + 1;
39         solution[i][j] = 'diagonal';
40       } else {
41         const a = l[i - 1][j];
42         const b = l[i][j - 1];
43         l[i][j] = a > b ? a : b; // max(a,b)
44         solution[i][j] = l[i][j] === l[i - 1][j] ? 'top' : 'left';
45       }
46     }
47     // console.log(l[i].join());
48     // console.log(solution[i].join());
49   }
50   return printSolution(solution, wordX, m, n);
51 }

LCS

2.3 矩阵链相乘

描述：给出一系列矩阵，目标是找到这些矩阵相乘的最高效办法（计算次数尽可能少）。相乘运算不会进行，解决方案是找到这些矩阵各自相乘的顺序（由于矩阵乘法结合律的原因）。

 1 function matrixChainOrder(p) {
 2   const n = p.length;
 3   const m = [];
 4   const s = [];
 5   for (let i = 1; i <= n; i++) {
 6     m[i] = [];
 7     m[i][i] = 0;
 8   }
 9   for (let i = 0; i <= n; i++) {
10     s[i] = [];
11     for (let j = 0; j <= n; j++) {
12       s[i][j] = 0;
13     }
14   }
15   for(let l = 2; l < n; l++) {
16     for (let i = 1; i <= (n - l) + 1; i++) {
17       const j = (i + l) - 1;
18       m[i][j] = Number.MAX_SAFE_INTEGER;
19       for (let k = i; k <= j - 1; k++) {
20         const q = m[i][k] + m[k + 1][j] +((p[i - 1] * p [k]) * p[j]);
21         if (q < m[i][j]) {
22           m[i][j] = q;
23           s[i][j] = k; 
24         }
25       } 
26     }
27   }
28   printOptimalParenthesis(s, 1, n - 1);
29   return m[1][n - 1];
30 }
31 function printOptimalParenthesis(s, i, j) {
32   if (i === j) {
33     console.log('A[' + i + ']');
34   } else {
35     console.log('(');
36     printOptimalParenthesis(s, i, s[i][j]);
37     printOptimalParenthesis(s, s[i][j] + 1, j);
38     console.log(')');
39   }
40 }
41 const p = [10, 100, 5, 50, 1];
42 console.log(matrixChainOrder(p));

matrixChainOrder

2.4 硬币找零

描述：给出面额为d1,...,dn的一定数量的硬币和要找零的钱数，找出有多少种找零的方法。

我们来研究一下最少硬币找零问题。（找出最少硬币个数的方案）

 1 function minCoinChange(coins, amount) {
 2   const cache = [];
 3 
 4   const makeChange = (value) => {
 5     if(!value) {
 6       return [];
 7     }
 8     if (cache[value]) {
 9       return cache[value];
10     }
11     let min = [];
12     let newMin;
13     let newAmount;
14     for (let i = 0; i < coins.length; i++) {
15       const coin = coins[i];
16       newAmount = value - coin;
17      // console.log(coin);
18       if (newAmount >= 0) {
19         newMin  = makeChange(newAmount);
20       }
21       if (
22         newAmount >= 0 
23         && (newMin.length < min.length - 1 ||!min.length)
24         && (newMin.length || !newAmount)
25         ) {
26         min = [coin].concat(newMin);
27       console.log('new Min ' + min + ' for ' + amount);
28       }
29     }
30     return (cache[value] = min);
31   };
32   return makeChange(amount);
33 }
34 
35 console.log(minCoinChange([1, 3, 4], 6));

minCoinChange

2.5 图的全源最短路径

描述：对所有顶点对（u，v），找出从顶点u到顶点v的最短路径。

用Floyd-Warshall算法：

 1 const floydWarshall = graph => {
 2   const dist = [];
 3   const {length} = graph;
 4   for (let i = 0; i < length; i++) {
 5     dist[i] = [];
 6     for (let j = 0; j < length; j++) {
 7       if (i === j) {
 8         dist[i][j] = 0;
 9       } else if (!isFinite(graph[i][j])) {
10         dist[i][j] = Infinity;
11       } else {
12         dist[i][j] = graph[i][j];
13       }
14     }
15   }
16   for (let k = 0; k < length; k++) {
17     for(let i = 0; i < length; i++) {
18       for (let j = 0; j < length; j++) {
19         if (dist[i][k] + dist[k][j] < dist[i][j]) {
20           dist[i][j] = dist[i][k] + dist[k][j];
21         }
22       }
23     }
24   }
25   return dist;
26 };
27 
28 const INF = Infinity;
29 const graph = [
30   [INF, 2, 4, INF, INF, INF],
31   [INF, INF, 2, 4, 2, INF],
32   [INF, INF, INF, INF, 3, INF],
33   [INF, INF, INF, INF, INF, 2],
34   [INF, INF, INF, 3, INF, 2],
35   [INF, INF, INF, INF, INF, INF]
36 ];
37 
38 dist = floydWarshall(graph);
39 let s = '';
40 for (let i = 0; i < dist.length; i++) {
41   s = '';
42   for (let j = 0; j < dist.length; j++) {
43     if (dist[i][j] === INF) {
44       s += 'INF ';
45     } else {
46       s += dist[i][j] + ' ';
47     }
48    
49   }
50   console.log(s);
51 }
52 
53 floydWarshall

FloydWarshall

3、贪心算法

概念：贪心算法遵循一种近似解决问题的技术，期盼通过每个阶段的局部最优选择（当前最好的解），从而达到全局的最优（全局最优解）。它不像动态规划算法那那样计算更大的格局。

3.1最少硬币找零问题

 1 function minCoinChangeGreedy (coins, amount) {
 2   const change = [];
 3   let total = 0;
 4   for (let i = coins.length; i >= 0; i--) {
 5     const coin = coins[i];
 6     while (total + coin <= amount) {
 7       change.push(coin);
 8       total += coin;
 9     }
10   }
11   return change;
12 }
13 
14 
15 
16 
17 console.log(minCoinChangeGreedy([1, 5, 10], 15)); // [5, 10]
18 console.log(minCoinChangeGreedy([1, 3, 4], 6)); //not the best

minCoinChangeGreedy

3.2 分数背包问题

概念：在分数背包问题中，可以装入分数的物品。

 1 function knapSackGreedy(capacity, weights, values) {
 2   const n = values.length;
 3   let load = 0;
 4   let val = 0;
 5   for (let i = 0; i < n && load < capacity; i++) {
 6     if (weights[i] <= capacity - load) {
 7       val += values[i];
 8       load += weights[i];
 9     } else {
10       const r = (capacity - load) / weights[i];
11       val += r*values[i];
12       load += weights[i]; 
13     }
14   }
15   return val;
16 }
17 
18 
19 
20 const values = [3,4,5];
21 const weights = [2,3,4];
22 const capacity = 5;
23 
24 console.log(knapSackGreedy(capacity, weights, values));

knapSackGreedy

4、回溯算法

概念：回溯是一种渐进式寻找并构建问题解决方式的策略。从一个可能的动作开始并试着用这个动作解决问题。如果不能解决，就回溯并选择另一个动作直到问题解决为止。根据这种行为，回溯算法会尝试所有可能的动作（如果更快找到了解决办法就尝试较少的次数）来解决问题。可用回溯解决的著名问题有：骑士巡逻问题，N皇后问题，迷宫老鼠问题，数独解问题。

4.1 迷宫老鼠问题

 1 function ratInAMaze(maze) {
 2   const solution = [];
 3   for (let i = 0; i < maze.length; i++) {
 4     solution[i] = [];
 5     for (let j = 0; j < maze[i].length; j++) {
 6       solution[i][j] = 0;
 7     }
 8   }
 9   if (findPath(maze, 0, 0, solution) === true) {
10     return solution;
11   }
12   return 'NO PATH FOUND';
13 }
14 
15 function findPath(maze, x, y, solution) {
16   const n = maze.length;
17   if (x === n - 1 && y === n -1) {
18     solution[x][y] = 1;
19     return true;
20   }
21   if (isSafe(maze, x, y) === true) {
22     solution[x][y] = 1;
23     if (findPath(maze, x + 1, y, solution)) {
24       return true;
25     }
26     if (findPath(maze, x, y + 1, solution)) {
27       return true;
28     }
29     solution[x][y] = 0;
30     return false;    
31   }
32   return false;
33 }
34 
35 function isSafe(maze, x, y) {
36   const n = maze.length;
37   if (x >= 0 && y >= 0 && x < n && y < n && maze[x][y] !== 0) {
38     return true;
39   }
40   return false;
41 }
42 
43 const maze = [
44   [1, 0, 0, 0],
45   [1, 1, 1, 1],
46   [0, 0, 1, 0],
47   [0, 1, 1, 1]
48 ];
49 
50 console.log(ratInAMaze(maze));

ratInAMaze

4.2 数独解问题

 1 function sudokuSolver(matrix) {
 2   if (solveSudoku(matrix) ===  true) {
 3     return matrix;
 4   }
 5   return 'NO SOLUTION';
 6 }
 7 const UNASSIGNED = 0;
 8 
 9 function solveSudoku(matrix) {
10   let row = 0;
11   let col = 0;
12   let checkBlankSpaces = false;
13   for (row = 0; row < matrix.length; row++) {
14     for (col = 0; col < matrix[row].length; col++) {
15       if (matrix[row][col] === UNASSIGNED) {
16         checkBlankSpaces = true;
17         break;
18       }
19     }
20     if (checkBlankSpaces === true) {
21       break;
22     }
23   }
24   if (checkBlankSpaces === false) {
25     return true;
26   }
27   for (let num = 1; num <= 9; num++) {
28     if (isSafe(matrix, row, col, num)) {
29       matrix[row][col] = num;
30       if (solveSudoku(matrix)) {
31         return true;
32       }
33       matrix[row][col] = UNASSIGNED;
34     }
35   }
36   return false;
37 }
38 
39 function isSafe(matrix, row, col, num) {
40   return (
41     !usedInRow(matrix, row, num) 
42     && !usedInCol(matrix, col, num) 
43     && !usedInBox(matrix, row - (row % 3), col - (col % 3), num)
44   );
45 }
46 function usedInRow(matrix, row, num) {
47   for (let col = 0; col < matrix.length; col++) {
48     if (matrix[row][col] === num) {
49       return true;
50     }
51   }
52   return false;
53 }
54 
55 function usedInCol(matrix, col, num) {
56   for (let row = 0; row < matrix.length; row++) {
57     if (matrix[row][col] === num) {
58       return true;
59     }
60   }
61   return false;
62 }
63 
64 function usedInBox(matrix, boxStartRow, boxStartCol, num) {
65   for (let row = 0; row < 3; row++) {
66     for (let col = 0; col < 3; col++) {
67       if (matrix[row + boxStartRow][col + boxStartCol] === num) {
68         return true;
69       }
70     }
71   }
72   return false;
73 }
74 const sudokuGrid = [
75   [5, 3, 0, 0, 7, 0, 0, 0, 0],
76   [6, 0, 0, 1, 9, 5, 0, 0, 0],
77   [0, 9, 8, 0, 0, 0, 0, 6, 0],
78   [8, 0, 0, 0, 6, 0, 0, 0, 3],
79   [4, 0, 0, 8, 0, 3, 0, 0, 1],
80   [7, 0, 0, 0, 2, 0, 0, 0, 6],
81   [0, 6, 0, 0, 0, 0, 2, 8, 0],
82   [0, 0, 0, 4, 1, 9, 0, 0, 5],
83   [0, 0, 0, 0, 8, 0, 0, 7, 9]
84 ];
85 
86 console.log(sudokuSolver(sudokuGrid));

sudokuSolver