konsep dasar algoritma greedy

 Konsep dasar algoritma Greedy

Algoritma greedy adalah jenis algoritma yang memilih langkah terbaik secara lokal pada setiap
langkahnya, dengan harapan akan mencapai solusi yang optimal secara global. Algoritma ini
memilih opsi terbaik berdasarkan kondisi saat ini tanpa mempertimbangkan konsekuensi jangka
panjang. Pada setiap langkah, algoritma greedy hanya mempertimbangkan informasi yang tersedia
saat ini, tanpa melihat ke belakang atau melihat langkah-langkah selanjutnya.
Konsep dasar algoritma greedy melibatkan tiga elemen utama: pilihan lokal terbaik, sifat greedy,
dan optimasi global.

berikut implementasi algoritma greedy di dalam bahasa C

1.
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int index;
    int waktuMulai;
    int waktuSelesai;
    int bobot;
} Tugas;

void tukar(Tugas *a, Tugas *b) {
    Tugas temp = *a;
    *a = *b;
    *b = temp;
}

void urutBerdasarkanWaktuSelesai(Tugas tugas[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (tugas[j].waktuSelesai > tugas[j + 1].waktuSelesai) {
                tukar(&tugas[j], &tugas[j + 1]);
            }
        }
    }
}

void jadwalkanTugas(Tugas tugas[], int n) {
    urutBerdasarkanWaktuSelesai(tugas, n);

    int *terpilih = (int *)malloc(n * sizeof(int));
    int jumlahTerpilih = 0;

    terpilih[jumlahTerpilih++] = tugas[0].index;

    int terpilihTerakhir = 0;

    for (int i = 1; i < n; i++) {
        if (tugas[i].waktuMulai >= tugas[terpilihTerakhir].waktuSelesai) {
            terpilih[jumlahTerpilih++] = tugas[i].index;
            terpilihTerakhir = i;
        }
    }

    printf("Urutan Pelaksanaan Tugas untuk Keuntungan Maksimum:\n");
    for (int i = 0; i < jumlahTerpilih; i++) {
        printf("Tugas %d (Waktu Mulai: %d, Waktu Selesai: %d, Bobot: %d)\n",
               tugas[terpilih[i]].index + 1, tugas[terpilih[i]].waktuMulai,
               tugas[terpilih[i]].waktuSelesai, tugas[terpilih[i]].bobot);
    }

    free(terpilih);
}

int main() {
    int n;

    printf("Masukkan jumlah tugas: ");
    scanf("%d", &n);

    Tugas *tugas = (Tugas *)malloc(n * sizeof(Tugas));

    printf("Masukkan waktu mulai, waktu selesai, dan bobot untuk setiap tugas:\n");
    for (int i = 0; i < n; i++) {
        tugas[i].index = i;
        printf("Tugas %d: ", i + 1);
        scanf("%d %d %d", &tugas[i].waktuMulai, &tugas[i].waktuSelesai, &tugas[i].bobot);
    }

    jadwalkanTugas(tugas, n);

    free(tugas);

    return 0;
}

output :



Program ini meminta pengguna untuk memasukkan jumlah tugas, waktu mulai, waktu selesai, dan bobot untuk setiap tugas. Kemudian, program akan menjadwalkan tugas-tugas tersebut untuk memaksimalkan keuntungan total menggunakan algoritma Greedy Activity Selection.

Semoga program ini membantu dan memberikan pemahaman mengenai implementasi algoritma greedy untuk masalah penjadwalan tugas.

