六角形のフィールドで構成されるマップがあります。このマップにはポーンがあります。彼はどの場所にも 2 回訪れることはできません。繰り返しなしですべての可能なパスを見つけるアルゴリズムの複雑さはどれくらいですか? (基本的にすべての可能なパスを見つけます。すべてのフィールドを通過する必要はありません。ポーンがコーナーにぶつかる可能性があるため、ha が移動できる限り進みます)。
3 に答える
1
最初に、与えられた n フィールドのマップと与えられた開始位置 (つまり、構成と開始位置のために特別に設計されたアルゴリズム)に対する答えの境界: O(n) (孤立したヘックスがある場合は O(1)) から O(e ^n)。
つまり、マップがヘクスの行である場合、n の値に関係なく、開始位置が行の最後にある場合は 1 つのパスしかなく、それ以外の場合は 2 つのパスしかありません。マップがヘクスの円である場合、パスは常に 1 つです。一方、マップの大部分が接続されたヘクスの「正方形」である場合、パスの数は指数関数的に増加し、すべてのパスを見つけるアルゴリズムはそれより速く進むことはできません (パスが何らかの形で明らかであっても、それでもそれらを出力します）。
マップの構成と開始位置もアルゴリズムの入力である場合、質問はより困難になります。理論的には、アルゴリズムは最初にマップを「分析」して、マップが十分に「具体的」であるかどうかを確認できます (たとえば、マップは繰り返しパターンを持つことができます。オズワルドのアルゴリズムよりも優れたマップに進みます。
接続されたヘックスで構成される「平均的な」マップの場合、パスの数は指数関数的であるように見えます (厳密な証明はありません)。そのため、時間によるアルゴリズムの複雑さも指数関数的です (改善できず、オズワルドのアルゴリズムはその限界に達します) ）。平均的なランダム マップ パスの指数の正確な値は評価が難しく、おそらく必要ありません。
于 2013-10-25T07:41:15.220 に答える
0
問題を正しく理解していれば、ランダム マップ上で、このアルゴリズムの複雑さは、このマップの答えがO(x)どこにあるかということになります。x
于 2013-10-25T00:35:11.730 に答える