Page 206 - Bkhargava_-_Grokaem_algoritmy

Шпаргалка 205

Упражнения

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

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

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

Шпаргалка

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

а У NР-полных задач не существует известных быстрых решений.

о Если у вас имеется NР-полная задача, лучше всего воспользоваться при­
ближенным алгоритмом.

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

www.trk.kg