article Free Access Share on Dynamic Programming Treatment of the Travelling Salesman Problem Author: Richard Bellman RAND Corporation, Santa Monica, California RAND Corporation, Santa Monica, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 9Issue 1Jan. 1962 pp 61–63https://doi.org/10.1145/321105.321111Online:01 January 1962Publication History 445citation6,030DownloadsMetricsTotal Citations445Total Downloads6,030Last 12 Months785Last 6 weeks106 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Given a sequential machine, in the terminology of E. F. Moore, Annals of Mathematics Studies, No. 34, 1956, a problem of some interest is that of determining testing procedures which will enable one to transform it into a known state starting from an initial situation in which only the set of possible states is given. To treat this problem, we introduce the concept of ambiguity, and show how the functional equation approach of dynamic programming can be applied.

In this paper we wish to initiate the study of the application of dynamic programming to the domain of problems arising in the synthesis of logical systems. In a number of fields one encounters the problem of converting a system in one state into another state in a most efficient fashion—in mathematical economics, in the theory of control processes, in network theory, and in trajectory processes. Here we wish to consider a type of question which arises in the design of computers and switching circuits. We shall first treat the problem in general terms, and then consider a special example to illustrate the methods.

By imbedding a complex physical process under consideration within an appropriate class of processes and expressing the functional relationships among the members of the class, it is frequently possible to obtain insights into the structure of the original process which would not be feasible through consideration of that process alone. Not only may analytical expressions be obtained, but frequently computational tools are forged which make possible the exploitation of modern digital computing machines. By way of illustration, this paper is devoted to a discussion of recent applications o f the functional equation techniques of dynamic programming and invariant imbedding to the study of some problems arising in the theory of adaptive control processes and that of transmission through random media. Still other applications which have been made in modulation theory, communication theory, and network analysis are briefly sketched.

In this paper we wish to show that the fundamental problem of determining the utility of a communication channel in conveying information can be interpreted as a problem within the framework of multistage decision processes of stochastic type, and as such may be treated by means of the theory of dynamic programming. We shall begin by formulating some aspects of the general problem in terms of multistage decision processes, with brief descriptions of stochastic allocation processes and learning processes. Following this, as a simple example of the applicability of the techniques of dynamic programming, we shall discuss in detail a problem posed recently by Kelly. In this paper, it is shown by Kelly that under certain conditions, the rate of transmission, as defined by Shannon, can be obtained from a certain multistage decision process with an economic criterion. Here we shall complete Kelly's analysis in some essential points, using functional equation techniques, and considerably extend his results.