En İyi Çözüm Yerine Yeterince İyi Çözüm

RotaAkıl'ı tasarlamaya başladığım gün problemi tek cümleyle yazmıştım: “Bir depo, otuz durak, iki araç; en kısa rotayı bul.” Cümle bu kadar masum görünüyor. Birkaç gün sonra anladım ki içindeki en pahalı kelime “en” imiş.

Araç rotalama problemi (VRP) ve onun daha sade hâli olan gezgin satıcı problemi (TSP), bilgisayar biliminde NP-zor sınıfında. Bunun pratikteki karşılığı şu: durak sayısı arttıkça kesin çözümü bulmak, daha hızlı bir bilgisayar alarak kapatabileceğiniz bir açık olmaktan çıkıyor.

Otuz durak kaç ihtimal demek?

Depodan çıkıp bütün durakları gezip depoya döneceksiniz. Durakların gezilme sırası değişebildiğine göre olası rota sayısı, durak sayısının faktöriyeli kadar. Sayılar insanın sezgisini hızla terk ediyor.

Tablodaki asıl mesaj süreler değil, süreler arasındaki sıçrama. Bir durak eklediğinizde iş yükü kabaca o sayıyla çarpılıyor: 21. durak, denenecek sıralama sayısını yirmi bir katına çıkarıyor. Makineyi iki kat hızlandırmak bunun yanında hiçbir şey ifade etmiyor. Donanımla kovalayabileceğiniz bir eğri değil bu.

Kaba kuvvetin yerine akıllı kesin yöntemler koyabilirsiniz — dinamik programlama, dal-sınır gibi. Bunlar tabloyu epey iyileştiriyor ve orta boy örnekleri gerçekten çözüyor. Ama yaptıkları şey eğrinin dikliğini azaltmak değil, patlamanın başladığı noktayı biraz ileri itmek. Yeterince büyük bir örnekte yine aynı duvara tosluyorsunuz.

Kesin çözüm hedef mi, lüks mü?

Bu noktada soru teknik olmaktan çıkıp ürün sorusuna dönüşüyor. RotaAkıl'ı kimin kullanacağını düşündüm: sabah sekizde deposunda duran, günün teslimatlarını planlamak isteyen biri. Bu kişinin önünde iki seçenek var.

• Matematiksel olarak en kısa rota. Ne zaman hazır olacağı belli değil.
• En kısaya yakın bir rota. Birkaç saniyede ekranda.

İkincisini seçmeyecek tek bir kullanıcı düşünemedim. Çünkü rotayı beklemek için harcanan her dakika, rotanın kazandıracağı dakikadan düşüyor. Bir noktadan sonra “daha iyi çözüm” aramak, çözümün kendisini değersizleştiriyor.

Bunu netleştirdikten sonra hedef cümlem değişti: “En kısa rotayı bul” değil, “üç saniye içinde bulabildiğin en kısa rotayı ver”. Aynı problemin bu iki hâli, tamamen farklı iki yazılım demek. Birincisi ne zaman biteceğini bilmediğiniz bir hesap; ikincisi ölçebildiğiniz, bütçeleyebildiğiniz, arayüze yerleştirebildiğiniz bir işlev.

Sezgisel yaklaşımın iskeleti: önce bir çözüm, sonra iyileştirme

Sezgisel (heuristic) yöntemlerin ortak mantığı basit. Bütün ihtimalleri taramak yerine makul bir cevapla işe başlıyor, sonra o cevabı adım adım iyileştiriyorsunuz. Garantiden vazgeçiyor, karşılığında süre satın alıyorsunuz.

Birinci aşama, en yakın komşu kuralı: bulunduğun noktadan en yakın gezilmemiş durağa git. Saniyenin altında bir rota üretiyor ama sonuç genelde kötü. Çünkü açgözlü davrandığı için yol boyunca birkaç durağı atlıyor; sonunda onları toplamak için haritanın öbür ucuna dönmek zorunda kalıyor.

İkinci aşama bu hatayı düzeltiyor. 2-opt denen yerel iyileştirme, rotadaki iki bağlantıyı söküp aradaki parçayı ters çeviriyor; toplam mesafe kısaldıysa değişikliği kabul ediyor. Haritada birbirini çaprazlayan yolları teker teker açıyor diye düşünebilirsiniz.

# 1. Aşama — hızlı başlangıç çözümü (en yakın komşu)
rota  = [depo]
kalan = duraklar[:]
while kalan:
    d = en_yakini(rota[-1], kalan)
    rota.append(d)
    kalan.remove(d)

# 2. Aşama — yerel iyileştirme (2-opt)
# İki kenarı sök, aradaki parçayı ters çevir, kısaldıysa kabul et.
for i in range(1, len(rota) - 2):
    for j in range(i + 1, len(rota) - 1):
        eski = mesafe(rota[i-1], rota[i]) + mesafe(rota[j], rota[j+1])
        yeni = mesafe(rota[i-1], rota[j]) + mesafe(rota[i], rota[j+1])
        if yeni < eski:
            rota[i:j+1] = rota[i:j+1][::-1]

Bu iki aşamanın sonunda elinizde yerel olarak iyi bir rota oluyor: tek başına yapılan hiçbir küçük değişiklik onu daha kısa yapmıyor. Ama bu, rotanın genel olarak en iyisi olduğu anlamına gelmiyor. Algoritma bir çukura düşüyor ve orada kalıyor.

Süreyi bir parametre hâline getirin

