Form Dynamic Programming To Search Algorithms With Functional Costs

I. Introduction

Dynamic programming is a well-known methodology for representing optimization problems in terms of the so-called functional equations and for solving them. While in the artificial intelligence literature dynamic programming is often described reductively as a static, breadth-first tech· nique for searching cycle-free graphs, a general model for the discrete, deterministic case has been given by Karp and Held I I). This model, called sequential decision process consists essentially of a fmite automaton with cull/unctions associated with the transitions. If the cost functions are monotone, and if a limit condition is satisfied, searching the transition graph of the fmite automaton is equivalent to solving a suitable set of functional equations. The authors have shown how both the functional equations model and the Karp and Held model can be derived from a quite primitive problem-reduction schema [2,3] which directly interprets the Bellman's concept of problem embedding and shows how the optima· lily principle holds if and only if the cost functions are monotone .

In this paper, we approach the problem of searching a functionally weighted graph with methods proper of artificial intelligence, in particular we extend the heuristically guided search method by Hart, Nilsson and Raphael (4 ). Since here the cost of an arc is represented by a generic monotone function, the extension is nontrivial, and it may happen that no simp/(' or no finite optimal path exists. Putting further constraints on the cost functions and on the estimaie (strict mono tonicity, positive mo· notonicity) it is then possible to simplify the general search algorithm until the classical version is reached.

The relevance of bridging the gap between dynamic programming and heuristic search methods is twofold . On one hand, the Karp and Held model provides a framework where search problems can be stated in quite general terms and (heuristic) search algorithms can be proved effective under well specified constraints. On the other hand, if good estimates can be derived from the problem domain, the solution of prob· lems amenable to a dynamic programming representation can be greatly sped up.

2. Dynamic Programming

Dynamic programming (5) is an optimization technique based on the representation of a problem as a process which evolves from state to state. When the cost structure is appropriate, the determination of an optimal solution may be reduced to the solution of a system of functional equations. A general form of such equations is the following I I)

where variables y 1 can assume any value in the complete lattice·

