Об авторе: Анатолий Шалыто, профессор, д.т.н., Университет ИТМО.
Стали мы как-то с выдающимся олимпиадным программистом совместно выбирать тему его кандидатской диссертации. Он высказал пожелание писать о тестировании программ. На это я ответил: «Только через мой труп», — а увидев удивлённое лицо молодого человека, пояснил: «Если бы в этой области можно было бы что-то человеческое получить, то каждый программист не тестировал бы по-своему, а в каждой мало-мальской программистской конторе не было бы подразделения тестирования».
Однако я понимал, что человек наиболее продуктивно работает над проблемой, которую выбрал сам. Поэтому решил сохранить проблему тестирования, ограничив её олимпиадными задачами, в которых он отлично разбирался. Молодой человек обрадовался моему предложению.
Прошло пару недель, и мне в руки попала книжка об олимпиадном программировании, из которой, в частности, следовало, что известен двадцать один класс олимпиадных задач. Стало ясно, что область олимпиадных программ почти такая же разнообразная, как программы вообще. При этом я подумал, что подходы к тестированию решений задач на геометрию могут не иметь ничего общего с проверкой решений комбинаторных задач.
Я забил тревогу, и молодой человек понял, что попал в безнадёгу. У меня других предложений не было, а аспирант серьёзно задумался над тем, решения каких классов задач или просто отдельных задач тестировать, имея при этом шанс получить научные результаты. Это направление мыслей молодого человека мне понравилось, и я мотивировал его тем, что сказал: «Если тебе удастся сделать задуманное, то не исключено, что это, возможно, будет первый в мире научный результат, полученный в области олимпиадного программирования». Действительно, олимпиадные задачи решают и тестируют тысячи программистов в мире, однако я никогда не слышал, чтобы кто-то из них сам предложил новый метод решения хотя бы какой-то задачи.
Через какое время аспирант, а это был Максим Буздалов (чемпион мира 2009 года по спортивному программированию по версии ACM ICPC), определился и пошёл к своей цели. Не буду рассказывать все подробности того, как это было, так как про произошедшее можно писать, а потом снимать детектив, но кое-что всё-таки расскажу.
Сначала Макс для своей бакалаврской работы выбрал трудную задачу о мультирюкзаке. Обычная задача о рюкзаке состоит в следующем: есть несколько предметов, у каждого из которых есть вес и стоимость, а также рюкзак, который выдерживает только какой-то максимальный вес, и нужно выбрать такие предметы, чтобы их можно было унести в этом рюкзаке, а суммарная стоимость была максимальной. Задача о мультирюкзаке отличается от этой задачи тем, что рюкзаков имеется больше одного – что, как можно догадаться, задачу не упрощает.
Потом он связался с администраторами сайта, на котором решалась эта задача. После этого, используя генетические алгоритмы, начал генерировать дополнительно к используемым новые тесты, которые «убивали» по времени выполнения (одно из ограничений на качество предложенных решений) существовавшие на тот момент решения, считавшиеся правильными. По состоянию на 15 июня 2009 в наборе присутствовало 47 тестов, а из 3100 посланных на проверку решений было принято 260. В течение нескольких дней у меня на глазах число решений, считавшихся правильными, «усыхало», и за день до защиты бакалаврской работы правильных решения оставалось … два, а в последнюю ночь правильных решений … не осталось вовсе.
Можете себе представить удивление сильного олимпиадного программиста, например, другого чемпиона мира, который лет эдак через пять после написания программы, признанной правильной, неожиданно получает уведомление, что задача была решена им неправильно!
После этого началась борьба, которая обычно имеет место при написании вирусов и антивирусов – люди писали новые решения этой задачи, а Макс с помощью разработанного метода добавлял новые тесты, которые делали эти решения неправильными. Однако «нападающим» писать «правильные» решения становилось все труднее, и в каждый момент времени на сайте для этой задачи уже не было сотен правильных решений, а было одно-два.
Потом Макс, уже в магистерской диссертации, продолжил «издеваться» над людьми, которые в свое время предложили для другой задачи (о поиске минимальной клики в графе) решения, в то время считавшиеся правильными. Смысл этой задачи состоит в нахождении максимального подмножества вершин графа, в котором любая пара вершин соединена ребром.
Однако эта задача и её решения не сдались Максу так же легко, как предыдущая, и довести до нуля число правильных решений ему так и не удалось. Это, по моему мнению, должно вдохновить на «бой» следующих борцов с, возможно, временно правильными решениями.
Та же ситуация возникла у Макса и в кандидатской диссертации, в которой, кроме задачи о мультирюкзаке, он разрабатывал более мощные, чем известные, тесты для графовых задач на примере задачи о поиске максимального потока. Суть задачи состоит в следующем: задан граф, в котором каждое ребро имеет какую-то пропускную способность. Вместо рёбер можно представить себе трубы разного сечения, тогда пропускная способность будет выражена, скажем, в литрах в секунду. В графе также имеются две вершины – исток и сток — и требуется найти способ пропустить от истока к стоку через этот граф максимальный поток (передать между истоком и стоком как можно больше литров в секунду).
В результате на примере задачи о мультирюкзаке Максим создал метод генерации тестов для программ решения NP-трудных задач (NP-трудность – специальная характеристика, определяющая класс сложности вычислительных задач – ред.) на основе генетического алгоритма. При этом было показано, что этот метод с бо́льшим уровнем статистической значимости генерирует более сложные тесты, чем наилучшие методы случайной генерации тестов из известных на сегодняшний день.
Максимом на примере задачи о поиске максимального потока был также создан метод генерации тестов для программ решения графовых задач на основе генетического алгоритма. Было показано, что разработанный метод генерирует более сложные тесты, чем метод их случайной генерации, а также большинство известных методов генерации тестов для указанных задач. Для некоторых программ, реализующих, например, алгоритм Диница, тесты, построенные генетическим алгоритмом, были очень эффективными, так как по времени выполнения в несколько раз превосходили тесты, построенные другими методами.
Алгоритм Диница – один из алгоритмов решения задачи о максимальном потоке. Как и многие такие алгоритмы, он имеет внешний цикл, на каждой итерации которого алгоритм пытается добавить ещё немного потока. Его отличие состоит в том, что он на каждой итерации строит от истока к стоку сеть кратчайших по числу рёбер путей из тех рёбер, по которым ещё можно пропустить поток, и ищет максимальный поток, который можно добавить с использованием этой сети. Это сделать намного проще, чем в произвольном графе. Длина кратчайшего пути строго увеличивается от итерации к итерации, а следовательно, когда-нибудь этот процесс закончится.
С деталями борьбы Макса можно познакомиться здесь:
- Буздалов М.В. Применение генетических алгоритмов для генерации тестов, выявляющих неэффективные решения олимпиадных задач по программированию, на примере задачи о рюкзаке. Бакалаврская работа. СПбГУ ИТМО. 2009, 65 с.
- Буздалов М.В. Генерация тестов для олимпиадных задач по теории графов с использованием эволюционных алгоритмов. Магистерская диссертация. СПбГУ ИТМО. 2011, 59 с.
- Буздалов М.В. Генерация тестов для определения неэффективных решений олимпиадных задач по программированию с использованием эволюционных алгоритмов. Диссертация на соискание ученой степени кандидата технических наук. НИУ ИТМО. 2014 г., 204 с.
У читателя, естественно, может возникнуть вопрос: «А каков практический смысл предлагаемого подхода?» Ответ прост: при применении этого метода на соревнованиях может появиться дополнительная интрига. Суть предложения в следующем: соревнования проводятся, как обычно. После их завершения ко всем признанным правильными по тестам жюри решениям для каждой задачи применяется обсуждаемый метод. Возможно, что новые тесты будут сильнее исходных, что может позволить отклонить некоторые решения признанные жюри правильными. Максим обрабатывал решения вручную, но сегодня имеются все предпосылки, чтобы автоматизировать этот процесс и использовать его на соревнованиях. Изложенный подход соответствует «фазе взлома» в некоторых соревнованиях на платформе Codeforces, когда после завершения соревнования участники получают доступ к принятым по тестам составителей задач решениям и могут предложить дополнительные тесты для «убийства» некоторых из этих решений. Эти соревнования могут стать хорошим полигоном для апробации метода Буздалова после его автоматизации.
Из изложенного следует, что мой труп при решении задачи о тестировании программ так и не понадобился, а Макс стал классным учёным, решающим в том числе и задачи, сильно отличающиеся от олимпиадных.
