Jarak Topologis vs Jarak Geometris: Contoh Penerapan Formulasi Matematika Komputasional dalam Usaha Penyelesaian Permasalahan Sehari-hari

Saya sempat menulis sebuah draft yang idenya sama persis dengan postingan ini, tapi waktu itu saya terlalu elitis dengan membuatnya penuh simbol-simbol Matematika, memanfaatkan kode-kode Latex plus bahasa yang formal. Alhasil, ngetiknya jadi lama dan saya jadi malas menyelesaikannya. Pun itu orang juga belum tentu paham, jadi usahanya sia-sia. Makanya, ide itu saya tulis ulang di sini dengan istilah Matematika sehari-hari.

Katakan kita punya himpunan semesta S. Terus, kita terapkan algoritma clustering berdasarkan jarak geometris untuk mengelompokkan anggota-anggota S menjadi kelompok-kelompok yang anggotanya saling berdekatan…ya secara geometris. Maksudnya di sini adalah anggota-anggota yang secara fisik dekat. Mari kita namakan kelompok-kelompok ini menjadi G1, G2, dan seterusnya. Untuk saat ini, asumsinya mereka tidak saling tumpang tindih. Dengan kata lain, sebuah elemen hanya bisa masuk ke dalam sebuah kelompok macam ini. Kemudian, kita terapkan lagi algoritma clustering ke S, tapi kali ini berbeda, berdasarkan jarak topologis, untuk mengelompokkan anggota-anggota S berdasarkan kedekatannya secara topologis. Sepasang elemen unik dibilang dekat secara topologis jika dan hanya jika perjalanan antara kedua elemen tersebut termasuk mudah. Cluster-cluster hasil algoritma ini kita namakan T1, T2, dan seterusnya. Kita masih memakai asumsi ketidak-tumpang-tindihan yang serupa antar grup sejenis dengan sebelumnya. Sebagai catatan, mengukur jarak topologis kita anggap lebih sulit,  kompleks, dan lama daripada mengukur jarak geometris. Cuma, kesulitan pengukuran jarak topologis akan berkurang jika kita tahu bahwa jarak geometris sepasang elemen dekat. Oleh karena itu, biasanya orang mengukur jarak geometris dulu sebelum menghitung jarak topologis.

Sampai sini, apakah sudah bingung?

Biar mudah, saya beri ilustrasi. Letakkan dua butir kelereng di tanah lapang dengan jarak 1 meter. Jarak geometris = 1 meter, jarak topologis = 1 meter. Nah, sekarang pindahkan kelereng-kelereng itu ke dalam dua buah ruangan yang bersebelahan. Satu kelereng di satu kamar, dan kelereng lainnya di kamar lainnya. Jaraknya masih satu meter. Tapi perjalanan antar kelereng itu menjadi lebih jauh, bukan? Dalam kasus ini, jarak topologisnya menjadi lebih dari satu meter. Kira-kira seperti itu.

Apakah sudah paham?

Kembali ke topik utama. Eh tunggu dulu. Mari memperumit kondisi awalnya dulu. Masih menggunakan asumsi ketidak-tumpang-tindihan, kita izinkan grup-grup itu, baik yang grup geometris maupun topologis, untuk berubah seiring berjalannya waktu. Dengan kata lain, grup-grup ini bersifat dinamis. Dengan begini, ukuran tiap grup bisa berubah, membesar ataupun mengecil, dan kita bisa memasukkan/mengeluarkan sebuah anggota S ke/dari grup topologis maupun geometris. Perbedaannya, memperbesar ukuran grup tidak mudah dan membutuhkan waktu yang lama, tapi memperkecilnya dengan membuang beberapa elemen di grup lebih gampang. Malah, kalau dibiarkan begitu saja, jumlah anggota grup bisa berkurang sendiri.

Satu lagi sebelum penjelasan masalah. Untuk sepasang elemen unik s dan t di S, kita definisikan sebuah fungsi kedekatan f(s, t) yang memberikan penjumlahan berbobot dari jarak topologis dan jarak geometris antara s dan t. Kalau mau dipaksa nulis matematis, ya…misalkan g(s,t) dan h(s,t) berturut-turut mengembalikan jarak geometris dan topologis antara s dan t,

f(s,t) = a \times g(s,t)^i + b \times h(s,t)^j

dengan a, b, i, k semua positif.

*fyuh*

Saya belum tahu nilai variabel-variabel ini, maka ini saya jadikan future work™. Persamaan ini pun asal-asalan, baru dibikin waktu nulis ini.

Pada titik ini, kita tahu kondisi awalnya seperti apa. Sekarang tugas utamanya adalah menyelesaikan permasalahan optimisasi berikut ini. Diketahui sebuah elemen s anggota sebuah grup geometris (katakan) G1 dan sebuah grup topologis (katakan) T1. Ukuran T1 kecil bila dibandingkan dengan S, anggap saja kurang dari 20%-nya. Untuk mempermudah permasalahan, mari asumsikan bahwa s tidak berpindah grup. Tugas no 1 nya adalah, dengan waktu yang terbatas, carilah t anggota S yang nilai f(s, t)-nya lebih kecil dari suatu nilai threshold, dengan syarat bahwa dengan kondisi awal apapun, pada saat penentuan jawaban, t harus ada di dalam G1 dan T1. Perumusan ini lebih mudah daripada mencari t yang memaksimalkan f(s,t), yang bakalan lebih lama lagi, tapi sebenarnya sudah cukup untuk menyelesaikan masalah.

