Pengantar Algoritma Greedy dengan Java

1. Perkenalan

Dalam tutorial ini, kami akan memperkenalkan algoritme serakah di ekosistem Java.

2. Masalah Serakah

Saat menghadapi masalah matematika, mungkin ada beberapa cara untuk merancang solusi. Kita dapat mengimplementasikan solusi iteratif, atau beberapa teknik lanjutan, seperti prinsip divide and conquer (misalnya algoritma Quicksort) atau pendekatan dengan pemrograman dinamis (misalnya masalah Knapsack) dan banyak lagi.

Seringkali, kami mencari solusi yang optimal, tetapi sayangnya, kami tidak selalu mendapatkan hasil seperti itu. Namun, ada kasus di mana bahkan hasil yang kurang optimal pun berharga. Dengan bantuan beberapa strategi khusus, atau heuristik , kita mungkin mendapatkan hadiah yang sangat berharga untuk diri kita sendiri.

Dalam konteks ini, dengan adanya masalah yang dapat dibagi, strategi yang pada setiap tahap proses mengambil pilihan yang optimal secara lokal atau "pilihan rakus" disebut algoritma rakus.

Kami menyatakan bahwa kami harus mengatasi masalah "yang dapat dibagi": Situasi yang dapat digambarkan sebagai sekumpulan subproblem dengan karakteristik yang hampir sama. Akibatnya, sebagian besar waktu, algoritme greedy akan diimplementasikan sebagai algoritme rekursif .

Algoritme yang rakus dapat menjadi cara untuk mengarahkan kita ke solusi yang masuk akal meskipun lingkungannya keras; kurangnya sumber daya komputasi, batasan waktu eksekusi, batasan API, atau jenis batasan lainnya.

2.1. Skenario

Dalam tutorial singkat ini, kami akan menerapkan strategi rakus untuk mengekstrak data dari jaringan sosial menggunakan API-nya.

Katakanlah kami ingin menjangkau lebih banyak pengguna di media sosial "burung biru kecil". Cara terbaik untuk mencapai tujuan kami adalah dengan memposting konten orisinal atau tweet ulang sesuatu yang akan membangkitkan minat untuk khalayak luas.

Bagaimana kami menemukan penonton seperti itu? Nah, kita harus menemukan akun dengan banyak pengikut dan tweet beberapa konten untuk mereka.

2.2. Klasik vs. Serakah

Kami memperhitungkan situasi berikut: Akun kami memiliki empat pengikut, yang masing-masing memiliki, seperti yang digambarkan pada gambar di bawah, masing-masing 2, 2, 1 dan 3 pengikut, dan seterusnya:

Dengan tujuan ini dalam pikiran kami, kami akan mengambil yang memiliki lebih banyak pengikut di antara pengikut akun kami. Kemudian kami akan mengulangi prosesnya dua kali lagi hingga kami mencapai tingkat koneksi ke-3 (total empat langkah).

Dengan cara ini, kami menentukan jalur yang dibuat dari pengguna, mengarahkan kami ke basis pengikut terluas dari akun kami. Jika kami dapat menyampaikan beberapa konten kepada mereka, mereka pasti akan mencapai halaman kami.

Kita bisa mulai dengan pendekatan "tradisional". Di setiap langkah, kami akan melakukan kueri untuk mendapatkan pengikut akun. Sebagai hasil dari proses pemilihan kami, jumlah akun akan meningkat setiap langkahnya.

Anehnya, secara total, kami akhirnya melakukan 25 kueri:

Di sini muncul masalah: Misalnya, API Twitter membatasi jenis kueri ini menjadi 15 setiap 15 menit. Jika kami mencoba melakukan lebih banyak panggilan daripada yang diizinkan, kami akan mendapatkan " Batas kecepatan melebihi kode - 88 ", atau " Dikembalikan di API v1.1 saat permintaan tidak dapat dilayani karena batas kapasitas aplikasi telah habis untuk sumber daya “. Bagaimana kita bisa mengatasi batasan seperti itu?

Nah, jawabannya ada di depan kita: Algoritma yang rakus. Jika kita menggunakan pendekatan ini, di setiap langkah, kita dapat berasumsi bahwa pengguna dengan pengikut terbanyak adalah satu-satunya yang perlu dipertimbangkan: Pada akhirnya, kita hanya membutuhkan empat kueri. Peningkatan yang lumayan!

Hasil dari kedua pendekatan tersebut akan berbeda. Dalam kasus pertama, kami mendapatkan 16, solusi optimal, sedangkan dalam kasus terakhir, jumlah pengikut yang dapat dijangkau maksimum hanya 12.

Akankah perbedaan ini begitu berharga? Kami akan memutuskan nanti.

3. Implementasi

Untuk mengimplementasikan logika di atas, kami menginisialisasi program Java kecil, di mana kami akan meniru API Twitter. Kami juga akan memanfaatkan perpustakaan Lombok.

Sekarang, mari kita definisikan komponen SocialConnector kita di mana kita akan mengimplementasikan logika kita. Perhatikan bahwa kami akan membuat penghitung untuk mensimulasikan pembatasan panggilan, tetapi kami akan menurunkannya menjadi empat:

public class SocialConnector { private boolean isCounterEnabled = true; private int counter = 4; @Getter @Setter List users; public SocialConnector() { users = new ArrayList(); } public boolean switchCounter() { this.isCounterEnabled = !this.isCounterEnabled; return this.isCounterEnabled; } } 