· The presentation of functional equations Jiven here is bated On I model of dynamic prosramming developed by the authors in (2(.

A. Martelli and U. Montanari lstituto di Elaborazione dell'lnformazione Consiglio Nazionale delle Ricerche Pisa, Italy

L = R U (+oo) U (--).consisting of the real numbers together with a bottom element - 00 and a top element +oo; the functions f 1 i : L .... L are monotone (i.e. x 1 .;;; x 2 · f(x 1 ).;;; f(x 2 )), continuous from above; the values a 1 are real constants.

The solution of system (2.1) is the maximal n·tuple (y 1 , .·. , yn) satisfying the given inequalities. Although for general functions such a maximum does not exist, it is possible to prove, by using the fixpoint theorem of lattice theory, that in the monotone case the maximum exists and satisfies (2.1) with the equal sign. Furthermore, the fixpoint theory provides an iterative algorithm for· computing the solution.

The relationships between dynamic programming and search algorithms can be made clear by introducing a model of dynamic prog· ramming, due to Karp and Held [I), called sequential decision process. This model is a finite automaton with functions associated to its transi· lions, but it can also be presented as a graph (the transition graph of the automaton).

We have a directed graph G with n+l nodes N 1 , .·· , Nn ' Nn+t ' A monotone function continuous from above f 1 J (x), called cost functjon. is associated with each arc (N 1 Ni). The node Nn+ 1 , called the solved node, has no outgoing arcs and has a constant cn+t (its cost) associated with it. The graph G with cost functions is called a functionally weighted graph An example is given in Fig. I .

Given a functionally weighted graph G, we can obtain from it a system of functional equations by associating a variable y 1 to each node N 1 (i = I, ... , n) and by writing a system of the type (2.1) where the functions f 1 i are the cost functions of the arcs (N 1 NJ) in G. Furthermore, we put a 1 = fl,n+t (cn+t ), for each i such that arc (N 1 Nn+1) exists. Con· versely, we can obtain a functionally weighted graph from a system of functional equations. For istance, the functionally weighted graph of Fig. I corresponds to the following system of functional equations, if a=f 4 (c 3 ) :

Given a path in a functionally weighted graph from node N; to the solved node Nn+t, its cost is obtained by applying in the reverse order to constant cn+a the cost functions of the arcs of the path . The next theo· rem shows how the solution of the (unctional equations is related to the costs of the paths in the corresponding functionally weighted graph. (See (3) for a proof).

Theorem 2.1. The solution Y; of functional equations for node N 1 is equal to the greatest lower bound (glb) of the costs of all paths in the functionally weighted graph from nude N 1 to the solved node Nn+t .

This theorem shows that a dynamic programming problem can be reduced to a minimal-cost path problem, if the cost of a path is suitably defined . Therefore such a problem could be solved by using algorithms for finding minimal-cost paths in a functionally weighted graph. These algorithms are well-known in the case of additive costs, i.e. where the cost functions have the form f(x) = x+a [4,6). In the next section we give a general search algorithm which uses heuristic infonnation to guide the search.

Conversely, this theorem says that a minimal-cost path problem can be solved by solving a system of functional equations with, for example, the iterative algorithm. Such a result is well-known in the additive case, and several iterative algorithms have been given for fmding the shortest path in a graph [7 ).

We point out that the model of dynamic programming presented in this section is general as far as motuldic functions are considered. However there are dynamic programming problems which are better modelled by assuming that the functional equations contain polytJdic functions (8). In this case our model can be generalized to an AND/OR graph [9).

3. A General Propagation Algorithm with Estimate

In the previous section we have d~scribed a general model for dy­ namic programming and an iterative solution algorithm. No better method is available, unless special assumptions are made on the functions fij and/ or an estimate is supplied for the cost of all intermediate problems based on information from the problem domain . This line of development cor­ responds to merging the branch-and-bound idea with dynamic program· ming and has been originally pursued by llart, Nilsson and Raphael (4) in the special case of additive functions with positive weights. Here we give a general algorithm for searching functionally weighted graphs and we show its validity when the estimates are lower bounds.

Let G be a functionally weighted graph with n+ I nodes N 1 , ·.. ... , Nn' Nn+t · and monotone cost functions fli" Given a path p from rtode N 11 to node N 1 k (p = Nil Ni 2 ... N 1 k) we defme the cost function of path pas the (monotone) function fP(x) obtained by composing the cost functions of the arcs of p:

Furthermore we define the distance function d 11 (x) from node N 1 to node N 1 u

where P 11 is the (possibly infinite) set of paths from N 1 to Nr Notice that the distance is defined, for every x, as the greatest lower bound and not simply as the minimum, because, in some cases, it can only be obtained as a limit, i.e. with an infinite path .

Finally we can define the solution cost c 1 of a node N 1 (i =I, ... , n) as the glb of all values which can be achieved by applying the cost func­ tion of every path from N 1 to Nn·· to the cost cn·· of the solved node Nn+t :

We give now an algorithm for finding the solution cost c 1 of a given node N 1 of G. called the top node, and a path for which this cost is achieved , called solution path. Note that , when the solution cost c 1 is obtained as a limit, no (finite) solution path exists. This algorithm is a bottom-up propagation algorithm, i.e. it propagates toward the top node starting with the solved node Nn·· , which, from now on, will also be called bottom node and denoted with Nb . No restriction is made on the generality of the algorithm by having only one bottom node and one top node . In fact, if more than one top node were present , we could add to the graph a new nude N 0 connected to each top node through an arc with the identity function associated with it, and we could consider N 0 as the top node of the new graph.

· Usually , in the artificial intl·llilence literalure, ~eerch ... orithms are aiven for infinite crapha. Most r~ulh of th~ paper can be extended to this case.

At each step, the algorithm selects a node N 1 and expands it gene· rating all of its parents, i.e. all nodes Ni such that (Ni N 1 ) is an arc of G. The selection of the node to be expanded is made according to a total estimate e 1 associated with each node N 1 , which is an estimate of the solution cost c 1 of node N 1 , with the constraint that . the solution path passes through node N 1 · The total estimate e 1 can be expressed as follows

where g 1 is an estimate of the solution cost c 1 of node N 1 and h 1 (x) is a monotone function which gives an estimate of the distance function c 11 (x) from N 1 to N 1 . This estimate can be obtained using the heuristic information available from the problem domain, whereas gi will be constructed step by step by the algorithm.

Our algorithm is an extension to the case of monotone cost func· tions of algorithm A· by Hart, Nilsson and Raphael [4,10), which consi­ ders the case of additive cost functions with positive weights, i.e.

for every arc (N 1 Ni). Furthermore, algorithm A· assumes that the bottom node Nb has a cost cb = 0 and that the estimate h 1 (x) is also an additive function, i.e . hi (x) = x + hr Thus, the total estimate becomes, in this ca· se , e; = gl + hi .

Since our algorithm deals with the general case of monotone cost functions, the extension is nontrivial and some new features have to be added . First of all we point out that the solution path can contain the top node N 1 more than once. This happens when the distance function from the top node to itself is smaller than the identity function (d 11 (x) < x, for some x), i.e . the top node belongs to a cycle which can reduce its cost. This fact is taken into account by adding a new node N 0 to the graph and an arc (N 0 N 1 ) with the identity function l(x) associated with it. The algorithm will stop only when this node wiU be encountered.

Furthennore, a solution path can contain the same node several times. Therefore, if we want to obtain the solution path by tracing back through the pointers from the top node, we must have more than one poiitter for each node. This is achieved by associating with each node a stack of pointers, to which a new element is added every time the riode is reopened .

Algorithm SEARCH

1. Add a new node N 0 to the graph and an arc (N 0 N 1 ) . Let the cost function of this arc be f 01 (x) = I (x) = x and h 0 (x) = I (x) .
2. Put the bottom node Nb on a list called OPEN and let gb +- ~ and eb +- hb(~).
3. If OPEN is empty, exit with failure ; otherwise continue.
4. Remove from OPEN that node Ni whose total estimate e 1 is smallest and put it on a list called CLOSED. In case of tie on the e values, choose the node N 1 whose g 1 value is smallest . Resolve further ties arbi· lrarily, but always in favor of node N 0 ·
5. If N 1 is node N 0 · exit with the solution path obtained by tracing back through the pointers; otherwise continue.
6. Expand Ni' generating all of its parents. For each parent N 1 compute g; + - fii (g;).
7. Associate with the parents N 1 not already on either OPEN or CWSED the values gi +- g; and ei +- hi (gi). Put these nodes on OPEN and put on top of their stacks a pointer back to the top of the stack of N 1 .
8. If a parent Ni is on OPEN and g; < g 1 let

Replace the pointer on top of the stack of N 1 with a pointer to the top of the stack of Ni .

9) If a parent Ni is on CWSED and g; < gl' put it on OPEN and let

Add on top of the stack of Ni a pointer to the top of the stack of N 1 · 10) Go to 3.

It is possible to prove that the above algorithm is admissible (il'. if it terminates cleanly it finds an optimal solution), if the estimate h 1 (x) is a lower bound on the distance dli (x' for each node (h 1 (x).;; d 1 i (x) for each x and for each i) . The proof is contained in the Appendix.

The proof is based on a lemma which states that, if the estimate hi (x) is a lower bound on dli (x), then at any iteration of algorithm SEARCU there is an open node Ni with e 1 .;; c 1 · This result is not trivial since the solution cost c 1 might be achieved only as a limit, and thus infinite paths have to be considered.

Notice that, in general, there is no way of deciding whether the algorithm will stop . Special classes of functions and estimates for which such a decision can be made will be presented later on .

As a further remark we point out that the bottom-up structure of our algorithm is the .most natural choice for the general case. In fact, when no estimate is available, with our algorithm we propagate costs, i.e. constants, from the solved node toward the top node, whereas, by using a top-down approach, we should propagate functions. Such a difference between bottom-up and top-down is not present in the case of additive cost functions, where functions can be propagated very easily. In fact, bidirectional search algorithms have been given for this case [ 12 ).

Algorithm SEARCH can be easily extended to the case where the estimate hi (x) is not a lower bound on tl 11 (x), but the maximal amount by which hi (x) can exceed dli (x) is known . This case has been studied in [ 13) for additive cost functions .

Assume that a strictly monotone· e"or function b (x) is given such that hi(x).;; b(d 11 (x)) for every x and for every node. Algorithm SEARCH can be modified by associating with the arc (N 0 N 1 ) the cost function b(x). It is easy to see that the new algorithm finds the solution cost of node N 1 · In fact, the distance function from N 0 to every node Ni is d 01 (x)=b(d 11 (x)) and the estimate h 1 (x) can be considered as a lower bound on d 01 (x). Therefore the algorithm fmds the solution cost of node N 0 , but, since every solution path for N 0 is a solution path for N 1 as well, for the strict monotonicity of b, it finds also the solution cost of N 1 ·

In order to see how algorithm SEARCH works, let us consider the following problem. A functionally weighted graph is given with n +I nodes, where each node N 1 (i = I, ... , n) corresponds to a different cur­ rency Ci . A directed arc (N 1 N 1 ) denotes the possibility of exchanging currency C 1 into Cr To each arc (N 1 N 1 ) (i, j = I, ... , n) we associate a cost function f 11 (x) = aii x + bii (ail > 0, biJ > 0), which means that, if we want to have the amount x of currency c 1 , we have to change an amount of currency C 1 proportional to x plus a fixed amount for taxes. Furthermore, the solved node Nn· 1 corresponds to some goods and, for each arc (N 1 Nn+l ), the value fl,n+l (cn+ 1 ) gives the cost of these goods in the currency Cl"

Our problem is that of buying the given goods with the smallest amount of currency C 1 . Notice that, if we are quite optimistic, we can hope of fmding a cycle which gives us some gain, and thus the solution path may contain some cycles.

An example is given in Fig. 2. The operator /in the cost functions denotes integer division. The given estimates imply that very little heuristic information is assumed. However it is clear that they are lower bounds if the domain of the cost functions are the nonnegative integers.

In Fig. 3 we give some steps of the execution of algorithm SEARCH. In Fig. 3a we show the stacks of pointers after node N 1 has been expanded for the first time. Each element of a stack has a number associated with a pointer. This. number is the g value of the node, and it gives the cost of the path obtained by following the pointers. Furthermore, the encircled numbers are the total estimate e of the open nodes. Notice that every time a node is reopened, a new clement is added to the stack of pointers.

Finally, in Fig. 3b we give the last step of the algorithm. We see that the solution cos_t of node N 1 is 8 and the solution path, obtained by tracing through the pointers, is N 1 N 1 N 3 N 1 N 3 N, . Thus we have obtained a solution path with a cycle.

We want to sec now how algorithm SEARCH behaves when no estimate is available . This means that, if we do not put any restriction on the cost functions, we must have hi (x) = - oo for each node . At each step of the alsorithm, each node N 1 has a total estimate e 1 = - 00 , except for node N 0 for which we have e 0 = So. According to the condition on ties in step 4 of the alsorithm, the node whose g 1 value is smallest is expanded at each step. Since N 0 is the only node with total estimate *- oo, the algorithm will stop only after all other nodes have been closed . In this case it is clear that the solution cost of all nodes is determined simulta­ neously . Thus the estimate h 1 (x) = - 00 for each node can be always assumed when the above more general problem must be solved.

· A runction r is strictly monotone if x1 < x, · rex,) < rex,).

