問題タブ [hilbert-curve]

Codility から次のタスクにアプローチする方法についてヒントを教えてください: https://codility.com/programmers/task/hilbert_maze/

迷路を生成し、BFS を使用して最短経路を検索することで、最短経路を見つけることができますが、最悪の場合の時間の複雑さは O(N) であると予想されるため、これは正しい方法ではないと思います行く。BFS の時間計算量は O(|V| + |E]) で、V は頂点の数、E はエッジの数です。たとえば、N = 3 の場合、サイズが 17x17 のグリッドがあり、3 ステップだけではパスを見つけることができないことは直感的に明らかです。

したがって、示された時間計算量が間違っていて、M^2 のようなものである必要があるか、グラフ アルゴリズムを使用せずに 2 点間の距離を単純に計算するための簡単なトリックがあります。与えられた 2 点のヒルベルト距離を計算するためのアルゴリズムをいくつか見つけました (ここで必要な場合)。これはビット操作などを使用しますが、まったく理解できませんでした。また、このタスクの目標は、既存の式を使用せずに距離を計算する方法を自分で見つけることだと思います。

このタスクを解決し、さらに私を助けてくれる人はいますか? ありがとう！

ヒルベルト キューブに関するウィキペディアの記事には、ヒルベルト曲線上の任意の点との間で任意のインデックスをエンコード/デコードする関数が含まれています。これらのアルゴリズムは一定時間ではありません。曲線上の実際のポイント (および、おそらくいくつかの必要な状態) を指定して、次のポイント (および次の状態) を生成する定数時間アルゴリズムはありますか?

正式には、 を適用するたびにヒルベルト曲線の次の点が得られ、それが最適であるように、 typeStateと tupleが必要です。これは、ウィキペディアで提示されているアルゴリズムには当てはまらない可能性があります。ここにあるインクリメンタル計算の機会。図：(initialState, nextState) :: (State, State -> ((Nat, Nat), State)nextStatenextState

空間データを 1 次元間隔にマッピングします。まず、ポイントを接続するために、空間充填ルベーグ曲線 (または Z 曲線) を使用します。これは機能し、gnuplot を使用すると次のプロットが得られます。

次に、ルベーグ曲線をヒルベルト曲線に変換します。しかし、うまくいきません。これは出力です：

だから、最初はうまくいくようです。しかし、しばらくすると奇妙なことが起こり、その理由がわかりません。

これが私のコードです：

私が見逃したものを見た人はいますか？

巡回セールスマン問題の解をヒルベルト曲線プログラムで近似しようとしています。私はアプレットを使ってそれをしなければなりません。コードにマトリックスを追加する方法と、アプレットに座標を表示する方法を教えてください。複数のフレームを持つ必要はありません。

コードは以下のとおりです。

マトリックスに都市を設定し、都市に到達したら都市間に線を引き、そこに到達するための最短経路を見つける必要があります。