Çukurdan çıkmanın yolu, elinizdeki iyi çözümü kasten biraz bozup yeniden toparlamak. Birkaç durağı rastgele yerinden oynatıyor, sonra tekrar 2-opt uyguluyorsunuz. Bazen daha kötü bir sonuç çıkıyor, atıyorsunuz; bazen daha iyisi çıkıyor, saklıyorsunuz.

Bu döngünün ne zaman duracağına karar veren şey artık matematik değil, verdiğiniz süre bütçesi:

en_iyi = baslangic_cozumu(duraklar)
bitis  = simdi() + butce_saniye        # örneğin 3 saniye

while simdi() < bitis:
    aday = rastgele_sars(en_iyi)       # rotayı biraz boz
    aday = yerel_iyilestir(aday)       # 2-opt ile toparla
    if uzunluk(aday) < uzunluk(en_iyi):
        en_iyi = aday

return en_iyi                          # süre dolduğunda elde ne varsa o

Bu yapının en sevdiğim tarafı şu: algoritmanın her an geçerli bir cevabı var. İstediğiniz saniyede durdurabilirsiniz, elinizde çalışan bir rota kalır. Kesin çözüm arayan bir algoritmayı yarıda kesemezsiniz; ya bitirir ya da hiçbir şey vermez.

Ürün tarafında bu fark doğrudan arayüze yansıyor. “Yükleniyor” çemberi göstermek yerine “işte rotanız, arka planda iyileştirmeye devam ediyorum” diyebiliyorsunuz. Kullanıcı beklemiyor, izliyor. Aynı hesabın iki farklı sunumu ve ikisi arasındaki fark, algoritmanın değil, tasarımın kararı.

Zaten tahmini bir girdiye kusursuz cevap veriyorsunuz

Optimal çözüm takıntısını asıl kıran şey buydu. Rotayı hesaplarken kullandığınız mesafeler ve süreler gerçek değil, tahmin. Trafik akşamüstü değişiyor. Bir durakta müşteri kapıyı geç açıyor. Park yeri aramak beş dakika sürüyor. Bir sokak kazı yüzünden kapanıyor.

Yani kesin çözüm bile aslında “kesin” değil. Yanlış bir haritanın üzerine matematiksel olarak kusursuz bir çizgi çizmiş oluyorsunuz. Sezgisel yöntemin bıraktığı küçük fark, girdinin belirsizliğinin altında kalıyor. İki rakam arasındaki farkı sahada kimse ayırt edemiyorsa, o farkı almak için ödediğiniz süre boşa gidiyor demektir.

Arayüzde “en iyi rota” yazmayın

Bu kararın doğrudan arayüze yansıyan bir tarafı var. Ekrana “en iyi rota” yazarsanız iki şey oluyor: tutamayacağınız bir söz vermiş oluyorsunuz ve kullanıcıyı susturuyorsunuz. Oysa sahayı bilen kişi kullanıcı. O sokakta öğlen saatlerinde park edilemediğini algoritma bilmiyor.

Tasarımda şu üçlüye karar verdim:

• Dil: “en iyi” değil, önerilen sıra.
• Müdahale: kullanıcı durakları sürükleyip sırayı değiştirebilsin.
• Geri bildirim: değiştirdiğinde toplam sürenin ne kadar arttığını ya da azaldığını anında görsün.

Üçüncü madde ilk ikisini anlamlı kılan şey. Kullanıcı algoritmayla tartışabiliyor ve tartışmanın sonucunu sayıyla görüyor. Bu, “bize güvenin” demekten çok daha güçlü. Üstelik dürüst: sezgisel bir çözüm zaten en iyi olduğunu iddia edemez, o hâlde arayüz de etmesin.

Aynı takas rotalamaya özel değil

Bu düşünce biçimini fark ettikten sonra daha önce yaptığım işlerde de görmeye başladım. Social Connect'te görüntülü görüşmeyi kendi sunucumda barındırdığım JitsiMeet üzerine kurmuştum. Oradaki soru da aynıydı: mümkün olan en yüksek görüntü kalitesi mi, yoksa ağ zayıfladığında çözünürlüğü düşse bile kopmayan bir bağlantı mı? Kullanıcı için doğru cevap ikincisi. Kimse net bir donmuş kare istemiyor.

Kalabalık bir listeyi sıralarken, arama sonuçlarını dizerken, bir öneri üretirken hep aynı soru karşınıza çıkıyor: mükemmel cevabı mı istiyorsunuz, yoksa kullanıcının bekleyebileceği sürede gelen iyi cevabı mı? Ürünün cevabı neredeyse her zaman ikincisi oluyor.

Bunun mesleki karşılığı bence şu: “optimal” bir hedef değil, bir bütçe kalemi. Ne kadar optimallik istediğinize, elinizdeki süreye ve verinin kalitesine bakarak siz karar veriyorsunuz. Bu kararı bilinçli vermek mühendislik. Vermeyip “en iyisini bulana kadar çalışsın” demek ise çoğu zaman hiçbir şey teslim etmemek anlamına geliyor.

RotaAkıl hâlâ tasarım aşamasında; kodunu yazmadım. Ama bu çalışmanın bana kazandırdığı asıl şey bir algoritma değil, bir soru oldu: “Bu problemde yeterince iyi ne demek?” Bu soruyu baştan cevaplamadan başlanan işler, sonu gelmeyen iyileştirmeler yüzünden hiç yayınlanamıyor.

• Algoritma
• Rota Optimizasyonu
• NP-Zor
• Sezgisel Yöntem
• Ar-Ge