检索结果-内蒙古大学图书馆

On the design of a constructive algorithm to solve the multi-peg towers of Hanoi problem

THEORETICAL COMPUTER SCIENCE 2000年第1-2期237卷 407-421页

作者： Sarkar, UK Indian Inst Management Calcutta 700027 W Bengal India

The multi-peg Towers of Hanoi problem is still open. No provably optimal constructive algorithm to solve the problem is known. The minimum number of moves required is also unknown. This paper analyses the properties of an optimal algorithm and presents a deterministic algorithm to solve the problem. An execution trace of the algorithm is given. An important conjecture called the serialization conjecture is presented. The proposed algorithm is proved to be optimal subject to thc validity of the conjecture. (C) 2000 Published by Elsevier Science B.V. All rights reserved.

关键词： Towers of Hanoi combinatorial problem design of algorithm recursive formulation dynamic programming combinatorial explosion

来源：评论

学校读者我要写书评

暂无评论

Range-free localization algorithm using a customary drone: Towards a realistic scenario

引用

PERVASIVE AND MOBILE COMPUTING 2019年 54卷 1-15页

作者： Sorbelli, Francesco Betti Pinotti, Cristina M. Ravelomanana, Vlady Univ Florence Dept Comp Sci & Math Florence Italy Univ Perugia Dept Comp Sci & Math Perugia Italy Univ Paris 07 Dept Comp Sci Paris France

The localization of devices is a key ingredient of Internet of Things (IoT) which may require extra cost for deploying anchor nodes aware of their position. In this work, we propose a range-free localization algorithm, called DRONE RANGE-FREE (briefly, DRF), that replaces the anchor nodes with an off-the-shelf drone. When the radio communications are isotropic, our algorithm localizes the IoT devices ensuring the level of precision required by the final user. However, since an isotropic antenna that propagates its signal in a perfect sphere does not exist in reality, we face a more realistic scenario by proposing an enhanced version of our localization algorithm, called DRONE RANGE-FREE ENHANCED (briefly, DRFE), that well tolerates high degrees of irregularity of the antenna signal. Under the anisotropic model, DRF and DRFE exceed in precision all the computational-light previous known range-free localization algorithms based on a mobile rover. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Drone Range-free Localization design of algorithm Radio propagation model

来源：评论

学校读者我要写书评

暂无评论

A genetic algorithm for solving dual-homing cell assignment problem of the two-level wireless ATM network

引用

COMPUTER COMMUNICATIONS 2002年第17期25卷 1536-1547页

作者： Din, DR Tseng, SS Natl Chiao Tung Univ Dept Comp & Informat Sci Hsinchu 30050 Taiwan Hung Kuang Inst Technol Dept Comp Sci & Informat Management Taichung 433 Taiwan

In this paper, we investigate the optimal assignment problem, which assigns cells in Personal Communication Service to switches on Asynchronous Transfer Mode network in an optimum manner. The cost has two components: one is the cost of handoffs that involve two switches, and the other is the cost of cabling. This problem is model as dual-homing cell assignment problem, which is a complex integer programming problem. Since finding an optimal solution of this problem is NP-hard, a stochastic search method, based on a genetic approach, is proposed to solve this problem. In this paper, domain-dependent heuristics are encoded into crossover operations, mutations of genetic algorithm (GA) to solve this problem. Simulation results show that GA is robust for this problem. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： cell assignment dual-homing wireless ATM genetic algorithm design of algorithm

来源：评论

学校读者我要写书评

暂无评论

Real scaled matching

引用

INFORMATION PROCESSING LETTERS 1999年第4期70卷 185-190页

作者： Amir, A Butman, A Lewenstein, M Georgia Inst Technol Coll Comp Atlanta GA 30332 USA Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel

Scaled matching refers to the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary integral scale, appears. Scaled matching is an important problem that was originally inspired by problems in Vision. However, in real life, a more natural model of scaled matching is the real scaled matching model. Real scaled matching is an extended version of the scaled matching problem allowing arbitrary real-sized scales, approximated by some function, e.g., truncation. It has been shown that the scaled matching problem can be solved in linear time. However, even though there has been follow-up work on the problem, it remained an open question whether real scaled matching could be solved faster than the simple solution of O(nm) time, where n is the text size and m is the pattern size. Using a new approach we show how to solve the real scaled matching problem in linear time. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： design of algorithm analysis of algorithms combinatorial algorithms on words pattern matching scaled pattern matching approximate pattern matching generalized pattern matching

来源：评论

学校读者我要写书评

暂无评论

A Novel Hybrid Slot Allocation Mechanism for 802.11e EDCA Protocol

引用

INFORMATION PROCESSING LETTERS 2014年第1-2期114卷 25-30页

作者： Yao, Xin-Wei Wang, Wan-Liang Wu, Teng-cao Yao, Xiao-min Yang, Shuang-Hua Zhejiang Univ Technol Coll Comp Sci & Technol Hangzhou Zhejiang Peoples R China Univ Loughborough Dept Comp Sci Loughborough Leics England

