黄金分割搜索

黄金分割搜索是一种通过不断缩小单峰函数最值的已知范围,从而找到最值的方法。它的名称源于这个算法保持了间距具有黄金分割特性的三个点。这个算法与斐波那契搜索和二分查找关系紧密。黄金分割搜索是由Kiefer提出的,而斐波那契搜索是由Avriel和Wilde所提出。

黄金分割搜索示意图

内容

基本概念

上图表示了算法中找最小值的一个步骤。的函数值位于垂直坐标轴上,参数x位于水平坐标轴。已经有三个位于函数上的点的值被计算出来。: ,和。可见小于,所以很明显的,最小值处于之间。

接下来的步骤是通过计算函数位于另一个点的值。在最大的区间选择会更有效率,例如:之间。从图中我们可以看出,如果函数的值落在的话,最小值落于之间,并且新的一组点将会是。然而如果函数的值为的话,新的一组点将会是。因此,无论是哪种情况,我们都可以建立一个新的更狭窄的区间,用于搜索函数的最小值。

点的选择

由图可知,新的区间会介于,长度为a+c,或者介于,长度为。黄金分割搜索要求这些区间是相等的。若不是如此,较宽的区间会被使用很多次,降低了收敛率。为了确保 = + ,算法应确保 = - +

然而的确定仍是一个问题。我们避免了非常接近或者的情况,确保了每一次迭代区间宽度会缩小同样的比例。

为了确保计算后的值与之间的成比例,假设的值为,且我们新的一组点为,则必须使:

。然而,如果的值为,并且我们新的一组点为,则必须使:
。结合 = + 可解得

而φ就是黄金比例

这就是这个算法被称为黄金分割搜索的原因。

3.终止条件

4.递归算法

5.斐波那契搜索

6.参阅

Read other articles:

Biografi ini tidak memiliki sumber tepercaya sehingga isinya tidak dapat dipastikan. Bantu memperbaiki artikel ini dengan menambahkan sumber tepercaya. Materi kontroversial atau trivial yang sumbernya tidak memadai atau tidak bisa dipercaya harus segera dihapus.Cari sumber: Jan Mølby – berita · surat kabar · buku · cendekiawan · JSTOR (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) Jan Mølby Informasi pribadiTanggal lahir 4 Juli 1...

 

 

Diskografi SS501SS501 di My Style My MTV pada 2008(f.l.t.r.) Kim Hyung-jun, Heo Young-saeng, Park Jung-min, Kim Kyu-jong dan leader Kim Hyun-joongAlbum studio3Album kompilasi4Album video20Video musik19Extended play10Album soundtrack10 Artikel utama: SS501 Boy band SS501 (Hangul: 더블에스오공일) (pengucapan: Double-S Five-Oh-One dalam bahasa Inggris, Deo- Beur-E-Seu Oh-Gong-Il dalam bahasa Korea), yang dibentuk di bawah manajemen DSP Media, sebelumnya dikenal sebagai Daesung En...

 

 

Untuk sejarah Gereja Katolik pada umumnya, lihat Garis waktu Gereja Katolik dan Sejarah Gereja Katolik. Artikel ini merupakan bagian dari seriKota Vatikan Sejarah Kadipaten Roma (533–751) Donasi Pippin (750-an) Negara Kepausan (754–1870) Annatae Kongregasi untuk Perbatasan Undang-Undang Dasar Pemerintahan Sekuler Negara Gereja Penyerangan Roma oleh Muslim (846) Penaklukan Roma (1870) Tahanan dalam Vatikan (1870–1929) Permasalahan Roma Undang-Undang Jaminan Perjanjian Lateran (1929) Kota...

Pour les articles homonymes, voir Gallica (homonymie). Adresse https://gallica.bnf.fr/ Slogan Source de culture et d'émotions Commercial non Type de site Bibliothèque numérique Langue Français, anglais, allemand, italien, russe Siège social Paris, Île-de-France France Propriétaire Bibliothèque nationale de France Lancement 1997 modifier  Gallica est la bibliothèque numérique de la Bibliothèque nationale de France et de ses partenaires. En libre accès depuis 1997, elle regrou...

 

 

