Алгоритм Британского музея

Алгоритм Британского музея заключается в переборе всех возможных вариантов, начиная с самого маленького по размеру, пока верное решение не будет найдено. Данный алгоритм почти не применим на практике, являясь лишь принципом, в теории применимым к любой задаче с большим числом возможных вариантов.

Например, с помощью алгоритма можно найти самую короткую программу, решающую поставленную задачу, следующим образом. Сначала создаются все возможные программы с исходным кодом длиной в один символ. Затем осуществляется проверка, решает ли каждая из программ задачу. (Такая проверка значительно затрудняется проблемой остановки). Если ни одна из программ не справляется с задачей, рассматриваются все программы длиной в два символа, три символа и так далее. В теории в результате искомая программа действительно будет найдена, однако на практике алгоритм будет работать чрезмерно долго (во многих случаях время работы может превысить продолжительность существования Вселенной).

Пользуясь аналогичными выкладками, алгоритм можно использовать для доказательства оптимизаций, теорем, тестирования систем распознавания языков и для иных целей.

Американские учёные Аллен Ньюэлл, Клифф Шоу и Герберт Саймон^[1] нарекли данную процедуру «алгоритмом Британского музея», поскольку

«[идея] показалась им столь же безумной, как и попытка рассаживать обезьян перед печатными машинками в надежде, что они воспроизведут все книги из Британского музея»

См. также

Источники

Оригинальный текст за авторством Black, Paul E. «British Museum technique». Dictionary of Algorithms and Data Structures. NIST.

Примечания

↑ Newell Allen, Shaw J. C., Simon Herbert A. Elements of a theory of human problem solving. // Psychological Review. — 1958. — Т. 65, № 3. — С. 151—166. — ISSN 0033-295X. — doi:10.1037/h0048495. [исправить]

Алгоритмы поиска на графах
Неинформированные методы	Алгоритм Брона — Кербоша Двунаправленный поиск Лучевой поиск Лексикографический поиск в ширину Поиск в ширину Поиск по критерию стоимости Поиск в глубину Поиск с возвратом Поиск восхождением к вершине Поиск с ограничением глубины Поиск в глубину с итеративным углублением
Информированные методы	Альфа-бета-отсечение Метод ветвей и границ Поиск по первому наилучшему совпадению A* B* D* Поиск точки перехода IDA* Рекурсивный поиск по первому наилучшему совпадению SMA*
Кратчайшие пути	Волновой алгоритм Алгоритм Беллмана — Форда Алгоритм Дейкстры Алгоритм Джонсона Алгоритм Левита Алгоритм Флойда — Уоршелла Поиск по краям
Минимальное остовное дерево	Алгоритм Борувки Алгоритм Прима Алгоритм Краскала
Другое	Алгоритм Британского музея Алгоритм Эдмондса Обход дерева Алгоритм ближайшего соседа в задаче коммивояжёра

Read other articles:

Datsakorn Thonglao

Datsakorn Thonglao Informasi pribadiNama lengkap Datsakorn ThonglaoTanggal lahir 30 Desember 1983 (umur 40)Tempat lahir Nong Bua Lamphu, ThailandTinggi 1,69 m (5 ft 6+1⁄2 in)Posisi bermain Gelandang serangInformasi klubKlub saat ini Kanchanaburi CityNomor 7Karier junior1998–1999 Raj PrachaKarier senior*Tahun Tim Tampil (Gol)1999 Raj Pracha 23 (8)2000–2006 BEC Tero Sasana 77 (18)2001–2002 → 1. FC Kaiserslautern (pinjaman) 0 (0)2007–2009 Hoang Anh Gia Lai 28...

Domninus dari Larissa

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Oktober 2022. Domninus dari LarissaNama dalam bahasa asli(grc) Δομνίνος ο Λαρισσαίος BiografiKelahiran(grc) Δομνίνος k. 420 Larisa in Syria (en) Kematiank. 480 (59/60 tahun)KegiatanSpesialisasiFilsafat dan matematika PekerjaanMat...

Hendrik Maarten Krabbé

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada November 2022. Heinrich Maarten KrabbeHendrik Maarten Krabbé (tanggal tidak diketahui)Lahir(1868-05-04)4 Mei 1868London, InggrisMeninggal22 Desember 1931(1931-12-22) (umur 63)Amsterdam, BelandaNama lainHeinrich Martin KrabbéPekerjaanArtist Hendrik Maarte...

