Additive AND/OR Graphs

ADDITIVE AND/OR GRAPHS A. Martelli and u. Montanari Istituto di Elahorazione dell'Informazione del Consiglio Nazionale delle Ricerche Via s. Maria, 4fi - 56100 - Pisa Italy.

Abstract

Additive AND/OR graphs are defined as AND/ /OR graphs without circuits, which can be con­ sidered as folded AND/OR trees; i.e. the cost of a common subproblem is added to the cost as many times as the subproblem occurs, but it is computed only once. Additive AND/OR graphs are naturally obtained by reinterpreting the dy~ namic programming method in the light of the problem-reduction approach. An example of this reduction is given.

A top-down and a bottom-up method are pro­ posed for searching additive AND/OR graphs. These methods are, respectively, extensions of the "arrow" method proposed by Nilsson for searching AND/OR trees and Dijkstra's algo­ rithm for finding the shortest path. A proof is given that the two methods find an optimal solution whenever a solution exists.

1) Introduction

In the literature on artificial intelli­ gence, AND/OR trees have proved to be a good formalism for representing the problem-reduc­ tion approach to problem solving 1 · Usually, the search is fo~ any solution tree, but in a paper by Nilsson the problem is presented of finding the best solution tree, where arcs have a given cost, and the cost of a tree is simply the sum of the costs of the arcs. Nilsson gives there an algorithm "'hich as­ sumes available, for each node, an estimate of the cost of th~ ·optimal solution tree rooted at that node.

An algorithm for searching AND/OR jraphs has been proposed by Chang and Slagle · Here a solution graph is defined in the usual v1ay, and, as for trees, the cost of a solution graph is the sum of the costs of its arcs.

In this paper we introduce a new type of AND/OR graphs called additive, v1hich can be considered as folded AND/OR trees, i.e. trees where different nodes have been recognized to be roots of equal subtrees and have been iden­ tified, thus generating AND/OR graphs without circuits. However, the cost of a solution sub­ graph is defined as equal to the cost of the unfolded equivalent tree. In other words, the cost of a common subproblem is added to the cost as many times as the subproblem occurs, but it is computed only once.

Additive AND/OR graphs are naturally ob­ tained by reinteroreting the dynamic program­ ming method of optimization in the light of the problem-reduction approach 4 ·

For giving an idea of the technique of reduction, we will consider here the well­ -known problem of balancing binary search trees, solved by Knuth with a (modified) " dynamic programming algorithm- . Here a number of ordered items (lexicographically ordered words, for instance) are given, together with the probabilities of a new item occurence to be any of the given items or to he a new item located in any intermediate position. For example, the data

mean that there are 3 probabi 11 ties out of 31 that a new vrord vlill be "do" and ::l probahilities that a new word will he any word hetvreen 11 do" and "if".

A binary search tree for these data is a tree of the type shown in Fig. 1. For instance lf the new word "array" is generated, its proper location is found by means of three tests, namely comparisons vii th the given words "if" and "begin" respectively and a termina­ tion test.

Given a search tree, the average number of tests M necessary for reaching a node, is then given by summing up the products of the number mi of tests required for any node i and its probability Pi

For instance, the average number of tests for the tree in Fig. 1 is

The problem is to find a search tree with minimal cost M. For instance, the tree of Fig.1 is optimal for the data (1).

An equivalent formulation of the same problem considers frequencies instead of pro­ babilities. In this case the cost is called weighted path lenath.

Tv1o properties allow the use of a rlynamic programming technique in this case. First, if T = (a A e)is an optimal tree rooted in A and having a and e as subtrees, then both a and e are optimal. Furthermore, the data for a and e are disjoint substrings of the data for T. Second, if fA,fa ,fe ,La ,Le are the frequencies of A,a and e and the weighted path lengths of a and e, then the value is the weighted path length of T. For in­ stance the left and right subtrees of the tree in Fig. 1 are the optimal trees for the data and Furthermore, we have La= 34,fa=18, Le =8, fe = 8, fA= 5 and L = 73.

In the dynamic programming algorithm, all the subproblems of the given problem are considered, whose data are substrings of the given data. Such problems are divided in lev els, according to the length of the data, - and solved in increasing order. A problem at a level can be solved by picking up a root in all possible ways<·> (say k) and thus decomposing the problem in k pairs of subproblems at lower levels. The cost of every decomposition is computed using (2)and a best decomposition is chosen.

