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
A diszkrét esetben a keresési teret egy 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 csúcsot a 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.[1]
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.[1] Ők Markov-stratégiákra szorítkoztak, ami azt jelenti, hogy egy A ágens egy adott időpillanatban pA valószínűséggel marad ott, ahol van, és (1-pA)/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=pA=pB.
| Gráfosztály | optimális Markov-stratégiák | |
|---|---|---|
| szimmetrikus | aszimmetrikus | |
| teljes gráfok | ismeretlen | pA=0 pB=1 [1] |
| páros csúcsszámú körgráfok | p≈0,2791[1] | ismeretlen |
| páratlan csúcsszámú körgráfok | p=1/3[1] | 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 valamely összefüggő részhalmaza, a keresési stratégiák pedig folytonos görbék.