Pendakian bukit (algoritma) - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-23T04:05:38Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 23 Agustus 2026 04.05
Baris 1:		Baris 1:
			[[File:Hill_climb.png\|thumb\|right\|280px\|Suatu permukaan yang hanya memiliki satu nilai maksimum. Di sini, teknik pendakian bukit sangat cocok untuk mengoptimalkan permukaan tersebut, dan akan konvergen ke maksimum global]]

	Dalam [[analisis numerik]], '''pendakian bukit''' atau dalam bahasa Inggris '''''hill climbing''''' merupakan teknik [[Optimisasi\|optimasi matematis]] yang termasuk dalam keluarga algoritma [[Pencarian setempat (optimasi)\|pencarian setempat]]. Ia adalah [[algoritma berulang]] yang diawali dengan memulakan sembarang solusi untuk suatu masalah, kemudian mencoba menemukan solusi yang lebih baik dengan melakukan perubahan [[Pencarian heuristik tambahan\|bertambah secara bertahap]] pada solusi tersebut. Jika perubahan tersebut menghasilkan solusi yang lebih baik, maka perubahan bertambah secara bertahap lainnya akan dilakukan pada solusi yang baru, dan begitu seterusnya hingga tak ada lagi perbaikan yang dapat ditemukan.		Dalam [[analisis numerik]], '''pendakian bukit''' atau dalam bahasa Inggris '''''hill climbing''''' merupakan teknik [[Optimisasi\|optimasi matematis]] yang termasuk dalam keluarga algoritma [[Pencarian setempat (optimasi)\|pencarian setempat]]. Ia adalah [[algoritma berulang]] yang diawali dengan memulakan sembarang solusi untuk suatu masalah, kemudian mencoba menemukan solusi yang lebih baik dengan melakukan perubahan [[Pencarian heuristik tambahan\|bertambah secara bertahap]] pada solusi tersebut. Jika perubahan tersebut menghasilkan solusi yang lebih baik, maka perubahan bertambah secara bertahap lainnya akan dilakukan pada solusi yang baru, dan begitu seterusnya hingga tak ada lagi perbaikan yang dapat ditemukan.

	Sebagai contoh, pendakian bukit dapat diterapkan pada [[Permasalahan Penjual Keliling\|masalah penjualan keliling]]. Sangat mudah untuk menemukan solusi awal yang dapat mengunjungi semua kota, tetapi kemungkinan solusi tersebut akan sangat buruk (tinggi biaya), jika dibandingkan dengan solusi optimal. Algoritma ini dimulai dengan solusi seperti itu dan melakukan perbaikan kecil terhadap solusi tersebut, seperti menukar urutan dua kota. Secara bertahap, jalur yang jauh lebih pendek bisa ditemukan.		Sebagai contoh, pendakian bukit dapat diterapkan pada [[Permasalahan Penjual Keliling\|masalah penjualan keliling]]. Sangat mudah untuk menemukan solusi awal yang dapat mengunjungi semua kota, tetapi kemungkinan solusi tersebut akan sangat buruk (tinggi biaya), jika dibandingkan dengan solusi optimal. Algoritma ini dimulai dengan solusi seperti itu dan melakukan perbaikan kecil terhadap solusi tersebut, seperti menukar urutan dua kota. Secara bertahap, jalur yang jauh lebih pendek bisa ditemukan.

	Pendakian bukit mampu menemukan solusi optimal, khususnya untuk masalah [[optimasi cembung]], sedangkan untuk masalah lain, pendakian bukit hanya akan menemukan optimum setempat (solusi yang tak dapat diperbaiki dengan konfigurasi tetangga manapun), yang tidak selalu merupakan solusi terbaik yang mungkin ([[Maksimum dan minimum\|optimum global]]) di antara semua solusi yang mungkin di [[ruang pencarian]]. Contoh algoritma yang dapat menyelesaikan masalah optimasi cembung dengan algoritma pendakian bukit, antara lain adalah [[Metode mufrad\|algoritma mufrad]] untuk [[Program linear\|pemrograman linier]] dan [[Algoritma pencarian biner\|pencarian biner]]. Untuk menghindari terjebak dalam optimum setempat, dapat digunakan pendekatan, seperti memulai ulang, yaitu pencarian setempat berulang, atau dengan skema yang lebih rumit berdasarkan perulangan, seperti [[Pencarian setempat berulang\|perulangan pencarian setempat]], atau berdasarkan memori, seperti optimisasi pencarian bereaksi dan [[pencarian tabu]]), atau dengan modifikasi stokastik tanpa penggunaan memori (seperti [[penaruman tersimulasi]]).		Pendakian bukit mampu menemukan solusi optimal, khususnya untuk masalah [[optimasi cembung]], sedangkan untuk masalah lain, pendakian bukit hanya akan menemukan optimum setempat (solusi yang tak dapat diperbaiki dengan konfigurasi tetangga manapun), yang tidak selalu merupakan solusi terbaik yang mungkin ([[Maksimum dan minimum\|optimum global]]) di antara semua solusi yang mungkin di [[ruang pencarian]]. Contoh algoritma yang dapat menyelesaikan masalah optimasi cembung dengan algoritma pendakian bukit, antara lain adalah [[Metode mufrad\|algoritma mufrad]] untuk [[Program linear\|pemrograman linier]] dan [[Algoritma pencarian biner\|pencarian biner]].<ref>Steven Skiena. [https://archive.org/details/algorithmdesignm0000stev The Algorithm Design Manual]. Springer Science+Business Media. 2010. ISBN 1-849-96720-2.</ref> Untuk menghindari terjebak dalam optimum setempat, dapat digunakan pendekatan, seperti memulai ulang, yaitu pencarian setempat berulang, atau dengan skema yang lebih rumit berdasarkan perulangan, seperti [[Pencarian setempat berulang\|perulangan pencarian setempat]], atau berdasarkan memori, seperti optimisasi pencarian bereaksi dan [[pencarian tabu]]), atau dengan modifikasi stokastik tanpa penggunaan memori (seperti [[penaruman tersimulasi]]).

	Kesederhanaan relatif algoritma ini menjadikannya pilihan awal yang populer di antara algoritma optimasi. Algoritma ini telah digunakan secara luas dalam [[kecerdasan buatan]], seperti untuk mendapatkan kondisi tujuan dari simpul awal yang mana terdapat beberapa pilihan yang berbeda untuk simpul berikutnya dan simpul awal yang digunakan dalam algoritma terkait. Walau terdapat algoritma yang lebih canggih, seperti [[penaruman tersimulasi]] atau [[pencarian tabu]] yang mungkin memberikan hasil yang lebih baik, tetapi dalam beberapa situasi saat pendakian bukit dapat bekerja sama baiknya. Pendakian bukit sering kali dapat memberikan hasil yang lebih baik, dibandingkan dengan algoritma lain ketika jumlah waktu yang tersedia terbatas untuk melakukan pencarian, seperti pada sistem [[waktu nyata]], selama jumlah penambahan bertahap yang kecil umumnya konvergen pada solusi yang baik (solusi optimal atau pendekatan yang mendekati). Di sisi lain, salah satu algoritma pengurutan, [[pengurutan gelembung]] dapat dilihat sebagai algoritma pendakian bukit, sebab setiap pertukaran unsur yang berdekatan akan mengurangi jumlah pasangan unsur yang tidak terurut), tetapi pendekatan ini jauh dari efisien, bahkan untuk N yang kecil sekalipun, karena jumlah pertukaran yang dibutuhkan akan bertambah secara kuadratik.		Kesederhanaan relatif algoritma ini menjadikannya pilihan awal yang populer di antara algoritma optimasi. Algoritma ini telah digunakan secara luas dalam [[kecerdasan buatan]], seperti untuk mendapatkan kondisi tujuan dari simpul awal yang mana terdapat beberapa pilihan yang berbeda untuk simpul berikutnya dan simpul awal yang digunakan dalam algoritma terkait. Walau terdapat algoritma yang lebih canggih, seperti [[penaruman tersimulasi]] atau [[pencarian tabu]] yang mungkin memberikan hasil yang lebih baik, tetapi dalam beberapa situasi saat pendakian bukit dapat bekerja sama baiknya. Pendakian bukit sering kali dapat memberikan hasil yang lebih baik, dibandingkan dengan algoritma lain ketika jumlah waktu yang tersedia terbatas untuk melakukan pencarian, seperti pada sistem [[waktu nyata]], selama jumlah penambahan bertahap yang kecil umumnya konvergen pada solusi yang baik (solusi optimal atau pendekatan yang mendekati). Di sisi lain, salah satu algoritma pengurutan, [[pengurutan gelembung]] dapat dilihat sebagai algoritma pendakian bukit, sebab setiap pertukaran unsur yang berdekatan akan mengurangi jumlah pasangan unsur yang tidak terurut), tetapi pendekatan ini jauh dari efisien, bahkan untuk N yang kecil sekalipun, karena jumlah pertukaran yang dibutuhkan akan bertambah secara kuadratik.
