Algoritma Deteksi Siklus Floyd (Algoritma penyu dan kelinci) adalah deteksi siklus yang efektif dalam struktur iteratif. Selain daftar tertaut, ini berlaku untuk masalah -masalah praktis seperti deteksi penipuan dan alur kerja pengguna di mana data digandakan di mana ada dependensi siklus dalam alur kerja atau transaksi keuangan.

Artikel ini menggambarkan implementasinya yang praktis dengan sistem deteksi penipuan untuk transaksi perbankan.

Kasus Pengguna: Mendeteksi penipuan dalam transfer uang

Bank secara teratur memantau transfer uang antar akun pelanggan. Penipuan dapat melibatkan siklus uang yang mengalir dalam sejumlah akun dan kembali ke sumber (biasanya untuk menghindari deteksi atau menyembunyikan asal usul uang). Dengan mengidentifikasi siklus ini, bank dapat diperingatkan tentang tindakan pencucian uang apa pun.

Contoh data untuk contoh ini:

Memahami data yang telah disampel

1. Transfer akun “ABC” ke akun “BCD”.
2. Dari akun “BCD” ke akun “CDE”.
3. Akhirnya, “CDE” mengirim “def”.
4. Pindah dari akun “DEF” ke akun “BCD” membuat loop: BCD → CDE → DEF → BCD.

Cara menggunakan algoritma untuk deteksi

Saat menerapkan deteksi siklus menggunakan algoritma Floyd, transaksi dimodelkan sebagai grafik terarah di mana:

1. Node mewakili akun
2. Tepi mewakili transfer uang antar node individu

Ada dua pointer (pointer lambat dan cepat) yang digunakan untuk memeriksa siklus / loop.

Java Objects Transfer Akun Pemetaan Transfer:

class AccountTransferGraph {
    private final Map> adjacencyMap=new HashMap<>();
    //add a transfer from one account to another
    public void addAccountTransfer(String source,String destination){
        adjacencyMap.computeIfAbsent(source, k -> new ArrayList<>()).add(destination);
    }
    //retrieve all transfers from a given account
    public List getTransfers(String account){
        return adjacencyMap.getOrDefault(account,new ArrayList<>());
    }
    //retrieve all accounts
    public Set getAllAccounts(){
        return adjacencyMap.keySet();
    }
}

Bantuan kelas untuk menemukan siklus dari grafik yang dibuat menggunakan objek Java di atas:

class FloydCycleDetector{
   public static boolean isCyclePresent(AccountTransferGraph graph,String start){
       String slow=start,fast=start;
       while(true){
           // Move slow pointer one step
           slow = next(graph, slow);

           // Move fast pointer two steps
           fast = next(graph, next(graph, fast));

           // If pointers meet, a cycle is detected
           if (slow != null && slow.equals(fast)) {
               return true;
           }

           // If fast pointer reaches null, no cycle exists
           if (fast == null || slow == null) {
               return false;
           }

       }
   }
    // get next account
    private static String next(AccountTransferGraph graph, String account) {
        List transfers = graph.getTransfers(account);
        return transfers.isEmpty() ? null : transfers.get(0);
    }

}

Kelas uji untuk memvalidasi logika di atas:

// Main class to test the algorithm
public class FraudDetectionSystem {
    public static void main(String[] args) {
        //STEP 1: Build the account transfer graph object
        AccountTransferGraph graph = new AccountTransferGraph();

        //STEP 2: add test account transfer data
        graph.addAccountTransfer("a", "b");
        graph.addAccountTransfer("b", "c");
        graph.addAccountTransfer("c", "d");
        graph.addAccountTransfer("d", "b");

        //STEP 3: check for cycles starting from each account
        for (String account : graph.getAllAccounts()) {
            if (FloydCycleDetector.isCyclePresent(graph, account)) {
                System.out.println("Cycle detected starting from account: " + account);
                return;
            }
        }
        System.out.println("No cycles detected.");
    }
}

