Organizations maintain informational websites for wired devices. The information content of such websites tends to change slowly with time, so a steady pattern of usage is soon established. User preferences, both at the individual and at the aggregate level, can then be gauged from user access log files. We propose a heuristic scheme based on simulated annealing that makes use of the aggregate user preference data to re-link the pages to improve navigability. This scheme is also applicable to the initial design of websites for wireless devices. Using the aggregate user preference data obtained from a parallel wired website, and given an upper bound on the number of links per page, our methodology links the pages in the wireless website in a manner that is likely to enable the “typical” wireless user to navigate the site efficiently. Later, when a log file for the wireless website becomes available, the same approach can be used to refine the design further.

The best-first search algorithm A* allows search graphs that are trees, directed acyclic graphs or directed graphs with cycles. In real life applications of A* the search graph is generally implemented as a tree. It is shown here that for certain well known one-machine job sequencing problems that arise in job shops, graph search is much faster than best-first tree search when problem instances are of small and medium size. Moreover, graph search uses less memory and so is able to solve larger problems. Depth-first search needs little memory, and is therefore capable in principle of solving problems of arbitrary size, but is slower than graph search by orders of magnitude for the examples that were studied.

Three different approaches to heuristic search in networks are analyzed. In the first approach, as formulated initially by Hart, Nilsson, and Raphael, and later modified by Martelli, the basic idea is to choose for expansion that node for which the evaluation function has a minimum value. A second approach has recently been suggested by Nilsson. In this method, in contrast to the earlier one, a node that is expanded once is not expanded again; instead, a “propagation” of values takes place. The third approach is an adaptation for networks of an AND/OR graph “marking” algorithm, originally due to Martelli and Montanari. Five algorithms are presented. Algorithms A and C illustrate the first approach; PropA and PropC, the second one; and MarkA, the third one. The performances of these algorithms are compared for both admissible and inadmissible heuristics using the following two criteria: (i) cost of the solution found; (ii) time of execution in the worst case, as measured by the number of node expansions (A, C), or node “selections” (PropA, PropC), or arc “markings” (MarkA). The relative merits and demerits of the algorithms are summarized and indications are given regarding which algorithm to use in different situations.

Two new marking algorithms for AND/OR graphs called CF and CS are presented. For admissible heuristics CS is not needed, and CF is shown to be preferable to the marking algorithms of Martelli and Montanari. When the heuristic is not admissible, the analysis is carried out with the help of the notion of the first and second discriminants of an AND/OR graph. It is proved that in this case CF can be followed by CS to get optimal solutions, provided the sumcost criterion is used and the first discriminant equals the second. Estimates of time and storage requirements are given. Other cost measures, such as maxcost, are also considered, and a number of interesting open problems are enumerated.

Three heuristic search algorithms, called Algorithms A, B, and C, are presented.Their performance, with the admlssib/hty condition relaxed, is compared using the following two criteria: (i) number of node expansions and (u) cost of solutmn found.First, a general comparison is made.In this process some variations and extensions of C are also considered.Subsequently, two types of heuristic estimates, called proper and path dependent, are defined, and the algorithms are reexamined.It is shown that on the whole A (Nilsson's algorithm) and B (Martelli's algorithm) are inferior to C, which is a slightly modified version of B.