Randevúprobléma
A Wikipédiából, a szabad lexikonból.
A randevúprobléma informálisan a következőképpen szól:
Ketten megbeszélnek egy találkozót egy parkban, ahol még egyikük sem volt. Külön érkeznek, és azt tapasztalják, hogy a park hatalmas és nem találják egymást. Ekkor mindkét személynek döntenie kell, hogy milyen stratégia szerint keresi a másikat.
[szerkesztés] Definíció
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észtvevő ágensnek azonos stratégiát kell követnie. A homogén keresési tér lehet diszkrét vagy folytonos.
- A diszkrét esetben a keresési tér egy csúcsszimmetrikus (V,E) gráf, értve ezalatt azt, hogy minden
csúcspárra létezik olyan automorfizmus, ami az u csúcsot a v csúcsra képezi le. Ebben az esetben a keresési stratégia egy csúcssorozat, ami az ágens mozgását írja le. - Folytonos esetben a keresési tér
valamely összefüggő részhalmaza, a keresési stratégiák pedig
folytonos görbék.


Based on work by