Optimization technique using heap sort
First Claim
1. A method for optimizing a decision assignment based on a sought benefit, said method comprising:
- mapping a plurality of agents to a plurality of actions into a plurality of agent-action pairs;
designating a benefit to each pair of said plurality of pairs to generate a corresponding plurality of benefits in a set of nodes;
arranging said set of nodes into a plurality of heaps corresponding to said plurality of agents, such that for each heap in said plurality of heaps, a node having the sought benefit is disposed as a head of said each heap to establish a plurality of heads corresponding to said plurality of heaps, with a tail of said each heap containing any remaining node in said each heap;
assigning a first head among said plurality of heads as an initial head, said initial head corresponding to an initial action and an initial benefit;
comparing a second head among said plurality of heads to said initial head, such that said second head corresponds to a second benefit;
removing, from said each heap, each tail node that includes a tail action corresponding to said initial action; and
repeating said comparing and removing operations for any remaining heap of said plurality of heaps;
summing each benefit for said plurality of heads to determine a cumulative benefit.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and a corresponding computer-readable medium are provided for optimizing a decision assignment based on a sought benefit. The optimization operations include mapping agents to actors into pairs, designating a benefit to each pair for a set of nodes, arranging the nodes into heaps (with each heap corresponding to an agent), selecting the node with the sought benefit as the head of the heap for all the heaps, and summing each benefit of the heads to establish a cumulative benefit. The benefit designation further includes associating the node with the benefit, action and agent that correspond to that pair, and disposing the node into the heap that corresponds to the agent. Arranging the heap further includes comparing first and second nodes to determine which has the sought benefit within the heap, and ordering the peak node as the head of the heap. Further operations include deconflicting first and second heaps that have heads with equal benefit, and truncating tail nodes from the head of each heap.
10 Citations
16 Claims
-
1. A method for optimizing a decision assignment based on a sought benefit, said method comprising:
-
mapping a plurality of agents to a plurality of actions into a plurality of agent-action pairs; designating a benefit to each pair of said plurality of pairs to generate a corresponding plurality of benefits in a set of nodes; arranging said set of nodes into a plurality of heaps corresponding to said plurality of agents, such that for each heap in said plurality of heaps, a node having the sought benefit is disposed as a head of said each heap to establish a plurality of heads corresponding to said plurality of heaps, with a tail of said each heap containing any remaining node in said each heap; assigning a first head among said plurality of heads as an initial head, said initial head corresponding to an initial action and an initial benefit; comparing a second head among said plurality of heads to said initial head, such that said second head corresponds to a second benefit; removing, from said each heap, each tail node that includes a tail action corresponding to said initial action; and repeating said comparing and removing operations for any remaining heap of said plurality of heaps; summing each benefit for said plurality of heads to determine a cumulative benefit. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A computer-readable medium that provides instructions for optimizing a decision assignment based on a benefit, said instructions comprising:
-
mapping a plurality of agents to a plurality of actions into a plurality of agent-action pairs; designating a benefit to each pair of said plurality of pairs to generate a corresponding plurality of benefits in a set of nodes; arranging said set of nodes into a plurality of heaps corresponding to said plurality of agents, such that for each heap in said plurality of heaps, a node having the sought benefit is disposed as a head of said each heap to establish a plurality of heads corresponding to said plurality of heaps, with a tail of said each heap containing any remaining node in said each heap; assigning a first head among said plurality of heads as an initial head, said initial head corresponding to an initial action and an initial benefit; comparing a second head among said plurality of heads to said initial head, such that said second head corresponds to a second benefit; removing, from said each heap, each tail node that includes a tail action corresponding to said initial action; and repeating said comparing and removing operations for any remaining heap of said plurality of heaps; summing each benefit for said plurality of heads to determine a cumulative benefit. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
Specification