當正確輸出未知時有效驗證程序邏輯的方法

Question

在今年Google Code Jam的資格輪迴中遇到「Djikstra」問題時，我遇到了試圖驗證我的程序的問題。我用來完成這種任務的標準方法是編寫兩個以完全不同的方式完成相同任務的程序。然後你在輸入上運行這兩個。如果兩個程序之間的輸出不同，則知道一個或兩個程序中存在錯誤。這種方法的缺點是程序員必須創建兩個程序，這樣纔能有效地將時間加倍。

與編寫程序的多個版本並運行它們相比，是否有更好/更有效的方法來驗證程序是否正確？

請注意，只有當正確的輸出未知時纔會出現此問題並且您無法生成驗證輸入輸出集。如果你知道先驗對於任何給定的輸入組應該是什麼輸出，那麼很容易驗證程序。所以，這個問題只適用於你不知道正確輸出應該是什麼的情況，你只知道程序應該執行的過程的規範。

在Dijkstra問題的情況下，我可能寫了一個「測試數據生成器」，它將從輸出向後生成一個已知的輸入狀態。通過這樣做，我可以通過編寫第二個程序來創建測試數據集，但是這個程序本來比解算器要簡單得多，因此比編寫兩個解算器要少得多，但是爲了爭論起見，讓我們假設這個選項不可用。

Answer 1

看不到更好的測試方式。通常其中一個程序應該是一個蠻力算法，您可以確信在任何輸入集上都能正確輸出。然後你確認具有最佳記憶和時間複雜性的程序給出了相同的輸出（你沒有提及它們以何種方式不同，但我認爲這就是你的意思）。