...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Mathematical Problems in Engineering >A Linear Time Complexity of Breadth-First Search Using P System with Membrane Division
【24h】

A Linear Time Complexity of Breadth-First Search Using P System with Membrane Division

机译：膜分区P系统的广度优先搜索的线性时间复杂度

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

One of the known methods for solving the problems with exponential time complexity such as NP-complete problems is using the brute force algorithms. Recently, a new parallel computational framework called Membrane Computing is introduced which can be applied in brute force algorithms. The usual way to find a solution for the problems with exponential time complexity with Membrane Computing techniques is by P System with active membrane using division rule. It makes an exponential workspace and solves the problems with exponential complexity in a polynomial (even linear) time. On the other hand, searching is currently one of the most used methods for finding solution for problems in real life, that the blind search algorithms are accurate, but their time complexity is exponential such as breadth-first search (BFS) algorithm. In this paper, we proposed a new approach for implementation of BFS by using P system with division rule technique for first time. The theorem shows time complexity of BSF in this framework on randomly binary trees reduced from O(2~d) to O(d).
机译：解决诸如NP-完全问题之类的指数时间复杂性问题的已知方法之一是使用蛮力算法。最近，引入了一种称为膜计算的新并行计算框架，该框架可以应用于蛮力算法。用膜计算技术找到具有指数时间复杂性问题的解决方案的常用方法是使用带有活动膜的P System使用划分规则。它构成了一个指数工作区，并在多项式（甚至线性）时间内解决了指数复杂的问题。另一方面，盲目搜索算法是准确的，但是其时间复杂度却是指数级的，例如广度优先搜索（BFS）算法，它是当前现实生活中解决问题最常用的方法之一。在本文中，我们首次提出了将P系统与划分规则技术结合使用的BFS实现新方法。该定理表明，在随机二叉树上，BSF的时间复杂度从O（2〜d）降低到O（d）。

著录项

  • 来源
    《Mathematical Problems in Engineering》 |2013年第5期|424108.1-424108.11|共11页
  • 作者

    Einallah Salehi; Siti Mariyam Shamsuddin; Kourosh Nemati;

  • 作者单位

    Soft Computing Research Group, Universiti Teknologi Malaysia, 81310 Skudai, Johor, Malaysia;

    Soft Computing Research Group, Universiti Teknologi Malaysia, 81310 Skudai, Johor, Malaysia;

    Soft Computing Research Group, Universiti Teknologi Malaysia, 81310 Skudai, Johor, Malaysia;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号