» » »

=6. Методика «грубой силы» разработки алгоритмов (Определение. Алгоритмы и задачи: сортировка выбором, пузырьковая сортировка, последовательный поиск, поиск подстроки, задача о паре двух ближайших точек, задача о выпуклой

Метод грубой силы («в лоб»)

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

Пример: вычисление степени числа умножением 1 на это число n раз
  • Применим практически для любых типов задач

  • Часто оказывается наиболее простым в применении

  • Редко дает красивые и эффективные алгоритмы

  • Стоимость разработки более эффективного алгоритма может оказаться неприемлемой, если требуется решить только несколько экземпляров задачи

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

  • Может служить мерилом для определения эффективности других алгоритмов

src=img/6-1.jpg

src=img/6-2.jpg

src=img/6-3.jpg

src=img/6-4.jpg

src=img/6-5.jpg

src=img/6-6.jpg

src=img/6-7.jpg

src=img/6-8.jpg

src=img/6-9.jpg

src=img/6-10.jpg

src=img/6-11.jpg

src=img/6-12.jpg

src=img/6-13.jpg

src=img/6-14.jpg

src=img/6-15.jpg

src=img/6-16.jpg

src=img/6-17.jpg

src=img/6-18.jpg

src=img/6-19.jpg

src=img/6-20.jpg

src=img/6-21.jpg

src=img/6-22.jpg

src=img/6-23.jpg

src=img/6-24.jpg

src=img/6-25.jpg

src=img/6-26.jpg

src=img/6-27.jpg

src=img/6-28.jpg

src=img/6-30.jpg

src=img/6-31.jpg

src=img/6-32.jpg

src=img/6-33.jpg

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

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

Задача о рюкзаке: дано N предметов заданного веса и стоимости рюкзак, выдерживающий вес W. Загрузить рюкзак с максимальной стоимостью.


Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.