Note that this algorithm may be used in the case of additive cost functions, if negative weishts are allowed and no estimate is available.

4 . !'_o.s~t.~~~L~'!!!~~()_!I~Cost_ F~nctions, !!J~Consisten~and Strictly Monotone Estimates -- -- ·- ·----

The first case we examine is when all cost functions are positively monotone. A monotone function is called positively monotone iff for all arsurnents x we have

Examples of positively monotone functions are as follows

It is easy to see that the composition of two positively monotone functions is still a positively monotone function, and thus the cost func· lion of every path is also a positively monotone function. As a conse­ quence, the estimates can also be assumed positively monotone without restrictions.

For positively monotone cost functions we have the following theorem, (For the proofs of all theorems in this section, see the Appendix).

The~_m __ 4 .1. let G be a functionally weighted graph with positively monotone cost functions. Then there always exists a simple solution path from the top node.

From the above theorem it follows that algorithm SEARCII can take into account only temporary solution paths without cycles. Thus the algorithm can be simplified by eliminating the stacks of pointers and by replacin& them with only one pointer for each node (as in algorithm A·).

When the estimate h is strictly monotone, looking at g values in step 4 of algorithm SEARCH for solving ties is no longer useful since h 1 (g 1 ) = hi (gi) implies B; = &i . Thus in this case algorithm SEARCH behaves exactly as A · .

