Bài học và trò chơi học tập

Quy hoạch động và tối ưu

Giải những lựa chọn khó nhất của một nhiệm vụ không gian bằng bảng, trên Raspberry Pi 4: từ thang ghép nối tới bộ dò tuyến đường giữa các trạm không gian.

Khóa học

Quy hoạch động và tối ưu là khóa Lập trình nâng cao gồm bảy bài học, sau khóa Đệ quy và quay lui. Mỗi bài học dùng Python thuần trên Pi, với bộ hai LED trong thư viện và mô-đun đèn giao thông nơi cần có thứ gì đó sáng lên. Mỗi bước được kiểm tra dựa trên những gì Pi in ra hoặc chân của nó làm, và mọi con số trong bài học đều là con số chương trình thật sự in ra.

  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. Balo: 10 kg hàng tên lửa cho nhiều khoa học nhất. Vét cạn 256 cách xếp, bảng balo 0/1, lần ngược lại cách xếp, bản một dòng với lỗi kinh điển đi xuôi, và 30 thùng giải xong trong 3.030 ô.
  4. Khoảng cách chỉnh sửa: các lệnh que đo bị nhiễu. Vì sao đếm vị trí thất bại, bảng Levenshtein in ra trọn vẹn, lần ngược lại các chỉnh sửa, và một dòng lệnh trả lời "ý bạn là DEPLOY?"
  5. Tham lam và QHĐ: các quỹ đạo vệ tinh chọn theo giờ kết thúc sớm nhất (chứng minh được là đúng) đối đầu với ngắn nhất trước (sai), chia nhỏ nhiên liệu đối đầu với nguyên bình, và một lần kiểm tra xem hệ đồng xu nào tham lam giải được.
  6. Phân lịch: các quỹ đạo chở lượng dữ liệu khác nhau. Tham lam được 105 MB, QHĐ với bisect được 120, lịch được lần ngược và chiếu lên LED đỏ, và một đường quét đếm anten.
  7. Dự án: bộ lập lộ trình: phần kết.

Hồi kết

Bộ lập lộ trình cho phà giữa tám trạm không gian. Thời gian ngắn nhất đến từ QHĐ theo thứ tự trạm (bản đồ chỉ bay ra ngoài, nên là đồ thị có hướng không chu trình): Trái Đất đến Titan trong 45 giờ. Lộ trình được lần ngược từ came_from, bảng thứ hai trả lời lộ trình tốt nhất với nhiều nhất k chặng (các vòng Bellman-Ford, 49 giờ trong bốn chặng), và một ki-ốt nhận điểm đến qua Serial Monitor và bật đèn giao thông: xanh nếu có lộ trình, đỏ nếu trạm không tồn tại.

Pi engine khác gì ở điểm nào

Pi chạy MicroPython 1.29, không phải CPython:

  • Không có numpy, nên mọi bảng là một list hoặc list của list, mà đó cũng là cách QHĐ thường được dạy.
  • Dict không giữ thứ tự các khóa được đưa vào. Bộ lập lộ trình chỉ đọc dict theo khóa, và mọi thứ in ra đều đến từ list.
  • Đệ quy dừng lại gần 1.000 lần gọi, nên memo từ trên xuống không leo nổi thang 1000 bậc. Khóa học dùng điều đó để cho thấy vì sao bảng từ dưới lên quan trọng.
  • Thiếu str.rjust, nên bảng khoảng cách chỉnh sửa căn số bằng "%2d" % v. bisect, functools và số nguyên lớn hoạt động như trong CPython.