Harga diri

Harga diri adalah pandangan keseluruhan dari individu tentang dirinya sendiri.[1] Individu melakukan penilaian terhadap hal-hal yang berkaitan dengan dirinya.[2] Harga diri juga mencakup bagaimana individu memandang dirinya sebagai pribadi yang cakap, berharga, serta berhasil. Penghargaan diri juga kadang dinamakan martabat diri atau gambaran diri.[1] Misalnya, anak dengan penghargaan diri yang tinggi mungkin tidak hanya memandang dirinya sebagai seseorang, tetapi juga...

The Canadian (film)

1926 film The CanadianLobby cardDirected byWilliam BeaudineWritten byArthur Stringer (adaptation, scenario)Julian Johnson (intertitles)Based onThe Land of Promiseby W. Somerset MaughamProduced byAdolph ZukorJesse LaskyStarringThomas MeighanCinematographyAlvin WyckoffDistributed byParamount PicturesRelease date November 27, 1926 (1926-11-27) Running time80 minutes; 8 reels (7,753 feet)CountryUnited StatesLanguageSilent (English intertitles) The Canadian is an extant 1926 America...

1810 New Hampshire gubernatorial election

New Hampshire gubernatorial election For related races, see 1810 United States gubernatorial elections. 1810 New Hampshire gubernatorial election ← 1809 March 13, 1810 1811 → Nominee John Langdon Jeremiah Smith Party Democratic-Republican Federalist Popular vote 16,325 15,166 Percentage 51.70% 48.03% Governor before election Jeremiah Smith Federalist Elected Governor John Langdon Democratic-Republican Elections in New Hampshire Federal government Presidential...

Guelph Royals (baseball)

Guelph RoyalsInformationLeagueIntercounty Baseball League (1919–present)LocationGuelph, OntarioBallparkDavid E. Hastings StadiumFounded1861Nickname(s)The RoyalsLeague championships9 1919 1920 1921 1932 1970 1993 1997 2003 2004 Former name(s) Guelph Royals Guelph CJOYs Guelph Royals (1962–63) Guelph Merchants (1958–61) Guelph Plymouths (1957) Guelph-Waterloo Royals (1954–56) Guelph Maple Leafs (1861–1953) Former league(s) Intercounty League (1911–18) Canadian League (1896–1911) I...

مستقبلية

مستقبليةمعلومات عامةالبداية 1909 البلد إيطاليا — روسيا — بولندا المؤسس فيليبو توماسو مارينيتي[1] التأثيراتتأثرت بـ مدرسة تكعيبية تعديل - تعديل مصدري - تعديل ويكي بيانات تشكيل برونزي مستقبلي من عام 1913 المستقبلية[2][3] (بالإنجليزية: Futurism ؛ بالإيطالية: Futurismo) حركة فن�...

SD Negeri 001 Belakang Padang

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Februari 2023. SDN 001 Belakang PadangInformasiJenisSekolah NegeriAlamatLokasiJl. Sulawesi, Kelurahan Tanjung Sari Kecamatan Belakang Padang, Batam, Kepri, IndonesiaMoto SDN 001 Belakang Padang, merupakan salah satu Sekolah Menengah Dasar Negeri yang ada di Pr...

Automotive industry in Russia

Overview of the automotive industry in Russia Parts of this article (those related to informations about the situation after february 2022) need to be updated. Please help update this article to reflect recent events or newly available information. (July 2022) Lada Vesta went into production in 2015 Automotive production is a significant industry in Russia, directly employing around 600,000 people or 1% of the country's total workforce. Russia produced 1,767,674 vehicles in 2018, ranking 13t...

ソー (オー＝ド＝セーヌ県)

Sceaux 行政国フランス地域圏 (Région) イル＝ド＝フランス地域圏県 (département) オー＝ド＝セーヌ県郡 (arrondissement) アントニー郡小郡 (canton) 小郡庁所在地INSEEコード 92071郵便番号 92330市長（任期）フィリップ・ローラン（2008年-2014年）自治体間連合 (fr) メトロポール・デュ・グラン・パリ人口動態人口 19,679人（2007年）人口密度 5466人/km2住民の呼称 Scéens地理座標北緯48度4...

卡洛斯·梅内姆