Note that positive monotonicity alone, while insuring termination, does not guarantee that all closed nodes arc never reopened . This case is well-known in the special, classical case of a graph weighted with positive constants, with estimate I4J. l'ollowing I4J, we thus introduce consistent estimates. An estimate ht(x), k = I, .... n is consistent iff for all arcs (Ni N 1 ) and for all x we have

In the cue of consistent estimate , but not necessarily for positively monotone cost functions, we can prove the followins theorem.

!!!..~!!1-4:2. let (; be a functionally weighted sraph with consistent estimate ht(x), k = I , ... , n . Then the values of the total estimate e 1 of the nodes closed in the successive iterations of algorithm SEARCU form a (possibly infinite) nomlecreasing sequence .

The above result docs not mean that closed nudes arc never reope· ned . In fact a node N 1 could he closed a second time with the same esti· mate e 1 but with an impruved cost gr (Since g 1 < gi' otherwise N 1 would not be reopened. the monotonicity of h 1 docs not allow e 1 > c 1 ) .

For instance, let us consider the graph in Fig. 4 . The exact distances arc as follows :

let us take as estimate the following functions

It is easy to see that this estimate is consistent. For instance, for the loop at node N 1 we have

llowever algorithm SEARCII does not stop, even if a solution path exists, and reopens node N 1 infinitely many tin·es. The values of the coats and of the total estimates for nodes closed in successive iterations are as follows :

The following result allows to characterize the set of closed nodes which could possibly be reopened.

!heoren~~ let G be a functionally weighted eraph with consistent estimate hk(x), k = I, ... . n. At some stase of algorithm SEARCH, let N 1 be a closed node with cost s 1 and total estimate e 1 sm111ler than the total estimate ei of all open nodes . Then node N 1 will never be reopened, and its solution cost is g 1 .

If the estimate is consistent, the above theorem allows to add a new termination condition to algorithm SEARCH: "If the top node in closed and has a total estimate sm·ller than the node currently under closure, stop with success". This condition allows for instance to stop at the third iteration of the previous example.

If the two conditions of positive monotonicity of the cost functions and of consistency of the estimate are taken jointly, we can prove the fgllowin.: theorem, which is an extension of a result by llart, Nilsson and Raphaeii4J .

Theo!e_!!l _4~ let G be a functionally weighted graph with positively monotone cost functions and with a consistent estimate . Then when alsorithm SEAR('Ii closes a node N 1 · its cost g 1 is the solution cost of Nr Thus algorithm SEARCU never reopens a node .

The above theorem provides an obvious termination condition for algorithm SEAR('II: "Stop when the top node is closed".

The abyve results apply, as pointe~! out before, to the well-known case of additive cost functions . Uowever their generality allows also the application to cost functions of different form, where the standard A · algorithm cannot he used. An example is provided by the so called secondary optimization problem which arises when we want to find the best ordering of variable elimination in non-serial dynamic programming (14(. The problem can be stated as that of finding the minimal cost path in a weighted graph, but where the cost of a path is the maximum among all the weights of its arcs. Therefore the cost functions of this graph are of the form

i.e. they arc positively monotone functions and algorithm SEARCH can be used for finding the solution path, if suitable estimates arc provided· .

A further example of positively monotone but nonadditive cost functions is the so called 1-dimemioTIIJI stock cutting problem [I), where we want to determine the minimum number of standard pieces of material of length L from which it is possible to cut a 1 pieces of length 1 1 , a 2 pieces of length 1 2 , ··· , and a 0 pieces of length 1 0 . In the graph represen­ tation of this problem, the meaning of an arc is "cut a piece of length li" and the cost function associated with it is

The second case in the definition of f(x) corresponds to the situation in which the current standard piece does not have enough material remaining for the next cut, and a new standard piece is required .

According to Theorem 4 .2 and 4.3, if the estimate in consistent , then a closed node N 1 can be reopened only with the same total estimate e 1 = c 1 and with a better cost g 1 < gr Thus it is clear that, if the estimate is strictly monotone, then no closed node can be reopened . Thus the same result proved in Theorem 4 .4 holds also in this case .

As a conclusion, we point out that in this paper we have given algorithm SEARCH for searching functionally weighted graphs which is an extension of algorithm A ·, and we have shown that, for generic mo­ notone functions , this algorithm requires some new features such as the addition of node N 0 , the stack of pointers and the tie handling procedure in Step 4. Furthermore, we have shown that, by considering restricted classes of cost functions and estimates, simpler versions of algorithm SEARCH can be given . In particular, the validity of the trivial generaliza­ tion of A · is extended either to the case of strictly monotone estimates and positively monotone cost functions or to the case of strictly mono­ tone and consistent estirnares. Properties of algorithm SEARCH for another special class of cost functions (stricly monotone cost functions) are described and proved in [II).

Appendix

~:Cm'!la 3.1 . If hi (x) .;;; d 1 i (x) for every x and for every node, then at any step of the algorithm and for any path p from N 0 to Nb , there exists an open node N 1 on p with e 1 .;;; f P ( cb ).

Pro~[: Let Ni be the first open node we encounter by following path p backwards from Nb to N 0 . There must be such a node because otherwise N 0 is closed and the algorithm has terminated . Let p' be the part of path p from N 1 to Nb . Since all nodes on p' are closed, we must have

Since the distance function d 1 i (x) is a monotone function and since, in general, pis not a solution path . we have

Finally, since hi (x) is a lower bound on d 1 i (x) , we have

· Note that if estimates of the same type h. (x) = max (x,c) arc considered, the tic handling procedure in Step 4 of all!orithm S~ARCH is essential for Theorem 4.4 to hold. The same happens whenever the estimates are not strictly monotone.

• I . Karp, K.M. and Held, M .· Finite· state processes and dynamic pro!(· rammina SIAM J. Appl. Math., 15. 1'167, pp. 69.l-71K.
• Martelli, A. and Montanari, U., On the foundations of dynamic prog­ ramming, N.J. B73-ll,I.E.I. , Pisa, Oct. 197.1, to appear in li1pir.! in 01mbinatorial Optimization , S. Kinaldi ed .. ('ISM, Springer Verlag.
• Martelli,A. and Montanari U., Dynamic programming schemata, Prur. second Coil on Automata, Languages and Programming. Saarbriicken, July 1974, Springer Verlag, pp. 66-80.
• Hart , P .· Nilsson, N. and Raphael , B., A formal basis for the heuristic determination of minimum cost paths, IEEE Trant on Sy1 Sci. Cybernetics, SSC-4, N. 2, July 1968, pp. 100-107.
• Bellman, R.E., DyTIIJmic Programming, Princeton University Press, Princeton NJ . 1957.
• Dijkstra, E., A note on two problems in connection with graphs, Numerische Matk, I, 1959, pp. 269-271.
• Johnson . D.B., Algorithms for shortest paths, Ph. D. Thesis, Cornell University,lthaca, N.Y., May 1973.
• Martelli , A. and Montanari, U., Additive AND/OR graphs, Proc TltiTd Int. Joint Conf on Art. Int. , Stanford, 1973, pp. I-ll .
• 9 . Martelli . A. and Montanari, U. , Programmazione dinamica c punto fisso,Atti Conv. di Informatica Teorica, Mantova, Nov. 1974, pp. l-19 (in Italian).
• Nilsson, N.J ., Problem-solving methods in artificial intelligence, Me Graw-Hill, N.Y., 1971.
• II . Martelli, A. and Montanari, U., From dynamic programming to search algorithms with functional costs, lEI Internal Report 875-1, January 1975.
• Pohl, 1., Bi-directional and heuristic search in path problems, Ph.D. Thesis, Stanford University, Stanford, 1969.
• I J . Harris, L.R., The heuristic search under conditions of error, Artificial Intelligence, 5, N. 3, Fall1974, pp. 217-234.
• Brioschi, F. and Even, S., Minimizing the number of operations in certain discrete-variable optimization problems, Operations Research, 18, N. I , 1970, pp. 66-81.

Lemma 3.2. If hi (x).;;; d 1 i (x) for every x and for every node, then at any step of the algorithm there exists an open node Ni with ei .;;; c 1 .

Proof: If c 1 is achieved with a finite path p, then c 1 = fP (cb) and the lemma is proved by Lemma 3.1. Assume now that c 1 is obtained as a limit, and let p 1 , p 2 , p 3 , ... be an infinite sequence of paths from N 0 to Nb such that

Let us apply now the construction of Lemma 3.1 to each path of the sequence and let us consider the subsequences of paths for which the same node is obtained . Among these subsequences, there must be an infi­ nite subsequence pil . pil' piJ , ... such that

Let N. be the node obtained with the construction of Lemma 3.1 from J these paths. We have Therefore we hne and

Theorem 3.1 . If h 1 (x) < d 11 (x) for every x and for every node, and if the algorithm terminates cleanly (i.e. without failure), then it finds the solution cost c 1 of node N 1 ·

Proof. When the algorithm stops we have e 0 = h 0 (g 0 ) = f 01 (g 1 ) = g, · Assume now that e 0 is not the solution cost of N 1 , i.e . e 0 = g 1 > c 1 · By lemma 3.2 we know that there existed just before termination an open node N 1 with e 1 < c 1 . Thus, Ni , which must be different from N 0 , would have been selected for expansion rather than N 0 , contradicting the hypothesis that the alsorithm terminates. Q.E.D.

Theorem 4.1. Let G be a functionally weighted graph with positively monotone cost functions . Then there always exists a simple solution path from the top node.

Proof. Given a nonsimple path P 1 b of cost

there always exists a simple path P;b cf not larger cost

In fact, p 11 (x), being the composition of positively monotone functions, is positively monotone and thus

But p 11 (x) is monotone, so we have

As a consequence, any path of minimum cost in the finite set of simple paths is optimal. Q.E.D.

Theorem 4.2. Let G be a functionally weighted graph with consistent estimate hk(x), k = I , ... , n. Then the values of the total estimate e 1 of the nodes closed in the successive iterations of algorithm SEARCH form a (posaibly infinite) nondecreasing sequence.

Proof. When a node N 1 is closed by algorithm SEARCH its total estimate e 1 = h 1 (g 1 ) by construction is not larger than the total estiinates ek of all open nodes. In the updating phase, the total estimate of some node N 1 , adjacent to N 1 , may be decreased as follows:

and, if NJ was closed, it will be reopened. However, the new value e 1 is not smaller than e 1 by the consistency assumption. Thus, the total esti­ mate of tbe next closed node, which is the minimal among the total estimates of all open nodes after updating, will not be smaller than er Q.E.D.

Theorem 4.3. Let G be a functionally weighted graph with consistent estimate hk(x), k = I, ... , n. At some stage of algorithm SEARCH, let N 1 be a closed node with cost g 1 and total estimate e 1 fmJI/Ier than the total estimate e 1 of all open nodes. Then node N 1 will never be reopened, and its solution cost is g 1 ·

Proof. The cost g 1 is clearly not worse than the costs of all paths visiting only closed nodes. Let now P be any path from N 1 to Nb which passes through at least one open node, and let Ni be the last open node on P. We have

From the consistency assumption, extended to the part of P from N 1 to N 1 we have

But since

by assumption, we have

and finally , since h 1 is monotone,

Clearly, since g 1 is already the optimal cost , node N 1 will never be reope­ ned .

Q.E.D.

Theorem 4.4. . Let G be a functionally weighted graph with positively monotone cost functions and with a consistent e$1imate . Then when algorithm SEARCH closes a node Nl' its cost g 1 is the solution cost of N 1 · Thus algorithm SEARCH never reopens a node.

Proof. The proof is quite similar to that of Theorem 4.3. We can write again

and

Now if

the result of the proof of Theorem 4.3 is valid and the thesis follows. On the other hand, if

then we have

since N 1 was closed before N 1 . Thus we have

But since p 11 (x) is now positively monotone we have