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.

Definíció[szerkesztés]

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 gráf, értve ezalatt azt, hogy minden csúcspárra létezik olyan automorfizmus, ami az csúcsot a 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.

Szerk. megj.:

Antistub.png Habozás és változtatás nélkül lenyúlva a Wikipédiából. (Nem számítva az elütéseket, egyes helyesírási hibákat, megmégamiaszemünketbáncsa...)