Методы последовательных приближений проб и ошибок перебора

Метод проб и ошибок
– старейший из методов поиска новых
решений.

Впервые метод проб
и ошибок был описан немецким физиологом
Э.Торндайком в 1898г.

Метод проб и ошибок
— форма обучения, описанная, основанная
на закреплении случайно совершенных
двигательных и мыслительных актов, за
счет которых была решена значимая для
животного задача. В следующих пробах
время, которое затрачивается животным
на решение аналогичных задач в аналогичных
условиях, постепенно, хотя и не линейно,
уменьшается, до тех пор, пока не приобретает
форму мгновенного решения. В дальнейшем
более точный анализ поведения методом
проб и ошибок показал, что оно не является
полностью хаотическим и нецелесообразным,
как считал Торндайк, но интегрирует в
себе прошлый опыт и новые условия для
решения задачи.

Сегодня, с развитием
электронно-вычислительной техники,
метод проб и ошибок стал отправной
точкой для создания разнообразных
методов случайного поиска, где используется
не просто перебор всех возможных
вариантов, а сложная система «весовых»
коэффициентов, которая позволяют
отбросить неэффективные варианты уже
на ранних этапах поиска.

Метод проб и ошибок
— способ выработки новых форм поведения
в проблемных ситуациях. М. п. и о., широко
используемый бихевиоризмом для объяснения
научения как вероятностного процесса,
получил распространение в психологии
после работ Э. Л. Торндайка, согласно
которым слепые пробы, ошибки и случайный
успех, закрепляющий удачные пробы,
определяют путь приобретения
индивидуального опыта у животных и
человека. Тем самым была выделена
согласованность поведения со средой
на вероятностной основе, что позволило
при интерпретации категории действия
выйти за пределы жесткой альтернативы:
либо механистической, либо телеологической
его трактовки. Гештальтпсихология
подвергла М. п. и о. критике, противопоставив
ему решение проблемы путем инсайта.
Непродуктивность и теоретическая
слабость такого противопоставления
была показана И. П. Павловым. Свое значение
М. п. и о. сохранил лишь в узкой сфере
искусственно создаваемых ситуаций; в
частности, он вошел в состав конструктивных
принципов кибернетических устройств.

2. Метод случайного поиска.

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

Итерационные
методы минимизации функции F(x) состоят
в построении последовательности

векторов, то есть
точек x0, x1, …, xk, таких, что F(x0) > F(x1)
>…>F(xk)>… Любой такой метод называется
методом спуска. Естественно, должна
быть обеспечена сходимость. Иными
словами, рассматриваются методы,
позволяющие получить точку минимума
за конечное число шагов, или приблизиться
к ней достаточно близко при соответствующем
числе шагов. Дето в том, что теоретически
все сходящиеся методы этим свойством
обладают, но практически близость к
минимуму в задачах большой размерности
ограничивается ошибками вычислений. В
этой связи необходимо вести вычисления
с самой большой возможной точностью.
Для построения итерационной
последовательности необходимо выбрать
начальное приближение x0. В задачах с
ограничениями это должна быть допустимая
точка, а в задачах без ограничений
теоретически любая точка. Однако
целесообразно использовать всю имеющуюся
информацию о поведении целевой функции
F(x), чтобы выбрать x0 поближе к точке
минимума.

После того, как
начальное приближение получено, прежде
чем перейти к следующей точке нужно
принять два решения:

1). Выбрать
направление, по которому пойдем из x0 в
точку с меньшим значением целевой
функции (направление спуска).

2). Определить
величину шага по направлению спуска.

Для задач безусловной
минимизации любое напрвление является
возможным (никакие ограничения не
мешают), но далеко не все направления
приемлемы. Нас могут интересовать только
те направления, которые обеспечивают
убывание целевой функции, хотя бы при
достаточно малом шаге. Предполагая
непрерывность первых частных производных
целевой функции и используя её разложение
в ряд Тэйлора в произвольной точке х,
получим F(x+λp) ~ F(x) + X(g,p). Здесь g — градиент
функции, вычисленный в точке х. Отсюда
следует, что приращение функции F(x+Xp) –
F(x) < 0 при отрицательном скалярном
произведении (g,p). Итак, направление
спуска должно составлять острый угол
с антиградиентом. Этот вывод справедлив
и для задач с ограничениями, но там ещё
дополнительно требуется, чтобы при
достаточно малом шаге не нарушалось ни
одно из ограничений.

