共查询到20条相似文献,搜索用时 31 毫秒
1.
Witold Charatonik 《国际计算机数学杂志》2013,90(6):1150-1170
There are many decision problems in automata theory (including membership, emptiness, inclusion and universality problems) that are NP-hard for some classes of tree automata (TA). The study of their parameterized complexity allows us to find new bounds of their nonpolynomial time algorithmic behaviours. We present results of such a study for classical TA, rigid tree automata, TA with global equality and disequality and t-DAG automata. As parameters we consider the number of states, the cardinality of the signature, the size of the term or the t-dag and the size of the automaton. 相似文献
2.
The paper presents a first step of a coalgebraic analysis of the concept of communicating sequential processes as introduced by Hoare in [3]. We make apparent the strong relationship between CSP and partial automata, i.e., special coalgebras. Thereby it turns out that [3] is only dealt with very special automata, namely, with final automata, i.e., automata where the difference between the concepts of state and of process, respectively, disappears. The coalgebraic approach will allow us to develop a proper model theory for process calculi. As first steps in this direction we outline firstly how operations on processes can be generalized in a compatible way to constructions on automata. Secondly, we present a new method for solving recursive process equations. Finally, we discuss that the nondeterminism in CSP can not be modeled based on nondeterministic transition systems usually considered in the coalgebraic literature [5]. 相似文献
3.
Riitta Hellman 《Behaviour & Information Technology》1989,8(6):417-435
The development of different help systems and the application of numerous approaches to user support have shown (a) that end-users may encounter insuperably complex use situations, and (b) that it is possible to assist users significantly by implementing computerized help systems. There are many approaches to the realization of user support, varying from the use of natural language to user modelling. However, the current help systems seem to focus on relatively technical data processing issues, ignoring the organizational context in which the use takes place. It is asserted in this paper that it is relevant for users to perceive the organizational context and that it is possible to reflect the context in a support system. Representing the context in a support system is made possible by introducing a context database. A context database is parallel to the actual database and contains information about task flows, task-connected information objects and the like. Therefore the analysis of work and information systems has to be based on related areas. The areas of inquiry are (a) tasks, (b) job design, (c) organization of work, (d) computer applications and (e) information media. The following kinds of mappings can be incorporated within the context database: [organizational unit Ol]-T_person PI in job]-[job task Tl]-[task-connected information Il]-[task-connected information 12]-[job task T2]-[person in job P2]-[organizational unit O2], This type of chain (or parts of it) can then be visualized as context support. 相似文献
4.
Consistency enforcement is used to prune the search tree of a constraint satisfaction problem (CSP). Arc consistency (AC) is a well-studied consistency level, with many implementations. Bounds consistency (BC), a looser consistency level, is known to have equal time complexity to AC. To solve a CSP, we have to implement an algorithm of our own or employ an existing solver. In any case, at some point, we have to decide between enforcing either AC or BC. As the choice between AC or BC is more or less predefined and currently made without considering the individualities of each CSP, this study attempts to make this decision deterministic and efficient, without the need of trial and error. We find that BC fits better while solving a CSP with its maximum domains' size being greater than its constrained variables number. We study the behavior of maintaining arc or bounds consistency during search, and we show how the overall search methods complexity is affected by the employed consistency level. 相似文献
5.
Hulisi Öğüt 《Computers & Mathematics with Applications》2013,65(9):1234-1253
Intrusion Detection Systems (IDSs) have become an important element of the Information Technology (IT) security architecture by identifying intrusions from both insiders and outsiders. However, security experts questioned the effectiveness of IDSs recently. The criticism known as Base Rate fallacy states that when IDS raises an alarm, the event is more likely to be benign rather than intrusive since the proportion of benign activity is significantly larger than that of intrusive activity in the user population. In response to too many false alarms, system security officers (SSO) either ignore alarm signals or turn off the IDS as the information provided by IDS is very skeptical. To alleviate this problem of IDSs, Ogut et al. (2008) [6] suggest that the firm may choose to wait to get additional signal and to make better decision about user type. One of the limitations of their model is that configuration point at which IDSs operate (the false negative and false positive rates) is exogenously given. However, the firm trying to minimize expected cost should also make a decision regarding the configuration level of IDSs since these probabilities are one of the determinants of future cost. Therefore, we extend Ogut et al. (2008) [6] by considering configuration and waiting time decisions jointly in this paper. We formulate the problem as dynamic programming model and illustrate the solution procedure for waiting time and configuration decision under optimal policy when cost of undetected hacker activity follows step wise function. As it is difficult to obtain waiting time and configuration decision under optimal policy, we illustrate the solution procedures for under myopic policy and focus on the characteristics of configuration decision under myopic policy. Our numerical analysis suggested that configuration decision is as important as waiting time decision to decrease the cost of operating IDS. 相似文献
6.
以微小卫星集群实现小行星探测为背景,研究局部信息交互的空间目标观测任务构形调整.针对难以直接求取集群构形调整的全局最优解问题,利用通信协调图,将全局协调决策分解成多个局部求解问题,并引入强化学习机制实现求解.针对集群全局协调决策问题,通过设计基于Max-plus算法的全局协调决策算法来实现全局协作;针对单星局部优化问题,设计基于神经网络的局部Q学习算法来实现单星动作调整规划.仿真结果表明,本文所提的协作规划算法能自主有效地将集群调整至期望构形,实现协同观测任务. 相似文献
7.
《Behaviour & Information Technology》2012,31(6):417-435
Abstract The development of different help systems and the application of numerous approaches to user support have shown (a) that end-users may encounter insuperably complex use situations, and (b) that it is possible to assist users significantly by implementing computerized help systems. There are many approaches to the realization of user support, varying from the use of natural language to user modelling. However, the current help systems seem to focus on relatively technical data processing issues, ignoring the organizational context in which the use takes place. It is asserted in this paper that it is relevant for users to perceive the organizational context and that it is possible to reflect the context in a support system. Representing the context in a support system is made possible by introducing a context database. A context database is parallel to the actual database and contains information about task flows, task-connected information objects and the like. Therefore the analysis of work and information systems has to be based on related areas. The areas of inquiry are (a) tasks, (b) job design, (c) organization of work, (d) computer applications and (e) information media. The following kinds of mappings can be incorporated within the context database: [organizational unit Ol]-T_person PI in job]-[job task Tl]-[task-connected information Il]-[task-connected information 12]-[job task T2]-[person in job P2]-[organizational unit O2], This type of chain (or parts of it) can then be visualized as context support. 相似文献
8.
The Constraint Satisfaction Problem (CSP) formalism is used to represent many combinatorial decision problems instances simply and efficiently. However, many such problems cannot be solved on a single, centralized computer for various reasons (e.g., their excessive size or privacy). The Distributed CSP (DisCSP) extends the CSP model to allow such combinatorial decision problems to be modelled and handled. In this paper, we propose a complete DisCSP-solving algorithm, called Distributed Backtracking with Sessions (DBS), which can solve DisCSP so that each agent encapsulates a whole “complex” problem with many variables and constraints. We prove that the algorithm is sound and complete, and generates promising experimental results. 相似文献
9.
Ana Reyes Badillo Juan Jesús Ruiz Carlos Cotta Antonio J. Fernández-Leiva 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2013,17(2):285-300
Memetic algorithms (MAs) constitute a metaheuristic optimization paradigm [usually based on the synergistic combination of an evolutionary algorithm (EA) and trajectory-based optimization techniques] that systematically exploits the knowledge about the problem being solved and that has shown its efficacy to solve many combinatorial optimization problems. However, when the search depends heavily on human-expert’s intuition, the task of managing the problem knowledge might be really difficult or even indefinable/impossible; the so-called interactive evolutionary computation (IEC) helps to mitigate this problem by enabling the human user to interact with an EA during the optimization process. Interactive MAs can be constructed as reactive models in which the MA continuously demands the intervention of the human user; this approach has the drawback that provokes fatigue to the user. This paper considers user-centric MAs, a more global perspective of interactive MAs since it hints possibilities for the system to be proactive rather than merely interactive, i.e., to anticipate some of the user behavior and/or exhibit some degree of creativity, and provides some guidelines for the design of two different models for user-centric MAs, namely reactive and proactive search-based schema. An experimental study over two complex NP-hard problems, namely the Traveling Salesman problem and a Gene Ordering Problem, shows that user-centric MAs are in general effective optimization methods although the proactive approach provides additional advantages. 相似文献
10.
SVM决策树是解决多分类问题的有效方法之一,由于分类器组合策略不同,构成的决策树构型以及分类精确度也各有差异。提出基于欧氏距离的SVM决策树构造方法,通过两种欧氏距离组合策略,生成不同构型的SVM决策树。实验结果表明,采用组合策略二的SVM决策树分类器相比组合策略一,具有更高的分类精度和更短的训练及测试时间。 相似文献
11.
Wafa Jguirim Wady Naanaa Martin C. Cooper 《Annals of Mathematics and Artificial Intelligence》2018,83(1):1-20
Finding a solution to a constraint satisfaction problem (CSP) is known to be an NP-hard task. Considerable effort has been spent on identifying tractable classes of CSP, in other words, classes of constraint satisfaction problems for which there are polynomial time recognition and resolution algorithms. In this article, we present a relational tractable class of binary CSP. Our key contribution is a new ternary operation that we name mjx. We first characterize mjx-closed relations which leads to an optimal algorithm to recognize such relations. To reduce space and time complexity, we define a new storage technique for these relations which reduces the complexity of establishing a form of strong directional path consistency, the consistency level that solves all instances of the proposed class (and, indeed, of all relational classes closed under a majority polymorphism). 相似文献
12.
Yokoo M. Durfee E.H. Ishida T. Kuwabara K. 《Knowledge and Data Engineering, IEEE Transactions on》1998,10(5):673-685
We develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various application problems in distributed artificial intelligence can be formalized as distributed CSPs. We present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently without any global control, while guaranteeing the completeness of the algorithm. Furthermore, we describe how the asynchronous backtracking algorithm can be modified into a more efficient algorithm called an asynchronous weak-commitment search, which can revise a bad decision without exhaustive search by changing the priority order of agents dynamically. The experimental results on various example problems show that the asynchronous weak-commitment search algorithm is, by far more, efficient than the asynchronous backtracking algorithm and can solve fairly large-scale problems 相似文献
13.
为了解决无人机轨迹优化、用户功率分配和任务卸载策略问题,提出了一种双层深度强化学习任务卸载算法。上层采用多智能体深度强化学习来优化无人机的轨迹,并动态分配用户的传输功率以提高网络传输速率;下层采用多个并行的深度神经网络来求解最优卸载决策以最小化网络的时延和能耗。仿真结果表明,该算法使得无人机能够跟踪用户的移动,显著降低系统的时延和能耗,能够给用户提供更优质的任务卸载服务。 相似文献
14.
Solution Generation with Qualitative Models of Preferences 总被引:2,自引:0,他引:2
We consider automated decision aids that help users select the best solution from a large set of options. For such tools to successfully accomplish their task, eliciting and representing users' decision preferences is a crucial task. It is usually too complex to get a complete and accurate model of their preferences, especially regarding the trade-offs between different criteria.We consider decision aid tools where users specify their preferences qualitatively : they are only able to state the criteria they consider, but not the precise numerical utility functions. For each criterion, the tool provides a standardized numerical function that is fixed and identical for all users and used to compare solutions. To compensate for the imprecision of this qualitative model, we let the user choose among a displayed set of possibilities rather than a single optimal solution. We consider the probability of finding the most preferred solution as a function of the number of displayed possibilities and the number of preferences. We present a probabilistic analysis, empirical validation on randomly generated configuration problems and a commercial application. We provide mathematical principles for the design of the selection mechanism, guaranteeing that users are able to find the target solution. 相似文献
15.
在网络贷款用户数据集中,贷款成功和贷款失败的用户数量存在着严重的不平衡,传统的机器学习算法在解决该类问题时注重整体分类正确率,导致贷款成功用户的预测精度较低。针对此问题,在代价敏感决策树敏感函数的计算中加入类分布,以减弱正负样本数量对误分类代价的影响,构建改进的代价敏感决策树;以该决策树作为基分类器并以分类准确度作为衡量标准选择表现较好的基分类器,将它们与最后阶段生成的分类器集成得到最终的分类器。实验结果表明,与已有的常用于解决此类问题的算法(如MetaCost算法、代价敏感决策树、AdaCost算法等)相比,改进的代价敏感决策树对网络贷款用户分类可以降低总体的误分类错误率,具有更强的泛化能力。 相似文献
16.
基于相似度衡量的决策树自适应迁移 总被引:2,自引:0,他引:2
如何解决迁移学习中的负迁移问题并合理把握迁移的时机与方法,是影响迁移学习广泛应用的关键点. 针对这个问题,提出一种基于相似度衡量机制的决策树自适应迁移方法(Self-adaptive transfer for decision trees based on a similarity metric,STDT). 首先,根据源任务数据集是否允许访问,自适应地采用成分预测概率或路径预测概率对决策树间的相似性进行判定,其亲和系数作为量化衡量关联任务相似程度的依据. 然后,根据多源判定条件确定是否采用多源集成迁移,并将相似度归一化后依次分配给待迁移源决策树作为迁移权值. 最后,对源决策树进行集成迁移以辅助目标任务实现决策. 基于UCI 机器学习库的仿真结果说明,与多源迁移加权求和算法(Weighted sum rule,WSR)和MS-TrAdaBoost 相比,STDT 能够在保证决策精度的前提下实现更为快速的迁移. 相似文献
17.
18.
Taehyun Ha 《International journal of human-computer interaction》2013,29(6):371-384
This study proposes a new approach to developing a user behavior model to explain how a user finds the optimal use. This is achieved by considering user concerns, task significances, affordances, and emotional responses as the interaction components and by exploring behavior sequences for a goal in using a product the first time. The tasks in the same group at each level in the user concern structure are therefore in a competing relationship in going up to a higher task. The task tree with the significances and the affordance probabilities can be analyzed. The order of a user’s exploring behavior sequences can be determined through comparisons of the expected significances, which can be obtained by the modified subjective expected utility theory. A user’s emotional responses for the tasks that a behavior sequence is composed of can be calculated by the modified decision affect theory. Here, the emotional response refers to a user’s internal reactions for the degree to which a product’s affordance features can meet his or her mental model in use. The average emotional response for a behavior sequence can be a user’s decisional factor for the optimal use method in using a product with a goal. Also, the design problems of a product can be checked from users’ point of view, and the emotional losses/changes by usage failures can be discussed. For an illustrative purpose, the proposed model is applied to a numerical example with some assumptions. 相似文献
19.
讨论有限自动机的分解有助于分析弱可逆有限自动机的结构和求解弱逆.首先证明了弱同构的弱可逆有限自动机具有相似的分解形式;接着考虑了一类特殊的弱可逆线性有限自动机的分解, 从状态输出权的角度刻画了该分解存在的一个充分条件;然后把这种分解形式推广到了一般的弱可逆线性有限自动机上, 即:延迟τ步弱可逆线性有限自动机分解成延迟0步弱可逆有限自动机和一种特殊的有限自动机M\\-D, 并得到了分解存在的充要条件;最后, 用输出序列的代数性质来刻画其中的充分条件, 并把它转化成了一个矩阵的秩的计算.这种分解形式并不局限于n元弱可逆有限自动机, 而且分解条件也比较简单, 仅与输出序列的性质有关. 相似文献
20.
With the context of individualized product design in mass customization, the practice of product configuration is transformed
from traditional unidirectional process into bidirectional design interactions. In this interactive configuration manner,
maintaining the consistency of configuration assignments, often referred to as consistency restoration, is one of the primary
issues which should be addressed. The task of consistency restoration faces two great challenges: the uncertainty and individualized
flexibility of customer requirements. The uncertainty turns problem dynamic and deteriorates the computational complexity
of existing consistency restoration methods. The individualized flexibility turns the task of consistency restoration ill-structured.
Consequently, these two characteristics increase the response time in interactive configuration and make companies face the
challenge of ‘customization-responsiveness squeeze’. To leverage this problem, this paper proposes a responsive approach to
facilitate the task of consistency restoration. A methodology based on content-addressable memory (CAM) is established, which
compiles a CSP-based consistency restoration into a memory recalling process and automatically corrects the incompleteness
and inconsistency within the memory. Specific orientation mechanism based on customer preference is proposed to introduce
customer flexibility into CAM model. The resulting oriented-CAM method is demonstrated by a case study and the performance
and responsiveness are analyzed. 相似文献