Главная » Хабрахабр » Книга «Теоретический минимум по Computer Science. Все что нужно программисту и разработчику»

Книга «Теоретический минимум по Computer Science. Все что нужно программисту и разработчику»

image

Изучение Computer Science может быть веселым и увлекательным занятием. Хватит тратить время на скучные академические фолианты!

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

3.5. Эвристические алгоритмы

В обычных шахматах — 32 фигуры шести типов и 64 клетки, по которым они ходят. После каких-то четырех первых ходов число возможных дальнейших позиций достигает 288 млрд. Даже самые сильные игроки в мире не в состоянии найти идеальный ход. Они полагаются на интуицию, чтобы найти тот, который окажется достаточно хорошим. Мы можем делать то же самое при помощи алгоритмов. Эвристический метод, или просто эвристика, — это метод, который приводит к решению, не гарантируя, что оно — лучшее или оптимальное. Эвристические алгоритмы помогут, когда методы вроде полного перебора или поиска с возвратом оказываются слишком медленными. Существует много отличных эвристических подходов, но мы сосредоточимся на самом простом: на поиске без возврата.

«Жадные» алгоритмы

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

Он решает использовать ваш рюкзак, чтобы унести в нем украденное. Жадный грабитель и рюкзак. Грабитель пробирается в ваш дом, чтобы украсть предметы, которые вы хотели продать. Имейте в виду, что чем быстрее он уйдет, тем меньше вероятность, что его поймают с поличным. Что он возьмет?

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

function greedy_knapsack(items, max_weight) bag_weight ← 0 bag_items ← List.new for each item in sort_by_value(items) if max_weight ≤ bag_weight + item.weight bag_weight ← bag_weight + item.weight bag_items.append(item) return bag_items

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

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

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

главу 1), число возможных комбинаций в этой задаче демонстрирует взрывной рост и достигает неприлично больших величин, даже если городов всего несколько. Как мы убедились в разделе «Комбинаторика» (см. Найти оптимальное решение задачи коммивояжера с тысячами городов — чрезвычайно дорого (а то и вовсе невозможно).

Вот простой «жадный» алгоритм для этой задачи: И тем не менее вам нужен маршрут.

1) посетить ближайший город, где вы еще не были;
2) повторять, пока не объедете все города.

image

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

Когда жадность побеждает силу

Выбирая эвристический алгоритм вместо классического, вы идете на компромисс. Насколько далеко от идеального решения вы можете отойти, чтобы результат все еще удовлетворял вас? Это зависит от конкретной ситуации.

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

Энергия пойдет от поселка к поселку по линиям электропередач. Электрическая сеть. Поселки в удаленном районе не были электрифицированы, но вот в одном из них начали строить электростанции. Как включить все поселки в сеть, используя минимум проводов?
Данная задача может быть решена очень просто.

1.Среди поселков, еще не подключенных к сети, выбрать тот, который находится ближе всех к электрифицированному поселку, и соединить их.
2.Повторять, пока все поселки не будут подключены.

image

На каждом шаге мы выбираем для соединения пару поселков, которая на текущий момент выглядит самой лучшей. Несмотря на то что мы не анализируем, как этот вариант влияет на будущие возможности выбора, присоединение самого близкого поселка без электричества — всегда правильный выбор. Здесь нам повезло: структура задачи идеально подходит для решения «жадным» алгоритмом. В следующем разделе мы увидим структуры задач, для решения которых нужна стратегия великих полководцев.

» Более подробно с книгой можно ознакомиться на сайте издательства
» Оглавление
» Отрывок

Для Хаброжителей скидка 20% по купону — Computer Science


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Больше всех пахала лошадь, но председателем колхоза так и не стала

Мне стало интересно понять профит от этих штук. В последнее время в мобильном сообществе часто можно услышать про Flutter, React Native. В итоге было создано 4 (одинаковых с точки зрения выполняемых функции) приложения: нативное Android, нативное iOS, Flutter, React Native. ...

Бесплатная трансляция DotNext 2018 Moscow

Меньше недели осталось до конференции DotNext 2018 Moscow: она пройдет в конгресс-парке гостиницы «Рэдиссон Ройал Москва» 22-23 ноября. Между докладами будут вестись интервью с ключевыми спикерами конференции. По традиции, прямо на YouTube будет открыта бесплатная онлайн-трансляция первого зала (ссылка спрятана ...