Грокаем алгоритмы

6.2 Найдите длину кратчайшего пути от «cab» к «bat».

Ответ: Длина кратчайшего пути равна 2.

6.3 Перед вами небольшой граф моего утреннего распорядка.

Для каждого из следующих трех списков укажите, действителен он или недействителен.

Ответы: A — недействителен; B — действителен; С — недействителен.

6.4 Немного увеличим исходный граф. Постройте действительный список для этого графа.

Ответ: 1 — Проснуться; 2 — Сделать зарядку; 3 — Принять душ; 4 — Почистить зубы; 5 — Одеться; 6 — Упаковать обед; 7 — Позавтракать.

6.5 Какие из следующих графов также являются деревьями?

Ответы: A — дерево; B — не дерево; C — дерево. В последнем примере дерево просто повернуто набок. Деревья составляют подкатегорию графов, поэтому любое дерево является графом, но граф не обязательно является деревом.

Глава 7

7.1 Каков вес кратчайшего пути от начала до конца в каждом из следующих графов?

Ответы: A — 8; B — 60; C — каверзный вопрос (кратчайший путь не существует из-за наличия цикла с отрицательным весом).

Глава 8

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

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

8.2 Вы едете в Европу, и у вас есть 7 дней на знакомство с достопримечательностями. Вы присваиваете каждой достопримечательности стоимость в баллах (насколько вы хотите ее увидеть) и оцениваете продолжительность поездки. Как обеспечить максимальную стоимость (увидеть все самое важное) во время поездки? Предложите жадную стратегию. Будет ли полученное решение оптимальным?

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

Для каждого из приведенных ниже алгоритмов укажите, является ли этот алгоритм жадным или нет.

8.3 Быстрая сортировка.

Ответ: Нет.

8.4 Поиск в ширину.

Ответ: Да.

8.5 Алгоритм Дейкстры.

Ответ: Да.

8.6 Почтальон должен доставить письма в 20 домов. Ему нужно найти кратчайший путь, проходящий через все 20 домов. Является ли эта задача NP-полной?

Ответ: Да.

8.7 Имеется задача поиска максимальной клики в множестве людей (кликой называется множество людей, каждый из которых знаком со всеми остальными.) Является ли эта задача NP-полной?

Ответ: Да.

8.8 Вы рисуете карту США, на которой два соседних штата не могут быть окрашены в одинаковый цвет. Требуется найти минимальное количество цветов, при котором любые два соседних штата будут окрашены в разные цвета. Является ли эта задача NP-полной?

Ответ: Да.

Глава 9

9.1 Предположим, к предметам добавился еще один: MP3-плеер. Он весит 1 фунт и стоит $1000. Стоит ли брать его?

Ответ: Да. Вы сможете положить в рюкзак MP3-плеер, iPhone и гитару общей стоимостью $4500.

9.2 Предположим, что вы собираетесь в турпоход. Емкость вашего рюкзака составляет 6 фунтов, и вы можете взять предметы из следующего списка. У каждого предмета имеется стоимость; чем она выше, тем важнее предмет:

• Вода, 3 фунта, 10

• Книга, 1 фунт, 3

• Еда, 2 фунта, 9

• Куртка, 2 фунта, 5

• Камера, 1 фунт, 6

Как выглядит оптимальный набор предметов для похода?

Ответ: Возьмите воду, еду и камеру.

9.3 Нарисуйте и заполните таблицу для вычисления самой длинной общей подстроки между строками blue и clues.

Ответ:

Глава 10

10.1 В примере с Netflix сходство между двумя пользователями оценивалось по формуле расстояния. Но не все пользователи оценивают фильмы одинаково. Допустим, есть два пользователя, Йоги и Пинки, вкусы которых совпадают. Но Йоги ставит 5 баллов любому фильму, который ему понравился, а Пинки более разборчива и ставит «пятерки» только самым лучшим фильмам. Вроде бы вкусы одинаковые, но по метрике расстояния они не являются соседями. Как учесть различия в стратегиях выставления оценок?

Ответ: Можно воспользоваться нормализацией: вы вычисляете среднюю оценку для каждого человека и используете ее для масштабирования оценок. Например, вы определили, что средняя оценка Пинки равна 3, а средняя оценка Йоги – 3,5. Соответственно оценки Пинки немного увеличиваются так, чтобы ее средняя оценка тоже была равна 3,5. После этого оценки можно сравнивать по единой шкале.