Я хотел бы предвосхитить это, что этот вопрос похож, но мой вопрос не связан со случайностью, а является просто привередливым детерминизмом, поэтому ответ «использовать известное семя» на самом деле не применим. Аналогично, этот вопрос похож, но, опять же, я не ожидаю, что алгоритм когда-нибудь потерпит неудачу - я просто не знаю, каким образом он будет правильным.
Этот вопрос возник во время тестирования графовых алгоритмов. но ни в коем случае не ограничен ими. Некоторые алгоритмы, такие как A *, могут иметь несколько правильных ответов. В зависимости от вашей конкретной реализации вы можете получить любой из нескольких ответов, каждый из которых одинаково корректен. Однако это может затруднить их тестирование, поскольку вы не знаете, какой из них он выплюнет раньше времени, и очень сложно вычислить ответы вручную.
В моем конкретном случае я справился с этим, изменив Floyd-Warshall так, чтобы он выплевывал все возможные кратчайшие пути, и потратил время на ручное тестирование этого. У него было то преимущество, что оно само по себе было хорошей чертой. Затем я мог бы протестировать другие функции с точки зрения известных правильных путей из FW (если возвращаемый путь - это любой из путей, возвращаемых FW для этой пары начала / конца, это правильно). Конечно, это работает только для плотных графов из-за того, как работает FW, но это все же приятно.
Однако это не всегда может быть жизнеспособным для всех алгоритмов с этой характеристикой. Пока что лучший ответ, который я придумал, это проверить характеристики правильного ответа, а не самого правильного ответа. Чтобы вернуться к алгоритмам кратчайшего пути, вы можете сравнить стоимость возвращенного пути с известной правильной стоимостью и убедиться, что путь действителен.
Это работает, но может быть риск того, что все будет проверено неправильно, чем больше критериев правильности, особенно если проверка сама по себе сложна (например, когда существуют правильные алгоритмы , проверка минимального связующего дерева - известная трудная проблема; вероятно, сложнее, чем создание самого MST), и в этом случае вам теперь необходимо тщательно протестировать код тестирования. Хуже того: по-видимому, вам нужно создать MST для проверки алгоритма проверки MST, чтобы у вас был отличный сценарий, в котором ваш MST-тест основан на работающем алгоритме MST-проверки, а тестирование алгоритма MST-проверки основано на работе кода генерации MST.
Наконец, есть «дешевый способ», который заключается в том, чтобы наблюдать результаты, проверять их вручную, а затем жестко программировать тест, чтобы проверить только что проверенный результат, но это не очень хорошая идея, поскольку вам, возможно, придется пересматривать тест каждый раз, когда вы немного измените реализацию (чего и следует избегать при автоматическом тестировании).
Очевидно, что ответ зависит от того, какой именно алгоритм вы тестируете, но мне было интересно, есть ли «лучшие практики» для проверки алгоритмов, которые имеют несколько определенных, детерминированных «правильных» выходных данных, но эти точные правильные выходные данные трудно знать заранее, и, возможно, трудно даже проверить после факта.
источник
Ответы:
Я не уверен, что вы пытаетесь проверить правильность свойства, и это вызывает вашу двусмысленность.
Алгоритмы графа направлены не на поиск кратчайшего пути (это побочный эффект), а на минимизацию или максимизацию некоторой функции стоимости, определенной на множестве ребер и вершин. Таким образом, вы можете проверить правильность решения, проверив окончательное значение этого функционала и заявив, что первый и последний узлы - это те, которые действительно необходимы.
Если вы можете предварительно вычислить окончательное значение функции стоимости для каждого возможного пути (обычно нереально), то вам просто нужно проверить, что стоимость решения, предоставляемого тестируемой реализацией, равна минимальной стоимости среди этого набора (абсолютное сравнение ). Если у вас «просто» есть алгоритм и / или реализация «золотого стандарта», то вы должны сравнить стоимость его вывода с стоимостью тестируемого алгоритма (относительное сравнение)
Например, настройка наивного теста будет:
Если вы хотите узнать больше об оптимизации на основе графов, вы можете взглянуть на публикации Юрия Бойкова здесь , хотя и в другом контексте (проблемы с компьютерным зрением).
источник
Я думаю, что прямой ответ на ваш вопрос - выбрать лучшие тестовые случаи. Мне интересно, какие тестовые примеры вы используете. Используемые вами графики могут быть графиками CANNED, где человеку относительно легко определить ожидаемый ответ. Попробуйте выяснить «крайние» случаи, которые вы хотите быть уверенными в том, что ваш алгоритм обрабатывает, и создать постоянный граф для каждого из конкретных крайних случаев, который легко вычислить для человека. Например, в случае алгоритма Djikstra вы, вероятно, можете создать несколько графиков 5x5 или 7x7, которые покрывают все ваши граничные случаи, даже если ваша реальная система может иметь размер 500x500.
Затем, в качестве окончательной проверки работоспособности, вы можете создать более реалистичный график или два тестовых примера. Но в любом случае, я думаю, что у sansuiso есть место, где указано, что вы должны быть уверены, что проверяете правильное свойство.
источник