Baris 15:		Baris 17:

	== Lihat juga ==		== Lihat juga ==

	* [[Penurunan gradien]]		* [[Penurunan gradien]]
	* [[Algoritma greedy]]		* [[Algoritma greedy]]
Baris 21:		Baris 22:
	* [[Pergeseran rata-rata]]		* [[Pergeseran rata-rata]]
	* [[Algoritma a-star\|Algoritma pencarian A*]]		* [[Algoritma a-star\|Algoritma pencarian A*]]

	~~== Referensi ==~~


	== Bacaan lanjutan ==		== Bacaan lanjutan ==
			*
	*

	== Pranala luar ==		== Pranala luar ==

	*		*

			== Referensi ==
			<references />

			== Sumber dan atribusi ==

	== ~~Sumber~~ dan ~~atribusi ==~~		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pendakian+bukit+%28algoritma%29&oldid=29187993 Wikipedia bahasa Indonesia], revisi 29187993 (2026-05-02T15:36:22Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

	~~Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pendakian+bukit+%28algoritma%29&oldid=29187993 Wikipedia bahasa Indonesia], revisi 29187993 (2026~~-05-~~02T15:36:22Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi~~-~~BerbagiSerupa (CC BY~~-~~SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.~~		<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29187993; atribusi sumber disertakan.

2026-08-23T03:26:13Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29187993; atribusi sumber disertakan.

Halaman baru

Dalam [[analisis numerik]], '''pendakian bukit''' atau dalam bahasa Inggris '''''hill climbing''''' merupakan teknik [[Optimisasi|optimasi matematis]] yang termasuk dalam keluarga algoritma [[Pencarian setempat (optimasi)|pencarian setempat]]. Ia adalah [[algoritma berulang]] yang diawali dengan memulakan sembarang solusi untuk suatu masalah, kemudian mencoba menemukan solusi yang lebih baik dengan melakukan perubahan [[Pencarian heuristik tambahan|bertambah secara bertahap]] pada solusi tersebut. Jika perubahan tersebut menghasilkan solusi yang lebih baik, maka perubahan bertambah secara bertahap lainnya akan dilakukan pada solusi yang baru, dan begitu seterusnya hingga tak ada lagi perbaikan yang dapat ditemukan.

Sebagai contoh, pendakian bukit dapat diterapkan pada [[Permasalahan Penjual Keliling|masalah penjualan keliling]]. Sangat mudah untuk menemukan solusi awal yang dapat mengunjungi semua kota, tetapi kemungkinan solusi tersebut akan sangat buruk (tinggi biaya), jika dibandingkan dengan solusi optimal. Algoritma ini dimulai dengan solusi seperti itu dan melakukan perbaikan kecil terhadap solusi tersebut, seperti menukar urutan dua kota. Secara bertahap, jalur yang jauh lebih pendek bisa ditemukan.

Pendakian bukit mampu menemukan solusi optimal, khususnya untuk masalah [[optimasi cembung]], sedangkan untuk masalah lain, pendakian bukit hanya akan menemukan optimum setempat (solusi yang tak dapat diperbaiki dengan konfigurasi tetangga manapun), yang tidak selalu merupakan solusi terbaik yang mungkin ([[Maksimum dan minimum|optimum global]]) di antara semua solusi yang mungkin di [[ruang pencarian]]. Contoh algoritma yang dapat menyelesaikan masalah optimasi cembung dengan algoritma pendakian bukit, antara lain adalah [[Metode mufrad|algoritma mufrad]] untuk [[Program linear|pemrograman linier]] dan [[Algoritma pencarian biner|pencarian biner]]. Untuk menghindari terjebak dalam optimum setempat, dapat digunakan pendekatan, seperti memulai ulang, yaitu pencarian setempat berulang, atau dengan skema yang lebih rumit berdasarkan perulangan, seperti [[Pencarian setempat berulang|perulangan pencarian setempat]], atau berdasarkan memori, seperti optimisasi pencarian bereaksi dan [[pencarian tabu]]), atau dengan modifikasi stokastik tanpa penggunaan memori (seperti [[penaruman tersimulasi]]).

Kesederhanaan relatif algoritma ini menjadikannya pilihan awal yang populer di antara algoritma optimasi. Algoritma ini telah digunakan secara luas dalam [[kecerdasan buatan]], seperti untuk mendapatkan kondisi tujuan dari simpul awal yang mana terdapat beberapa pilihan yang berbeda untuk simpul berikutnya dan simpul awal yang digunakan dalam algoritma terkait. Walau terdapat algoritma yang lebih canggih, seperti [[penaruman tersimulasi]] atau [[pencarian tabu]] yang mungkin memberikan hasil yang lebih baik, tetapi dalam beberapa situasi saat pendakian bukit dapat bekerja sama baiknya. Pendakian bukit sering kali dapat memberikan hasil yang lebih baik, dibandingkan dengan algoritma lain ketika jumlah waktu yang tersedia terbatas untuk melakukan pencarian, seperti pada sistem [[waktu nyata]], selama jumlah penambahan bertahap yang kecil umumnya konvergen pada solusi yang baik (solusi optimal atau pendekatan yang mendekati). Di sisi lain, salah satu algoritma pengurutan, [[pengurutan gelembung]] dapat dilihat sebagai algoritma pendakian bukit, sebab setiap pertukaran unsur yang berdekatan akan mengurangi jumlah pasangan unsur yang tidak terurut), tetapi pendekatan ini jauh dari efisien, bahkan untuk N yang kecil sekalipun, karena jumlah pertukaran yang dibutuhkan akan bertambah secara kuadratik.

