Kombinatorial Masalah Optimasi
optimasi kombinatorial adalah cabang dari optimasi. domainnya adalah masalah optimasi di mana set solusi layak adalah diskrit atau dapat dikurangi menjadi satu diskrit, dan tujuannya adalah untuk menemukan solusi terbaik.
Untuk menangani masalah optimasi kombinatorial, tujuannya adalah untuk menemukan solusi terbaik atau solusi optimal, salah satu yang meminimalkan fungsi biaya diberikan.
Ada beberapa teknik untuk memecahkan tidak masalah yang kompleks, seperti Branch and Bound atau Cabang dan Cut. Sebagai kompleksitas ruang pencarian tumbuh, biaya algoritma yang dapat meningkatkan secara eksponensial, membuat pencarian solusi tidak layak.
Cara lain untuk mengatasi masalah ini adalah untuk menemukan solusi suboptimal tetapi dalam waktu yang wajar. Dalam beberapa kasus, Anda mungkin menemukan solusi optimal untuk masalah ini.
Teknik-teknik tersebut dapat dibagi menjadi dua kelompok utama:
- Heuristik
- Metaheuristik
Sebuah teknologi baru dapat digunakan untuk memecahkan masalah optimasi kombinatorial disebut Case Based Reasoging (CBR), di samping kelompok-kelompok ini.
Heuristik
Dapat menemukan solusi yang baik untuk masalah kombinatorial yang kompleks dengan memanfaatkan pengetahuan dari domain aplikasi. algoritma heuristik mudah untuk menerapkan dan menemukan solusi yang baik dengan upaya komputasi yang relatif kecil, namun, mengundurkan diri (dari sudut pandang teoritis) untuk menemukan solusi optimum global dari masalah. Dalam masalah besar jarang algoritma heuristik menemukan solusi terbaik.
Metaheuristik
algoritma metaheuristik algoritma tujuan umum, yang tidak tergantung pada masalah dan menawarkan hasil yang baik tetapi biasanya tidak "solusi terbaik". Biasanya digunakan untuk masalah tanpa algoritma atau heuristik solver tertentu, atau jika tidak berguna untuk menerapkan metode ini.
Kombinatorial adalah topik yang terdiri dari menemukan sebuah objek yang optimal dari sebuah himpunan berhingga obyek. Dalam banyak masalah seperti, pencarian lengkap tidak layak. Beberapa masalah umum yang melibatkan optimasi kombinatorial adalah masalah salesman keliling ( "TSP") dan spanning minimum masalah pohon ( "MST").
optimasi kombinatorial adalah bagian dari optimasi matematika yang berhubungan dengan riset operasi, teori algoritma, dan teori kompleksitas komputasi. Ini memiliki aplikasi penting di beberapa bidang, termasuk kecerdasan buatan, pembelajaran mesin, matematika, teori lelang, dan rekayasa perangkat lunak.
https://en.wikipedia.org/wiki/Combinatorial_optimization
Lookahead merupakan komponen penting dari pencarian kombinasi, yang menentukan, kira-kira, seberapa dalam grafik yang mewakili masalah dieksplorasi. Kebutuhan batas tertentu pada lookahead berasal dari grafik masalah besar di banyak aplikasi, seperti catur komputer dan komputer Go. Sebuah pencarian luas-pertama naif grafik ini akan cepat mengkonsumsi semua memori dari setiap komputer modern. Dengan menetapkan batas lookahead tertentu, waktu algoritma dapat dikontrol secara teliti; waktu meningkat secara eksponensial sebagai batas lookahead meningkat.
teknik pencarian yang lebih canggih seperti alpha-beta pruning mampu menghilangkan seluruh sub pohon dari pohon pencarian dari pertimbangan. Ketika teknik ini digunakan, lookahead bukan kuantitas tepat didefinisikan, melainkan baik kedalaman maksimum mencari atau beberapa jenis rata-rata.
https://en.wikipedia.org/wiki/Combinatorial_search
Kombinasi adalah cabang matematika tentang studi struktur diskrit terbatas atau bisa dihitung. Aspek kombinatorika termasuk menghitung struktur dari jenis dan ukuran (enumerative kombinatorika) diberikan, memutuskan kapan kriteria tertentu dapat dipenuhi, dan membangun dan menganalisis objek memenuhi kriteria (seperti dalam desain kombinasi dan teori matroid), menemukan "terbesar", " terkecil ", atau" optimal "benda (kombinatorik extremal dan optimasi kombinatorial), dan mempelajari struktur kombinasi yang timbul dalam konteks aljabar, atau menerapkan teknik aljabar untuk masalah kombinasi (aljabar kombinatorik).
masalah kombinatorial muncul dalam banyak bidang matematika murni, terutama dalam aljabar, teori probabilitas, topologi, dan geometri, Banyak pertanyaan kombinasi historis telah dipertimbangkan dalam isolasi, memberikan solusi ad hoc untuk masalah yang timbul dalam beberapa konteks matematika.
Jenis-jenis Kombinatorika :
Kombinatorika enumerative
Kombinatorika enumerative adalah daerah yang paling klasik dari kombinatorika dan berkonsentrasi pada menghitung jumlah objek kombinatorial tertentu. Meskipun menghitung jumlah elemen dalam himpunan adalah masalah matematika yang agak luas, banyak masalah yang timbul dalam aplikasi memiliki deskripsi kombinatorial yang relatif sederhana.
Kombinatorika analitik
Kombinatorika analitik menyangkut penghitungan struktur kombinasi menggunakan alat dari analisis kompleks dan teori probabilitas. Berbeda dengan kombinatorika enumerative, yang menggunakan rumus kombinasi eksplisit dan fungsi menghasilkan untuk menggambarkan hasil, kombinatorika analitik bertujuan memperoleh rumus asimtotik.
Partisi pesawat.
Studi teori partisi berbagai pencacahan dan masalah asymptotic terkait dengan partisi integer, dan berkaitan erat dengan q-seri, fungsi khusus dan polinomial orthogonal. Awalnya bagian dari nomor teori dan analisis, sekarang dianggap sebagai bagian dari kombinatorika atau bidang yang independen. Menggabungkan pendekatan bijective dan berbagai alat dalam analisis dan analisis nomor teori, dan memiliki koneksi dengan mekanika statistik.
Grafik teori
Grafik adalah objek dasar dalam kombinatorika. Pertanyaan berkisar dari menghitung (misalnya, jumlah grafik pada n simpul dengan tepi k) ke struktural (misalnya, yang grafik berisi siklus Hamiltonian) ke algebraic pertanyaan (misalnya, diberikan grafik G dan dua nomor x dan y, tidak Tutte yang polinomial TG (x, y) memiliki interpretasi kombinatorial?). Perlu dicatat bahwa sementara ada koneksi yang sangat kuat antara teori graf dan kombinatorika, kedua kadang-kadang dianggap sebagai subjek yang terpisah.
Desain teori
Teori desain adalah studi desain kombinasi, yang merupakan kumpulan dari himpunan bagian dengan sifat persimpangan tertentu. Blok desain adalah desain kombinasi dari tipe khusus. Daerah ini merupakan salah satu bagian tertua dari kombinatorika, seperti di masalah sekolahan Kirkman yang diusulkan pada tahun 1850. Solusi dari masalah adalah kasus khusus dari sistem Steiner, yang sistem memainkan peran penting dalam klasifikasi sederhana kelompok terbatas. Daerah ini memiliki koneksi lebih lanjut untuk coding teori dan kombinatorik geometris.
Hingga geometri
Geometri terbatas adalah studi tentang sistem geometrik hanya memiliki jumlah terbatas poin. Struktur analog dengan yang ditemukan dalam geometri terus menerus (Euclidean pesawat, ruang proyektif nyata, dll) tapi didefinisikan combinatorially adalah item utama dipelajari. Daerah ini menyediakan sumber yang kaya contoh untuk teori desain. Seharusnya tidak bingung dengan geometri diskrit (kombinasi geometri).
Teori rangka
Teori order adalah studi tentang set sebagian memerintahkan, baik terbatas dan tidak terbatas. Berbagai contoh perintah parsial muncul dalam aljabar, geometri, nomor teori dan seluruh kombinatorika dan teori graf. kelas terkemuka dan contoh perintah parsial termasuk kisi dan aljabar Boolean.
Teori Matroid
Teori Matroid abstrak bagian dari geometri. Ini mempelajari sifat-sifat set (biasanya, set terbatas) dari vektor-vektor pada ruang vektor yang tidak bergantung pada koefisien tertentu dalam ketergantungan hubungan linear. Tidak hanya struktur tetapi juga sifat enumerative milik matroid teori. Teori Matroid diperkenalkan oleh Hassler Whitney dan dipelajari sebagai bagian dari teori order. Sekarang bidang independen studi dengan jumlah koneksi dengan bagian lain dari kombinatorika.
Kombinatorika Extremal
Kombinatorika Extremal studi extremal pertanyaan pada sistem set. Jenis-jenis pertanyaan yang ditujukan dalam hal ini adalah tentang grafik kemungkinan terbesar yang memenuhi sifat tertentu. Misalnya, grafik segitiga bebas terbesar di simpul 2n adalah graf bipartit lengkap Kn, n. Sering terlalu sulit bahkan untuk menemukan extremal jawaban f (n) tepat dan satu hanya dapat memberikan perkiraan asimtotik.
Kombinatorika probabilistik
Dalam metode probabilistik juga digunakan untuk menentukan keberadaan objek kombinatorial dengan sifat yang ditentukan tertentu (yang contoh eksplisit mungkin sulit untuk menemukan), hanya dengan mengamati bahwa probabilitas secara acak memilih objek dengan properti-properti lebih besar dari 0. Pendekatan ini ( sering disebut sebagai metode probabilistik) terbukti sangat efektif dalam aplikasi untuk extremal kombinatorika dan teori graf.
Kombinatorika aljabar
Kombinatorika aljabar adalah bidang matematika yang menggunakan metode aljabar abstrak, terutama teori grup dan teori representasi, dalam berbagai konteks kombinasi dan, sebaliknya, berlaku teknik kombinasi untuk masalah dalam aljabar. kombinatorika aljabar terus memperluas jangkauannya, baik topik dan teknik, dan dapat dilihat sebagai bidang matematika di mana interaksi metode kombinatorial dan aljabar sangat kuat dan signifikan.
Kombinasi kata-kata
Kombinasi kata-kata berhubungan dengan bahasa formal. Ini muncul secara independen dalam beberapa cabang matematika, termasuk nomor teori, teori grup dan probabilitas. Ini memiliki aplikasi untuk kombinatorika enumerative, analisis fractal, ilmu komputer teoritis, teori automata dan linguistik
Kombinatorika geometris
Kombinatorika geometris berhubungan dengan cembung dan geometri diskrit, di kombinatorika polyhedral tertentu. Ia meminta, misalnya, berapa banyak wajah masing-masing dimensi sebuah polytope cembung dapat memiliki. sifat metrik polytopes memainkan peran penting juga, misalnya Teorema Cauchy pada kekakuan polytopes cembung.
Kombinatorika opological
Analog kombinasi dari konsep dan metode dalam topologi digunakan untuk mempelajari pewarnaan graf, divisi adil, partisi, set sebagian memerintahkan, pohon keputusan, masalah kalung dan teori Morse diskrit. Seharusnya tidak bingung dengan kombinasi topologi yang merupakan nama yang lebih tua untuk algebraic topology.
Kombinatorika aritmatika
Kombinatorika aritmatika muncul dari interaksi antara teori bilangan, kombinatorika, teori ergodic dan analisis harmonik. Ini adalah tentang perkiraan kombinatorial terkait dengan operasi aritmatika (penjumlahan, pengurangan, perkalian, dan pembagian). Kombinatorika aditif mengacu pada kasus khusus ketika hanya operasi penjumlahan dan pengurangan yang terlibat. Salah satu teknik penting dalam aritmatika kombinatorika adalah teori ergodic sistem dinamis.
Kombinatorika infinitary
Kombinatorika infinitary, atau teori set kombinasi, adalah perluasan dari ide-ide dalam kombinatorika untuk set terbatas. Ini adalah bagian dari teori himpunan, daerah logika matematika, tetapi menggunakan alat dan ide-ide dari kedua teori set dan kombinatorika extremal.
https://en.wikipedia.org/wiki/Combinatorics
Tidak ada komentar:
Posting Komentar