Berikut adalah penjelasan mengenai implementasi program dalam bahasa C untuk menjadwalkan tugas-tugas dengan algoritma greedy:

  1. Struktur Data Tugas (Tugas):

    • Struktur ini digunakan untuk merepresentasikan setiap tugas dengan empat atribut: index (nomor urutan), waktuMulai, waktuSelesai, dan bobot (keuntungan).

  2. Fungsi Tukar (tukar):

    • Fungsi ini digunakan untuk menukar dua elemen dari tipe data Tugas. Fungsi ini membantu dalam pengurutan elemen tugas berdasarkan waktu selesai.

  3. Fungsi Urut Berdasarkan Waktu Selesai (urutBerdasarkanWaktuSelesai):

    • Fungsi ini mengurutkan array tugas berdasarkan waktu selesai secara ascending menggunakan algoritma Bubble Sort.

  4. Fungsi Jadwalkan Tugas (jadwalkanTugas):

    • Fungsi utama yang menerima array tugas (tugas) dan jumlah tugas (n).
    • Fungsi ini memanggil urutBerdasarkanWaktuSelesai untuk mengurutkan tugas berdasarkan waktu selesai.
    • Selanjutnya, fungsi menggunakan algoritma Greedy Activity Selection untuk memilih tugas-tugas yang akan dijadwalkan.
    • Hasilnya, fungsi mencetak urutan pelaksanaan tugas beserta waktu mulai, waktu selesai, dan bobotnya untuk keuntungan maksimum.

  5. Fungsi main:

    • Di dalam fungsi utama (main), pengguna diminta untuk memasukkan jumlah tugas, waktu mulai, waktu selesai, dan bobot untuk setiap tugas.
    • Program memanggil fungsi jadwalkanTugas untuk menyelesaikan masalah penjadwalan tugas dan mencetak hasilnya.

  6. Dealokasi Memori:

    • Terdapat penggunaan malloc untuk alokasi memori dinamis untuk array tugas (Tugas). Setelah selesai, memori tersebut di-dealokasi menggunakan free.

Program ini menggunakan algoritma Greedy Activity Selection untuk memilih tugas-tugas yang memberikan keuntungan maksimum dengan memperhatikan waktu selesai. Semoga penjelasan ini membantu Anda memahami implementasi algoritma greedy dalam konteks penjadwalan tugas.




2.
#include <stdio.h>
#include <stdlib.h>

#define MAX_VARIABLES 10

void gaussElimination(double matriks[MAX_VARIABLES][MAX_VARIABLES + 1], int n) {
    for (int i = 0; i < n; i++) {
        // Membuat elemen diagonal menjadi 1
        double pivot = matriks[i][i];
        for (int j = i; j <= n; j++) {
            matriks[i][j] /= pivot;
        }

        // Menghilangkan elemen di bawah diagonal menjadi 0
        for (int k = 0; k < n; k++) {
            if (k != i) {
                double factor = matriks[k][i];
                for (int j = i; j <= n; j++) {
                    matriks[k][j] -= factor * matriks[i][j];
                }
            }
        }
    }
}

int main() {
    int n; // Jumlah persamaan
    printf("Masukkan jumlah persamaan: ");
    scanf("%d", &n);

    double matriks[MAX_VARIABLES][MAX_VARIABLES + 1];

    printf("Masukkan koefisien variabel dan hasil untuk setiap persamaan:\n");
    for (int i = 0; i < n; i++) {
        printf("Persamaan %d: ", i + 1);
        for (int j = 0; j <= n; j++) {
            scanf("%lf", &matriks[i][j]);
        }
    }

    gaussElimination(matriks, n);

    printf("Solusi variabel:\n");
    for (int i = 0; i < n; i++) {
        printf("Variabel %d: %.2f\n", i + 1, matriks[i][n]);
    }

    return 0;
}
output : 


Program ini meminta pengguna untuk memasukkan jumlah persamaan, kemudian memasukkan koefisien variabel dan hasil untuk setiap persamaan. Setelah itu, program menggunakan algoritma eliminasi Gauss untuk menemukan solusi variabel yang memenuhi persamaan-persamaan tersebut.

