4

私はnearfieldscannerに取り組んでおり、スキャナーヘッドの最短経路を取得する方法を見つける必要があります。

一度に13ポイントを使いたいとしましょう。

  • 次に、スキャナーから現在の位置（point0）を取得し、最も近いポイント（Point1）を探します。
  • これでPoint1が現在の位置になり、point1-（point2）に最も近いポイントを探します。
  • これで、point2が現在のポイントになります。

オフコースこれは実際には最短経路ではありません。

スキャナーは一度に25ポイント以上を処理できる必要があるため、順列はオプションではありません。1cm移動するのに0.45秒かかり、表面はほとんど10x15cmです。

主な目標は、時間を稼ぎ、スキャンを高速化することです。

これは、C＃またはMatlabで実行する必要があります。

これは可能ですか？

4

1 に答える 1

0

考えられるすべての組み合わせを総当たりにする以外に、数学的な「解決策」はありません。
http://en.wikipedia.org/wiki/Travelling_salesman_problem

「良い」解決策 (遺伝的アルゴリズムなど) を見つけるためにさまざまなアルゴリズムを試すことができますが、最良の解決策が見つかったかどうかはわかりません。

SO については、What is an NP-complete in computer science? を参照してください。例えば

時々編集 して、最善の解決策があるかどうかを判断できます（すべてを試した後を除く）。しかし、これらはまれな特殊なケースです。パスの「長さ」が各ポイントの最短距離の合計に等しい場合、最適なパスが見つかりました。すべてのポイントが一直線上にあるように、1-2-3-n になります。しかし、通常、より良い解決策があるかどうかを知らずに、最良の解決策ではないものを見つけることしかできません。

EDIT2 アイデアとして：主な目標がいつでも「無駄にする」ことではない場合、私は次のようにします：最初のポイントを選択し、スキャナーを移動させます。スキャナの移動を開始します。スキャナが移動している間 (別のスレッド)、NN アルゴリズムでパスを計算します。パス上でモンテカルロアルゴリズムを実行して、より良いものを見つけます。スキャナーが最初のポイントに到達したら、MC アルゴを停止し (スキャナーは MoveCompletetion を通知する必要があります!)、パスから最初のポイントを新しいスキャナー ターゲットとして取得します。最後のポイントに到達するまで、前の手順を繰り返します。
これにより、とにかくスキャナーが移動するために必要な時間を計算するためだけに使用しています。また、常に NN パスをベースとして使用するため、悪化することはありませんが、時には (多くの場合?) 改善されることもあります。このアルゴリズムは並列で簡単に実行できるため、マルチコア マシンでより良い結果が得られます。

于 2012-11-26T10:24:04.557 に答える