Penjelasan Kode

ITU AccountTransferGraph Kelas mewakili hubungan antara akun sebagai grafik terarah. Berikut beberapa metodenya:

• addAcountTransfer(String source, String destination) – Tambahkan transfer (tepi terarah) antara dua akun
• getTransfers(String account) – Memulihkan daftar akun yang telah ditransfer oleh akun tertentu
•  getAllAccounts() – Mengembalikan semua akun (node) di grafik

Algoritma Deteksi Siklus Floyd

ITU FloydCycleDetector Kelas menggunakan dua pointer:

• Slow Pointer (Turtle) – Pergi satu posisi pada satu waktu.
• Pointer Rapid (Hare) – Pergi dua posisi secara bersamaan.

Perilaku Algoritma:

1. Jika ada siklus dalam grafik:
   • Pointer lambat, yang bergerak pada tingkat reguler, akhirnya memenuhi penunjuk cepat pada saat tertentu.
2. Jika tidak ada siklus / loop yang ada:
   • Salah satu petunjuk program melintasi akhir (null).

Metode utama

ITU isCyclePresent(AccountTransferGraph graph, String start) Metode ini dirancang untuk:

• Deteksi jika ada siklus dari akun yang diberikan
• Gunakan metode bantuan next() Untuk memulihkan akun berikut dalam rantai

Kelas Uji untuk memvalidasi algoritma di atas dalam deteksi penipuan.

ITU FraudDetectionSystem Kelas mengintegrasikan accountTransferGraphdan logika deteksi siklus:

1. Bangun grafik dengan transfer
2. Periksa setiap akun dalam grafik siklus menggunakan algoritma Floyd
3. Hasil Jika suatu siklus terdeteksi

Kemungkinan batasan dan peningkatan

• Deteksi siklus yang unik. Algoritma Floyd mengidentifikasi siklus. Penelitian -Depth pertama (DFS) harus digunakan dalam semua kasus untuk mengidentifikasi semuanya.
• Grafik yang kompleks. Algoritma mengandaikan tepi per node. Untuk grafik dengan beberapa tepi, adaptasi tertentu mungkin diperlukan.

Penggunaan serbaguna dari algoritma deteksi siklus Floyd

Ini sangat populer untuk memberikan deteksi siklus dalam daftar dan grafik yang terkait dengan manajemen memori yang efektif dan menghindari loop tak terbatas dalam algoritma. Dalam jaringan, ini mengidentifikasi loop routing dan mengoptimalkan model sistem terdistribusi yang menghindari jalan buntu. Dalam bioinformatika, ini membantu menganalisis sekuens DNA dan simulasi struktur protein dengan mengidentifikasi model pengulangan dalam data biologis yang kompleks.

Ini juga digunakan dalam AI dan ML untuk mencegah loop pelatihan terjadi selamanya dalam belajar penguatan atau untuk mengidentifikasi ketergantungan siklus dalam model berdasarkan grafik. Baik di blockchain, sistem operasi atau kriptografi, algoritma Floyd terus menjadi anugerah untuk menawarkan stabilitas dan efisiensi di berbagai bidang perhitungan.

Kesimpulan

Algoritma Deteksi Siklus Floyd adalah solusi sederhana dan efektif untuk masalah dunia nyata yang melibatkan struktur siklik. Dalam contoh di atas, permintaannya untuk mendeteksi penipuan perbankan menyiratkan bahwa itu dapat berguna dalam kasus penggunaan lainnya. Algoritma ini dapat diintegrasikan ke dalam sistem pada tingkat yang berbeda untuk meningkatkan integritas dan efisiensi operasional karena kesederhanaan dan efisiensinya.

Contoh kode di atas hadir di Repositori GitHub.

Rincian lebih lanjut tentang algoritma di atas dapat ditemukan di Geeksforgeeks. ITU Sanfoundry menunjukkan integrasi algoritma deteksi siklus Floyd ke dalam aplikasi Java.