此條目需要擴充。 (2015年11月27日)请協助改善这篇條目，更進一步的信息可能會在討論頁或扩充请求中找到。请在擴充條目後將此模板移除。卡洛斯·梅内姆阿根廷總統府官方照片第47任阿根廷總統任期1989年7月8日—1999年12月10日副总统爱德华多·杜阿尔德卡洛斯·鲁考夫（英语：Carlos Ruckauf）前任劳尔·阿方辛个人资料出生(1930-07-02)1930年7月2日阿根廷拉里奥哈省阿尼利亚�...

1941 au Manitoba

Cet article est une ébauche concernant une chronologie ou une date et le Manitoba. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Chronologie du Manitoba ◄◄ 1937 1938 1939 1940 1941 1942 1943 1944 1945 ►► Chronologies Données clés 1938 1939 1940 1941 1942 1943 1944Décennies :1910 1920 1930 1940 1950 1960 1970Siècles :XVIIIe XIXe XXe XXIe XXIIeMillénair...

السويد في كأس العالم 2002

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (ديسمبر 2018) السويد كأس العالم 2002 الاتحاد المشرف اتحاد السويد لكرة القدم البلد المضيف كوريا الجنوبية و اليابان ...

Bygones (sculpture)

Sculpture in Houston, Texas, U.S. BygonesArtistMark di SuveroYear1976 (1976)LocationMenil Collection, Houston, Texas, United StatesCoordinates29°44′15″N 95°23′50″W / 29.737586°N 95.397145°W / 29.737586; -95.397145 Bygones is an outdoor 1976 sculpture by Mark di Suvero, installed at Houston's Menil Collection, in the U.S. state of Texas. The abstract, geometric sculpture is made of Cor-ten beams and a milled steel plate, and measures 25 ft. 11 in. ...

Gonçalo Byrne

Portuguese architect Gonçalo Byrne. Gonçalo Byrne, GCIH (born 17 January 1941[1] in Alcobaça)[2] is a Portuguese architect. Byrne is responsible for a vast accomplishment of architectural work, and has been awarded with many national and international prizes. In 2005 he was awarded the title of Doctor Honoris Causa from the Lisbon Faculty of Architecture, Technical University of Lisbon, and was awarded the Grand Cross of the Order of Santiago da Espada by the President of t...

Landkreis Altenburger Land

Wappen Deutschlandkarte Basisdaten Koordinaten: 50° 58′ N, 12° 24′ O50.9612.4Koordinaten: 50° 58′ N, 12° 24′ O Bundesland: Thüringen Verwaltungssitz: Altenburg Fläche: 569,39 km2 Einwohner: 88.692 (31. Dez. 2023)[1] Bevölkerungsdichte: 156 Einwohner je km2 Kfz-Kennzeichen: ABG, SLN Kreisschlüssel: 16 0 77 NUTS: DEG0M Kreisgliederung: 30 Gemeinden Adresse der Kreisverwaltung: Lindenaustraße 9046...

The Puritan

17th-century play sometimes attributed to Shakespeare For other uses, see Puritan (disambiguation). Title page of the 1607 quarto The Puritan, or the Widow of Watling Street, also known as The Puritan Widow, is an anonymous Jacobean stage comedy, first published in 1607. It is often attributed to Thomas Middleton, but also belongs to the Shakespeare Apocrypha due to its title page attribution to W.S.. Date and authorship The Puritan probably dates from the year 1606. Some of its incidents are...

Comparative Literary Studies: An Introduction

1973 book by Siegbert Salomon Prawer Comparative Literary Studies: An Introduction EditorsSiegbert Salomon PrawerLanguageEnglishSubjectcomparative literaturePublisherDuckworth BooksMedia typePrint (Hardcover)Pages180 pp.ISBN978-0064956987 Comparative Literary Studies: An Introduction is a 1973 textbook by Siegbert Salomon Prawer in which the author provides an introduction to comparative literature.[1] Reception Alireza Anoushirvani (from Shiraz University) calls the book one of ...

Matarazzo Building

Palace in São Paulo, BrazilMatarazzo BuildingEdifício MatarazoThe Palácio do Anhangabaú in the center of the city.Matarazzo BuildingLocation within São PauloShow map of São PauloMatarazzo BuildingMatarazzo Building (Brazil)Show map of BrazilAlternative namesAnhangabaú Palace (Portuguese: Palácio Anhangabaú)General informationTypePalaceArchitectural styleItalian rationalismLocationSão Paulo, BrazilAddressViaduto do Chá, 15Coordinates23°32′51.64″S 46°38′15.32″W / &#...