Search

In this paper a novel optimized graph referencing method is proposed to tackle combinatorial problems with greater ease. The proposed algorithm is a modification of the existing backtracking algorithm. It takes into account the advantage of backtrack algorithm while eliminating its disadvantages. Special care has been taken to reduce the time complexity in avoiding frequent unsuccessful searches and in providing accurate and fast solution to the targeted sub problem. The theoretical analysis and experimental results presented reveal the superiority of proposed algorithm over the conventional algorithms. I. Introduction A special branch of mathematics known as Combinatorics deals with the study of finite structure including counting the structure of a given kind and size, depending upon criteria to be met and analysis and constructs objectives meeting such criteria. Combinatorial problems find extensive application in fields of mathematics, machine learning, AI, Auction Theory, Software Engineering etc. Backtracking is a general algorithm for finding all or some solution to some combinatorial problems. However, Backtracking suffers inherent disadvantages in terms of conjunction of a large processing time and memory space. It is here that the proposed novel optimized graph referencing method established its superiority. The algorithm as proposed by the authors, which is a modification of conventional Backtracking algorithm, not only solves efficiently different combinatorial problems but does so in the least possible time. Tackling various combinatorial problems is a subject of research worldwide. Different efficient algorithms are being developed to this purpose. Xiao et. al. (1) designed a stepwise enumerative algorithm while another algorithm based on GA was developed by Liu et. al. (2). The Backtracking algorithm is reported to be used to solve Sudoku, a combinatorial problem, by Xu (3). The solution to the Sudoku problem was proposed by Zhang (4) who intend to use the application development language AutoLISP embedded in AutoCAD for this purpose. An altogether different algorithm to solve Sudoku was proposed by Zhao et. al. (5) while the same was tackled with the help of cultural algorithm and GA optimization as reported by Mantere and Kolijonen (6

There are several possible algorithms to automatically solve Sudoku boards; the most notable is the backtracking algorithm, that takes a brute-force approach to finding solutions for each board configuration. The performance of the backtracking algorithm is usually said to depend mainly on two implementation aspects: finding the next available empty cell in the board and finding the options of available legal number that are relevant to the given cell. While these pieces of the backtracking algorithm can vary in efficiency based on their implementation, tests show that the algorithm itself also relies on the statistical distribution of the guesses that it attempts to “plug in” to the board in every given cell. The backtracking algorithm uses an array of the legal numbers in the cell to attempt a solution before it moves on to the next cell. If a solution cannot be found, it backtracks and attempts to solve the board again with a different guess choice. The more errors the solver makes, the more backtracks it must perform, which decreases its overall efficiency and increases its effective runtime. Tests of the solving algorithm were performed using 195 base solutions with multiple initial board configurations were performed to analyze the difference in the algorithm performance by comparing the number of recursive backtracks between sequential and randomly distributed guesses. Analysis show that using values that are given in a shuffled array significantly reduces the number of backtracks done by the solver and, as a result, improve the total effective efficiency of the algorithm as a whole.

We discuss weighted deductive parsing and consider the problem of finding the derivation with the lowest weight. We show that Knuth's generalization of Dijkstra's algorithm for the shortest-path problem offers a general method to solve this problem. Our approach is modular in the sense that Knuth's algorithm is formulated independently from the weighted deduction system.

AN EXTENSION of Knuth's algorithm for parsing context-free languages is considered. The algorithm proposed is not a left-sided parsing algorithm. It is shown how, by slightly changing the grammar, it is in many cases possible to attain unique parsing by means of an extension of Knuth's algorithm.

In this paper we will take a detailed look at a larger example of program analysis by transformation. We will be considering Algorithm 2.3.3.A from Knuth's «Fundamental Algorithms» Knuth (1968) (p. 357) which is an algorithm for the addition of polynomials represented using four-directional links. Knuth (1974) describes this as having «a complicated structure with excessively unrestrained goto statements» and goes on to say «I hope someday to see the algorithm cleaned up without loss of its efficiency». Our aim is to manipulate the program, using semantics-preserving operations, into an equivalent, high-level specification. The transformations are carried out in the WSL language, a «wide spectrum language» which includes both low-level program operations and high level specifications, and which has been specifically designed to be easy to transform