精华内容
下载资源
问答
  • 二进制搜索算法原理
    2020-06-20 01:37:07
    JavaScript

    在本文中,我将比较线性搜索和二进制搜索算法。 您将看到每种算法的伪代码,以及示例和实现每种方法的逐步指南。

    介绍

    作为程序员,您想找到问题的最佳解决方案,以使您的代码不仅正确而且高效。 选择次优算法可能意味着更长的完成时间,增加的代码复杂度或使崩溃的程序更糟。

    您可能已经使用搜索算法来查找数据集合中的项目。 JavaScript语言有多种方法,例如find ,可以在数组中定位项目。 但是,这些方法使用线性搜索。 线性搜索算法从列表的开头开始,并将每个元素与搜索值进行比较,直到找到它为止。

    当元素较少时,这很好。 但是,当您搜索包含数千或数百万个元素的大型列表时,您需要一种更好的方式来查找项目。 这是您将使用二进制搜索的时间。

    在本教程中,我将解释二进制搜索的工作原理以及如何在JavaScript中实现该算法。 首先,我们将回顾线性搜索算法。

    线性搜寻

    我们将首先说明如何在JavaScript中实现线性搜索。 我们将创建一个名为linearSearch的函数,该函数接受一个整数或字符串值以及一个数组作为参数。 该函数将在数组中的每个元素中搜索该值,如果找到该值,则返回该值在数组中的位置。 如果该值不在数组中,则它将返回-1。 例如,调用linearSearch(1, [3, 4, 2, 1, 5])将返回3,而调用linearSearch(0, [3, 4, 2, 1, 5])将返回-1。

    这是我们函数的一些伪代码:

    Set found to false
    Set position to −1
    Set index to 0
    while found is false and index < number of elements
        if list[index] is equal to search value
            Set found to true
            Set position to index
        else Add 1 to index
    return position

    线性搜索JavaScript实现

    这是线性搜索算法JavaScript实现:

    function linearSearch(value, list) {
        let found = false;
        let position = -1;
        let index = 0;
    
        while(!found && index < list.length) {
            if(list[index] == value) {
                found = true;
                position = index;
            } else {
                index += 1;
            }
        }
        return position;
    }

    重要的是要注意,线性搜索算法不需要使用排序列表。 而且,可以自定义算法以用于不同的场景,例如通过键搜索对象数组。 如果您的客户数据数组包含名字和姓氏的键,则可以测试该数组是否有一个具有指定名字的客户。 在这种情况下,您可以检查list[index].first ,而不是检查list[index]是否等于我们的搜索值。

    在上面的示例中,我在具有五个元素的数组上使用了linearSearch函数。 在最坏的情况下,当搜索值不在列表中或不在列表末尾时,该函数将必须进行五次比较。 由于我们的数组很小,因此无需使用其他算法进行优化。 但是,超出某个点,使用线性搜索算法不再有效,也就是说,使用二进制搜索算法会更好。

    二元搜寻

    假设您正在玩数字猜谜游戏。 要求您猜测一个介于1到100之间的数字。如果您的数字太大或太小,都会得到提示。

    您的策略是什么? 您会随机选择数字吗? 您会从1开始,然后从2开始,依此类推,直到猜对为止? 即使您有无限的猜测,您也想通过尽可能少的尝试做出正确的猜测。 因此,您可以从猜测50开​​始。如果数字较高,则可以猜测75。如果数字较低,则表示数字在50到75之间,您可以选择一个中间的数字。 您将继续这样直到到达正确的数字。 这类似于二进制搜索的工作方式。

    与线性搜索不同,二进制搜索使用排序列表。 要搜索值,首先将值与列表的中间元素进行比较。 如果它们相等,则找到搜索值。 如果搜索值大于中间元素,则搜索数据的上半部分。 然后,将本节的中间元素与搜索值进行比较。 或者,如果该项小于中间元素,则搜索列表的下半部分并比较其中间值。 将该列表重复分成两半,直到找到该元素或没有其他要搜索的项目为止。

    要在列表中搜索9:

    1 2 3 4 5 6 7 8 9 10

    我们首先找到中间元素。 这是位置Math.floor((first + last)/2)处的元素,其中first是第一个索引, last是最后一个索引。 我们选择四舍五入,以便如果结果为分数,则变为整数。 该列表的中间元素为5。我们的搜索值9大于5,因此我们搜索列表:

    6 7 8 9 10

    这部分的中间元素是8。9大于8,所以我们搜索列表:

    9 10

    中间元素是9,因此我们可以在此处停止搜索。

    这是一些表示上述用于二进制搜索的算法的伪代码:

    Set first to 0
    Set last to the last index in the list
    Set found to false
    Set position to −1
    while found is false and first is less than or equal to last
        Set middle to the index halfway between first and last
        if list[middle] equals the desired value
            Set found to true
            Set position to middle
        else if list[middle] is greater than the desired value
            Set last to middle − 1
        else
            Set first to middle + 1
    return position

    二进制搜索JavaScript实现

    现在,让我们用JavaScript编写二进制搜索算法!

    我们将创建一个函数binarySearch ,该函数接受一个值和一个数组作为参数。 如果找到,它将返回列表中值所在位置的索引。 如果找不到该值,则返回-1。 这是我们用JavaScript编写的实现:

    function binarySearch(value, list) {
        let first = 0;    //left endpoint
        let last = list.length - 1;   //right endpoint
        let position = -1;
        let found = false;
        let middle;
    
        while (found === false && first <= last) {
            middle = Math.floor((first + last)/2);
            if (list[middle] == value) {
                found = true;
                position = middle;
            } else if (list[middle] > value) {  //if in lower half
                last = middle - 1;
            } else {  //in in upper half
                first = middle + 1;
            }
        }
        return position;
    }

    结论

    在本教程中,我们看到了如何实现线性搜索和二进制搜索算法。 线性搜索算法更简单,不需要排序数组。 但是,与较大的数组一起使用时效率很低。 在最坏的情况下,该算法必须搜索所有进行n次比较的元素(其中n是元素数)。

    另一方面,二进制搜索算法要求您首先对数组进行排序,并且实现起来更加复杂。 但是,即使考虑分拣成本,它也更有效。 例如,具有10个元素的数组最多可以对二进制搜索进行4个比较,而对于线性搜索最多可以进行10个比较-并不是很大的改进。 但是,对于具有1,000,000个元素的数组,二进制搜索中最坏的情况是只有20个比较。 与线性搜索相比,这是一个巨大的进步!

    知道如何使用二进制搜索不仅是面试问题的练习内容。 这是一项实用技能,可以使您的代码更高效地工作。

    翻译自: https://code.tutsplus.com/tutorials/the-binary-search-algorithm-in-javascript--cms-30003

    更多相关内容
  • 二进制搜索算法原理.doc
  • 射频识别技术(RFID)是从20世纪80年代走向成熟的一项自动识别技术[1]。...介绍了常用防碰撞算法原理,并详细分析了二进制搜索算法原理和实现过程,最后对算法的效率进行了研究和比较,得出了改进的建议。
  • 提出一种基于模型的配电网故障诊断方案,该方案首先根据配电网原理模型的仿真数据和实际观测值存在的差异得到极小冲突集,然后由离散二进制粒子群优化算法推出可能的故障元件和故障形式,最后由贝叶斯方法确定概率...
  • 动态二进制树搜索算法 二进制搜索树 (Binary Search Tree) A binary search tree is a useful data structure for fast addition and removal of data. 二进制搜索树是用于快速添加和删除数据的有用数据结构。 It...

    动态二进制树搜索算法

    A binary search tree is a useful data structure for fast addition and removal of data.

    二进制搜索树是用于快速添加和删除数据的有用数据结构。

    It is composed of nodes, which stores data and also links to upto two other child nodes. It is the relationship between the leaves linked to and the linking leaf, also known as the parent node, which makes the binary tree such an efficient data structure.

    它由节点组成,节点存储数据并链接到最多两个其他子节点。 链接到的叶子与链接叶子(也称为父节点)之间的关系使二叉树成为一种高效的数据结构。

    For a binary tree to be a binary search tree, the data of all the nodes in the left sub-tree of the root node should be less than the data of the root. The data of all the nodes in the right subtree of the root node should be greater than equal to the data of the root. As a result, the leaves on the farthest left of the tree have the lowest values, whereas the leaves on the right of the tree have the greatest values.

    为了使二叉树成为二叉搜索树,根节点左子树中所有节点的数据应小于根节点的数据。 根节点右子树中所有节点的数据应大于等于根节点的数据。 结果,树最左边的叶子具有最低的值,而树右边的叶子具有最大的值。

    A representation of binary search tree looks like the following:

    二进制搜索树的表示形式如下所示:

    Binary Search Tree

    Consider the root node 20. All elements to the left of subtree(10, 5) are less than 20 and all elements to the right of subtree(25, 30, 35) are greater than 20.

    考虑根节点20。子树(10,5)左侧的所有元素都小于20,子树(25,30,35)右侧的所有元素都大于20。

    实施BST (Implementation of BST)

    First, define a struct as tree_node. It will store the data and pointers to left and right subtree.

    首先,将一个结构定义为tree_node 。 它将存储数据以及指向左和右子树的指针。

    struct tree_node
    {
    	int data;
    	tree_node *left, *right;
    };

    The node itself is very similar to the node in a linked list. A basic knowledge of the code for a linked list will be very helpful in understanding the techniques of binary trees.

    该节点本身与链表中的节点非常相似。 链表代码的基本知识将有助于理解二叉树的技术。

    It is most logical to create a binary search tree class to encapsulate the workings of the tree into a single area, and also making it reusable. The class will contain functions to insert data into the tree, search if the data is present and methods for traversing the tree.

    创建二进制搜索树类以将树的工作封装到单个区域中并使其可重用是最合乎逻辑的。 该类将包含将数据插入树中,搜索数据是否存在以及遍历树的方法的函数。

    class BST
    {
    	tree_node *root;
    	void insert(tree_node* , int );
    	bool search(int , tree_node* );
    	void inorder(tree_node* );
    	void preorder(tree_node* );
    	void postorder(tree_node* );
    
    	public:
    	BST()
    	{
    		root = NULL;
    	}
    	void insert(int );
    	bool search(int key);
        void inorder();
        void preorder();
        void postorder();
    };

    It is necessary to initialize root to NULL for the later functions to be able to recognize that it does not exist.

    必须将root初始化为NULL,以便以后的功能能够识别它不存在。

    All the public members of the class are designed to allow the user of the class to use the class without dealing with the underlying design. The functions which will be called recursively are the ones which are private, allowing them to travel down the tree.

    该类的所有公共成员都被设计为允许该类的用户使用该类,而无需处理基础设计。 将被递归调用的函数是私有的,从而使它们可以向下移动。

    插入BST (Insertion in a BST)

    To insert data into a binary tree involves a function searching for an unused node in the proper position in the tree in which to insert the key value. The insert function is generally a recursive function that continues moving down the levels of a binary tree until there is an unused leaf in a position which follows the following rules of placing nodes.

    将数据插入二叉树涉及到一个函数,该函数在树中要插入键值的适当位置中搜索未使用的节点。 插入函数通常是递归函数,它继续向下移动二叉树的级别,直到某个位置上有未使用的叶子为止,该叶子遵循以下放置节点的规则。

    • Compare data of the root node and element to be inserted.

      比较根节点和要插入的元素的数据。

    • If the data of the root node is greater, and if a left subtree exists, then repeat step 1 with root = root of left subtree. Else,

      如果根节点的数据更大,并且存在左子树,则使用root = left subtree的root重复步骤1。 其他,

    • Insert element as left child of current root.

      插入元素作为当前根的左子元素。

    • If the data of the root node is greater, and if a right subtree exists, then repeat step 1 with root = root of right subtree.

      如果根节点的数据更大,并且存在右子树,则使用root = right subtree的root重复步骤1。

    • Else, insert element as right child of current root.

      否则,将元素插入为当前根的右子元素。

    Binary Search Tree
    void BST :: insert(tree_node *node, int d)
    {
    	// element to be inserted is lesser than node’s data
    	if(d < node->data)
    	{
    		// if left subtree is present
    		if(node->left != NULL)
    			insert(node->left, d);
    		
    		// create new node
    		else
    		{
    			node->left = new tree_node;
    			node->left->data = d;
    			node->left->left = NULL;
    			node->left->right = NULL;
    		}
    	}
    
    	// element to be inserted is greater than node’s data
    	else if(d >= node->data)
    	{
    		// if left subtree is present
    		if(node->right != NULL)
    			insert(node->right, d);
    		
    		// create new node
    		else
    		{
    			node->right = new tree_node;
    			node->right->data = d;
    			node->right->left = NULL;
    			node->right->right = NULL;
    		}
    	}
    	
    }

    Since the root node is a private member, we also write a public member function which is available to non-members of the class. It calls the private recursive function to insert an element and also takes care of the case when root node is NULL.

    由于根节点是私有成员,因此我们还编写了一个公共成员函数,该函数可供该类的非成员使用。 它调用私有递归函数来插入元素,并且还要注意当根节点为NULL时的情况。

    void BST::insert(int d)
    {
    	if(root!=NULL)
                    insert(root, d);
    	else
        {
            root = new tree_node;
            root->data = d;
            root->left = NULL;
            root->right = NULL;
        }
    }

    在BST中搜索 (Searching in a BST)

    The search function works in a similar fashion as insert. It will check if the key value of the current node is the value to be searched. If not, it should check to see if the value to be searched for is less than the value of the node, in which case it should be recursively called on the left child node, or if it is greater than the value of the node, it should be recursively called on the right child node.

    搜索功能的工作方式与插入类似。 它将检查当前节点的键值是否为要搜索的值。 如果不是,则应检查要搜索的值是否小于节点的值,在这种情况下,应在左侧的子节点上递归调用该值,或者应大于节点的值,应该在正确的子节点上递归调用它。

    • Compare data of the root node and the value to be searched.

      比较根节点的数据和要搜索的值。

    • If the data of the root node is greater, and if a left subtree exists, then repeat step 1 with root = root of left subtree. Else,

      如果根节点的数据更大,并且存在左子树,则使用root = left subtree的root重复步骤1。 其他,

    • If the data of the root node is greater, and if a right subtree exists, then repeat step 1 with root = root of right subtree. Else,

      如果根节点的数据更大,并且存在右子树,则使用root = right subtree的root重复步骤1。 其他,

    • If the value to be searched is equal to the data of root node, return true.

      如果要搜索的值等于根节点的数据,则返回true。

    • Else, return false.

      否则,返回false。

    bool BST::search(int d, tree_node *node)
    {
    	bool ans = false;
    
    	// node is not present
      	if(node == NULL)
     		return false;
    	
    	// Node’s data is equal to value searched
        if(d == node->data)
          	return true;
    	
    	// Node’s data is greater than value searched
        else if(d < node->data)
           	ans = search(d, node->left);
    
    	// Node’s data is lesser than value searched
        else
           	ans = search(d, node->right);
      
        return ans;
    }

    Since the root node is a private member, we also write a public member function which is available to non-members of the class. It calls the private recursive function to search an element and also takes care of the case when root node is NULL.

    由于根节点是私有成员,因此我们还编写了一个公共成员函数,该函数可供该类的非成员使用。 它调用私有递归函数来搜索元素,并且还要注意根节点为NULL的情况。

    bool BST::search(int d)
    {
    	if(root ==  NULL)
    		return false;
    	else	
    		return  search(d, root);
    }

    在BST中遍历 (Traversing in a BST)

    There are mainly three types of tree traversals:

    树遍历主要有三种类型:

    1.预定遍历: (1. Pre-order Traversal:)

    In this technique, we do the following :

    在此技术中,我们执行以下操作:

    • Process data of root node.

      根节点的处理数据。

    • First, traverse left subtree completely.

      首先,完全遍历左子树。

    • Then, traverse right subtree.

      然后,遍历右子树。

    void BST :: preorder(tree_node *node)
    {
    	if(node !=  NULL)
        {
    		cout<<node->data<<endl;
           	preorder(node->left);
           	preorder(node->right);
        }
    }

    2.订单遍历 (2. Post-order Traversal)

    In this traversal technique we do the following:

    在这种遍历技术中,我们执行以下操作:

    • First traverse left subtree completely.

      完全遍历左子树。

    • Then, traverse right subtree completely.

      然后,完全遍历右子树。

    • Then, process data of node.

      然后,处理节点的数据。

    void BST :: postorder(tree_node *node)
    {
    	if(node !=  NULL)
       	{
            postorder(node->left);
            postorder(node->right);
    	    cout<<node->data<<endl;
       	}
    }

    3.有序遍历 (3. In-order Traversal)

    In in-order traversal, we do the following:

    在有序遍历中,我们执行以下操作:

    • First process left subtree.

      首先处理左子树。

    • Then, process current root node.

      然后,处理当前的根节点。

    • Then, process right subtree.

      然后,处理右子树。

    void BST :: inorder(tree_node *node)
    {
    	if(node !=  NULL)
       	{
            inorder(node->left);
    	    cout<<node->data<<endl;
            inorder(node->right);
       	}
    }

    The in-order traversal of a binary search tree gives a sorted ordering of the data elements that are present in the binary search tree. This is an important property of a binary search tree.

    二进制搜索树的有序遍历给出了二进制搜索树中存在的数据元素的排序顺序。 这是二进制搜索树的重要属性。

    Since the root node is a private member, we also write public member functions which is available to non-members of the class. It calls the private recursive function to traverse the tree and also takes care of the case when root node is NULL.

    由于根节点是私有成员,因此我们还编写了公共成员函数,该函数可供该类的非成员使用。 它调用私有递归函数遍历树,并且还照顾根节点为NULL的情况。

    void BST :: preorder()
    {
    	if(root ==  NULL)
    		cout<<"TREE IS  EMPTY\n";
    	else
           	preorder(root);
    }
    
    void BST :: postorder()
    {
    	if(root ==  NULL)
    		cout<<"TREE IS  EMPTY\n";
    	else
    	    postorder(root);
    }
    
    void BST :: inorder()
    {
    	if(root == NULL)
    		cout<<"TREE IS EMPTY\n";
    	else
    		inorder(root);
    }

    复杂度分析 (Complexity Analysis)

    Binary Search Tree

    The time complexity of search and insert rely on the height of the tree. On average, binary search trees with n nodes have O(log n) height. However in the worst case the tree can have a height of O(n) when the unbalanced tree resembles a linked list. For example in this case :

    搜索和插入的时间复杂度取决于树的高度。 平均而言,具有n个节点的二叉搜索树的高度为O(log n) 。 但是,在最坏的情况下,当不平衡树类似于链表时,树的高度可能为O(n) 。 例如在这种情况下:

    Binary Search Tree

    Traversal requires O(n) time, since every node must be visited.

    遍历需要O(n)时间,因为必须访问每个节点。

    翻译自: https://www.studytonight.com/data-structures/binary-search-tree

    动态二进制树搜索算法

    展开全文
  • 物联12:二进制树型搜索算法

    万次阅读 2015-04-15 10:43:49
     纯ALOHA算法和时隙ALOHA算法的信道最佳利用率为18.4%和36.8%,随着标签数量的增加,其性能急剧恶化,因此人们提出了二进制搜索算法。二进制防碰撞算法基于轮询的办法,按照二进制树模型和一定的顺序对所有的可能...

    二进制树型搜索算法

            纯ALOHA算法和时隙ALOHA算法的信道最佳利用率为18.4%和36.8%,随着标签数量的增加,其性能急剧恶化,因此人们提出了二进制搜索算法。二进制防碰撞算法基于轮询的办法,按照二进制树模型和一定的顺序对所有的可能进行遍历,因此它不是基于概率的箅法,而是一种确定性的防碰撞算法,但该算法要将所有可能全部遍历,因此其应用起来比较慢。

            二进制树型搜索算法由读写器控制,基本思想是不断的将导致碰撞的电子标签进行划分,缩小下一步搜索的标签数量,直到只有一个电子标签进行回应。

    二进制搜索算法的基本思路是,多个标签进入读写器工作场后,读写器发送带限制条件的询问命令,满足限制条件的标签回答,如果发生碰撞,则根据发生错误的位修改限制条件,再一次发送询问命令,直到找到一个正确的回答,并完成对该标签的读写操作。对剩余的标签重复以上操作,直到完成对所有标签的读写操作。      

            为了实现二进制搜索算法,就要选用曼彻斯特编码,因为这种编码可以检测出碰撞位。    为了实现这个算法,引入以下4种命令。

    1.冲突位检测

            实现该算法系统的必要前提是能够辨认出在读写器中数据冲突位的准确位置。为此,必须有合适的位编码法。如图对NRZ编码和曼彻斯特编码的冲突状况作一比较。

    1)NRZ编码

            如果两个电子标签之一发送了副载波信号,那么,这个信号由读写器译码为“高”电平,就被认定为逻辑“1”。但读写器不能确定读入的某位究竟是若干个电子标签发送的数据相互重叠的结果,还是某个电子标签单独发送的信号。

    2)曼彻斯特编码

           如果两个或多个电子标签同时发送的数位有不同值,则接收的上升沿和下降沿互相抵消,“没有变化”的状态是不允许的,将作为错误被识别。用这种方法可以按位追溯跟踪冲突的出现。

      

             结论:二进制搜索算法,要选用曼彻斯特编码。

    2.用于“二进制树搜索”算法命令

    1)REQUEST 请求系列号

        发送一序列号作为参数给区域内标签。序列号小于或者等于的标签,回送其序列号给阅读器。(缩小范围)

    2)SELECT  选择系列号

        用某个(事先确定的)序列号作为参数发送给标签。具有相同的序列号的标签将以此作为执行其他命令(读出和写入)的切入开关,即选择了标签。

    3)READDATA  读出数据

         选中的标签将存储的数据发送给阅读器。

    4)UNSELECT   退出选择

         取消一个事先选中的标签,标签进入无声状态,这样标签对REQUEST命令不作应答。

    3.二进制树型搜索算法过程

        基本思想是将处于冲突的标签分成左右两个子集0和1,先查询子集0,若没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集0分成00和01两个子集,依次类推,直到识别出子集0中所有标签,再按此步骤查询子集1。

        因此,标签的序列号是处理碰撞的基础。

      

            具体实例,参照后一篇博文。

    展开全文
  • 提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 一、0-1背包问题 1、问题描述 2、数学模型 二 、二进制灰狼算法 1、引言 2、算法改进 3、数学模型 4、算法流程 三、源代码 四、运行...

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

    一、0-1背包问题

    1、问题描述

    背包问题早在 1978 年由 M. Ralph 和 H. Martin 提出,是一种组合优化类的 NP(Non-deterministic Polynomial)难解问题,简单来说,就是解决如何将有限的空间更高效地利用起来,即将不同价值和体积的物品装入背包中,从而使背包所载物品价值最大的问题。在包括 0-1 背包问题、完全背包问题及多重背包问题的三类背包问题中,0-1 背包问题自提出就受到众多学者的广泛关注。
    对于 0-1 背包问题的解法,就其计算复杂度来看,可以大致分为三类:传统算法如动态规划法、贪心算法、分支界定法及回溯法等;启发式算法如和声搜索算法、化学反应算法和预期效率算法等;另一种就是群智能优化算法,如差分进化算法、粒子群算法和遗传算法等都被应用于求解 0-1 背包问题中。对比来看,传统算法虽然可以得到精确解,但是无法解决因物品种类增加而形成的组合爆炸问题,启发式算法时间复杂度相对传统算法低些,但较难得到精确解,仍无法满足需求,而群智能算法的兴起有效地解决了这类问题,这类算法克服了传统算法与启发式算法存在的一些不足,提高了问题的求解精度与优化方案。
    0-1 背包问题作为经典的组合优化问题,它旨在寻找背包容积限制下物品价值达到最大的物品装载方案。0-1 背包问题目前已被应用于组合数学的优化、快递物流配送、企业规划等诸多领域。解决了此类问题,可以帮助人们高效地解决同类生活实际问题,进而提高人类的生存能力,是十分有意义的,随着问题复杂度的增加以及规模的扩大,对于其求解方法有着较高的要求,传统方法暴露出更多的局限性,因此,找到一种求解此类问题的高效的解决方法,就变得十分有意义。

    2、数学模型

    经典 0-1 背包问题的主要思路:有很多待选择的不同物品,每种物品都有自己的体积和价值,选择其中的部分放入背包,而背包的承受量和每一物品的体积及价值已知,问如何选择,才能使得在限定的总容量内,物品的总价值最高。通过描述建立如下的模型:这里假设背包容积为C,有m 个物品待选择,其中第i个物品的体积为wi,价值为pi,xi=1表示物品被装入背包中,xi=0表示物品不装入背包中,其中 i=i,2,3…m。这样问题就可以描述如下: f(x)为目标函数,maxf(x)表示物品总价值的最大值,约束条件为装入背包中的物品总容积不大于背包的最大容积。

    二 、二进制灰狼算法

    1、引言

    灰狼算法在连续灰太狼优化(CGWO)中,狼不断地改变它们在空间中的位置。在一些特殊的问题,如0-1背包问题的解决方案被限制在二进制{0,1}值,这激发了一个特殊版本的GWO。
    在bGWO中,任何给定的解都是二进制形式的,所有的解都位于超立方体的角上。根据CGWO原理更新给定狼的位置。

    2、算法改进

    在二进制灰狼算法中,引入了传递函数(sigmod函数)。利用传递函数将朝向前三个最佳解的各个步骤进行二值化,然后在三个基本移动之间执行随机交叉以找到更新的二值灰太狼位置。[1]

    3、数学模型

    1)x1、x2、x3的结算
    x1为α在二进制中的位置矢量,bstepα为二进制步长,可利用公式2计算
    cstepα为α的连续值步长,可用公式3计算。
    其中,公式3中的A1、Dα为连续灰狼算法中的A1、Dα。
    ps:x2、x3的计算方式与x1相同。

    公式1
    在这里插入图片描述
    公式2
    在这里插入图片描述
    公式3
    在这里插入图片描述

    4、算法流程

    在这里插入图片描述

    三、源代码

    
    clear all 
    clc
    
    NIND=100; % 种群数
    MAXGEN=500; % 最大迭代次数
    V=[44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63];%物品价值
    W=[92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58];
    C=878;%物品重量   
    N=length(V);%物品个数
    afa=3;惩罚函数
    t=0;循环次数
    FC=0;方差
    while t<30
    [Best_score,Best_pos,GWO_cg_curve]=bGWO1(NIND,MAXGEN,N,W,C,V,afa);
    display(['第',num2str(t+1),'次循环,价值为' ,num2str(Best_score)]);
    t=t+1;
    mean(t,1)=Best_score;
    end
    Best_score=sum(mean)/t;
    for x=1:t
        FC=FC+(mean(x,1)-Best_score)^2;
    end
    FC=sqrt(FC);
    
     display(['最大值: ', num2str(max(mean))]);
     display(['最小值: ', num2str(min(mean))]);
     display(['平均值: ', num2str(Best_score)]);
     display(['方差: ', num2str(FC)]);
    

    四、运行结果

    	最大值: 1024
    	最小值: 1024
    	平均值: 1024
    	方差: 0
    

    对OR-Library中9个算例进行测试的结果如下:
    的

    五、备注

    完整代码或者代写添加QQ437651208

    [1] Sa A , Pa B . Binary butterfly optimization approaches for feature selection - ScienceDirect[J]. Expert Systems with Applications, 2019, 116:147-160.

    展开全文
  • RFID-二进制搜索

    千次阅读 热门讨论 2019-06-16 22:28:22
    MATLAB编程实现二进制搜索与二分支搜索
  • 讲述 离散二进制原理 ,以背包问题具体讲解离散二进制粒子群。代码语言:python、MATLAB。
  • 这里写自定义目录标题原理: 实现语言:python 实验要求: (1)普通二进制树搜索: 设计一个1、11、21…标签数目 ...1.普通二进制搜索算法 二进制搜索技术以唯一的序列号来识别射频电子标签为基础。
  •   二制树型搜索算法由读写器控制,基本思想是...二进制树型搜索算法的模型如图所示,其基本思想是将处于冲突的标签分成左 右两个子集0和1,先查询子集0,若没有冲突,则正确识别标签,若仍有冲突 则再分
  • 原理:随机二进制算法需要每个标签维持一个计数器,计数器初始值为 0。 在每一个时隙开始时,如果标签的计数器为 0 时,则立即发送自己的标识符,否则该时隙不响应。 一般标签被成功识别,则该标签进入沉默状态...
  • 提出了一种基于二进制编码的优化关联规则挖掘算法,该算法是按项目支持数的升序从高到低地编制二进 制位,然后将事务转换成数字事务,通过构建候选数字事务区间来搜索频繁数字事务,最后产生关联规则.该算法原理...
  • 其基本思想是不断的将导致碰撞的电子标签进行划分,缩小下一步搜索的标签数量,直到没有发生碰撞。其具体实现步骤如下: 1、读写器广播发送最大序列号查询条件Q,其作用范围内的标签在同一时刻传输它们的序列号至...
  • 基于二进制正余弦算法的背包问题求解- 附代码 文章目录基于二进制正余弦算法的背包问题求解- 附代码1.二进制正余弦算法2.背包问题3.实验结果4.参考文献5.Matlab 摘要:本文主要介绍二进制正余弦算法,并用其对背包...
  • verilog语言实现简易二进制计算器

    千次阅读 2022-01-17 16:13:56
    建立二进制数转BCD码模块 原理为移位加三算法,由于8位二进制数最多位255,因此需要的最多的BCD码位数位10位,因此输出为10为用二进制表示的10进制数。代码如下。 module transferbcd( input wire [7:0] b, output ...
  • 1. 什么是离散粒子群算法? 普通粒子群算法(Particle Swarm Optimization Algorithm,PSO)的粒子初始位置、更新速度都是连续函数,与之对应,位置和速度更新均为离散值的算法是离散PSO算法(Discrete Particle ...
  • 在计算机安全与黑客攻防领域,CTF挑战经常以竞赛形式进行,目标是分析并利用指定的二进制文件,或者正在运行的进程/服务器,直至拿到隐藏在二进制文件中的“flag”为止。flag一般是十六进制的字符串,你可以用它来...
  •   最近在写一个golang实现的字符串搜索与替换程序练手,其中一个很大的问题就是程序不能识别二进制文件与文本文件,导致搜索出来的内容会乱码,非常的不雅观。如果再不小心替换一下的话,就会造成很大的影响,所以...
  • 题目:1000瓶药水,1瓶有毒药,服用后一小时...从0-7的顺序将三位的二进制数按顺序(如图)写出来,写好之后从横向看,三行就分配给三只老鼠,一代表是用这些瓶子的毒药做 了混合,零就是没有用到这些瓶子里的毒药。..
  • 二进制树型搜索算法由读写器控制。基本思想是不断将导致碰撞的电子标签进行划分,缩小下一步搜索的标签数量,直到只有一个电子标签进行回应,即没有碰撞发生。具体方法是将处于冲突的标签分为左右两个子集0和1,先...
  • Problem Description Everybody knows the number is saved with the binary string in the computer. Now, their have N (1 ) binary strings I tell you, your task is tell me what is the most binary ...
  • 但是我不会逐步解释算法,而是会深入了解二进制搜索的工作原理和使用方式。 如果您不知道Binary Search,请查看: geeksforgeeks.org/binary-search 。 给定一个已排序的数组,我们找到最中间的元素并使用键...
  •  二进制树型搜索算法由读写器控制,基本思想是不断的将导致 碰撞的电子标签进行划分,缩小下一步搜索的标签数量,直到只有 一个电子标签进行回应(即没有碰撞发生)。 二进制树型搜索算法实现步骤为:  【1】...
  • 二进制树型搜索算法步骤: 1.将处于冲突的标签分成左右两个子集0和1。 2.先查询子集0,若没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集0分裂成00和01两个子集。 3.依次类推,知道识别出子集0中的所有标签...
  • K8s——部署二进制方式---详解

    千次阅读 2021-09-24 13:55:29
    文章目录一.Kubernetes架构与组件示意图.部署准备 一.Kubernetes架构与组件示意图 .部署准备 准备三台虚拟机,master的cpu给大点
  • 两个n位二进制数分别存储在两个n元数组A和B中,这两个整数的和存在一个n+1元的数组C中答:此问题主要是考察相加进位的问题,元素1+1 =0 并且往前进一位ADD-BINARY(A,B)C=new integer[A.length+1]carry=0for i=A....
  • 图片来源于网络都知道计算机数据是以二进制数0和1补码的形式存储在内存中。那你知道它们转换关系吗?那么问题来了,为什么要转换?前面已经说过计算机数据是以二进制0和1存储,所以它们要转换为二进制存储在计算机中...
  • 使用二进制来表示数据状态

    千次阅读 2020-04-30 14:51:44
    使用二进制的方式来表示数据状态(支持无顺序状态) 文章目录使用二进制的方式来表示数据状态(支持无顺序状态)1. 背景介绍2. 通过一个案例引发思考2.1 当签章有顺序时,我们是如何设计的?2.2 当签章顺序无法控制...
  • 起初,我是希望寻找一个工具能够对比二进制文件的相似度,通过搜索之后,定位到了ssdeep这个工具,对这个工具进行了实践,能够得到一些相应的结果。但在这个过程中发现了一个博客复现了大致是17/18年左右一篇顶会...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 49,573
精华内容 19,829
关键字:

二进制搜索算法原理