Тестирование (детерминированные) алгоритмы с несколькими или трудно доказать правильные правильные ответы

11

Я хотел бы предвосхитить это, что этот вопрос похож, но мой вопрос не связан со случайностью, а является просто привередливым детерминизмом, поэтому ответ «использовать известное семя» на самом деле не применим. Аналогично, этот вопрос похож, но, опять же, я не ожидаю, что алгоритм когда-нибудь потерпит неудачу - я просто не знаю, каким образом он будет правильным.

Этот вопрос возник во время тестирования графовых алгоритмов. но ни в коем случае не ограничен ими. Некоторые алгоритмы, такие как A *, могут иметь несколько правильных ответов. В зависимости от вашей конкретной реализации вы можете получить любой из нескольких ответов, каждый из которых одинаково корректен. Однако это может затруднить их тестирование, поскольку вы не знаете, какой из них он выплюнет раньше времени, и очень сложно вычислить ответы вручную.

В моем конкретном случае я справился с этим, изменив Floyd-Warshall так, чтобы он выплевывал все возможные кратчайшие пути, и потратил время на ручное тестирование этого. У него было то преимущество, что оно само по себе было хорошей чертой. Затем я мог бы протестировать другие функции с точки зрения известных правильных путей из FW (если возвращаемый путь - это любой из путей, возвращаемых FW для этой пары начала / конца, это правильно). Конечно, это работает только для плотных графов из-за того, как работает FW, но это все же приятно.

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

Это работает, но может быть риск того, что все будет проверено неправильно, чем больше критериев правильности, особенно если проверка сама по себе сложна (например, когда существуют правильные алгоритмы , проверка минимального связующего дерева - известная трудная проблема; вероятно, сложнее, чем создание самого MST), и в этом случае вам теперь необходимо тщательно протестировать код тестирования. Хуже того: по-видимому, вам нужно создать MST для проверки алгоритма проверки MST, чтобы у вас был отличный сценарий, в котором ваш MST-тест основан на работающем алгоритме MST-проверки, а тестирование алгоритма MST-проверки основано на работе кода генерации MST.

Наконец, есть «дешевый способ», который заключается в том, чтобы наблюдать результаты, проверять их вручную, а затем жестко программировать тест, чтобы проверить только что проверенный результат, но это не очень хорошая идея, поскольку вам, возможно, придется пересматривать тест каждый раз, когда вы немного измените реализацию (чего и следует избегать при автоматическом тестировании).

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

LinearZoetrope
источник
3
Если язык позволяет это, вы можете доказать его правильность вместо тестирования
miniBill
Там много текста, но нет вопросов. Итак, что именно вы спрашиваете?
BЈовић
@ BЈовић "Как я должен тестировать реализации алгоритмов с несколькими и / или трудными для проверки правильных результатов?" Я не уверен, как сделать это намного яснее, извините. Я допускаю, что это может считаться немного широким в зависимости от вашей точки зрения, но я не думаю, что это неопределенно.
LinearZoetrope
Я до сих пор не понимаю. Ваш алгоритм не зависит от случайности, и все же он может давать разные результаты. Это не имеет смысла вообще. Каждый алгоритм для заданных входов должен иметь одинаковые выходы. И это то, что сделано и проверено в модульных тестах. Даже алгоритм в статье вы связаны.
BЈовић
@ BЈовић Конечно, это детерминированный, но он также очень чувствителен, например, порядок, в котором граф возвращает наследников узла. Это может вызвать эффект бабочки. Если вы поместите вершину A в стек перед вершиной B, вы получите другой результат, если оба приведут к кратчайшему пути. Использование библиотечных функций, таких как нестабильные сортировки или мини-кучи, только усугубляет проблему.
LinearZoetrope

Ответы:

5

Я не уверен, что вы пытаетесь проверить правильность свойства, и это вызывает вашу двусмысленность.

Алгоритмы графа направлены не на поиск кратчайшего пути (это побочный эффект), а на минимизацию или максимизацию некоторой функции стоимости, определенной на множестве ребер и вершин. Таким образом, вы можете проверить правильность решения, проверив окончательное значение этого функционала и заявив, что первый и последний узлы - это те, которые действительно необходимы.

Если вы можете предварительно вычислить окончательное значение функции стоимости для каждого возможного пути (обычно нереально), то вам просто нужно проверить, что стоимость решения, предоставляемого тестируемой реализацией, равна минимальной стоимости среди этого набора (абсолютное сравнение ). Если у вас «просто» есть алгоритм и / или реализация «золотого стандарта», то вы должны сравнить стоимость его вывода с стоимостью тестируемого алгоритма (относительное сравнение)

Например, настройка наивного теста будет:

  1. Вычислить все возможные пути между Va и Vb в тестовом графе с помощью жадного алгоритма.
  2. Вычислите функцию стоимости (например, длину, если все веса ребер равны 1) для каждого из этих путей и найдите минимальное значение.
  3. Примените тестируемый алгоритм.
  4. В своем модульном тесте сделайте утверждение, что стоимость стоимости протестированного алгоритма равна минимуму жадных решений.

Если вы хотите узнать больше об оптимизации на основе графов, вы можете взглянуть на публикации Юрия Бойкова здесь , хотя и в другом контексте (проблемы с компьютерным зрением).

sansuiso
источник
Я проголосовал, но я подожду немного, чтобы принять. Это «тест на характеристики правильного ответа», о котором я упоминал в вопросе. Проблема всегда в том, чтобы убедиться, что вы проверяете правильные вещи. Например, в тот момент я проверял возвращаемую стоимость и проверял, что путь верен. Конечно путь был действительным! Это был только начальный узел! Поэтому мне пришлось изменить тесты, чтобы убедиться, что сам путь действительно имеет возвращенную правильную стоимость. Глупая ошибка, конечно, но чем больше таких взаимодействий, тем больше вероятность их появления.
LinearZoetrope
@ Jsor, с моей точки зрения, это преимущество постоянного улучшения тестирования: вы не можете сначала выяснить все свойства корректности решения, а затем однажды потерпеть неудачу, улучшить свой тест и так далее.
Sansuiso
В этом ответе рекомендуется проверять характеристики правильного ответа, но важно выбрать, какие характеристики дают хороший тест. В этом примере проверка того, что ответ является путем от A до B и что функция стоимости равна минимальному значению, дает вам два критерия, которым будут удовлетворять все правильные ответы, в то время как никакие неправильные ответы не будут удовлетворять обоим критериям. Если бы этот ответ еще не был дан, я бы порекомендовал нечто подобное. Правда, зачастую нелегко узнать, какие характеристики нужно проверить.
Дэвид К
0

Я думаю, что прямой ответ на ваш вопрос - выбрать лучшие тестовые случаи. Мне интересно, какие тестовые примеры вы используете. Используемые вами графики могут быть графиками CANNED, где человеку относительно легко определить ожидаемый ответ. Попробуйте выяснить «крайние» случаи, которые вы хотите быть уверенными в том, что ваш алгоритм обрабатывает, и создать постоянный граф для каждого из конкретных крайних случаев, который легко вычислить для человека. Например, в случае алгоритма Djikstra вы, вероятно, можете создать несколько графиков 5x5 или 7x7, которые покрывают все ваши граничные случаи, даже если ваша реальная система может иметь размер 500x500.

Затем, в качестве окончательной проверки работоспособности, вы можете создать более реалистичный график или два тестовых примера. Но в любом случае, я думаю, что у sansuiso есть место, где указано, что вы должны быть уверены, что проверяете правильное свойство.

Замочить
источник