Persoalan ini menantang, karena alasan-alasan berikut.

  1. Adalah tidak mudah untuk memperbesar grup. Walaupun grup geometris lebih mudah diperbesar daripada grup topologi, tetap saja itu sulit. Menjaga agar grup geometris tetap besar pun juga tantangan tersendiri, karena kita musti pintar mengalokasikan sumber daya dengan pengukuran jarak topologis.
  2. Ukuran T1 kecil, dan karena itu, kemungkinan bahwa suatu elemen tidak termasuk dalam T1 sangatlah besar. Ini menambah kompleksitas problem yang kita ingin selesaikan.

Solusi saya sejauh ini macam begini.

  1. Perluas G1. Masukkan sebanyak-banyaknya elemen ke dalam G1, tapi tetap jaga supaya jumlah anggota G1 tidak berkurang.
  2. Cek jarak topologis setiap anggota G1 dengan s. Anggota-anggota G1 yang sudah pernah dihitung jaraknya juga tetap dihitung, karena bisa jadi jarak topologis pada saat itu menjadi sangat dekat.
  3. Jika menemukan kandidat jawaban yang nilainya langsung di bawah threshold, atau dengan kata lain dia juga berada di T1, langsung kembalikan itu.
  4. Ulangi dari 1 sampai waktu habis.

Kekurangan pendekatan ini, tentunya, adalah di langkah 2, ketika kita musti ngecek satu per satu anggota di dalam G1. Selain itu, bisa jadi sampai waktu habis kita tidak punya hasil apa-apa. Maka dari itu, apakah ada pembaca yang punya pendekatan yang lebih baik?

Penutup. Lah sampeyan bilang ini untuk permasalahan sehari-hari. Memangnya permasalahan macam apa sih yang sebenarnya ingin diselesaikan?

Itu PR nomor 2.

6 Responses to “Jarak Topologis vs Jarak Geometris: Contoh Penerapan Formulasi Matematika Komputasional dalam Usaha Penyelesaian Permasalahan Sehari-hari”


  1. 1 jensen99 24/12/2011 at 11:52 AM

    Maka dari itu, apakah ada pembaca yang punya pendekatan yang lebih baik?

    Kalo tidak ada permasalahan sehari-hari atau seabad sekali, ya ndak ada pendekatan…😐

  2. 2 lambrtz 24/12/2011 at 12:25 PM

    Ya makanya kriptik. Tag-nya aja begitu.:mrgreen:
    Mungkin kapan-kapan saya tulis permasalahan sebenarnya. Eh, mungkin(tm).

  3. 3 Pak Guru 25/12/2011 at 1:53 PM

    Kalimat penutup yang luar biasa.😆

  4. 4 sora9n 25/12/2011 at 9:30 PM

    Balada lagi mau ngisi liburan natal-tahun baru, tapi bingung mau ke mana, naik apa dan lewat mana.😛

    /my best guess

    Kekurangan pendekatan ini, tentunya, adalah di langkah 2, ketika kita musti ngecek satu per satu anggota di dalam G1. Selain itu, bisa jadi sampai waktu habis kita tidak punya hasil apa-apa. Maka dari itu, apakah ada pembaca yang punya pendekatan yang lebih baik?

    Saya ga tahu apa saya nangkep detail teknisnya benar, sih, tapi metode yg terlintas di benak…

    Kalau f(s, t) penjumlahan linier, dan nilai g(s,t) & h(s,t) selalu positif… di-brute force saja dengan g(s,t) & h(s,t) dari nol menuju besar. Selalu kembalikan hasil hingga nilai f(s,t) > threshold — stop. Dapat deh.😛

    (note: saya berasumsi jarak geometris diambil mutlak e.g. “4 meter”, jadi ga ada +/- menunjukkan arah. kurang yakin dgn jarak topologis — tapi saya anggap bisa dibegitukan juga. kalau meleset, ya, mohon maaf gagal membantu.:mrgreen: )

  5. 5 sora9n 25/12/2011 at 9:52 PM

    Nambah: Metode di atas juga berfungsi membatasi jumlah anggota G1 maupun T1. Sebab secara trivial, kita cuma mengecek nilai di mana 0 &lt= G1 <= threshold ; 0 &lt= T1 &;lt;= threshold.

    Jadi di sini kita punya constraint dalam memasukkan G1 (baca: ga mesti “input sebanyak-banyaknya”). Selanjutnya analisis topologi dilakukan ke semua anggota G1.

    (masih bertanya-tanya apa asumsi saya benar)
    (oh well, anggap saja tebar opini di hari raya😛 )

  6. 6 lambrtz 30/12/2011 at 1:25 AM

    BTW update, kayanya kita bisa kasih waktu, misalnya kalo waktu saat ini udah mendekati waktu yang diberikan, kembalikan hasilnya, apapun itu.😕

    @Pak Guru
    Walah, masa sih😆

    @sora9n
    It takes me some time to understand your comment @_@

    Asumsi situ bener, ndak pake arah. Kedua jarak murni skalar, real non-negatif. Tapi…

    di-brute force saja dengan g(s,t) & h(s,t) dari nol menuju besar

    ya itu sama dengan yang saya maksud toh. Brute force ngecek satu-satu. Cuman ini sayangnya variabel-variabelnya ndak bisa mudah diurutkan. Wong mengetahui jarak aja susah, apalagi mengurutkan.😕

    Makasih sora9n😀


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




lambrtz looks like this

Me

You can write comments in any language that you want, but please bear in mind that I only understand 4 languages: English, Indonesian, Javanese and Malay.

Archives

Categories

December 2011
S M T W T F S
« Nov   Jan »
 123
45678910
11121314151617
18192021222324
25262728293031
Click to view my Personality Profile page