Kemudian kami akan menambahkan metode untuk mengambil daftar pengikut dari akun tertentu:

public List getFollowers(String account) { if (counter < 0) { throw new IllegalStateException ("API limit reached"); } else { if (this.isCounterEnabled) { counter--; } for (SocialUser user : users) { if (user.getUsername().equals(account)) { return user.getFollowers(); } } } return new ArrayList(); } 

Untuk mendukung proses kami, kami memerlukan beberapa kelas untuk membuat model entitas pengguna kami:

public class SocialUser { @Getter private String username; @Getter private List followers; @Override public boolean equals(Object obj) { return ((SocialUser) obj).getUsername().equals(username); } public SocialUser(String username) { this.username = username; this.followers = new ArrayList(); } public SocialUser(String username, List followers) { this.username = username; this.followers = followers; } public void addFollowers(List followers) { this.followers.addAll(followers); } }

3.1. Algoritma Greedy

Akhirnya, saatnya menerapkan strategi serakah kita, jadi mari tambahkan komponen baru - GreedyAlgorithm - di mana kita akan melakukan rekursi:

public class GreedyAlgorithm { int currentLevel = 0; final int maxLevel = 3; SocialConnector sc; public GreedyAlgorithm(SocialConnector sc) { this.sc = sc; } }

Kemudian kita perlu memasukkan metode findMostFollowersPath di mana kita akan menemukan pengguna dengan pengikut terbanyak, menghitungnya, dan kemudian melanjutkan ke langkah berikutnya:

public long findMostFollowersPath(String account) { long max = 0; SocialUser toFollow = null; List followers = sc.getFollowers(account); for (SocialUser el : followers) { long followersCount = el.getFollowersCount(); if (followersCount > max) { toFollow = el; max = followersCount; } } if (currentLevel < maxLevel - 1) { currentLevel++; max += findMostFollowersPath(toFollow.getUsername()); } return max; }

Ingat: Di sinilah kita melakukan pilihan serakah. Karena itu, setiap kali kami memanggil metode ini, kami akan memilih satu dan hanya satu elemen dari daftar dan melanjutkan: Kami tidak akan pernah mundur pada keputusan kami!

Sempurna! Kami siap untuk pergi, dan kami dapat menguji aplikasi kami. Sebelum itu, kita perlu ingat untuk mengisi jaringan kecil kita dan akhirnya, jalankan pengujian unit berikut:

public void greedyAlgorithmTest() { GreedyAlgorithm ga = new GreedyAlgorithm(prepareNetwork()); assertEquals(ga.findMostFollowersPath("root"), 5); }

3.2. Algoritma Non-Greedy

Mari kita buat metode tidak serakah, hanya untuk memeriksa dengan mata kita apa yang terjadi. Jadi, kita perlu mulai dengan membangun kelas NonGreedyAlgorithm :

public class NonGreedyAlgorithm { int currentLevel = 0; final int maxLevel = 3; SocialConnector tc; public NonGreedyAlgorithm(SocialConnector tc, int level) { this.tc = tc; this.currentLevel = level; } }

Let's create an equivalent method to retrieve followers:

public long findMostFollowersPath(String account) { List followers = tc.getFollowers(account); long total = currentLevel > 0 ? followers.size() : 0; if (currentLevel 
    
      0; i--) { if (count[i-1] > max) { max = count[i-1]; } } return total + max; } return total; }
    

As our class is ready, we can prepare some unit tests: One to verify the call limit exceeds and another one to check the value returned with a non-greedy strategy:

public void nongreedyAlgorithmTest() { NonGreedyAlgorithm nga = new NonGreedyAlgorithm(prepareNetwork(), 0); Assertions.assertThrows(IllegalStateException.class, () -> { nga.findMostFollowersPath("root"); }); } public void nongreedyAlgorithmUnboundedTest() { SocialConnector sc = prepareNetwork(); sc.switchCounter(); NonGreedyAlgorithm nga = new NonGreedyAlgorithm(sc, 0); assertEquals(nga.findMostFollowersPath("root"), 6); }

4. Results

It's time to review our work!

First, we tried out our greedy strategy, checking its effectiveness. Then we verified the situation with an exhaustive search, with and without the API limit.

Our quick greedy procedure, which makes locally optimal choices each time, returns a numeric value. On the other hand, we don't get anything from the non-greedy algorithm, due to an environment restriction.

Comparing the two methods' output, we can understand how our greedy strategy saved us, even if the retrieved value that is not optimal. We can call it a local optimum.

5. Conclusion

Dalam konteks yang bisa berubah dan cepat berubah seperti media sosial, masalah yang membutuhkan solusi optimal bisa menjadi chimera yang mengerikan: Sulit dijangkau dan, pada saat yang sama, tidak realistis.

Mengatasi batasan dan mengoptimalkan panggilan API adalah tema yang lumayan, tetapi, seperti yang telah kita bahas, strategi serakah itu efektif. Memilih pendekatan semacam ini menyelamatkan kita dari rasa sakit, mengembalikan hasil yang berharga sebagai gantinya.

Ingatlah bahwa tidak setiap situasi cocok: Kita perlu mengevaluasi keadaan kita setiap saat.

Seperti biasa, kode contoh dari tutorial ini tersedia di GitHub.