The optimal search tree problem de­ scribed above is a good example of the gener al case where, at each stage, the computa- - tion of each alternative requires the sum of the costs of one or more (in fact, two) su£ problems.

In this case, the structure of the problem is conveniently reflected into an additive AND/OR graph, whose AND nodes correspond to subproblem cost sums, and OR nodes to alter­ native selections. For instance, the AND/OR graph for the optimal search tree problem, with data (1), is shown in Fig. 2. There,AND nodes are marked with circles and OR nodes (corresponding to subproblems) with squares. The optimal solution graph, corresponding to the search tree in Fig. 1, is blackened.

Reduction of dynamic programming to additi ve AND/OR graphs can imply several advan- - tages. First, the AND/OR graph expresses the structure of the problem in the form of a partial ordering of subproblems. Dynamic pro gramming solves all the subproblems bottom-­ -up in some static order which respects the partial orderings. However,in Section 4 of this paper a bottom-up algorithm is descri­ bed, which solves every time the cheapest available subproblem, thus considering, in general, only a subset of subproblems in a dynamic order.

<·> Actually, KnuthS gives a modified dynamic programming algorithm which excludes a priori most of the decompositions, using a particular monotonicity property.

Second, in many cases @stimates of the sub­ problem costs are available, which can be used for directing a top-down search. In fact, in Section 3 we give an extension of Nilsson's tree algorithm to the additive graph case, which, if the estimate is a lower bound of the minimal cost, is guaranteed to find the opti­ mal solution graph. The alqorithm is slightly simplified if the estimate satisfies a "con­ sistency" constraint. Finally, various known heuristic techniques can be applied to additi­ ve AND/OR graphs,which can find a good solu­ tion where the exact dynamic programming algorithm is too ~xpensive6. _

We emphasize that this paper extends to general dynamic programming a reduction tech­ nique which is well-known in the so called "sequential" case?, There, each alternative can be computed by summing a constant to the cost of ~ simpler subproblem, thus reducing an additive AND/OR graph to an OR graph. In this case, a solution tree reduces to a path and thus shortest path algorithms apply, like Dijkstra's algorithmS in the uninformed case and the algorithm by Hart, Nilsson, and Raphael9 if an estimate is available.

Finally, note that in the shortest path case no distinction between top-down and bot­ tom-up is needed, while it is suqqestive in the general case. -.

2) Additive AND/OR Graohs

In this paper, we shall consider AND/OR graphs without cycles. An example is given in Fig. 3. Node A is called the start node and represents the problem to be solved. Node A is called an OR node,(*) because a solution is constructed by selecting either its successor B or its successor c. Node B is called an AND node, because all of the suboroblems represent ed by its successors D and E must be solved i~ order to solve problem B. An AND node is indi­ cate by a line across the arcs connectinq it to the successor nodes. Nodes G and H ar~ cal­ led terminal nodes and correspond to problems with known solution.

We assume that all the nonterminal nodes are either OR nodes or AND nodes, that is, there are no nodes corresponding to problems which can be solved by solving some of their successors.

<·> We give here a definition of OR nodes and AND nodes, which is opposite to the one given by Nilsson 1 · We do so, because we want each node to be either an OR node or an AND node. Instead, with Nilsson's definition, we could have a node which is at the same time an OR node because of one parent and an AND node because of another parent.

We shall be concerned with AND/OR graphs .implicitly sPecified by a start node s arid a successor operator r .Application of r to any node n generates a finite number of successors of n and a label ~necifyi na ~thether the succe5sor~ are AND node~ or OR nodes.

A solution granh of an AND/OR crranh r, with start node ~ is any subaraph of G containing s and havincr the followi na properties:

1. Suppose node n of G is an OR node and is included in the solution crranh. Th~n one and only one of the successor~ of n is also included in the 5olution graph.
2. Suppose node n of G is an AND node and is included in the solution crranh. Then all of the ~uccessors of n are also included in the solution crranh.
3. The solution graph is finite, meanincr that it end~ in a set of terminal nodes.

Fia. 4 shows two solution aranhs of the AND/OR qranh in Fiq. 3.

In general, a cost i~ associated wi th every arc of an ~NO/OR aranh. Let the func­ tion c(ni,n,) aive the cost to he associated with the arcJconnectincr node ni with one of its successors n;. For additive AND/OR qranhs the cost of a solution granh is recursively defined as follows:

