無限ループ例外

Question

マップを折りたたみながら無限ループの例外を生成しようとしています。

module X=Map.Make(Int) 

問題は次のようになります。関数 "f"が無限ループにならない最大ランクを決定します。 （最初のペアのための

（1,2）=>（1）= 2今、私はみますF F：私たちは[(1,2);(2,3);(5,6);(6,7);(7,6)]

機能は、このようなマップのすべてのペアを通過するマップを持っています2）= 3（ペア（2,3）に存在するように）今私は試してみよう3 =>キーが見つからない= 3だからランクは関数fを呼び出すことができる回数です（5,6）=> f（5）= 6試してみるf（6）= 7（ペア（6,7）が存在する）試してみるf（7）= 6（ペア（7,6）が存在する）f（6）= 7はループに入ります。これは既にペアを使用していますので大文字小文字は0です。

結論：それは無限ループに入らない場合は、関数fの最大ランクは2

は、どのように私は私の例外を定義することができているだけでなく、私はこの問題を解決するために使用することができますどのような推論？

Answer 1

タスクを理解するのにしばらく時間がかかりました...それは基本的に私にWorld Chainゲームのルールに似ています。より科学的な記述は、与えられたノードから始まるsimple pathの長さを見つけることです。

何推論私はする最も簡単な方法の問題

を解決するために使用することができます

exception Loop_detected 

：私は私の例外

を定義することができます。これは、シンプルでどのように

ループを検出すると、すべての訪問先ノードのセットを維持することになります。すぐに、既に見たノードにヒットすると、例外（例：if Ints.mem dst visited then raise Loop_detected）で救済する必要があります。あなたは次のように定義されたint秒間Intsセット・モジュールを作成することができます。

module Ints = Set.Make(Int) 

全て訪問したノードのセットを使用してループを検出するための唯一の方法で一般的ではないです。これにはTortoise and Hareアルゴリズムを使用できます。また、StepanovのProgramming of Elementsの書籍、Transformations and their Orbitsの章にも正式に記載されており、オンラインで入手できます。