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

[szerkesztés] Történet


Más nyelveken