Алгоритм Британского музея
Sign in to saveAlso known as British Museum technique
Алгоритм, перебирающий все возможные решения с нарастанием сложности, обычно неоптимальный
In the Vinony graph
Within Vinony's link graph, Алгоритм Британского музея is referenced by 3 other articles, and connects out to National Institute of Standards and Technology, breadth-first search and bogosort.
It sits within the topics Algorithms and British Museum.
Its subject is documented across 6 Wikipedia language editions.
Article · Русский
Алгоритм Британского музея заключается в переборе всех возможных вариантов, начиная с самого маленького по размеру, пока верное решение не будет найдено. Данный алгоритм почти не применим на практике, являясь лишь принципом, в теории применимым к любой задаче с большим числом возможных вариантов. Например, с помощью алгоритма можно найти самую короткую программу, решающую поставленную задачу, следующим образом. Сначала создаются все возможные программы с исходным кодом длиной в один символ. Затем осуществляется проверка, решает ли каждая из программ задачу. (Такая проверка значительно затрудняется проблемой остановки). Если ни одна из программ не справляется с задачей, рассматриваются все программы длиной в два символа, три символа и так далее. В теории в результате искомая программа действительно будет найдена, однако на практике алгоритм будет работать чрезмерно долго (во многих случаях время работы может превысить продолжительность существования Вселенной). Пользуясь аналогичными выкладками, алгоритм можно использовать для доказательства оптимизаций, теорем, тестирования систем распознавания языков и для иных целей. Американские учёные Аллен Ньюэлл, Клифф Шоу и Герберт Саймоннарекли данную процедуру «алгоритмом Британского музея», поскольку «[идея] показалась им столь же безумной, как и попытка рассаживать обезьян перед печатными машинками в надежде, что они воспроизведут все книги из Британского музея»
Abstract from DBpedia / Wikipedia · CC BY-SA