0

これは、オプションが非常に多いという理由だけで、これらの難しいアルゴリズムの1つです。数「N」と10未満の素数のセット、つまり{2、3、5、7}を想像してみてください。目標は、1に達するまでNを分割し続けることです。いずれかのステップで、Nが指定された素数のいずれかで割り切れない場合は、次の操作を実行できます。

i）N = N-1またはii）N = N + 1

これにより、Nが均等になり、続行できるようになります。

最小限の操作で目標を達成する必要があります。

これは些細なことのように聞こえるかもしれません。つまり、「Nが任意の素数で割り切れる場合は、それを除算する」というステップをアルゴに実装できます。しかし、これは必ずしも最適なソリューションを生み出すとは限りません

たとえば、N = 134の場合：134は2で除算できます。2で除算すると、67になります。67は素数で割り切れないため、操作を実行すると、Nは66/68になり、どちらも別の操作が必要になります。したがって、合計2つの操作。

または、N = 134で、操作N = N + 1、つまりN = 135を実行する場合、この場合、1に到達するために必要な操作の合計は1です。したがって、これが最適なソリューションです。

4

1 に答える 1

2

この問題の数学的な解決策がない限り (数学的な解決策を探している場合は、math.SEがこの質問に適しています) 、問題を最短経路の問題に減らすことができます。

問題を (すべての自然数) と 1 のグラフG=(V,E)としてV = N表しE = {(u,v) | you can get from u to v in a single step }ます。

ここで、ソース (入力番号) からターゲット (番号 1) への従来の検索アルゴリズムを実行する必要があります。最適なソリューションを得るには、次のような選択肢があります。

  1. BFS - 縮小されたグラフは重み付けされていないため、BFS は完全 (存在する場合は解を見つける) かつ最適 (最短の解を見つける) であることが保証されます。
  2. ヒューリスティックA* - これも完全で最適2であり、優れたヒューリスティック関数を使用している場合は、情報に基づいていない BFS よりも高速になるはずです。

最適化に関する注意:
グラフは「オンザフライ」で作成でき、前処理として作成する必要はありません。そのためには、次のようなnext:V->2^V(ノードからノードのセットへの) 関数が必要です。next(v) = {u | (v,u) is in E}

PS複雑さのコメント：BFSソリューションは疑似多項式（入力数の最悪のケースで線形）です。これは、開発する「最高の」頂点がn+1であるため、ソリューションは基本的にO(n)最悪のケースです-ただし、より深い分析でより良い制限。

(1) +1/-1 のみを op としてカウントすることに関心がある場合は、分割を終えた後にターゲットに基づいてエッジを作成できます。
(2)許容可能なヒューリスティック関数が使用されている場合。

于 2012-09-21T14:02:41.050 に答える