Reply
Thu 27 Oct, 2005 06:20 am
My team is working on a computer algorithm for this problem. Does anyone know if this is a classic graph theory problem or where I might find some solutions for this...
We would like to write an algorithm that allows a manager to rank a product by asking him/her which product is better as compared to another product. However, the algorithm should minimize the number of comparison questions that are presented to the manager.
For exmaple, if a manager has 5 products represented by A, B, C, D, E, we would like to know which product is the best, which is 2nd best, which is 3rd best, and so on.
The algorithm should gather information from the manager by asking him/her questions in a sequential fashion that are in the form of...
Is A better than B?
Is B better than C?
Is C better than D?
Is D better than E?
However, the problem is that the algorithm should be able to infer the answer to some questions based on the answers give to previous questions. For example, if the manager answers that....
A is better than B (which be represented by A > B) and
B is better than C (which be represented by B > C)
the algorithm should infere that A is better than C, and therefore not ask the manager to answer the question "Is A better than C".
This algorithm should work for N number of products.
thanks for any insight.
Just write a recursive loop to check this
Michwell: What you're looking for is a topological sort. If your computer is running a Unix or Linux system, you can invoke its
tsort command and solve the problem without any programming of your own at all.
This is a simple ranking problem using a directed diagraphs and Markovian matrix power
First take the managers responses to the yes/no ranking problems and create a directed diagraph,
So if A->B->C->D->E is the
Let a yes be a 1 and no a 0 and create the following matrix
__A_B_C_D_E
A|0_1_0_0_0
B|0_0_1_0_0
C|0_0_0_1_0
D|0_0_0_0_1
E|0_0_0_0_0
The row suns of this matrix to determine product standing. In the first case all products are equal (except for E); however, if this matrix is squared from the row sums it becomes apparent that A, B, C are superior. Cubed A and B are superior. To the fourth power A is superior.
This process can also be expanded if you are looking for features, Say A is better than B for reason A, but B is better than A for another. The matrix can be created and multiplied by itself to determine the products ranking from the sum of the rows of the power matrix.
BTW I've seen this process used to handicap race horses.
Rap
This is a simple ranking problem using a directed diagraphs and Markovian matrix power
First take the managers responses to the yes/no ranking problems and create a directed diagraph,
So if A->B->C->D->E is the
Let a yes be a 1 and no a 0 and create the following matrix
__A_B_C_D_E
A|0_1_0_0_0
B|0_0_1_0_0
C|0_0_0_1_0
D|0_0_0_0_1
E|0_0_0_0_0
The row suns of this matrix to determine product standing. In the first case all products are equal (except for E); however, if this matrix is squared from the row sums it becomes apparent that A, B, C are superior. Cubed A and B are superior. To the fourth power A is superior.
This process can also be expanded if you are looking for features, Say A is better than B for reason A, but B is better than A for another. The matrix can be created and multiplied by itself to determine the products ranking from the sum of the rows of the power matrix.
BTW I've seen this process used to handicap race horses.
Rap
i don't understand what you're talking about with the powers, but if you simply sum each row while weighting the column values by the inverse column index, this number will indicate the relative order.
how does this relate to Markov?
Stumble It!
Tweet This
Bookmark on Delicious
Share on Facebook
Share on MySpace