Page 205 - Bkhargava_-_Grokaem_algoritmy

204 Глава 8. Жадные алгоритмы

главах я много говорил о кратчайших путях. Вы знаете, как вычислить
кратчайший путь из точки А в точку В.

A&TOEiYC НR 44

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

сильно замедляется при увеличении их числа;
i:J формулировка ~все комбинации х~ часто указывает на NР-полноту за­
дачи;
i:J вам приходится вычислять все возможные варианты Х, потому что за­
дачу невозможно разбить на меньшие подзадачи? Такая задача может
оказаться NР-полной;
l:J если в задаче встречается некоторая последовательность (например,
последовательность городов, как в задаче о коммивояжере) и задача не
имеет простого решения, она может оказаться NР-полной;

l:J если в задаче встречается некоторое множество (например, множество
радиостанций) и задача не имеет простого решения, она может оказаться
NР-полной;

l:J можно ли переформулировать задачу в условиях задачи покрытия
множества или задачи о коммивояжере? В таком случае ваша задача
определенно является NР-полной.

www.trk.kg