Optical device This article is about an optical device. For other uses, see Camera obscura (disambiguation). Illustration of the camera obscura principle from James Ayscough's A short account of the eye and nature of vision (1755 fourth edition) An image of the New Royal Palace at Prague Castle projected onto an attic wall by a hole in the tile roofing A camera obscura (pl. camerae obscurae or camera obscuras; from Latin camera obscūra 'dark chamber')[1] is a darke...

 

 

Elm cultivar Ulmus pumila 'Dropmore'Ulmus pumila 'Dropmore' (right), Ulmus 'Fremont' (U. pumila x U. rubra) (left), 1987, Madison Arboretum, University of WisconsinSpeciesUlmus pumilaCultivar'Dropmore'OriginUS The Siberian elm cultivar Ulmus pumila 'Dropmore' [1] was grown from seed collected in Harbin, Manchuria, China, by F. L. Skinner, of Dropmore, Manitoba.[1] Green reported (1964) a suggestion to merge the Siberian elm cultivars 'Harbin' and 'Manchu' with 'Dropmore', as all came ...

Renato Moicano Nazionalità  Brasile Altezza 180 cm Peso 66 kg Arti marziali miste Specialità Jiu jitsu brasiliano, Muay thai Categoria Pesi piuma Squadra Constrictor Team Carriera Combatte da Brasilia, Brasile Vittorie 12 per sottomissione 5 per decisione 7 Sconfitte 4 per knockout 3 per sottomissione 1 Pareggi 1   Modifica dati su Wikidata · Manuale Renato Moicano, pseudonimo di Renato Carneiro (Brasilia, 21 maggio 1989), è un artista marziale misto br...

 

 

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Summoner Wicca – news · newspapers · books · scholar · JSTOR (January 2018) (Learn how and when to rem...

 

 

VajiravudhRaja Rama VIRaja SiamBerkuasa23 Oktober 1910 – 25 November 1925(15 tahun, 33 hari)Penobatan23 OKtober 1910PendahuluRama VPenerusRama VIIInformasi pribadiKelahiran(1881-01-01)1 Januari 1881Bangkok, SiamKematian25 November 1925(1925-11-25) (umur 44)WangsaDinasti ChakriAyahRama VIbuSaovabha BongsriPasanganPutri Vanbimol VoravanPrueng SucharitakulPrabai SucharitakulKruakeaw AbhaiwongseAnakPutri Bejaratana RajasudaAgamaBuddha Theravada Phra Bat Somdet Phra Poramentharama...

I AmEP của (G)I-dlePhát hành2 tháng 5 năm 2018 (2018-05-02)Thu âm2018Thể loạiK-poptropical househip hopR&BThời lượng21:12Ngôn ngữHàn QuốcHãng đĩaCube EntertainmentThứ tự album của (G)I-dle ''I Am''(2018) I Made(2019) Đĩa đơn từ I Am LatataPhát hành: 2 tháng 5 năm 2018 I Am là mini album đầu tay của nhóm nhạc nữ Hàn Quốc (G)I-dle. Album được phát hành kỹ thuật số vào ngày 2 tháng 5 ...

 

 

Error in numerical data This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: False precision – news · newspapers · books · scholar · JSTOR (October 2015) (Learn how and when to remove this message) Fit approximation Concepts Orders of approximation Scale analysis Big O notation Curve fitting False precision Signi...

 

 

U.S. natural landmark in Washington state Drumheller ChannelsDrumheller ChannelsMap of Washington (state)Locationsouth central Washington (state)Coordinates46°58′30″N 119°11′47″W / 46.97500°N 119.19639°W / 46.97500; -119.19639Designated1986 Drumheller Channels National Natural Landmark showcases the Drumheller Channels, which are the most significant example in the Columbia Plateau of basalt butte-and-basin Channeled Scablands. This National Natural Landmar...

Current period in the history of Western philosophy Part of a series onPhilosophy Philosophy portal Contents Outline Lists Glossary History Categories Disambiguation Philosophies By period Ancient Ancient Egyptian Ancient Greek Medieval Renaissance Modern Contemporary Analytic Continental By region African Egypt Ethiopia South Africa Eastern philosophy Chinese Indian Indonesia Japan Korea Vietnam Indigenous American Aztec philosophy Middle Eastern philosophy Iranian Western American Briti...

 

 

US airspace system modernization project This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) The neutrality of this article is disputed. Relevant discussion may be found on the talk page. Please do not remove this message until conditions to do so are met. (November 2023) (Learn how and when to remove this message) This article relies largely or entirely on a single source. Relevant discussio...

 

 

