Rute pengiriman dengan kapasitas terbatas
Capacitated Vehicle Routing ProblemAntarkan 12 paket dengan kapasitas motor 6 paket per trip. Susun rute terpendek, lalu bandingkan dengan algoritma.
Peta pengantaran
Posisi disederhanakan. Jarak dihitung sebagai garis lurus.
Kompleksitas O(n!). Belum ada algoritma yang menjamin solusi optimal dalam waktu polinomial, sehingga masalah ini tergolong NP-hard.
Metode eksak menjamin solusi optimal dengan waktu yang dapat eksponensial; heuristik cepat dan cukup baik.
Savings menggabungkan trip paling hemat jarak; 2-opt menghilangkan jalur yang bersilangan.
Dipelajari di mata kuliah ini. Lanjutan: tabu search, simulated annealing, hyper-heuristics.
Penjadwalan kuliah tanpa bentrok
Scheduling ProblemTempatkan 9 kelas ke dalam 5 slot waktu hingga seluruh constraint terpenuhi dengan perpindahan seminimal mungkin.
Papan jadwal
Seret kartu atau gunakan menu pada kartu. = membutuhkan lab.Data dosen dan kelas bersifat fiktif.
Setiap kelas adalah variabel yang diberi slot tanpa melanggar constraint, sejalan dengan Struktur Diskrit.
Backtracking memotong cabang yang melanggar; MRV mendahulukan kelas dengan pilihan slot paling sedikit.
Dipelajari di kedua mata kuliah ini. Skala besar: tabu search, simulated annealing, algoritma genetika.
Prediksi selera dari pola rating
User-based collaborative filteringKorelasi Pearson mengukur kemiripan rating Anda dengan pengguna lain untuk memprediksi rating makanan yang belum Anda coba.
Rating Anda
1 = tidak suka, 5 = sangat sukaKemiripan dengan 6 pengguna
Korelasi Pearson bernilai −1 sampai 1. Data pengguna merupakan contoh.
Prediksi untuk Anda
skala 1 sampai 5Rating dinormalisasi terhadap rata-rata tiap pengguna karena standar penilaian berbeda.
Sistem tidak mengenal rasa makanan, hanya pola rating yang searah antarpengguna.
Cold start, sparsity, dan skala jutaan pengguna dihadapi Netflix, Spotify, dan marketplace.
Dipelajari di mata kuliah ini. Turut dibahas: sistem pakar, representasi pengetahuan, NLP.