Navigasyon ve arama konusunda çeşitli çevirimiçi eniyileme problemlerinin analizi

Bu tezde, ağ yapıları üstünde navigasyon ve arama ile ilgili çeşitli çevrimiçi eniyileme problemleri üzerinde çalışılmıştır. Çevrimiçi problemlerde bilgiler adım adım açıklanır ve tüm bilgiler mevcut olmadan önce kararlar alınmalıdır. Tez kapsamında, afete müdahale, arama kurtarma, güvenlik ve savunma alanlarında uygulamaları olan birkaç çevrimiçi eniyileme problemi için eniyi stratejiler tasarlanıp bunların performansları teorik olarak analiz edilmiştir. Önerilen stratejilerin performanslarını analiz etmek için en kötü durumda, bilginin baştan elde olduğu (çevrimdışı) durumdaki en iyi çözüme göre, rekabetçi oranlar belirlenmiştir. İlk olarak, çevrimiçi k-Kanadalı Gezgin Problemi (k-KGP), ayrıtları kesişmeyen yollara sahip çizgeler üzerinde incelenmiştir. Daha önce literatürde bu problem için bir eniyi rassal strateji verilmiştir. Bu çalışmada, bazı durumlarda bu stratejinin uygulanamaz olduğu gösterilerek, strateji her durumda uygulanabilir ve eniyi olacak şekilde değiştirilmiştir. Daha sonra çevrimiçi çok katılımcılı k-KGP ele alınmıştır. Bu problemin sınırlı ve sınırsız iletişimin olduğu iki durumuna bakılarak, literatürde verilen, deterministik stratejilerin rekabetçi oranına alt sınırı iyileştirilmiştir. Aynı iki durum, ayrıtları kesişmeyen yollara sahip çizgeler üzerinde incelenerek, iki deterministik strateji geliştirilmiştir. Bunlardan bir tanesinin eniyi olduğu ispatlanmıştır. Problemin iletişimin olmadığı, sınırlı ve sınırsız iletişimin olduğu üç durumuna bakılarak, rassal stratejilerin rekabetçi oranına alt sınırlar geliştirilmiştir. Ayrıca iletişimli durumlar için rassal bir strateji geliştirilerek, bunun ayrıtları kesişmeyen yollara sahip çizgeler üzerinde eniyi olduğu ispatlanmıştır. Ayrıt belirsizliği olan çevrimiçi Minimum Gecikme Problemi de ele alınan bir başka problemdir. Bu problem için bir eniyi deterministik strateji geliştirilmiştir. Ayrıca, rassal stratejilerin beklenen rekabetçi oranına bir alt sınır bulunmuştur. Son olarak, çevrimiçi Ayrık Arama Problemi, yönlendirilmemiş çizgelerdeki seyahat ve arama maliyetleriyle incelenmiştir. Eniyi deterministik ve rassal stratejiler bulunmuştur.