1. The cost c = 0 is associated with everv terminal node in the solution aranh.
2. Let c 1 , .·· ,ck be the costs associated with the k successors of node n in the solution with n the granh. Then we associate cost c aiven by(*)

1. The cost associated with the start node s is the cost of the solution granh.

The cost of a solution crranh can alwavs he obtained with the above definition, because solution araphs do not contain cycles.

The cost of a solution aranh can also be obtained by representing the solution aranh as a tree by dunlicating the subaranh~ rooted at nodes with more than one incident arc and taking the sum of all the arc costs of the tree.

(·)Note that both the AND and the OR case are here included, since in a solution gra~h OR nodes can have only one successor.

For examn] e, let us consider the t"Yrn solution crranhs in Ficr. 4, "'here l·re assume unit arc co5ts. The cost of the first so l u­ tion is 5 and the cn~t of the second one is 9, because the cost of the subtree rooted at r i~ considered t wice.

In the next ~ectinns, we ~hall nlve two alaorithm~ to find solut i on aran~s ha~ina minimal co~t for additive AND/OR aranhs.

3) Ton-down Search Alaorithm

The alaorithm criven in this section finds a solution aranh havina minimal co~t, beain­ nina with the start node s and uslna r to aenerate the "ranh. At everv staae in the aeneration of the aranh, a deci~ton must he made about which node should have its suece~sor~ aenerated next. cessors of a node by r a node.) · (Generatina the suc­ i~ called exnanding

The alaorithm l~ an extenslnn of the alno­ rithm nronosed hv Nilsson 2 for AND/ OR trees and the two alaorithms are nractl.callv identical for the narticular case of AND/OR trees. The search method uses a set of arrow~ to qulde it from the start node down throuah the AND/OR aranh ~earched thus far to that node to be exnanded next. Fach exnanded node has an arrow nointincr to one and onlv nne of its successors based on evaluations of the successors. 'Vo'hen a node is aenerated for the first time, its evaluation is an estimate, wh ich must be avai l a b le on s enarate nrounds, of the cost of a mlnimal cost ~olution crranh startinrr at this node. The net"YTork of arro·,rs is maintained bv undatina the evaluations nf nodes that are ancestral to those exnanded durina the nrocess. The evaluation of a node gives the estimate of the cost of an ontimal soluti on "ranh havincr that node a~ start node.

The alaori thm con~i st~ of the fol l o"Yrina stens:

1. Beain with the start nodes.
2. If . s ls not mar~ed SOLIIFD, ao to (3); nthen·l.se exit l·ri th the solution aranh. This aranh is constructed hv startlnn at s and us i nn the flnal dire~tion~ of the arro~o~s to decide ~o.·hich successor~ of 0R nodes 5hould he included.
3. Trace down the arrows from s n and exnand it. Sunno~e node succes~or~ n 1 , .·· ,nk· to a node n has
4. Undate the evaluation~ and arrow direc­ tions of node n and al l node~ ancestral to n, as follo-vrs:

If a succes~nr ni of n has been !'Te ner­ ated before, it has already an evaluation h(nil. If a successor n; is generated for the first time, its evaluation h(n·) is the estimate of the cost of a minlmal cost solution oranh startinn at node nj· If a successor is a terminal node, its evaluation is zero and it is marked SOLVED.

If node n is an OR node , its undated evaluation is

The arrow is directed from n to successor ni for which the minimum achieved and n is marked SOLVED and only if ni is marked SOLVED. the is if

If node n is an AND node, its updated evaluation is

The arrow is directed from n to one of its successors which is not marked SOLVED, accordinq to a qiven criterion. A reasonable heuristic is the one of directinq the arrow to that successor havin~ the larnest evaluation. If all the successors are marked SOLVED, n is marked SOLVED.

The procedure of undatinq evaluations and arrow directions is then repeated for all the ancestors of node n by backino uo the qranh to s.

( 5) Go to ( 2 ) .

Note that durinq step (4), a node can he updated several times, because there can be several paths in the qraoh bett.-1een a nair of nodes. However, the procedure will always terminate, since in the qraph there are no cycles by hypothesis.

