Application of Statistics and Probability in Algorithm Design

The field of Algorithm Design works with applying the results and techniques of Analysis of Algorithms to the real problems and algorithms that operate on common data structures, for instance sorting and searching; advanced design and analysis techniques such as dynamic programming and greedy algorithms; advanced graph algorithms such as minimum spanning trees and shortest paths; NP-completeness theory; and approximation algorithms.
This article refers to building efficient programs that employs the tools of data analysis and statistical inference, probabilistic analysis of algorithms, and simulation.It describes a various paradigm of Applied Algorithm Design in general terms.
Second, a detailed description of how these tecniques are used in a the study of an application involving the Traveling Salesman Problem using Gaussian process regression.

• A Paradigm of Applied Algorithm Design
  In this section we will look at the general paradigm of applied algorithm design. We will first describe the overall process by refining the diagram

  .

  The following list describes the entities-
  1.The Real Problem. This is the problem that the user brings to the algorithm designer; it is the input to the process of applied algorithm design'. It is
  important to note, though, that the algorithm designer should pay great attention to the statement of the problem to ensure that what the user says he wants is what he in fact does want.
  2.The Real Program. This is the output of the process of algorithm design; it is a functional program that runs in the context of a larger system.We will see that it is usually appropriate to build at least two "real" programs in the process of applied algorithm design.
  3.The Abstract Problem. The real problem that the user has is often hidden beneath a level of detail that, while 'important for the real solution, tends to obscure the underlying computational structure of the problem.
  4.The Algorithm. The algorithm that solves the problem is a general description of a solution process that is not imbedded in any particular programming language; it is a clean solution to the abstract problem. Although it does not solve the details of the real problem (which were eliminated to achieve the abstract problem), it must be easy to incorporate those details into the algorithm as it is made more precise in a program.
  5.The Real Data.If the best-worst case algorithm ,the algorithm designer can find what does not satisfy the user's needs, then they'll have to study the real input data to find the pattern that can be exploited to yield a faster algorithm.
  6.The Model of Data.the purpose of the data model is to provide a mathematical description of what the data is usually like;we use that decription on anaylizing the performance of our algorithm on average.The typical techique is to give a probablistic model of the inputs.

Solving Dynamic Travelling Salesman Problem using Gaussian Process Regression

Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.

• The problem of varying correlation tour is alleviated by the nonstationary covariance function interleaved with DGPR to generate a predictive distribution for DTSP(Dynamic travelling Salesman problem) tour.
• This approach is conjoined with Nearest Neighbor (NN) method and the iterated local search to track dynamic optima. Experimental results were obtained on DTSP instances. The comparisons were performed with Genetic Algorithm and Simulated Annealing.
• The proposed approach demonstrates superiority in finding good traveling salesman problem (TSP) tour and less computational time in nonstationary conditions.
• Dynamic traveling salesman problem (DTSP), as a case of dynamic combinatorial optimization problem, extends the classical traveling salesman problem and finds many practical importance in real-world applications, inter alia, traffic jams, network load-balance routing, transportation, telecommunications, and network designing

From figure described below, DTSP initial route is constructed upon visiting requests carried by the traveling salesman{A,B,C,D,E}.As the traveling salesman sets forth, different requests {X,Y} come about which compels the traveling salesman to change the itinerary to factor in the new trip layover demands,{A,B,C,D,E,X,Y}.

The Statiscial Graph below shows Minimum path generated by DGPR-

Conclusion-
Probablistic analysis of algorithm have had a rapid growth in recent years in theoritical computer sciemce community .
This Article uses a nonstationary covariance function in GPR for the dynamic traveling salesman problem.
The future of this research will be directed to design new nonstationary covariance functions to increase the ability to track dynamic optima. Also changes in size and evolution of optima should be factored in, over, and above changes in location.