This letter proposes a novel Hybrid Slot Allocation Mechanism (HSAM) to solve the high collision problem among four Access Categories (ACs) introduced by IEEE 802.11e EDCA protocol. In the HSAM, three time slots are assembled into a super-slot, each slot in the super slot is allocated to a particular AC according to its priority. The main idea of HSAM is to stagger the transmission slots of different ACs to reduce collisions, while maintaining the service differentiation. Extensive results from simulations have demonstrated good performance of HSAM comparing with EDCA protocol in terms of throughput, packet loss and MAC delay. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Scheduling design of algorithm Performance evaluation Slot allocation Service differentiation Collision Access category EDCA protocol

来源：评论

学校读者我要写书评

暂无评论

Generation of maximal fuzzy cliques of fuzzy permutation graph and applications

引用

ARTIFICIAL INTELLIGENCE REVIEW 2020年第3期53卷 1585-1614页

作者： Raut, Sreenanda Pal, Madhumangal Vidyasagar Univ Dept Appl Math Oceanol & Comp Programming Midnapore 721102 India

Fuzzy permutation graph (FPG) plays a significant role in solving real-life problems where the scope and application of crisp permutation graph get limited due to the fuzziness involved in real situations. In this article an algorithm is designed to find out all maximal fuzzy cliques of a FPG. A similar algorithm is developed at the same time to find out all maximal fuzzy independent sets of the said graph. The inter-relationship between FPG and its two types of complements is presented based on the facts and theories established on fuzzy cliques and fuzzy independent sets. The importance of fuzzy cliques of FPG is discussed through an application on a daily-life problem. The unique property of a FPG having two types of complement graphs help us to solve many useful problems. Here, we have shown how this property of FPG helps us to overcome a hazardous situation occurred due to disrupted scheduling of trains on a foggy day.

关键词： Fuzzy graph Fuzzy permutation graph Maximal fuzzy cliques Fuzzy independent sets Fuzzy complement design of algorithm

来源：评论

学校读者我要写书评

暂无评论

Detecting and extracting natural snow from videos

引用

INFORMATION PROCESSING LETTERS 2010年第24期110卷 1124-1130页

作者： Shen, Yang Ma, LiZhuang Liu, Hai Bao, Yanxia Chen, Zhihua Shanghai Jiao Tong Univ Shanghai Peoples R China E China Univ Sci & Technol Dept Comp Sci & Engn Shanghai 200237 Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing 210093 Peoples R China

In this paper, we propose a new algorithm to detect and extract natural snow from video. We detect the snow particle from images or videos by a series of filters, and each of these filters can recognize the features of snow efficiently. We label snow in videos and extract the alpha value of the snow particles by alpha matting. Our method can be applied to many fields such as background reconstruction. Experimental results show that our method is effective. (C) 2010 Elsevier B.V. All rights reserved.

关键词： design of algorithm Alpha matting Snow Video

来源：评论

学校读者我要写书评

暂无评论

On approximation of the submodular set cover problem

引用

OPERATIONS RESEARCH LETTERS 1999年第4期25卷 169-174页

作者： Fujito, T Nagoya Univ Dept Elect Nagoya Aichi 4648603 Japan

We design a primal-dural heuristic for the submodular set cover problem and analyze its performance giving an approximation bound as a generalization of the one for the set cover problem. As an application, a capacitated version of the partial vertex cover problem on hypergraphs with edge size at most d is considered. It will be shown that the problem can be approximated in polynomial time within a factor of d of the optimum, generalizing some existing results. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： combinatorial problem design of algorithm optimization

来源：评论

学校读者我要写书评

暂无评论

On uniqueness of solution to the multi-peg Towers of Hanoi

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2001年第1期78卷 57-72页

作者： Sarkar, UK Indian Inst Management Kolkata 700027 W Bengal India

The multi-peg Towers of Hanoi problem is still open. No provably optimal constructive algorithm to solve the problem is known. The minimum number of moves required is also unknown. Though optimal solutions are observed to be non-unique, the exact uniqueness criteria of an optimal solution are little known to the literature. This paper revisits a deterministic algorithm conjectured to optimally solve the problem and addresses the uniqueness characteristics of an optimal solution.

关键词： Towers of Hanoi combinatorial problem design of algorithm recursive formulation dynamic programming combinatorial explosion

来源：评论

学校读者我要写书评

暂无评论

A probabilistic algorithm for verifying polynomial middle product in linear time

引用

INFORMATION PROCESSING LETTERS 2018年 139卷 30-34页

作者： Giorgi, Pascal Univ Montpellier LIRMM CNRS Montpellier France

Polynomial multiplication and its variants are a key ingredient in effective computer algebra. While verifying a polynomial product is a well known task, it was not yet clear how to do a similar approach for its middle product variant. In this short note, we present a new algorithm that provides such a verification with the same complexity and probability that for the classical polynomial multiplication. Furthermore, we extend our algorithm to verify any operations that compute only a certain chunk of the product, which is the case for instance of the well known short product operation. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Probabilistic algorithm design of algorithm Computation on polynomials Polynomial multiplication

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：