Читать «Вычислительное мышление: Метод решения сложных задач» онлайн - страница 43

Все вершины на графе Кенигсберга имеют нечетное число ребер, поэтому искомый маршрут невозможен. Однако со времен Эйлера через реку построили новый мост, поэтому граф изменился. Экскурсоводам современного Калининграда живется легче.

Собираемся и путешествуем

Настоящее путешествие

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

Такую кратчайшую дорогу можно просчитать, но вряд ли получится каждый раз делать это за разумный промежуток времени. Даже если надо побывать у 20 клиентов, нельзя гарантировать, что вы ежедневно будете находить оптимальное решение — на это потребуется слишком много времени. И дело не в том, что требуется более мощный навигатор или компьютер. Если число мест, где необходимо побывать, достаточно велико (на самом деле оно не очень-то и велико), то на поиск совершенного решения уйдет больше времени, чем прошло с момента возникновения Вселенной, — даже при наличии самого быстрого компьютера! Почему? Потому что число возможных вариантов, которые необходимо проверить, стремительно растет с появлением каждого нового города. Даже если навигатор запрограммировать на какое-то решение, нельзя гарантировать, что оно будет безупречным. Заложенный в программу способ не обеспечит кратчайшего пути. Вполне вероятно, что в программе сработает так называемый Давайте изменим условия задачи, чтобы понять, о чем идет речь.

Пакуем чемоданы

Представьте, что вы отправляетесь в долгий отпуск, мечтая хорошо отдохнуть. Открытый чемодан лежит на кровати. Вы уже упаковали одежду и теперь собираете вещи, которые хотите взять с собой, — книги, настольные игры, пазлы, колоду карт, краски и бумагу… Все, что, по вашему мнению, поможет расслабиться. Все эти вещи разного размера. Их нужно сложить в чемодан. Как это сделать? Пробуем разные варианты. Сначала пазл, потом игральные карты, потом книга с кроссвордами — и так далее. Если у вас достаточно места, то все получится, однако, если места маловато или вы не хотите брать много чемоданов, намечается проблема.

Хорошей альтернативой будет . С его помощью не получится упаковать все максимально компактно, но порой он работает весьма хорошо. Как выбрать, что положить сначала? Исходите из жадности. Положите самый большой предмет внутрь, пусть он займет как можно больше места. Теперь положите следующий по размеру — и так далее. Если что-то не помещается, берите следующий чемодан. Обычно все получается само собой, потому что, когда у вас остаются небольшие свободные пространства, вы заполняете их небольшими предметами. Это годный алгоритм — с такими алгоритмами вы достаточно хорошо (но не безупречно) справитесь с задачей. Они не гарантируют оптимального решения.