Dersler ve öğrenme oyunu

Dinamik programlama ve optimizasyon

Bir uzay görevinin en zor seçimlerini tablolarla çöz, Raspberry Pi 4'te: kenetlenme merdiveninden uzay istasyonları arası rota planlayıcısına.

Kurs

Dinamik programlama ve optimizasyon, Özyineleme ve geri izleme sonrasında yedi derslik ileri seviye bir Kodlama kursudur. Her derste Pi üzerinde düz Python çalışır ve bir şeyin yanması gereken galerinin iki LED'li kurulumu ile trafik lambası modülü vardır. Her adım Pi'nin yazdırdıklarıyla ya da pinlerinin yaptıklarıyla kontrol edilir ve derslerdeki her sayı programın gerçekten yazdırdığı bir sayıdır.

  1. Overlapping subproblems: a 16-rung docking ladder climbed 1, 2 or 3 rungs at a time. The slow recursion makes 37,921 calls and works out rung 2 3,136 times; a memo cuts it to 49 calls, a table fills it bottom up, and three rolling numbers climb 1000 rungs.
  2. Coin change: thruster burns of 9, 6, 5 and 1 m/s. Greedy uses three burns for 11 m/s where DP finds two (5 and 6), a pick table says which, a second table counts the 6 mixes, and reachability lists the speeds 4 and 7 m/s burns can never make.
  3. Sırt çantası: en çok bilim için 10 kg roket yükü. 256 yük üzerinden kaba kuvvet, 0/1 sırt çantası tablosu, geri yürütülen yük, klasik ileri yönlü hatayla tek satırlık sürüm ve 30 sandık 3.030 hücrede çözülür.
  4. Düzenleme mesafesi: bozuk prob komutları. Konum saymanın neden başarısız olduğu, eksiksiz yazdırılmış Levenshtein tablosu, geri yürütülen düzenlemeler ve "DEPLOY mu demek istedin?" diye cevap veren bir komut satırı.
  5. Açgözlü ve DP: en erken bitişe göre (kanıtlanabilir şekilde doğru) en kısa önce (yanlış) uydular, bölünmüş yakıta karşı tam depolar ve açgözlü yöntemin hangi para sistemlerinde işe yaradığının kontrolü.
  6. Zamanlama: farklı miktarlarda veri taşıyan uçuşlar. Açgözlü yöntem 105 MB alır, bisect kullanan bir DP 120 alır, program geri yürütülür ve kırmızı LED'de oynatılır, bir tarama çizgisi de antenleri sayar.
  7. Proje: bir rota planlayıcı: final.

Final

Sekiz uzay istasyonu arasındaki feribotlar için bir planlayıcı. En kısa süreler istasyon sırasına göre bir DP'den gelir (harita yalnızca dışa doğru uçar, yani yönlü asiklik bir grafiktir): Dünya'dan Titan'a 45 saat. Rota came_from üzerinden geri yürütülür, ikinci bir tablo en fazla k bacakla en iyi rotayı verir (Bellman-Ford turları, dört bacakta 49 saat) ve bir kiosk, Seri Monitör üzerinden bir varış noktası alır ve trafik lambalarını yakar: rota varsa yeşil, var olmayan bir istasyon için kırmızı.

Pi motoru neyi farklı yapar

Pi, CPython değil MicroPython 1.29 çalıştırıyor:

  • numpy yok, bu yüzden her tablo bir liste ya da listelerin listesi, ki DP zaten böyle öğretilir.
  • Dict'ler anahtarların giriliş sırasını korumaz. Planlayıcı dict'lerini yalnızca anahtarla okur ve yazdırılan her şey listelerden gelir.
  • Özyineleme yaklaşık 1.000 çağrıda durur, yani yukarıdan aşağı bir memo 1000 basamaklı bir merdivene tırmanamaz. Kurs bunu, aşağıdan yukarı tabloların neden önemli olduğunu göstermek için kullanır.
  • str.rjust eksik, bu yüzden düzenleme mesafesi tablosu sayıları "%2d" % v ile hizalar. bisect, functools ve büyük tam sayılar CPython'daki gibi çalışır.