Lima algoritma komputer klasik: 1. Bahagikan dan taklukkan kaedah, membahagikan masalah kompleks kepada dua atau lebih sub-masalah yang serupa atau serupa 2. Kaedah pengaturcaraan dinamik 3. Algoritma rakus; jenis kaedah carian optimum, mencari ke hadapan mengikut keadaan optimum untuk mencapai matlamat 5. Kaedah cawangan dan terikat.
Persekitaran pengendalian tutorial ini: sistem Windows 10, komputer Dell G3.
Saya akan mula menghantar resume untuk mencari internship Saya masih tidak tahu bagaimana untuk melakukan apa-apa, jadi saya sangat panik mulai hari ini, saya akan melakukan lebih daripada 2 leetcode setiap hari dan kemudian meringkaskannya, dan meringkaskan mata pengetahuan pelbagai soalan temu bual Semakan selalunya pada masa hadapan, semoga berjaya.
Semasa saya memberus leetcode, saya sering melihat orang bercakap tentang DP Kemudian saya pergi ke Baidu untuk mengetahui apa itu DP, dan kemudian saya menyedari bahawa DP ialah salah satu daripada lima algoritma klasik yang akan saya ringkaskan lima algoritma klasik.
Lima algoritma klasik dibahagikan kepada
1 Kaedah bahagi dan takluk: Bahagikan masalah kompleks kepada dua atau lebih yang serupa atau serupa sub-masalah, dan kemudian bahagikan sub-masalah kepada sub-masalah yang lebih kecil... sehingga akhirnya sub-masalah dapat diselesaikan secara mudah dan langsung, dan penyelesaian kepada masalah asal ialah penggabungan penyelesaian kepada sub-masalah. .
2. Kaedah pengaturcaraan dinamik: Setiap keputusan bergantung pada keadaan semasa dan serta-merta menyebabkan peralihan keadaan. Urutan keputusan dijana dalam keadaan berubah, jadi proses membuat keputusan pengoptimuman pelbagai peringkat ini untuk menyelesaikan masalah dipanggil pengaturcaraan dinamik.
3 Algoritma tamak: Semasa menyelesaikan masalah, sentiasa buat pilihan terbaik pada masa ini. Dalam erti kata lain, tanpa mengambil kira penyelesaian optimum keseluruhan, apa yang dibuatnya hanyalah penyelesaian optimum tempatan dalam erti kata tertentu. Algoritma tamak biasa termasuk: Algoritma Prim dan algoritma Kruskal (kedua-duanya mencari pokok rentang minimum).
Idea asas: menguraikan masalah kepada beberapa masalah kecil, secara beransur-ansur mendapatkan penyelesaian optimum setempat bagi setiap sub-masalah, dan akhirnya menggabungkannya ke dalam penyelesaian masalah asal.
4. Kaedah penjejakan belakang: Algoritma penjejakan belakang sebenarnya adalah proses percubaan carian yang serupa dengan penghitungan , ia "undur" dan kembali , cuba jalan lain. Depth first;
Kaedah backtracking ialah kaedah carian optimum yang mencari ke hadapan mengikut keadaan optimum untuk mencapai matlamat. Tetapi apabila anda mencapai langkah tertentu dalam penerokaan dan mendapati bahawa pilihan asal tidak optimum atau tidak dapat mencapai matlamat, anda akan mengambil langkah ke belakang dan membuat pilihan lain Teknik ini untuk kembali dan mencuba lagi apabila ia tidak berkesan ialah kaedah menjejak ke belakang, dan titik dalam keadaan tertentu yang memenuhi syarat menjejak ke belakang Dipanggil "titik pandang belakang".
5. Kaedah cawangan dan terikat: Sama seperti kaedah menjejak ke belakang, ia juga merupakan algoritma yang mencari penyelesaian kepada masalah pada pokok ruang penyelesaian masalah T. Walau bagaimanapun, secara amnya, matlamat penyelesaian kaedah cawangan dan terikat dan kaedah penjejakan belakang adalah berbeza. Matlamat penyelesaian kaedah backtracking adalah untuk mencari semua penyelesaian dalam T yang memenuhi syarat kekangan, manakala matlamat penyelesaian kaedah cawangan dan terikat adalah untuk mencari penyelesaian yang memenuhi syarat kekangan, atau untuk mencari penyelesaian yang memenuhi kekangan. syarat supaya objektif tertentu Nilai fungsi mencapai penyelesaian maksimum atau minimum, iaitu penyelesaian optimum dalam erti kata tertentu.
1. Kaedah Bahagi dan Takluk
Masalah yang boleh diselesaikan dengan kaedah bahagi dan takluk umumnya mempunyai ciri-ciri berikut:
1) Masalah boleh diselesaikan dengan mudah apabila skala masalah dikurangkan ke tahap tertentu
2) Masalah boleh diuraikan kepada beberapa masalah yang sama berskala lebih kecil, iaitu masalah mempunyai substruktur yang optimum. harta benda.
3) Penyelesaian kepada sub-masalah yang diuraikan oleh masalah ini boleh digabungkan ke dalam penyelesaian masalah ini
4) Sub-masalah yang terurai daripada masalah ini adalah bebas antara satu sama lain; , iaitu sub-masalah Tiada sub-sub-masalah biasa antara soalan.
Jika anda tidak mempunyai ciri ketiga, anda boleh mempertimbangkan untuk menggunakan pengaturcaraan dinamik (DP) atau kaedah tamak.
Jika ciri keempat tidak dipenuhi, pengaturcaraan dinamik boleh dipertimbangkan.
Langkah asas kaedah divide-and-conquer:
penguraian langkah1: menguraikan masalah asal kepada beberapa sub-masalah bebas yang lebih kecil dengan bentuk yang sama seperti masalah asal; penyelesaian langkah2: Jika sub-masalah kecil dan mudah untuk diselesaikan, selesaikan terus, jika tidak selesaikan setiap sub-masalah secara rekursif
2. Kaedah pengaturcaraan dinamik
(2) Tiada kesan selepas: iaitu, sebaik sahaja keadaan peringkat tertentu ditentukan, ia tidak akan terjejas oleh keputusan seterusnya di negeri ini. Dengan kata lain, proses selepas keadaan tertentu tidak akan menjejaskan keadaan sebelumnya, tetapi hanya berkaitan dengan keadaan semasa.
(3) Terdapat sub-masalah yang bertindih: iaitu, sub-masalah tidak bebas, dan sub-masalah boleh digunakan beberapa kali dalam peringkat membuat keputusan seterusnya. (Harta ini bukan syarat yang diperlukan untuk aplikasi pengaturcaraan dinamik, tetapi tanpa sifat ini, algoritma pengaturcaraan dinamik tidak akan mempunyai kelebihan berbanding dengan algoritma lain)
Kes:
Terdapat n langkah , seseorang naik satu atau dua langkah pada satu masa, dan bertanya berapa banyak cara yang ada untuk melengkapkan n langkah.
Analisis: Kunci kepada pelaksanaan pengaturcaraan dinamik terletak pada sama ada jadual pengaturcaraan dinamik boleh digunakan dengan tepat dan munasabah untuk mengabstrakkan masalah praktikal. Dalam masalah ini, biarkan f(n) mewakili bilangan cara untuk naik n langkah.
Kemudian apabila n ialah 1, f(n) = 1, apabila n ialah 2, f(n) =2, iaitu apabila hanya terdapat satu langkah, bilangan kaedah ialah satu , apabila terdapat dua langkah, bilangan kaedah ialah 2. Jadi apabila kita ingin naik n langkah, kita mesti mengambil satu langkah dari n-1 langkah atau dua langkah dari n-2 langkah, jadi bilangan cara untuk mencapai n langkah mesti kaedah untuk mencapai n-1 langkah nombor tambah jumlah bilangan cara untuk mencapai n-2 langkah. Iaitu, f(n) = f(n-1) f(n-2), kita menggunakan dp[n] untuk mewakili jadual pengaturcaraan dinamik, dp[i],i>0,i<=n, menunjukkan capaian aras i Bilangan kaedah.
int fun(int n){
if (n==1||n==2)
return n;
/*判断n-1的状态有没有被计算过*/
if (!dp[n-1])
dp[n-1] = fun(n-1);
if(!dp[n-2])
dp[n-2]=fun(n-2);
return dp[n-1]+dp[n-2];
}3. Algoritma Tamak
Algoritma tamak bermaksud apabila menyelesaikan masalah, sentiasa membuat keputusan yang nampaknya Terbaik pilihan. Dalam erti kata lain, kami tidak menganggap penyelesaian optimum keseluruhan, tetapi hanya membuat penyelesaian optimum tempatan dalam erti kata tertentu. Algoritma tamak tidak memperoleh penyelesaian optimum keseluruhan untuk semua masalah. hanya berkaitan dengan keadaan semasa.
Langkah-langkah umum untuk menyelesaikan masalah ialah:
1 Wujudkan model matematik untuk menerangkan masalah
2 -masalah untuk mendapatkan sub-masalah Penyelesaian optimum tempatan bagi masalah itu;
public class charge {
public static void main(String[] args) {
// TODO 自动生成的方法存根
int res = charge(84);
System.out.println(res);
}
private static int charge(int money) {
int count = 0;
int value[] = {50,20,10,5,2,1};
while(money>0){
int length = value.length;
for(int i=0;i=value[i]){
money=money-value[i];
count++;
//System.out.println(money);
}
}
}
return count;
}
}
4. Kaedah backtracking
Kaedah backtracking ialah kaedah mencari penyelesaian masalah secara sistematik. Semasa proses carian, cuba cari penyelesaian kepada masalah tersebut Jika anda mendapati anda tidak dapat menemuinya, ambil langkah ke belakang dan naik semula (proses pemangkasan). Backtracking boleh digunakan untuk banyak masalah yang kompleks dan berskala besar. Idea asas kaedah penjejakan ke belakang adalah dengan mengikuti strategi carian mendalam-pertama dan mula mencari dari nod akar Apabila mencapai nod tertentu, adalah perlu untuk menentukan sama ada ia mengandungi penyelesaian kepada masalah tersebut ia disertakan, teruskan carian dari nod itu Jika ia tidak disertakan , undur ke nod induk. Jika kaedah backtracking digunakan untuk mencari semua penyelesaian kepada masalah, ia mesti dikesan kembali ke akar, dan semua subpokok yang boleh dilaksanakan bagi nod akar mestilah telah dicari sebelum tamat. Dan jika anda menggunakan kaedah backtracking untuk mencari sebarang penyelesaian, anda boleh menamatkannya selagi anda mencari penyelesaian kepada masalah tersebut.
Fungsi pemangkasan yang biasa digunakan dalam kaedah menjejak ke belakang: (1) Fungsi kekangan: tolak pokok kecil yang tidak memenuhi kekangan pada nod. (2) Fungsi sempadan: tolak pokok kecil yang tidak boleh mendapatkan penyelesaian optimum. Langkah umum: 1 Untuk masalah yang diberikan, tentukan ruang penyelesaian masalah2. Gunakan kaedah yang sesuai untuk mencari untuk mengatur ruang penyelesaian
3 carian mendalam-pertama Ruang penyelesaian
4. Gunakan fungsi pemangkasan semasa proses carian untuk mengelakkan carian tidak sah.
5. Kaedah cawangan dan terikat
Serupa dengan kaedah menjejak ke belakang, ia juga merupakan algoritma yang mencari penyelesaian kepada masalah pada pokok ruang penyelesaian T masalah . Walau bagaimanapun, secara amnya, matlamat penyelesaian kaedah cawangan dan terikat dan kaedah penjejakan belakang adalah berbeza. Matlamat penyelesaian kaedah backtracking adalah untuk mencari semua penyelesaian dalam T yang memenuhi syarat kekangan, manakala matlamat penyelesaian kaedah cawangan dan terikat adalah untuk mencari penyelesaian yang memenuhi syarat kekangan, atau untuk mencari penyelesaian yang memenuhi kekangan. syarat supaya objektif tertentu Nilai fungsi mencapai penyelesaian maksimum atau minimum, iaitu penyelesaian optimum dalam erti kata tertentu. (1) Algoritma carian cawangan Apa yang dipanggil "cawangan" adalah menggunakan strategi keluasan-pertama untuk mencari semua cawangan E-nod dalam urutan, iaitu, semua yang bersebelahan nod, dan buang yang tidak berpuas hati Nod syarat kekangan, dan nod yang selebihnya ditambah pada senarai nod langsung. Kemudian pilih nod daripada jadual sebagai E-nod seterusnya dan teruskan carian. Bergantung pada cara memilih E-nod seterusnya, akan terdapat beberapa kaedah carian cawangan yang berbeza. 1) Carian FIFO 2) Carian LIFO 3) Carian baris gilir keutamaan (2) Algoritma carian cawangan dan terikat
Proses am kaedah cawangan dan terikat
Disebabkan matlamat penyelesaian yang berbeza, kaedah cawangan dan terikat dan kaedah penjejakan belakang mempunyai kaedah carian yang berbeza pada pokok ruang penyelesaian T. Kaedah penjejakan belakang mencari pepohon ruang penyelesaian T secara mendalam-dahulukan, manakala kaedah bercabang-dan-terikat mencari pepohon ruang penyelesaian T dalam cara yang luas-didahulukan atau terkecil-kos-didahulukan.
Strategi carian kaedah cawangan dan terikat ialah: pada nod pengembangan, mula-mula jana semua nod anaknya (cawangan), dan kemudian pilih titik pasangan pengembangan seterusnya daripada jadual nod langsung semasa. Untuk memilih nod pengembangan seterusnya dengan berkesan dan mempercepatkan proses carian, pada setiap nod hidup, nilai fungsi (terikat) dikira, dan berdasarkan nilai fungsi yang dikira ini, nilai terbaik dipilih daripada jadual nod hidup semasa. Nod yang menguntungkan berfungsi sebagai nod pengembangan untuk memajukan carian ke arah cawangan dengan penyelesaian optimum pada pokok ruang penyelesaian, supaya dapat mencari penyelesaian optimum secepat mungkin.
Kaedah bercabang dan terikat sering mencari pokok ruang penyelesaian masalah dengan cara pertama yang luas-didahulukan atau kos-minimum (faedah-maksimum). Pokok ruang penyelesaian masalah ialah pokok tertib yang mewakili ruang penyelesaian masalah yang biasa termasuk pokok subset dan pokok pilih ubah. Apabila mencari pepohon ruang penyelesaian masalah, kaedah cawangan-dan-terikat dan kaedah penjejakan belakang menggunakan kaedah pengembangan yang berbeza untuk nod pengembangan semasa. Dalam kaedah cawangan dan terikat, setiap nod hidup hanya mempunyai satu peluang untuk menjadi nod pengembangan. Sebaik sahaja nod hidup menjadi nod pengembangan, semua nod anaknya dijana serentak. Antara nod anak ini, nod yang membawa kepada penyelesaian yang tidak boleh dilaksanakan atau penyelesaian tidak optimum akan dibuang, dan nod anak yang selebihnya ditambahkan pada senarai nod langsung. Selepas itu, satu nod diambil daripada jadual nod hidup untuk menjadi nod pengembangan semasa, dan proses pengembangan nod di atas diulang. Proses ini berterusan sehingga penyelesaian yang dikehendaki ditemui atau jadual simpulan hidup kosong.
Beberapa perbezaan antara kaedah backtracking dan kaedah branch and bound
Sesetengah masalah sebenarnya boleh diselesaikan dengan baik sama ada dengan kaedah backtracking atau branch and bound kaedah. Tetapi yang lain tidak. Mungkin kita memerlukan analisis yang lebih khusus - bila hendak menggunakan branch and bound dan bila hendak menggunakan backtracking?
Beberapa perbezaan antara kaedah menjejak ke belakang dan kaedah cawangan dan terikat:
Kaedah carian kaedah untuk pepohon ruang penyelesaian Struktur data biasa untuk menyimpan nod Aplikasi biasa ciri storan nod
Kaedah carian Depth-first Backtracking: Semua nod anak yang boleh dilaksanakan bagi nod hidup timbunan dilalui sebelum dikeluarkan daripada timbunan untuk mencari semua penyelesaian yang memenuhi kekangan
Kaedah cawangan dan terikat Breadth- penggunaan pertama atau minimum baris gilir carian pertama, baris gilir keutamaan Setiap nod hanya mempunyai satu peluang untuk menjadi nod langsung untuk mencari penyelesaian yang memenuhi kekangan atau penyelesaian optimum dalam erti kata tertentu
Untuk pengetahuan yang lebih berkaitan, sila lawati lajur Soalan Lazim !
Atas ialah kandungan terperinci Apakah lima algoritma komputer klasik?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