Методы
функционально-структурного исследования
объектов.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

From Wikipedia, the free encyclopedia

Trial and error is a fundamental method of problem-solving^[1] characterized by repeated, varied attempts which are continued until success,^[2] or until the practicer stops trying.

According to W.H. Thorpe, the term was devised by C. Lloyd Morgan (1852–1936) after trying out similar phrases «trial and failure» and «trial and practice».^[3] Under Morgan’s Canon, animal behaviour should be explained in the simplest possible way. Where behavior seems to imply higher mental processes, it might be explained by trial-and-error learning. An example is a skillful way in which his terrier Tony opened the garden gate, easily misunderstood as an insightful act by someone seeing the final behavior. Lloyd Morgan, however, had watched and recorded the series of approximations by which the dog had gradually learned the response, and could demonstrate that no insight was required to explain it.

Edward Lee Thorndike was the initiator of the theory of trial and error learning based on the findings he showed how to manage a trial-and-error experiment in the laboratory. In his famous experiment, a cat was placed in a series of puzzle boxes in order to study the law of effect in learning.^[4] He plotted to learn curves which recorded the timing for each trial. Thorndike’s key observation was that learning was promoted by positive results, which was later refined and extended by B. F. Skinner’s operant conditioning.

Trial and error is also a method of problem solving, repair, tuning, or obtaining knowledge. In the field of computer science, the method is called generate and test (Brute force). In elementary algebra, when solving equations, it is guess and check.

This approach can be seen as one of the two basic approaches to problem-solving, contrasted with an approach using insight and theory. However, there are intermediate methods which for example, use theory to guide the method, an approach known as guided empiricism.

This way of thinking has become a mainstay of Karl Popper’s critical rationalism.

Methodology[edit]

The trial and error approach is used most successfully with simple problems and in games, and it is often the last resort when no apparent rule applies. This does not mean that the approach is inherently careless, for an individual can be methodical in manipulating the variables in an attempt to sort through possibilities that could result in success. Nevertheless, this method is often used by people who have little knowledge in the problem area. The trial-and-error approach has been studied from its natural computational point of view ^[5]

Simplest applications[edit]

