multivoque application algorithms

From: Alexandre Carsac (acarsac_at_[hidden])
Date: 2003-03-03 09:08:11

I applologize, perhaps this is the wrong place, Just wondering if
the boost Graph library can be used for multivoque application.

-------------------------------------------------------------------------------------------

let be :
E = {x0, x1, ...,xp} 
F = {y0, y1, ...,yq}

G': y -> {xa.....xm}    and   card G'(y) = constant = m
G : x -> {ya.....yn}    and   card G(x) < M  for all x belongs to E

G' is the reverse application of G. G is irregular.

h : x -> h(x)  whose values are in [0,1]

The problem is to find the y0 so that G'(y0) maximise h(xa), ...,h(xm).
(assume that h(xi) near of 1 for all xi in G'(y0) )

One simple approch would be to calculate h(x) for all x associated to
all y and keep the maximum, but this lead to too much calculations.

-------------------------------------------------------------------------------------------------

I try to organized E into a binary tree. The idee is to shrink E
so that each schink step truncate the search space.

   lets take x0 so that card G(x0) be maximum. We have the composed
   application of G with its reverse one G':

       G o G' (x0) = {xaa....xpa, xab,...xpb, xpa,....xpn}

   means that x0 is tied to some other x's in E by G.

   if h(x0) is the not near 1, then the y we are looking for
   will have fewer chance to belongs to G'(x0), so it is not
   worth to look at all the h(xaa), ...h(xpn).

   This would create a bi-partion on E and so on.

 

---------------------------------
Do You Yahoo!? -- Une adresse @yahoo.fr gratuite et en français !
Testez le nouveau Yahoo! Mail

[Non-text portions of this message have been removed]