Results


DEVISING HEURISTICS / 23 A PROBLEM SIMILARITY APPROACH TO DEVISING HEURISTICS: FIRST RESULTS

Classics (Collection 2)

John Gaschnig Department of Computer Science Carnegie-Mellon University Pittsburgh, PA 15213 Abstract Here we describe an approach, based upon a notion of problem similarity, that can be used when attempting to devise a heuristic for a given search problem (of a sort represented by graphs). The next step is to find an algorithm for finding paths in P2, then apply this algorithm in a certain way as a heuristic for P1. Using the As algorithm, we experimentally compare the performance of this "maxsort" heuristic for the 8-puzzle with others in the literature. Many combinatorially large problems cannot be solved feasibly by exhaustive case analysis or brute force search, but can be solved efficiently if a heuristic can be devised to guide the search. Research to date on devising heuristics has spanned several problem-solving domains and several approaches.



19 Parallel and Serial Methods of Pattern Matching

Classics (Collection 2)

This paper is concerned with two aspects of the'exact match' problem which is that of searching amongst a set of stored patterns to find those specified by a given partial description. We describe how to design simple contentaddressable memories, functioning in parallel, which can do this and which, in some sense, can generalise about the stored data. Secondly, we consider how certain graphical representations of data may be suitable for use in efficient serial search strategies. We indicate how such structures can be used in diagnosis when the availability or cost of tests to be applied cannot be determined in advance. The type of parallel system to be considered is to store descriptions of a set of patterns, and is then to be used to supplement an incomplete description of a newly presented pattern by matching it against those in store.


Preface Introduction

Classics (Collection 2)

An approach to analytic integration using ordered algebraic expressions: L. I. HODGSON 47 5 Some theorem-proving strategies based on the resolution principle: J. L DARLINGTON 57


BOXES: AN EXPERIMENT IN ADAPTIVE CONTROL

Classics (Collection 2)

BOXES is the name of a computer program. This is what the chess player does when he lumps together large numbers of positions as being'similar' to each other, by neglecting the strategically irrelevant features in which they differ. The resultant small game can be said to be a'model' of the large game. To give a brutally extreme example, consider a specification of chess positions so incomplete as to map from the viewpoint of White the approximately 1050 positions of the large game on to the seven shown in Figure 1. Even this simple classification may have a role in the learning of chess.



9 Bi-Directional Search

Classics (Collection 2)

A technique that has proved useful in shortest path and other discrete optimization computations has been bidirectional search. The method has been well tested in the two-node shortest-path problem providing substantial computational savings. A natural impulse is to extend its benefits to heuristic search. In the unidirectional algorithms, the search proceeds from an initial node forward until the goal node is encountered. Problems for which the goal node is explicitly known can be searched backward from the goal node.


21 Relational Descriptions in Picture Processing

Classics (Collection 2)

We have written a program which will recognize a range of objects including a cup, a wedge, a hammer, a pencil, and a pair of spectacles. A visual image, represented by a 64.x 64 array of light levels, is first partitioned into connected regions. These regions are chosen to have welldefined edges. Having chosen the regions, the program then computes properties of and relations between regions. Properties include shape as defined by Fourier analysis of the s--tfr equation of the bounding curve.


20 Analysis of Curved Line Drawings Using Context and Global Information

Classics (Collection 2)

We describe the analysis of visual scenes consisting of black on white drawings formed with curved lines, depicting familiar objects and forms: houses, trees, persons, and so on; for instance, drawings found in coloring books. The goal of such analysis is to recognize (by computer) such forms and shapes when present in the input scene; that is, to name (correctly) as many parts of the scene as possible: finger, hand, girl, dance, and so on. Complications occur because each input scene contains several such objects, partially occluding each other and in varying degrees of orientation, size, and so on. The analysis of these line drawings is an instance of'the context problem', which can be stated as'given that a set (a scene) is formed by components that locally (by their shape) are ambiguous, because each shape allows a component to have one of several possible values (a circle can be sun, ball, eye, hole) or meanings, can we make use of context information stated in the form of models, in order to single out for each component a value in such manner that the whole set (scene) is consistent or makes global sense?' Thus, shape drastically limits the values that a component could have, and further disambiguation is possible only by using global information (derived from several components and their interrelations or interconnections) under the assumption that the scene as a whole is meaningful. This paper proposes a way to solve'the context problem' in the paradigm of coloring book drawings.