tailieunhanh - Comparison of the efficiency of two algorithms which solve the shortest path problem with an emotional agent

This paper discusses the comparison of the efficiency of two algorithms, by estimation of their complexity. For solving the problem, the Neural Network Crossbar Adaptive Array (NN-CAA) is used as the agent architecture, implementing a model of an emotion. The problem discussed is how to find the shortest path in an environment with n states. The domains concerned are environments with n states, one of which is the starting state, one is the goal state, and some states are undesirable and they should be avoided. | Yugoslav Journal of Operations Research 16 (2006), Number 2, 211-226 COMPARISON OF THE EFFICIENCY OF TWO ALGORITHMS WHICH SOLVE THE SHORTEST PATH PROBLEM WITH AN EMOTIONAL AGENT Silvana PETRUSEVA Mathematics Department, Faculty of Civil Engineering, "St. Cyril and Methodius" University, Skopje, Macedonia silvanap@ Received: October 2003 / Accepted: June 2006 Abstract: This paper discusses the comparison of the efficiency of two algorithms, by estimation of their complexity. For solving the problem, the Neural Network Crossbar Adaptive Array (NN-CAA) is used as the agent architecture, implementing a model of an emotion. The problem discussed is how to find the shortest path in an environment with n states. The domains concerned are environments with n states, one of which is the starting state, one is the goal state, and some states are undesirable and they should be avoided. It is obtained that finding one path (one solution) is efficient, . in polynomial time by both algorithms. One of the algorithms is faster than the other only in the multiplicative constant, and it shows a step forward toward the optimality of the learning process. However, finding the optimal solution (the shortest path) by both algorithms is in exponential time which is asserted by two theorems. It might be concluded that the concept of subgoal is one step forward toward the optimality of the process of the agent learning. Yet, it should be explored further on, in order to obtain an efficient, polynomial algorithm. Keywords: Emotional agent, complexity, polynomial time, exponential time, adjacency matrix, shortest path. 1. INTRODUCTION We shall recall some notions of the theory of complexity which will be used in this paper. The complexity of the algorithm is the cost of the computation measured in running time or memory, or some other relevant unit. The complexity of the spending time is presented as a function from the input data which describe the problem. 212 S. .