Как мне выполнить модульное тестирование эвристического алгоритма?

Скажем, у нас есть наш алгоритм поиска маршрута:

def myHeuristicTSP(graph):
    /*implementation*/
    return route

Теперь мы хотим проверить это:

class TestMyHeuristicTSP:
    def testNullGraphRaiseValueError(self):
        self.assertRaises(ValueError, myHueristicTSP(None))

    def testSimpleTwoNodeGraphReturnsRoute:
        self.assertEquals(expectedResult, myHeuristicTSP(input))

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

Но поскольку эвристический алгоритм, хотя он все еще детерминирован, является менее предсказуемым, просто предназначен для того, чтобы понять, как алгоритм должен работать и найти эти крайние случаи?

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

1. действительно ли решение действительно? Вы определенно хотите убедиться, что ваш алгоритм поиска маршрута не возвращает пути, которые невозможны или которые на самом деле не ведут от начала до конца. Возможно, вы не сможете доказать, что решение является идеальным, но вы должны, по крайней мере, убедиться, что возвращаемое значение действительно является решением.
2. Является ли решение "достаточно хорошим"? У вас должны быть некоторые требования, которые определяют, насколько алгоритм может быть хуже, чем идеальное решение. У вас должны быть тестовые случаи, в которых известно идеальное решение (или, по крайней мере, решение, которое считается достаточно хорошим для использования в качестве стандарта сравнения), и подтверждение того, что решение, предоставляемое алгоритмом, не хуже чем на x%.
3. Является ли алгоритм достаточно быстрым? Вы часто используете эвристический подход, когда предполагаете, что они восполняют недостаток точности, будучи намного быстрее. Чтобы убедиться в этом, вы должны измерить их время выполнения и убедиться, что они действительно работают быстрее, чем алгоритм, который получает точное решение. Измерения времени выполнения всегда немного нечетки, поэтому превышение ожидаемого времени выполнения должно быть предупреждением, а не ошибкой (когда ваша основа модульного тестирования позволяет различать предупреждения и ошибки).

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

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

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

Если вы ищете не юнит-тесты, а автоматические приемочные или интеграционные тесты, вы можете попробовать то, что @Phillip предложил в (2) или (3) .