Program ini menggunakan algoritma eliminasi Gauss untuk menyelesaikan sistem persamaan linear. Berikut adalah penjelasan singkat mengenai bagian-bagian kunci dari program:

  1. Fungsi gaussElimination:

    • Fungsi ini menerapkan algoritma eliminasi Gauss untuk mentransformasi matriks augmented menjadi bentuk segitiga atas dan kemudian membuat elemen diagonal menjadi 1.
    • Langkah-langkahnya mencakup membagi setiap elemen baris saat ini dengan elemen diagonalnya, dan mengurangkan baris lain dengan faktor yang sesuai untuk menghilangkan elemen di bawah diagonal.

  2. Fungsi main:

    • Di dalam fungsi utama (main), pengguna diminta untuk memasukkan jumlah persamaan.
    • Setelah itu, program meminta pengguna untuk memasukkan koefisien variabel dan hasil untuk setiap persamaan.
    • Program kemudian memanggil fungsi gaussElimination untuk menyelesaikan sistem persamaan linear.
    • Setelah eliminasi Gauss selesai, program mencetak solusi variabel yang memenuhi persamaan-persamaan.

  3. Variabel matriks:

    • Variabel ini digunakan untuk menyimpan matriks augmented yang terdiri dari koefisien variabel dan hasil dari setiap persamaan.

  4. Loop dan Perhitungan:

    • Terdapat loop untuk melakukan iterasi melalui setiap baris matriks dan mengaplikasikan langkah-langkah eliminasi Gauss.
    • Solusi variabel akhirnya dicetak setelah eliminasi Gauss selesai.

Program ini memberikan solusi variabel yang memenuhi sistem persamaan linear yang diberikan oleh pengguna. Semoga penjelasan ini membantu!

3.

#include <stdio.h>
#include <stdlib.h>

#define MAX_KOTA 10

int jarak[MAX_KOTA][MAX_KOTA];
int kota;
int kunjungan[MAX_KOTA];

int min(int a, int b) {
    return (a < b) ? a : b;
}

int tsp(int mask, int pos) {
    if (mask == (1 << kota) - 1) {
        // Semua kota telah dikunjungi
        return jarak[pos][0]; // Kembali ke kota awal
    }

    if (kunjungan[mask] != -1) {
        // Hasil sudah pernah dihitung sebelumnya
        return kunjungan[mask];
    }

    int hasil = __INT_MAX__;

    // Coba kunjungi setiap kota yang belum dikunjungi
    for (int next = 0; next < kota; next++) {
        if (!(mask & (1 << next))) {
            hasil = min(hasil, jarak[pos][next] + tsp(mask | (1 << next), next));
        }
    }

    return kunjungan[mask] = hasil;
}

void cariRuteTerpendek() {
    for (int i = 0; i < kota; i++) {
        for (int j = 0; j < kota; j++) {
            printf("Masukkan jarak dari Kota %d ke Kota %d: ", i + 1, j + 1);
            scanf("%d", &jarak[i][j]);
        }
    }

    // Inisialisasi array kunjungan
    for (int i = 0; i < (1 << kota); i++) {
        kunjungan[i] = -1;
    }

    int ruteTerpendek = tsp(1, 0); // Dimulai dari kota 0
    printf("Jarak Rute Terpendek: %d\n", ruteTerpendek);
}

int main() {
    printf("Masukkan jumlah kota: ");
    scanf("%d", &kota);

    cariRuteTerpendek();

    return 0;
}
output :


Program ini meminta pengguna untuk memasukkan jarak antar kota dan kemudian mencari rute perjalanan terpendek menggunakan algoritma TSP (Traveling Salesman Problem). Program ini menggunakan pendekatan rekursif dengan memoisasi untuk menghindari perhitungan berulang. Setelah semua jarak dimasukkan, program akan menampilkan jarak rute terpendek yang melintasi semua kota sekali dan kembali ke kota awal.

