Rendezvous-probléma

Az Unciklopédiából

A rendezvous-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.

A formális definíció szerint két vagy több ágens bolyong egy homogén keresési térben. Keresendő az a stratégia pár illetve stratégia n-es, amellyel a találkozási idő várható értékben minimális. Szimmetrikus rendezvous problémáról beszélünk, ha minden részvevő ágensnek azonos stratégiát kell követnie. A homogén keresési tér lehet diszkrét vagy folytonos.

[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 $u, v \in V$ 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 $\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.