An examnle of search with the oiven alqo­ rithm is shown in Fig. 5. The araph to be searched is shown in Fiq. Sa. Arc costs are assumed to be unity and terminal nodes are marked. The numbers adiacent to every node are the estimate of the cost of a minimal cost solution qraph startinq at that node. Fig. Sb throuqh Sq show the narts of the graph qenerated after each cycle of the algorithm. The numbers attached to each node are the updated evaluations and marked nodes are SOLVED nodes. Finally, Fiq. Sh qives the solution graph found by the aloorithm. Actually, this solution granh has minimal cost, as we shall show below.

As i~ the case of the arrow alqorithm of Nilsson2 or the alqorithm of Hart, Nilsson and Raphae 19 for OR qranhs, we .. ·can shovT that, if the estimate function h(n) is a lower bound on the cost of a minimal cost solution graoh , then the algorithm is admissible, that is it will always find a minimal cost solution crraph.

Let a tin node he a node o~ the crranh crenerated at a certain staae hv the alnorithm which has not vet been exnanded. Let ~(n) he the cost of a minimal cost snlution aranh startina at node n. We then have:

Lemma 1. I~ h(n) c h(n) ~or all tin nodes, then at anv stacre clurinn the search nrocess . . we have h(n)c h(n) ~or all nodes n in the aranh. ~loreover ,.i~ a none n is TNlr":ed SOLVED VIe have h(n) = h(n) anr an ontimal solution aranh can he obtaineo hv tracincr down the arrows from n.

Proof. ~e shall nrove the lemma hv induction on the staaes of the alcrorithm. The Jemma is trivially true at stacre 0. Let us assume that it is true at a certain stacre ann let us nrove that it is true at the next staoe, that is after the exnansion of a node (sav

node n).

In sten (4) of the aloorithm, we undate all t~e nodes w~ich are ancestors of node n. Therefore, let us consider t~e suharanh r. of the search aranh obtained un to this stacre, l··hich consists o~ all .the ancestors of none n. Beina the aranh without cvcles, an innex can he attached to each node of r., startincr with n° = n, in such a wav that all the naths.~rnm node ni to node nO contain onlv nodes n 1

vii th i c i.