Pendakian bukit termasuk dalam algoritma kapan pun atau [[Algoritma kapan pun|algoritma yang dapat digunakan kapan pun]], sebab ia dapat mengembalikan solusi yang sah. Bahkan, ketika diganggu kapan pun sebelum penyelenggaraan algoritma tersebut berakhir.

== Keterangan matematis ==
Pendakian bukit berupaya untuk memaksimalkan (atau meminimalkan) [[Fungsi (matematika)|fungsi]] target <math>f(\mathbf{x})</math>, dengan <math>\mathbf{x}</math> adalah sebuah vektor nilai bersinambung dan/atau berlainan. Di setiap perulangan, pendakian bukit akan menyesuaikan satu unsur dalam <math>\mathbf{x}</math> dan menentukan apakah perubahan tersebut meningkatkan nilai <math>f(\mathbf{x})</math>. (Perhatikan bahwa ini berbeda dengan metode [[penurunan gradien]], yang menyesuaikan semua nilai di dalamnya <math>\mathbf{x}</math> pada setiap perulangan sesuai dengan gradien bukit). Dengan pendakian bukit, perubahan apa pun yang meningkatkan <math>f(\mathbf{x})</math> akan diterima, dan proses akan terus berlanjut hingga tidak ditemukan perubahan yang meningkatkan nilai <math>f(\mathbf{x})</math>. Kemudian <math>\mathbf{x}</math> dikatakan “optimal secara setempat”.

Dalam [[ruang vektor]] berlainan, setiap nilai yang mungkin untuk <math>\mathbf{x}</math> dapat divisualisasikan sebagai sebuah [[Titik (teori graf)|simpul]] pada suatu [[Graf (matematika)|graf]]. ''Hill climbing'' akan mengikuti graf dari simpul ke simpul, selalu meningkatkan (atau menurunkan) nilai <math>f(\mathbf{x})</math> secara setempat, hingga [[Maksimum dan minimum|maksimum setempat]] (atau [[Maksimum dan minimum|minimum setempat]]) <math>x_m</math> tercapai.

== Lihat juga ==

* [[Penurunan gradien]]
* [[Algoritma greedy]]
* [[Lelang Walrasian|Tâtonnement]]
* [[Pergeseran rata-rata]]
* [[Algoritma a-star|Algoritma pencarian A*]]

== Referensi ==

== Bacaan lanjutan ==

*

== Pranala luar ==

*

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pendakian+bukit+%28algoritma%29&oldid=29187993 Wikipedia bahasa Indonesia], revisi 29187993 (2026-05-02T15:36:22Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.