ここで2つの懸念を分離する必要があります。近似アルゴリズムの品質とそれらのアルゴリズムの実装の正確さ。
近似アルゴリズムの品質をテストすることは、通常、ソフトウェア開発で使用される単体テスト方法には役立ちません。たとえば、問題の実際のサイズを表すランダムな問題を生成する必要があります。解決できない大きなインスタンスのアルゴリズムの品質を判断するために、上限/下限を取得するために数学的な作業を行う必要がある場合があります。または、既知または最もよく知られている解決策がある問題テストセットを使用して、結果を比較します。ただし、いずれの場合も、単体テストは近似アルゴリズムの品質を向上させるのにあまり役立ちません。これは、最適化と数学に関するドメイン知識が役立つ場所です。
実装の正確さは、単体テストが本当に役立つところです。ここでおもちゃサイズの問題を使用して、既知の結果（手動で解決するか、コードで慎重に段階的にデバッグすることで検証）をコードが生成するものと比較できます。ここでは、小さな問題があるだけで十分であるだけでなく、テストが高速に実行され、開発サイクル中に何度も実行できるようにすることが望ましいです。これらのタイプのテストは、アルゴリズム全体が正しい結果に到達していることを確認します。コードの大部分をブラックボックスとしてテストしているため、単体テストと統合テストの間のどこかにあります。しかし、私はこれらのタイプのテストが最適化ドメインで非常に役立つことを発見しました。このタイプのテストで行うことをお勧めすることの1つは、乱数ジェネレーターの固定シードを使用して、アルゴリズムのすべてのランダム性を削除することです。これらのテストは常に決定論的な方法で実行され、100％の時間でまったく同じ結果が得られる必要があります。また、アルゴリズムの下位レベルのモジュールで単体テストを行うことをお勧めします。グラフ上の円弧に重みを割り当てるメソッドを分離し、正しい重みが割り当てられているかどうかを確認します。目的関数値の計算関数を分離し、それを単体テストします。あなたは私の主張を理解します。
これらのスライスの両方をカットするもう1つの懸念は、パフォーマンスです。小さなトイプロブレムでパフォーマンスを確実にテストすることはできません。また、動作中のアルゴリズムのパフォーマンスを大幅に低下させる変更をすぐに実現することが非常に望ましいです。アルゴリズムの実行バージョンを取得したら、パフォーマンスを測定し、それを自動化してパフォーマンス/統合テストにする、より大きなテスト問題を作成できます。時間がかかるため、これらの実行頻度を減らすことができますが、少なくとも、リファクタリング中またはアルゴリズムへの新機能の追加中に、新たに導入されたパフォーマンスのボトルネックが早期に通知されます。