Ashby (1960, section 11/5) offers three simple strategies for dealing with the same basic exercise-problem, which have very different efficiencies. Suppose a collection of 1000 on/off switches have to be set to a particular combination by random-based testing, where each test is expected to take one second. [This is also discussed in Traill (1978–2006, section C1.2]. The strategies are:

• the perfectionist all-or-nothing method, with no attempt at holding partial successes. This would be expected to take more than 10^301 seconds, [i.e., 2^1000 seconds, or 3·5×(10^291) centuries]
• a serial-test of switches, holding on to the partial successes (assuming that these are manifest), which would take 500 seconds on average
• parallel-but-individual testing of all switches simultaneously, which would take only one second

Note the tacit assumption here that no intelligence or insight is brought to bear on the problem. However, the existence of different available strategies allows us to consider a separate («superior») domain of processing — a «meta-level» above the mechanics of switch handling — where the various available strategies can be randomly chosen. Once again this is «trial and error», but of a different type.

Hierarchies[edit]

Ashby’s book develops this «meta-level» idea, and extends it into a whole recursive sequence of levels, successively above each other in a systematic hierarchy. On this basis, he argues that human intelligence emerges from such organization: relying heavily on trial-and-error (at least initially at each new stage), but emerging with what we would call «intelligence» at the end of it all. Thus presumably the topmost level of the hierarchy (at any stage) will still depend on simple trial-and-error.

Traill (1978–2006) suggests that this Ashby-hierarchy probably coincides with Piaget’s well-known theory of developmental stages. [This work also discusses Ashby’s 1000-switch example; see §C1.2]. After all, it is part of Piagetian doctrine that children learn first by actively doing in a more-or-less random way, and then hopefully learn from the consequences — which all has a certain resemblance to Ashby’s random «trial-and-error».

Application[edit]

Traill (2008, espec. Table «S» on p.31) follows Jerne and Popper in seeing this strategy as probably underlying all knowledge-gathering systems — at least in their initial phase.

Four such systems are identified:

• Natural selection which «educates» the DNA of the species,
• The brain of the individual (just discussed);
• The «brain» of society-as-such (including the publicly held body of science); and
• The adaptive immune system.

Features[edit]

Trial and error has a number of features:

• solution-oriented: trial and error makes no attempt to discover why a solution works, merely that it is a solution.
• problem-specific: trial and error makes no attempt to generalize a solution to other problems.
• non-optimal: trial and error is generally an attempt to find a solution, not all solutions, and not the best solution.
• needs little knowledge: trials and error can proceed where there is little or no knowledge of the subject.

It is possible to use trial and error to find all solutions or the best solution, when a testably finite number of possible solutions exist. To find all solutions, one simply makes a note and continues, rather than ending the process, when a solution is found, until all solutions have been tried. To find the best solution, one finds all solutions by the method just described and then comparatively evaluates them based upon some predefined set of criteria, the existence of which is a condition for the possibility of finding a best solution. (Also, when only one solution can exist, as in assembling a jigsaw puzzle, then any solution found is the only solution and so is necessarily the best.)

Examples[edit]

Trial and error has traditionally been the main method of finding new drugs, such as antibiotics. Chemists simply try chemicals at random until they find one with the desired effect. In a more sophisticated version, chemists select a narrow range of chemicals it is thought may have some effect using a technique called structure–activity relationship. (The latter case can be alternatively considered as a changing of the problem rather than of the solution strategy: instead of «What chemical will work well as an antibiotic?» the problem in the sophisticated approach is «Which, if any, of the chemicals in this narrow range will work well as an antibiotic?») The method is used widely in many disciplines, such as polymer technology to find new polymer types or families.

Trial and error is also commonly seen in player responses to video games — when faced with an obstacle or boss, players often form a number of strategies to surpass the obstacle or defeat the boss, with each strategy being carried out before the player either succeeds or quits the game.

Sports teams also make use of trial and error to qualify for and/or progress through the playoffs and win the championship, attempting different strategies, plays, lineups and formations in hopes of defeating each and every opponent along the way to victory. This is especially crucial in playoff series in which multiple wins are required to advance, where a team that loses a game will have the opportunity to try new tactics to find a way to win, if they are not eliminated yet.

The scientific method can be regarded as containing an element of trial and error in its formulation and testing of hypotheses. Also compare genetic algorithms, simulated annealing and reinforcement learning – all varieties for search which apply the basic idea of trial and error.

Biological evolution can be considered as a form of trial and error.^[6] Random mutations and sexual genetic variations can be viewed as trials and poor reproductive fitness, or lack of improved fitness, as the error. Thus after a long time ‘knowledge’ of well-adapted genomes accumulates simply by virtue of them being able to reproduce.

Bogosort, a conceptual sorting algorithm (that is extremely inefficient and impractical), can be viewed as a trial and error approach to sorting a list. However, typical simple examples of bogosort do not track which orders of the list have been tried and may try the same order any number of times, which violates one of the basic principles of trial and error. Trial and error is actually more efficient and practical than bogosort; unlike bogosort, it is guaranteed to halt in finite time on a finite list, and might even be a reasonable way to sort extremely short lists under some conditions.

Jumping spiders of the genus Portia use trial and error to find new tactics against unfamiliar prey or in unusual situations, and remember the new tactics.^[7] Tests show that Portia fimbriata and Portia labiata can use trial and error in an artificial environment, where the spider’s objective is to cross a miniature lagoon that is too wide for a simple jump, and must either jump then swim or only swim.^[8][9]

See also[edit]

References[edit]

Further reading[edit]

• Ashby, W. R. (1960: Second Edition). Design for a Brain. Chapman & Hall: London.
• Traill, R.R. (1978–2006). Molecular explanation for intelligence…, Brunel University Thesis, HDL.handle.net
• Traill, R.R. (2008). Thinking by Molecule, Synapse, or both? — From Piaget’s Schema, to the Selecting/Editing of ncRNA. Ondwelle: Melbourne. Ondwelle.com — or French version Ondwelle.com.
• Zippelius, R. (1991). Die experimentierende Methode im Recht (Trial and error in Jurisprudence), Academy of Science, Mainz, ISBN 3-515-05901-6

Метод проб и ошибок

в решении текстовых задач.

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

Текстовые задачи можно разбить на два основных класса:

• текстовые арифметические задачи;

• текстовые задачи на составление уравнений.

Причем это разделение довольно условно. Многие текстовые арифметические задачи можно решить с помощью уравнений, а задачи на составление уравнений (систем уравнений) часто решают по действиям, а если это не получается, то используют метод проб и ошибок или метод перебора.

Мне бы хотелось продемонстрировать решение ряда задач этими методами.

Задача №1

Одна сторона прямоугольного участка земли на 3 м больше другой его стороны. Площадь участка равна 70 м². Найти размеры этого участка.

Пусть x м ширина участка, (x+3) м – длина участка, а площадь x·(x+3) м²,

что по условию задачи равно 70 м². Чтобы найти размеры участка надо составить уравнение x·(x+3)=70 и решить его. Но в 5^ом классе такие учащиеся решать еще не могут. Поэтому попробуем подобрать решение «экспериментально», так называемым методом проб и ошибок.

1. пусть x=4, т.е. 4·(4+3)=28, 28≠70;

2. x=6, т.е. 6·(6+3)=54, 54≠70;

3. x=7, т.е. 7·(7+3)=70, 70=70 верно.

Т.е. мы увидели, что метод проб и ошибок позволяет найти ответ даже в случае, когда математический модель представляет собой новый, не изученный еще объект. Но, решая задачи этим способом, следует помнить, что подбор одного решения не гарантирует полноты решения. Поэтому необходимы обоснования того, что найдены все возможные решения.

В нашей задаче, если бы x было больше 7,то x+310 и x·(x+3)70, если наоборот xx+3 x·(x+3)

Задачи для учащихся.

Переведи условие задачи на математический язык и найди решение методом проб и ошибок.

1. Площадь прямоугольника равна 68 дм², а длина больше ширины на 13 дм. Каковы стороны этого прямоугольника?

2. Ширина прямоугольника на 9 см меньше длины, а площадь равна 90 см². Найти стороны прямоугольника.

3. Найти периметр прямоугольника, площадь которого составляет 18 м², а ширина в 2 раза меньше длины.

4. Площадь прямоугольника равна 64 дм², а его длина в 4 раза больше ширины. Чему равен периметр прямоугольника?

5. Длину прямоугольника уменьшили на 3 см, а ширину увеличили на 4 см и получили квадрат. Найти сторону квадрата, если площадь прямоугольника равна 30 см².

6. После того как ширину прямоугольника увеличили на 1 м, а длину уменьшили на 5 м, получили квадрат. Чему равна площадь квадрата, если площадь прямоугольника 91 м².

7. Длина прямоугольника на 5 м больше ширины, а площадь составляет 24 м². каковы стороны этого прямоугольника?

8. Длину прямоугольника уменьшили в 2 раза, а ширину увеличили на 1 дм и получили квадрат. Найти сторону квадрата, если площадь прямоугольника 60 дм².

9. Найти периметр прямоугольника, у которого ширина на 4 см меньше длины, а площадь составляет 32 см².

10)Одна из сторон прямоугольника на 20 см больше другой. Если

