초록 ▼

A method and apparatus for dynamically providing a path through a network of nodes or granules may use a limited, advanced look at potential steps along a plurality of available paths. Given an initial position, at an initial node or granule within a network, and some destination node or granule in

A method and apparatus for dynamically providing a path through a network of nodes or granules may use a limited, advanced look at potential steps along a plurality of available paths. Given an initial position, at an initial node or granule within a network, and some destination node or granule in the network, all nodes or granules may be represented in a connected graph. An apparatus and method may evaluate current potential paths, or edges between nodes still considered to lie in potential paths, according to some cost or distance function associated therewith. In evaluating potential paths or edges, the apparatus and method may consider extrinsic data which influences the cost or distance function for a path or edge. Each next edge may lie ahead across the advancing "partial" wavefront, toward a new candidate node being considered for the path. With each advancement of the wavefront, one or more potential paths, previously considered, may be dropped from consideration. Thus, a "partial" wavefront, limited in size (number of nodes and connecting edges) continues to evaluate some number of the best paths "so far." The method deletes worst paths, backs out of cul-de-sacs, and penalizes turning around. The method and apparatus may be implemented to manage a computer network, a computer internetwork, parallel processors, parallel processes in a multi-processing operating system, a smart scissor for a drawing application, and other systems of nodes.

대표청구항 ▼

[ What is claimed and desired to be secured by United States Letters Patent is:] [1.] An apparatus for providing a near-optimal path through a plurality of nodes interconnected by edges, each edge associated with a unique connection between two nodes, each node comprising a component, and the nodes

[ What is claimed and desired to be secured by United States Letters Patent is:] [1.] An apparatus for providing a near-optimal path through a plurality of nodes interconnected by edges, each edge associated with a unique connection between two nodes, each node comprising a component, and the nodes configured in granules, the apparatus comprising:granules interconnected in a topology, each granule comprising one or more nodes operably interconnected by an edge, each edge having associated therewith a connection state selectable from an unloaded state and at least one loaded state, and having associated therewith an edge state comprising data corresponding to the connection state;a memory device comprising:a vacuum space containing vacuum data corresponding to the topology of the granules, the topology corresponding to the unloaded state corresponding to each granule and each edge connecting each granule to a proximate granule;a load space containing data corresponding to a topology of the granules in a loaded state comprising the granule states corresponding to a loaded state of the plurality of loaded states for each granule; anda processor operably connected to the memory device and programmed to execute an executable application comprising:a granule manager effective to provide definitions of the granules,a load manager effective to create and update load data stored in the load space,a granule event manager effective to provide data reflecting updated loads associated with edges between granules,an external agent for providing extrinsic data to the granule event manager wherein the extrinsic data influences loading decisions, anda vacuum space manager effective to receive data corresponding to events associated with changes in loading of the granules, and to update the load space with the load data corresponding to the events.