Program ini adalah implementasi algoritma Traveling Salesman Problem (TSP) dengan menggunakan pendekatan rekursif dan memoisasi (dynamic programming) untuk menghindari perhitungan berulang. Berikut adalah penjelasan singkat tentang program tersebut:

  1. Fungsi tsp:

    • Fungsi ini menerima dua parameter: mask (bitmask yang merepresentasikan kota yang telah dikunjungi) dan pos (kota saat ini).
    • Jika semua kota telah dikunjungi, fungsi mengembalikan jarak dari pos ke kota awal.
    • Jika hasil sudah pernah dihitung sebelumnya, fungsi langsung mengembalikan nilai tersebut.
    • Fungsi mencoba kunjungi setiap kota yang belum dikunjungi, dan memilih kota dengan jarak terpendek.

  2. Fungsi cariRuteTerpendek:

    • Fungsi ini meminta pengguna untuk memasukkan jarak antar kota dan inisialisasi array kunjungan.
    • Memanggil fungsi tsp untuk mencari rute perjalanan terpendek, dimulai dari kota 0.
    • Menampilkan jarak rute terpendek.

  3. Variabel dan Konstanta:

    • jarak: Matriks yang menyimpan jarak antar kota.
    • kota: Jumlah kota.
    • kunjungan: Array untuk memoisasi hasil perhitungan.

  4. Pemanggilan Fungsi di main:

    • Meminta pengguna untuk memasukkan jumlah kota.
    • Memanggil fungsi cariRuteTerpendek.

Program ini menggunakan pendekatan rekursif dengan memoisasi untuk mencari solusi optimal dari TSP. Dengan cara ini, program menghindari perhitungan berulang dan meningkatkan efisiensi. Semoga penjelasan ini membantu memahami program Traveling Salesman Problem dalam bahasa C.





















Comments

Post a Comment

Popular posts from this blog

If, If-else, For Loop, While Loop, Do-While Loop dengan Bahasa C

Image
If, If-else, For Loop, While Loop, Do-While Loop dengan Bahasa C daftar isi : 1. pengertian struktur kontrol 2. If Statment 3. If-Else Statment 4. For Loop 5. While Loop 6. Do-While Loop 1. Pngertian Struktur Kontrol Di dalam pemrograman ada istilah yang di sebut struktur kontrol, apa itu struktur kontrol?. Struktur kontrol di dalam bahasa pemrograman adalah  perintah dengan bentuk (struktur) tertentu yang digunakan untuk mengatur (mengontrol) jalannya program . kali ini kita akan mempraktekan apa itu struktur kontrol 2. If Statment Pemilihan if digunakan untuk menjalankan suatu blok kode jika kondisi tertentu terpenuhi. Jika kondisi evaluasi bernilai benar (true), blok kode di dalam if akan dieksekusi. Jika kondisi evaluasi bernilai salah (false), blok kode di dalam if akan dilewati. kita akan membuat sebuah Flowchart, Pseudocode, dan Code Program dari If Statmnet Flowchart Pseudocode Suruh User memasukan nilai     jika nilai di bagi 2 = 0        ...
Read more

konsep dasar algoritma graf

Image
Algoritma graf dalam bahasa C Algoritma graf adalah algoritma yang digunakan untuk memproses dan memanipulasi struktur data graf. Graf adalah kumpulan simpul (node) yang terhubung oleh sisi (edge). Algoritma graf berfungsi untuk menemukan jalur, menghitung jarak terpendek, mencari lintasan tertentu, atau melakukan operasi lainnya pada struktur data graf. Dalam bahasa C, beberapa algoritma graf populer melibatkan struktur data graf berarah dan tidak berarah. Berikut adalah beberapa algoritma graf umum yang dapat diimplementasikan dalam bahasa C: 1. **Depth-First Search (DFS):**    - DFS digunakan untuk menjelajahi atau mencari jalur dalam graf.    - Pada setiap simpul, DFS akan menelusuri sepanjang satu cabang hingga mencapai simpul leaf sebelum kembali dan menjelajahi cabang lain. 2. **Breadth-First Search (BFS):**    - BFS digunakan untuk menjelajahi atau mencari jalur dalam graf.    - Pada setiap level dari graf, BFS akan menelusuri semua simpul...
Read more