большую сторону уменьшить в 3 раза, а меньшую сторону увеличить

в 2 раза, то площадь нового прямоугольника будет равна 200 см².

Найти стороны данного прямоугольника.

Метод перебора при

нахождении НОД.

Рассмотрим еще один метод – метод перебора. Т.к. предыдущий метод решения задач – метод проб и ошибок не дает уверенности в том, что найдены все искомые значения. Поэтому для обоснования полноты решения требуются дополнительные, иногда очень непростые рассуждения. В этом недостаток метода проб и ошибок. Но он исключен в методе полного перебора.

Полный перебор требует, как правило, больших усилий и большого времени. Однако внимательный анализ условия часто позволяет найти систему перебора, охватывающую все возможные варианты, но более короткую, чем «лобовой» перебор.

Задача. На экскурсию едут 252 ученика школы. Для них заказаны

несколько автобусов. Однако выяснилось, что если заказать

автобусы, вмещающие на 6 человек больше, то автобусов

потребуется на один меньше. Сколько больших автобусов надо

заказать?

Составим таблицу.

Т.к. по условию в большой автобус вмещается на 6 детей больше, чем в маленький, то разность 252 : x — 252 : (x+1) = 6. Значит решением задачи является число X, удовлетворяющее равенству: 252 : x — 252 : (x+1) = 6.

Но можно получить более простую математическую модель этой задачи, обозначив дополнительно буквой Y число детей, которых можно разместить в большом автобусе.

Очевидно, что в этом случае математической моделью задачи являются два равенства:

1. xy = 252;

2. (x+1)·(y-6) = 252.

Искомые числа x и y должны удовлетворять как первому, так и

второму равенству. Найдем эти числа x и y.

