怎么使用栈的记忆化搜索来加速子集和算法

本篇内容主要讲解"怎么使用栈的记忆化搜索来加速子集和算法"，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习"怎么使用栈的记忆化搜索来加速子集和算法"吧!

所谓子集和就是在一个数组中找出它的子集，使得该子集的和等于某个固定值。

一般我们都是使用递归加回溯的方式来处理的，代码如下(此处我们只找出一组满足的条件即可)

public class SubSet {private List list = new ArrayList<>();   //用于存放求取子集中的元素    @Getter    private List res = new ArrayList<>();    //求取数组列表中元素和    public int getSum(List 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 list = new ArrayList<>();   //用于存放求取子集中的元素    @Getter    private List res = new ArrayList<>();    private Deque deque = new ArrayDeque<>();    private Map map = new HashMap<>();    //求取数组列表中元素和    public int getSum(List 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 array = new List();            public List res = new List();            public Stack stack = new Stack();            public Hashtable table = new Hashtable();            public decimal index = 0;            public decimal getSum(List list)            {                decimal sum = 0;                for (int i = 0; i < list.Count; i++)                {                    sum += list[i];                }                return sum;            }            public String stackValue(Stack 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 keySet = new HashSet();            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 array = new List();            public List res = new List();            public Stack stack = new Stack();            public HashFind table = new HashFind();            public decimal index = 0;            public decimal getSum(List list)            {                decimal sum = 0;                for (int i = 0; i < list.Count; i++)                {                    sum += list[i];                }                return sum;            }            //public String stackValue(Stack 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 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，增长的组合数绝对不是一点点。这是一个几何级数的增长。

到此，相信大家对"怎么使用栈的记忆化搜索来加速子集和算法"有了更深的了解，不妨来实际操作一番吧！这里是网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！