Книга является наиболее полным руководством по разработке эффективных ал

Часть I. Практическая разработка алгоритмов 
1.3.3. Демонстрация неправильности алгоритма 
Самый лучший способ доказать 
неправильность
алгоритма — найти экземпляр задачи, 
для которого алгоритм выдает неправильный ответ. Такие экземпляры задачи называ-
ются 
контрпримерами
. Никто не бросится на защиту алгоритма, для которого был 
предоставлен контрпример. Вполне разумно выглядящие алгоритмы можно момен-
тально опровергнуть посредством очень простых контрпримеров. Хороший контрпри-
мер должен обладать двумя важными свойствами: 
проверяемостью. 
Чтобы продемонстрировать, что некий входной экземпляр задачи 
является контрпримером для определенного алгоритма, требуется вычислить ответ, 
который алгоритм выдаст для данного экземпляра, и предоставить лучший ответ, 
с тем, чтобы доказать, что алгоритм не смог его найти; 
простотой.
Хороший контрпример не содержит ничего лишнего и ясно демонстри-
рует, 
почему
именно предлагаемый алгоритм неправильный. Поэтому обнаружен-
ный контрпример следует упростить. Контрпример на рис. 1.6, 
а
можно упростить и 
улучшить, сократив количество пересекающихся периодов с четырех до двух. 
Развитие навыков поиска контрпримеров будет стоить затраченного времени. Этот 
процесс в чем-то подобен разработке наборов тестов для проверки компьютерных про-
грамм, но в нем главную роль играет удачная догадка, а не перебор вариантов. Приве-
ду несколько советов. 
Ищите мелкомасштабные решения.
Обратите внимание, что мои контрпримеры 
для задач поиска маршрута содержат шесть или меньше точек, а для задач кален-
дарного планирования — только три временных интервала. Это обстоятельство ука-
зывает на то, что если алгоритм неправильный, то доказать это можно на очень про-
стом экземпляре. Алгористы-любители нередко создают большой запутанный эк-
земпляр, с которым потом не могут справиться. А профессионалы внимательно 
изучат несколько небольших экземпляров, т. к. их легче осмыслить и проверить. 
Рассмотрите все решения. 
Для наименьшего нетривиального значения 
n
имеется 
только небольшое количество экземпляров.
Например, существуют только три 
представляющих интерес способа расположения двух интервалов на прямой: непе-
рекрывающиеся интервалы, частично перекрывающиеся интервалы и полностью 
перекрывающиеся интервалы. Все случаи размещения на прямой трех интервалов 
(включая контрпримеры для обоих эвристических алгоритмов календарного плани-
рования) можно создать, по-разному добавляя третий интервал к этим двум, распо-
ложенным указанными тремя способами. 
Ищите слабое звено. 
Если рассматриваемый вами алгоритм работает по принципу 
"всегда берем самое большее" (так называемый 
жадный алгоритм
), то подумайте, 
почему этот подход может быть неправильным. 
Ищите ограничения.
"Жадный" эвристический алгоритм можно сбить с толку не-
обычным методом предоставления входного экземпляра, содержащего одинаковые 
элементы. В этой ситуации алгоритму будет не на чем основывать свое решение и 
он, возможно, возвратит неоптимальное решение. 
Рассматривайте крайние случаи. 
Многие контрпримеры представляют собой ком-
бинацию большого и малого, правого и левого, многих и немногих, далекого и 

---