we shall nrove the lemma hv induction on the index i. The lemma is certainlv true ~or node n. In fact, i~ anv of its succe~sors n; has been oenerated before, we have h(n;)ch(n;) hv induction and if the successor n; is - ~enerated for the first time, we have h(n;l~ h(n;~ bv hynothesis. Therefore, hv computina h(n) accQrdinq to sten (4) of the aloorithm, t.ole have h(n)~ h(n). Mnreover, i~ node n is marked snLVED and is an 0~ node, we know bv induction that for the su~cessor n; nointed to hv the arrm· ,,,e have h(n;)=h(n;) and that an ontima l solutinn ~or n; can be obtained hv tracincr down the arrows ~rom n;. An oPtimal solution aranh fnr none n will contain node n;, since anv other solution aranh throuah another successor ni would have a not smaller cost. In fact, ~rom

we have

Thus, if node n is marken S0L''FD and is an nR node, we have h(n) = h(n) and an optimal solution aranh can he obtainen bv tracincr down the arrov·s ~rom n. The same holds if node n is marked S0LVED and is an AND node.

Now, let us assume that the lemma is true for all the nodes nj with j < i; then the lemma is true for node ni . This can be shown easily, by repeating for node ni the above arguments for node n.

Now we can prove the foll01·1ing:

Theorem 1. If a solution graph exists, if h(n) ~ h(n) for all tip nodes n and if all arc costs are larger than some small positive amount 6 , then the top-down algo­

rithm is admissible.

Proof. We consider three cases:

Case 1. Termination without finding a solution ~· This case is impossible. In fact, termination can only occur at step (2) when the start node is solved. But this can only happen if a solution graph has been found.

Case 2. No termination. Let us examine the algorithm at a certain stage. If we trace down the arrows from node s, we obtain a path from node s to the node n to be expanded next. Let c(s,n) be the cost of this path, that is the sum of the costs of its arcs. For each !rc (ni;njl, belonging to this path, we have ~(ni)~c(ni,njl +h(njl. Therefore, we have ij(s)~ c(s~n). Let us assume now that, at a cer~ain stage, we expand a node n for which c(s,n) > h(s)! This is not possible because it would imply h(s) > h(s) contradicting Lemma 1. Therefore, the algorithm can only expand those nodes n for which c(s,n) ~ h(s). The number of these nodes is finite because every node has a finite number of successors and the cost of every arc is greater than 6, hence the algorithm must terminate.

Case 3. Termination with a solution graph having non minimal cost. When the algorithm terminate~, node s is marked SOLVED and we have h(s) = h(s) by Lemma 1. Moreover, Lemma 1 states that an optimal solution graph can be obtained by tracing down the arrows from s. Therefore, the algorithm can only terminate with an optimal solution graph.

Q.E.D.

9 Hart, Nilsson and Raphael introduced an assumption, called_the consistency assumption, for the estimate h(n), which allows a simplification of the algorithm for searching OR graphs. Analogously, we can give the con­ sistency assumption for additive AND/OR graphs as follows. Let h(n) be the given estimate of the cost of a minimal cost solution graph starting at n. Then the consistency assump­ tion is

if n is an OR node

h(n) < h(ni) + c(n,nil for each successor ni

if n is an AND node

With the consistency assumption, it is easy to see that the evaluation of each node can only increase at each stage of the algorithm. Therefore, we can modify the last statement of step (4) of the algorithm as follows. One step of the procedure of backing up the graph of the ancestors of node n, consists of updating all the parents of a certain node m. Assume that one of these parents mi is an OR node. Since the evaluation of each node can only increase, the evaluation of node mi will be changed only if node mi has the arrow pointing to node m. Therefore, in the procedure of backing up the qraph of the ancestors of node n, we can consider only those OR parents of a certain node m, which have the arrow pointing to m.Note that, even in this case, a node can be updated several times during step (4).

4) Bottom-uo Search Algorithm.

This algorithm finds a solution graph having minimal cost, starting from the termi­ nal nodes and expanding a node at each stage. In this case, expanding a node means genera­ ting all the parent nodes of that node. The algorithm does not use any estimate, thus it can be considered as an extension of Dijkstra~ algorithm for OR graphs8 . An evaluation function is computed for each node and the node whose evaluation function is minimal is expanded. The evaluation function for a node n gives the cost of a minimal cost solution graph starting at node n, obtained so far.

The algorithm is based on the assumption that we have a finite number of terminal nodes and it consists of the following steps:

1. Put every terminal node ti on a list called OPEN and set h(ti) = 0 for every i
2. Remove from OPEN that node whose h value is smallest and put it on a list called CLOSED. (Resolve ties arbitrarily). Call this node n.
3. If n is the start node, exit with the solution graph obtained by tracing back through the pointers, otherwise continue.
4. Expand node n, generating all of its parents. For each parent ni do the following:

If ni is an OR node, we can have three cases

1. ni is neither on OPEN nor on CLOSED. Associate with ni the value of the evaluation function

Put node ni on OPEN and direct a pointer from it to n.

1. ni is on OPEN. Let h(nil be the evaluation associated with ni· Associate with it a new value of the evaluation function given by

If h(ni) has been changed, redirect the pointer from ni to n.

c) ni is on CLOSED. Continue

If ni cases is an AND node, we can have two

1. There is some successor of ni which is not on CLOSED. Continue.
2. All of the successors of ni are on CLOSED. Associate with node ni the value of the evaluation function

where the nodes nk are the succes­ sors of ni · Direct pointers from ni to all of its successors and put ni on OPEN,

(5) Go to (2).

This algorithm is closely related to the dynamic programming method. In fact, the latter can be seen as a bottom-up breadth­ -first search algorithm, which expands all the nodes according to a fixed ordering. Our algorithm, on the contrary, expands the nodes according to their cost, thus expand­ ing, in general, fewer nodes.

An example of search with the given algo­ rithm is shown in Fig. 6. The graph to be searched is given in Fig. Sa. The estimates attached to its nodes are not used by this algorithm. Figs. 6a through 6j show the parts of the graph generated after each cycle of the algorithm. Marked nodes are the closed nodes and the other nodes are the open nodes. Arc costs are assumed to be unity and the numb~rs adjacent to the nodes are the values of h. Nodes without an adjacent number are AND nodes which have some successor not yet closed. Fig. 6k gives the solution graph.

Note that the graph generated by this algo­ rithm :1as a simpler structure than the one generated by the top-down algorithm. In fact, at every stage of the algorithm, an OR node has only one pointer to one if its successors whereas, at every stage of the top-down algorithm, the complete structure of the graph has to be retained.

We can show that the bottom-up algorithm is admissible, that is, it will always terminate in an optimal solution graph, whenever a solution qraph exists.

Lemma 2. If all arc costs are positive, then, when a node n_ is closed by the algorithm, we have h(n) = h(n) and the optimal solution graph can be obtained by tracing down the pointers from n. Moreover, all the nodes m with h(m) < h(n) have been closed before node n.

Proof. The lemma will be proved by induction on the stages of the algorithm. The lemma is trivially true at stage 0. Let us assume it is true at a certain stage and let us prove that it will still be true after the next stage.

Let n be the open node whose h value is smallest at this stage. This node is closed by the algorithm. Let us assume that a node m exists with h(m)<h(n), which has not yet been closed by the algorithm. Let G be an optimal solution graph for node m. Certainly, there is an open node r of G, such that all of its successors in. G are closed. It is possible to see that h(r) = h(r). In fact, if r is an AND node all its successors are closed and by the induction hypothesis their h value is the cost of a minimal cost solution graph, hence h(r) = h(r).

If r is an OR node, we have

where the nodes ri are the successors of r which have been closed so far. But we assumed that one of these successors belongs to an optimal solution graph for r, there­ fore h(r) = h(r).

Moreover we have

since the optimal solution graph for r is a subgraph of G, and

since n is the open node whose h value is smallest. Therefore we have

which contradicts our hypothesis that node m has not yet been closed and we have shown that all the nodes m with h(m)<h(n) have already been closed.

Now, we can show that h(n) = h(n). If n is a terminal node, this is obviously true. If n is an OR node, we have shown above that, for any successor ni of_ n which is not closed, we have h(nil~ h(n). There­ fore, an optimal solution graph must contain a closed successor, because any solution graph through one successor which is not closed would have a larger cost. The pointer is directed from n to the closed successor n . for which (h(nj) + c(n,nj)) !s minimal arid, by the inductio~ hypothesis,h(nj)=h(nj). Therefore, we have h(n) = h(n) and an optimal solution graph for n can be ob­ tained by tracing down the pointers.

If n is an AND node, all of its succes­ sors are already closed. Since the lemma is true for the successors by the induction hypothesis, it is also true for n.

Q.E.D.

Finally, we can prove:

Theorem 2. if all arc bottom-up If a solution graph exists and costs are positive, then the search algorithm is admissible.

Proof. We prove the theorem by assuming the contrary. There are three cases to consider:

Case 1. Termination without finding a solution graph. This case is impossible because the algorithm can only terminate at step (3) with a solution graph.

Case 2. No termination. Assume that at a certain stage the algorithm closes node n with h(n) > h(s). This is impossible, be~ cause, according to Lemma 2, node s must have been closed before and when s is closed the algorithm terminates. Therefore, the algorithm can only close those nodes n with h(n) ~ h(s). But the number of these nodes is finite, since the arc costs are positive, and the algorithm must terminate.

Case 3. Termination with a solution graph having nonminimal cost. This is not possible, because it would contradict Lemma 2.

Q.E.D.

References.

• Nilsson, N.J., Problem-Solving Methods in Artificial Intelligence, Me Graw-Hill, New York, 1 971.
• 2 Nilsson, N.J., Searching Problem-Solving and Game-Playing Trees for Minimal Cost Solutions, Proc. IFIP Congress 1968, H, pp. 125-130.
• 3 Chang, C.L. and Slagle, J.R., An Admissible and Optimal Algorithm for Searching AND/OR Graphs, Artificial Intelligence, Vol. 2, pp. 117- 128 (1971).
• 4 Martelli, A. and Montanari, u., Dynamic Programming via AND/OR graphs, in preparation.
• 5 Knuth, D.E., Optimum Binary Search Trees, Acta Informatica, Vol. 1, pp. 14-25 ( 1971) ·
• 6 Martelli, A., Edge Detection Using Heuristic Search Methods, Computer Graphics and Imaqe Processina,Vol. 1, N. 2, pp. 169-182, August 1972.
• 7 Kaufm~nn, A. and Cruon, R., Dynamic Programmina, Academic Press, 1967.
• 8 Dijkstra, E., A Note on Two Problems in Connection with Graphs, Numerische Mathematik, Vol. 1, pp. 269-271 (1959).
• 9 Hart, P., Nilsson, N.J. and Raphael, B., A Formal Basis for the Heuristic Determination of Minimum Cost Paths, I.E.E.E. Trans. SCC 4, N.2, pp.100-107, July 1968.