本篇内容主要讲解“怎么使用栈的记忆化搜索来加速子集和算法”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“怎么使用栈的记忆化搜索来加速子集和算法”吧!
所谓子集和就是在一个数组中找出它的子集,使得该子集的和等于某个固定值。
一般我们都是使用递归加回溯的方式来处理的,代码如下(此处我们只找出一组满足的条件即可)
public class SubSet {private List<Integer> list = new ArrayList<>(); //用于存放求取子集中的元素 @Getter private List<Integer> res = new ArrayList<>(); //求取数组列表中元素和 public int getSum(List<Integer> list) {int sum = 0; for(int i = 0;i < list.size();i++) sum += list.get(i); return sum; }public void getSubSet(int[] A, int m, int step) {if (res.size() > 0) {return; }while(step < A.length) {list.add(A[step]); if (getSum(list) == m) {if (getSum(res) == 0) {res.addAll(list); } } step++; getSubSet(A, m, step); list.remove(list.size() - 1); //回溯执行语句,删除列表最后一个元素 } }public static void main(String[] args) { SubSet test = new SubSet(); int[] A = new int[6]; for(int i = 0;i < 6;i++) { A[i] = i + 1; } test.getSubSet(A, 8, 0); System.out.println(test.getRes()); } }
运行结果
[1, 2, 5]
但是这个算法的时间复杂度非常高,是NP级别的。如果数据量比较大的时候,将很难完成运算。
现在我们用栈和哈希缓存来加速这个算法。主要是缓存计算结果,不用每次都去getSum中把list的和算一遍。其思想主要是记忆化搜索,可以参考本人这篇博客动态规划、回溯、贪心,分治
public class SubSet {private List<Integer> list = new ArrayList<>(); //用于存放求取子集中的元素 @Getter private List<Integer> res = new ArrayList<>(); private Deque<Integer> deque = new ArrayDeque<>(); private Map<String,Integer> map = new HashMap<>(); //求取数组列表中元素和 public int getSum(List<Integer> list) {int sum = 0; for(int i = 0;i < list.size();i++) sum += list.get(i); return sum; }public void getSubSet(int[] A, int m, int step) {if (res.size() > 0) {return; }while(step < A.length) {list.add(A[step]); if (!map.containsKey(deque.toString())) {int sum = getSum(list); deque.push(A[step]); map.put(deque.toString(),sum); if (sum == m) {if (getSum(res) == 0) {res.addAll(list); } } }else {int sum = map.get(deque.toString()) + A[step]; deque.push(A[step]); map.put(deque.toString(),sum); if (sum == m) {if (getSum(res) == 0) {res.addAll(list); } } } step++; getSubSet(A, m, step); list.remove(list.size() - 1); //回溯执行语句,删除列表最后一个元素 deque.pop(); } }public static void main(String[] args) { SubSet test = new SubSet(); int[] A = new int[6]; for(int i = 0;i < 6;i++) { A[i] = i + 1; } test.getSubSet(A, 8, 0); System.out.println(test.getRes()); } }
运算结果
[1, 2, 5]
但C#无法满足获取栈的值,只能获取栈的类型,如果我们用遍历的方式去获取栈的值又回到了以前NP级的时间复杂度,故直接使用数字来做哈希表的键。内容如下
using System; using System.Collections.Generic; using System.Collections; using System.Text.RegularExpressions; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApplication1 { class Program { private class Oranize { public List<decimal> array = new List<decimal>(); public List<decimal> res = new List<decimal>(); public Stack<decimal> stack = new Stack<decimal>(); public Hashtable table = new Hashtable(); public decimal index = 0; public decimal getSum(List<decimal> list) { decimal sum = 0; for (int i = 0; i < list.Count; i++) { sum += list[i]; } return sum; } public String stackValue(Stack<decimal> stack) { StringBuilder sb = new StringBuilder(); foreach (decimal s in stack) { sb.Append(s.ToString()); } return sb.ToString(); } public void org(decimal[] arr,decimal all, int step) { if (res.Count > 0) { return; } while (step < arr.Length) { array.Add(arr[step]); if (!table.ContainsKey(index.ToString())) { decimal sum = getSum(array); stack.Push(index); table.Add(stack.Peek().ToString(), sum); if (sum == all) { if (getSum(res) == 0) { foreach (decimal a in array) { res.Add(a); } } } } else { decimal sum = 0; if (stack.Count > 0) { sum = Convert.ToDecimal(table[stack.Peek().ToString()]) + arr[step]; } else { sum = Convert.ToDecimal(table["0"]) + arr[step]; } index++; stack.Push(index); if (table.ContainsKey(stack.Peek().ToString())) { table.Remove(stack.Peek().ToString()); } table.Add(stack.Peek().ToString(), sum); if (sum == all) { if (getSum(res) == 0) { foreach (decimal a in array) { res.Add(a); } } } } step++; org(arr, all, step); array.RemoveAt(array.Count - 1); stack.Pop(); } } } static void Main(string[] args) { decimal[] A = new decimal[6]; for (int i = 0; i < 6; i++) { A[i] = i + 1; } Oranize oranize = new Oranize(); oranize.org(A, 8, 0); foreach (decimal r in oranize.res) { Console.Write(r + ","); } Console.ReadLine(); } } }
这里我们可以看到如果使用stackValue来获取栈的各个值的字符串是不可取的,同样会非常慢。
由于C#本身的Hashtable在数据量大的情况下存在溢出风险,所以我们要重写哈希表。重写的哈希表的每个节点由红黑树组成,由于我们并不需要删除哈希表内的元素,所以就不写红黑树和哈希表的删除方法。
private class RedBlackTreeMap { private static bool RED = true; private static bool BLACK = false; private class Node { public String key; public decimal value; public Node left; public Node right; public bool color; public Node(String key,decimal value,Node left,Node right,bool color) { this.key = key; this.value = value; this.left = left; this.right = right; this.color = color; } public Node(String key): this(key, 0, null, null, RED) { } public Node(String key,decimal value): this(key, value, null, null, RED) { } } private Node root; private int size; public ISet<String> keySet = new HashSet<String>(); public RedBlackTreeMap() { root = null; size = 0; } private bool isRed(Node node) { if (node == null) { return BLACK; } return node.color; } private Node leftRotate(Node node) { Node ret = node.right; Node retLeft = ret.left; node.right = retLeft; ret.left = node; ret.color = node.color; node.color = RED; return ret; } private Node rightRotate(Node node) { Node ret = node.left; Node retRight = ret.right; node.left = retRight; ret.right = node; ret.color = node.color; node.color = RED; return ret; } private void flipColors(Node node) { node.color = RED; node.left.color = BLACK; node.right.color = BLACK; } public void add(String key,decimal value) { root = add(root, key, value); keySet.Add(key); } private Node add(Node node,String key,decimal value) { if (node == null) { size++; return new Node(key, value); } if (key.CompareTo(node.key) < 0) { node.left = add(node.left, key, value); }else if (key.CompareTo(node.key) > 0) { node.right = add(node.right, key, value); }else { node.value = value; } if (isRed(node.right) && !isRed(node.left)) { node = leftRotate(node); } if (isRed(node.left) && isRed(node.left.left)) { node = rightRotate(node); } if (isRed(node.left) && isRed(node.right)) { flipColors(node); } return node; } public bool contains(String key) { return getNode(root, key) != null; } public decimal get(String key) { Node node = getNode(root, key); return node == null ? 0 : node.value; } public void set(String key,decimal value) { Node node = getNode(root, key); if (node == null) { throw new ArgumentException(key + "不存在"); } node.value = value; } public int getSize() { return size; } public bool isEmpty() { return size == 0; } private Node getNode(Node node,String key) { if (node == null) { return null; } if (key.CompareTo(node.key) == 0) { return node; }else if (key.CompareTo(node.key) < 0) { return getNode(node.left, key); }else { return getNode(node.right, key); } } } private class HashFind { private int[] capacity = {53,97,193,389,769,1543,3079,6151,12289,24593, 49157,98317,196613,393241,786433,1572869,3145739, 6291469,12582917,25165843,50331653,100663319, 201326611,402653189,805306457,1610612741}; //容忍度上界 private static int upperTol = 10; //容忍度下届 private static int lowerTol = 2; private int capacityIndex = 0; private RedBlackTreeMap[] tables; private int M; private int size; public HashFind() { this.M = capacity[capacityIndex]; this.size = 0; tables = new RedBlackTreeMap[M]; for (int i = 0; i < M; i++) { tables[i] = new RedBlackTreeMap(); } } private int hash(String key) { return (key.GetHashCode() & 0x7fffffff) % M; } public void add(String key,decimal value) { RedBlackTreeMap map = tables[hash(key)]; if (map.contains(key)) { map.add(key, value); }else { map.add(key, value); size++; if (size >= upperTol * M && capacityIndex + 1 < capacity.Length) { capacityIndex++; resize(capacity[capacityIndex]); } } } public bool contains(String key) { int index = hash(key); return tables[index].contains(key); } public decimal get(String key) { int index = hash(key); return tables[index].get(key); } public void set(String key,decimal value) { int index = hash(key); RedBlackTreeMap map = tables[index]; if(!map.contains(key)) { throw new ArgumentException(key + "不存在"); } map.add(key, value); } public int getSize() { return size; } public bool isEmpty() { return size == 0; } private void resize(int newM) { RedBlackTreeMap[] newTables = new RedBlackTreeMap[newM]; for (int i = 0; i < newM; i++) { newTables[i] = new RedBlackTreeMap(); } int oldM = this.M; this.M = newM; for (int i = 0; i < oldM; i++) { RedBlackTreeMap map = tables[i]; foreach (String key in map.keySet) { int index = hash(key); newTables[index].add(key, map.get(key)); } } this.tables = newTables; } } private class Oranize { public List<decimal> array = new List<decimal>(); public List<decimal> res = new List<decimal>(); public Stack<decimal> stack = new Stack<decimal>(); public HashFind table = new HashFind(); public decimal index = 0; public decimal getSum(List<decimal> list) { decimal sum = 0; for (int i = 0; i < list.Count; i++) { sum += list[i]; } return sum; } //public String stackValue(Stack<decimal> stack) //{ // StringBuilder sb = new StringBuilder(); // foreach (decimal s in stack) // { // sb.Append(s.ToString()); // } // return sb.ToString(); //} public void org(decimal[] arr, decimal all, int step) { if (res.Count > 0) { return; } while (step < arr.Length) { array.Add(arr[step]); if (!table.contains(index.ToString())) { decimal sum = getSum(array); stack.Push(index); table.add(stack.Peek().ToString(), sum); if (sum == all) { if (getSum(res) == 0) { foreach (decimal a in array) { res.Add(a); } } } } else { decimal sum = 0; if (stack.Count > 0) { sum = Convert.ToDecimal(table.get(stack.Peek().ToString())) + arr[step]; } else { sum = Convert.ToDecimal(table.get("0")) + arr[step]; } index++; stack.Push(index); if (!table.contains(stack.Peek().ToString())) { table.add(stack.Peek().ToString(), sum); } if (sum == all) { if (getSum(res) == 0) { foreach (decimal a in array) { res.Add(a); } } } } step++; org(arr, all, step); array.RemoveAt(array.Count - 1); stack.Pop(); } } }
虽然该算法进行了加速,但是能否算出,依然在于数组元素的个数所组成的和的组合数,比如有1、2、3、4四个数,则这四个数的和的组合数为1、2、3、4、1+2、1+2+3、1+2+4、1+2+3+4、1+3、1+3+4、1+4、2+3、2+3+4、2+4、3+4总共15个。
我们可以用计算组合数算法来进行验证,该算法也是使用递归加记忆化搜索的方式
public class Combine {private static Map<String,Long> map= new HashMap<>(); /** * 计算从m个元素中拿出n个元素的组合数 * @param m * @param n * @return */ private static long comb(int m,int n){ String key= m+","+n; if(n == 0)return 1; if (n == 1)return m; if(n > m / 2)return comb(m,m-n); if(n > 1){if(!map.containsKey(key))map.put(key, comb(m-1,n-1)+comb(m-1,n)); return map.get(key); }return -1; }public static void main(String[] args) {long total = 0; for (int i = 1 ; i <= 4; i++) { total += comb(4,i); } System.out.println(total); } }
运行结果
15
我们现在的主要目的是寻找可计算的节点,我们可以先给出一个比较大的数,比如一个数组中有40个元素
public static void main(String[] args) {long total = 0; for (int i = 1 ; i <= 40; i++) { total += comb(40,i); } System.out.println(total);}
运行结果
1099511627775
由结果可知,40个数的组合数达到了万亿级别,一般我们计算机的计算级数量在亿级别就差不多了,再多的话就比较难算的出来了。当然这里我的个人建议是数组元素数量在28个
public static void main(String[] args) {long total = 0; for (int i = 1 ; i <= 28; i++) { total += comb(28,i); } System.out.println(total);}
运行结果
268435455
这里是2.6亿,最后我们来看一下30的组合数
public static void main(String[] args) {long total = 0; for (int i = 1 ; i <= 30; i++) { total += comb(30,i); } System.out.println(total);}
运行结果
1073741823
运行结果为10亿,所以我们可以看出从28到30,增长的组合数绝对不是一点点。这是一个几何级数的增长。
到此,相信大家对“怎么使用栈的记忆化搜索来加速子集和算法”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。