Boxing competitions Boxingat the Games of the XXIX OlympiadVenueWorkers Indoor ArenaDates9–24 August 2008Competitors283 from 77 nations← 20042012 → Boxing at the2008 Summer OlympicsLight flyweightFlyweightBantamweightFeatherweightLightweightLight welterweightWelterweightMiddleweightLight heavyweightHeavyweightSuper heavyweightvte The boxing program of the 2008 Summer Olympics in Beijing, China was held at the Workers Indoor Arena. Medals were awarded in eleve...

Indian actor Avinash TiwaryTiwary in 2023Born15 August[1]Gopalganj, Bihar, IndiaAlma materNew York Film AcademyOccupationActorYears active2009–present Avinash Tiwary (born 15 August) is an Indian actor who works in Hindi films and series. Tiwary had his first major roles in the television series Yudh (2014) and in the film Tu Hai Mera Sunday (2016). He gained recognition for starring in the romance Laila Majnu (2018) and the supernatural film Bulbbul (2020).[2][...

 

 

Baburu Babi Baburu babi (bahasa Indonesia: berburu babi) atau babubru alek (berburu besar) adalah kegiatan berburu untuk menangkap babi dengan menggunakan anjing yang sudah dilatih berburu. Kegiatan ini biasanya ada tiap nagari di Minangkabau dan dapat diikuti oleh semua orang yang hobi berburu. Praktik Pesisir Selatan Baburu babi sering diadakan di Nagari Batu Hampa, Kabupaten Pesisir Selatan dan lebih dikenal sebagai baburu alek. Kegiatan sudah sering diadakan pada masa dahulunya sebagai be...

 

 

ولاية سليانة   الاسم الرسمي (بالعربية: ولاية سليانة)‏   موقع ولاية سليانة في الجمهورية التونسية    الإحداثيات 36°10′00″N 9°22′00″E / 36.166666666667°N 9.3666666666667°E / 36.166666666667; 9.3666666666667   [1] تاريخ التأسيس 5 يونيو 1974  تقسيم إداري  البلد تونس[3][2] ...

Rice crossbred from different varieties Hybrid rice is a type of Asian rice that has been crossbred from two very different parent varieties.[1] As with other types of hybrids, hybrid rice typically displays heterosis or hybrid vigor, so when grown under the same conditions as comparable purebred rice varieties, it can produce up to 30% more yield.[2] To produce hybrid seeds in large quantity, a purebred sterile rice variety is fertilized with fertile pollen from a different v...

 

 

El Torreón Bien de interés culturalPatrimonio histórico de España LocalizaciónLocalidad Laviana (Asturias)Datos generalesCódigo RI-51-0008764[editar datos en Wikidata] La torre denominada El Torreón está situada en El Condado, concejo de Laviana (Asturias, España). Constituye uno de los pocos ejemplos de arquitectura militar que se conservan en Asturias. Descripción Vista del torreón Está levantada sobre un espolón calizo, que le imprime carácter de edificación aislad...