Två vänner har blivit separerade i en byggnad eller köpcentrum och vill träffas så snabbt som möjligt. Det finns n möjliga platser där de kan mötas. Platserna är dock identiska och det har inte funnits någon överenskommelse om var man ska mötas eller hur man ska söka. Därför måste de använda identiska strategier och behandla alla platser på ett symmetriskt sätt. Anta att deras sökning fortsätter i diskret tid. Eftersom de vill undvika möjligheten att aldrig träffas, kommer de att vilja använda någon randomisering strategi. Om varje person söker en av de n platser slumpmässigt vid varje steg, då möte kommer att kräva n steg i genomsnitt. Det är möjligt att göra bättre än så: även om den optimala strategin är svår att karakterisera för allmänna n, finns det en strategi med en förväntad tid fram till mötesplatsen på mindre än 0,829 n för stora nog n. För n = 2 och 3 den optimala strategin kan fastställas och i genomsnitt 2 respektive 8/3 steg krävs. Det finns många lockande variationer i detta problem, som vi diskuterar med några gissningar. DYNAMISK PROGRAMMERING; SÖKPROBLEM I detta dokument introducerar vi en ny klass av problem som rör två spelare som vill träffas så snabbt som möjligt. Det problem vi beskriver har några ovanliga drag och ger upphov till ett förvirrande antal relaterade problem, av vilka många tycks vara intressanta i sig själva. I den sista delen av detta dokument gör vi en kort genomgång av några av dessa relaterade problem, tillsammans med ett antal gissningar och öppna problem. Kanske det bästa sättet att introducera problemet är att anta att två personer blir separerade i en byggnad, ett varuhus till exempel, och vill träffas igen. Om de inte har någon på förhand fastställd plan för att ta itu med denna situation, kommer det inte att vara lätt att bestämma vad man skall göra. Ska en av dem stanna där han eller hon är tills hittas av den andra? Och i så fall, hur länge bör de vänta (eftersom de kanske båda har beslutat att stanna still)? Den enklaste matematiska formulering som fångar några av särdragen i denna situation är att anta att det finns n olika platser i byggnaden, och
I asymmetriskt möte är den optimala strategin för en robot med ett känt ID att förbli stilla medan den andra roboten besöker varje vertex REF.
The Rendezvous Problem on Discrete Locations
{'venue': None, 'journal': 'Journal of Applied Probability', 'mag_field_of_study': ['Mathematics']}