Randevúprobléma

A randevúprobléma egy optimalizálási probléma, s mint olyat, jellemzően az operációkutatás témakörébe sorolják.

Szemléletesen szólva a randevúprobléma azt jelenti, hogy két vagy több ágens keresi egymást egy homogén keresési térben. Kérdés, hogy mely stratégiákkal kell keresniük egymást ahhoz, hogy várhatóan a lehető leghamarabb találkozzanak.

Definíciók, eredmények

Két vagy több ágens bolyong egy homogén keresési térben. Keresendő az a stratégiapár, illetve stratégia n-es, amellyel a találkozási idő várható értéke minimális. Szimmetrikus randevú-problémáról beszélünk, ha minden részt vevő ágensnek azonos stratégiát kell követnie. A homogén keresési tér lehet diszkrét vagy folytonos.

A diszkrét optimalizálási probléma

Két ágens az ötcsúcsú teljes gráfban.

A diszkrét esetben a keresési teret egy $G=(V,E)$ csúcstranzitív gráf csúcsainak összessége alkotja. (A csúcstranzitivitás azt jelenti, hogy minden u, v ∈ V csúcspárra létezik olyan automorfizmus, ami az $u$ csúcsot a $v$ csúcsra képezi le.) Az ágensek a keresési térben, tehát a gráf csúcsain helyezkednek el. Ebben az esetben az idő is diszkrét, tehát az ágensek diszkrét időpillanatokban léphetnek csúcsról csúcsra az élek mentén.

Jól ismert csúcstranzitív gráfok a teljes gráfok és a körgráfok. Ezekben kerestek 2 ágensre optimális stratégiákat Alpern, Baston és Essegaier. Ők Markov-stratégiákra szorítkoztak, ami azt jelenti, hogy egy A ágens egy adott időpillanatban p_A valószínűséggel marad ott, ahol van, és (1-p_A)/d valószínűséggel lép az egyes szomszédos csúcsokba, ahol d a csúcs fokszáma. Külön foglalkoztak a szimmetrikus esettel, amikor mindkét ágensnek ugyanazt a stratégiát kell követnie, azaz p=p_A=p_B.

Gráfosztály	optimális Markov-stratégiák
	szimmetrikus	aszimmetrikus
teljes gráfok	ismeretlen	pA=0    pB=1
páros csúcsszámú körgráfok	p≈0,2791	ismeretlen
páratlan csúcsszámú körgráfok	p=1/3	ismeretlen
szabályos testek élgráfjai	ismeretlen
hiperkockák élgráfjai	ismeretlen
Kneser-gráfok	ismeretlen

A folytonos optimalizálási probléma

Folytonos esetben a keresési tér $\mathbb {R} ^{n}$ valamely összefüggő részhalmaza, a keresési stratégiák pedig $s:\mathbb {R} ^{+}\to \mathbb {R} ^{n}$ folytonos görbék.

Irodalom

• E.J. Anderson and R.R. Weber (1990). „The rendezvous problem on discrete locations”. Journal of Applied Probability 27, 839-851. o, Kiadó: Applied Probability Trust.  
• S. Alpern (1995). „The rendezvous search problem”. SIAM Journal of Control and Optimization 33, 673-683. o. [2009. január 9-i dátummal az eredetiből archiválva]. (Hozzáférés: 2007. július 17.)  
• Tracy Truong, Andrew Stacey (2001. szeptember). „Exploration a two sided rendezvous search problem using genetic algorithms”, Kiadó: The Australian Society for Operation Research. [2007. június 30-i dátummal az eredetiből archiválva]. (Hozzáférés: 2007. július 17.)