Из равенства xy = 252 можно заметить, что числа x и y не могут быть

больше, чем 252. Однако и в этом случае «лобовой» перебор потребовал бы рассмотрения огромного числа вариантов. Но более внимательный анализ первого равенства показывает, что числа x и y – это парные делители 252: при делении 252 на x получается y, и наоборот. Следовательно, достаточно рассмотреть лишь парные делители числа 252, причем для случая, когда y6 (y-60).

Составим таблицу:

+1

— 6

Анализ второго равенства позволяет еще больше сократить число возможных вариантов. Оно означает, что число (x+1) и (y-6) так же являются парными делителями 252. Из таблицы видно, что такими свойствами обладает только пара x=6, y=42.

Ответ: для экскурсии надо заказать 6 больших автобусов.

Задачи для учащихся.

1. Сумма цифр двузначного числа равна 15. Если эти цифры поменять местами, то получится число, которое на 27 меньше исходного. Найти эти числа.

2. Сумма цифр двузначного числа равна 12. число, записанное теми же цифрами, но в обратном порядке, составляет ⁴ /₇ исходного числа. Найти эти числа.

3. Одно из двух натуральных чисел на 4 больше другого. Найди эти числа, если их произведение равно 96.

4. У причала находилось 6 лодок, часть из которых была двухместными, а часть трехместными. Всего в эти лодки может поместиться 14 человек. Сколько двухместных и трехместных лодок было у причала?

5. Прямоугольный газон обнесен изгородью, длинна которой 30 м. Площадь газона 56 м². Найди длины газона, если известно, что они выражаются натуральными числами.

6. В несколько посылок упаковали 36 книг и 54 журнала, распределив их между посылками поровну. В каждой посылке книг на 2 меньше, чем журналов. Сколько получилось посылок?

7. Произведение двух натуральных чисел равно 72. Найти эти числа, если одно из них больше другого на 6.

8. На турбазе имеются палатки и домики, общее число которых равно 25. в каждом домике живут 4 человека, а в палатке – 2 человека. Сколько на турбазе палаток и сколько домиков, если всего на этой турбазе отдыхают 70 человек?

9. Прямоугольный участок земли обнесен забором, длина которого 40 м. Площадь участка 96 м². Найти длины сторон этого участка, если известно, что они выражаются натуральными числами.

Еще один тип задач, которые решаются методом перебора.

Задумано двузначное число, которое на 52 больше произведения своих цифр. Какое число задумано?

Пусть xy – задуманное двузначное число, где x – цифра десятков, а y – цифра единиц. Тогда их произведение равно xy. Само двузначное число можно записать как 10x+y. По условию 10x+y на 52 больше произведения своих цифр xy. Т.е. должно выполняться равенство 10x+y= xy+52, которое является математической моделью данной задачи.

Решается это уравнение методом перебора. Полный перебор можно провести, рассматривая последовательно все значения x от 1 до 9 и подбирая в каждом случае соответствующее значение y от 0 до 9.

Однако этот перебор можно сократить, если заметить, что первая часть данного равенства больше 52. Значит, и первая его часть, т.е. задуманное число, больше 52. Поэтому неизвестное число x не меньше 5, и можно рассматривать только пять значений x – от 5 до 9.

При x=5 будем иметь равенство 50+y=5y+52, оно невозможно, т.к. 50+yy+52.

При x=6 60+y=6y+52 | -y

60=5y+52

5y=8 невозможно для натурального y.

При x=7 70+y=7y+52

70=6y+52

6y=18

y=3 Число 73

При x=8 80+y=8y+52

80=7y+52

7y=28

y=4 Число 87

При x=9 90+y=9y+52

38=8y невозможно

Таким образом, задумано либо 73, либо 84.

Условие задачи не дает возможности ответить на этот вопрос. Поэтому два ответа: 73 или 84.

Задачи для учащихся.

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

Например: Доказать, что сумма любых трех последовательных натуральных чисел делится на 3.

1 сл. 1,2,3 1+2+3=6, 6:3=2

2 сл. 5,6,7 5+6+7=18, 18:3=6

3 сл. 21,22,23 21+22+23=66 66:3=22

и т.д.

Возьмем произведение натурального числа и обозначим его n. Тогда следующие за ним два числа соответственно равны n+1 и n+2.

Их сумма: n+(n+1)+(n+2)=3n+3=3(n+1) делится на 3, т.к. один из множителей делится на 3.