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.|thumb|right 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.
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 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 aszimmetrikusteljes gráfok ismeretlen pA=0 pB=1 páros csúcsszámú körgráfok p≈0,2791 ismeretlenpáratlan csúcsszámú körgráfok p=1/3 ismeretlenszabályos testek élgráfjai ismeretlenhiperkockák élgráfjai ismeretlenKneser-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.
Történet Jegyzetek
Irodalom
Kategória:Játékelmélet Kategória:Operációkutatás