質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.33%

  • アルゴリズム

    428questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

フリーグリッドのルート探査

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 2
  • VIEW 478

efcode

score 392

フリーグリッドのルート探査について助言が欲しいです。
既にライブラリやアルゴリズムについて書かれている物がある場合は教えて欲しいです。
イメージ説明
初期位置と最終到達座標が与えられます。
半径(r)のある物体が移動します。(1)
位置は実数(浮動小数)で表されます。
マップ上には厚みのない壁があり、整数座標の位置にP(座標)とV(ベクトル)で表されます。(2)(3)
壁の端は半径rの分だけ離れて通過します。(4)(5)
計算量や計算の難易度により、多少めり込んでも構いません。(4')
最悪壁から離れなくても構いません。(4'')

手作業でおおよその目標ルートを(4)(4')と(5)で書いてみました。
最終的にこの赤点を辿る順番で得られたらいいと思っています。
マップのサイズは可変でここでは単純に小さく示していますが、とても広いマップを想定しています。

・単純な上下左右移動による検索
アルゴリズムとして確立した物があるので、この検索自体は出来るのですが問題があります。
上側を通るルートは(0,0)(1,0)(1,1)(2,1)(2,0)...
となりますが、最終的に得られたステップ数と移動ルートの長さが(3)の壁を回り込む様な場合に正しく得られない事です。
最短を得たい場合に全てのルートを取得した上で、赤点を算出して全てのルートの長さを得なければなりません。
また、(2)壁の下の2x2の様な同じコストのルートがある場合など、赤点を正しく作る方法が思いつきません。
この方法は、到達できるかの判定用には使えるのですが、もう少しエレガントな方法でルートを見つけられないかなと思っています。

・壁とベクトルの衝突判定
始めにスタート地点から目標地点までの直通ベクトルに対して全ての壁との衝突判定をして、ヒットしていたら分割して行くという方法も考えたのですが、
(4,3)(7,4)(8,5)の壁がまずヒットし...と仮の中間点を追加して行きつつそれらを結ぼうと思っても、(7,4)の壁から座標(7,3)辺りに中間点を置くとした場合に、上のルートにならない状況が考えられてしまったりしてどうしたものかと思っています。

(2018/06/07)追記
重要なのは壁の端というのは分かっていたのですが、「どの壁の端か」を特定する為に、ベクトルの衝突(交差)という方法を用いようとしました。
追加した中継点が必要か不必要かの判定も必要で、「端点か角」の中継点が有用であるのも直感的に理解は出来ます。
「上下移動による検索」のルート探査を行った上で、中継点がどの領域と接しているかによってどっちのルートの中継点になるかを判別可能である、というのは上の文章を書いてから気がつきました。(下図)
イメージ説明
灰色はルート1とルート2の共有ルートです。
色(ルート)に属していない中継点は検索の対象から外せます。
ルートであるのに色の付いていない所は、同じコストの別ルートがある場合。(だけど、条件としてはこれでは駄目で、route2と書かれた右上の白い場所が壁で囲まれていた場合、この条件では破綻します)

色の上であるのに端点としては使えないものがあるが、条件が分からない。(灰色に青い点が付いた中継点)
ベクトルの衝突判定は、端点を出す為ではなく、中継点を接続した時に有効かどうかを判定する為に使えそう。

まだ整理が付いていないですが、まだまだ自分の理解が浅いというのを痛感しています。
時間もなく、考える頭の許容量も目一杯で、分不相応な課題に取り組んでいる事も痛感しています。
議論の場として機能してほしいのですが、ベストアンサーを付けて終了しなければならないのかとも思っていて不安です。もう少し考える時間がほしいと思っています。私のわがままなのですがすいません。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

+2

質問者さんが真に望んでおられる最適解(幾何的な最適解)ではない「ナンチャッテ」な方法なのですが、アルゴリズムが単純なので一例としてコメントしてみます。

ご質問にある

単純な上下左右移動による検索

これは格子上にある隣接したセルに「出発点からの上下左右での移動回数」を記録していき最短経路を大まかに求める手法だと思います。そこに次のような工夫をちょこっと追加してみます。

  • 格子の分割を少し細かくする

  • 斜め方向の移動も可能とする
    上下左右の移動距離を1と見做しますが斜め方向は2の平方根としておきます。

  • セルの値(距離)の決定方法を若干変更する
    オリジナルのアルゴリズムでは「隣接したセルがまだ未探索なら、そのセルの値を現在のセルの値+1と定める」という具合に未探索のセルの値を決めますが、斜め方向の移動を導入するにあたり、「隣接したセルが既に探索済みであっても、より短い距離と見做せるときは値を書き換える」ようにしてみます。

このような方針で単純探索すると以下のような経路が求まります。

イメージ説明

グレーは壁から一定距離のセルを「通過不能」と記録していることを表します。淡い色がスタート地点からゴールに向けて計算した距離を表します。

この結果は本当に求めたい「真の幾何的最短距離」ではありませんが、「最短距離のルートに概ね近い経路」を表しているとは言えると思います。

このようにして仮の経路を決定した後、ゴールからスタートに向けて
p1, p2, p3, ...
という経路上の各点を吟味し、p1->p2の幾何的な距離よりp1->p3の距離が近く、かつp1->p3に障壁がない場合はp2を削除する・・・と言った方針で途中の経路点のうち「真の最短経路から外れている点」を取り除いてみてはどうでしょう?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/06 13:19

    すみません、回答した後に思ったのですが、
    斜め方向は本質的には不要な気がしました。ポイントは「格子を少し細かくする」点だと思います。

    キャンセル

  • 2018/06/06 20:02

    回答ありがとうございます。
    半分のサイズは考えたのですが、更に細かくすることで近似値は出せるみたいですね。
    大変参考になりました。すいませんがもう少し様子を見させてください。

    キャンセル

  • 2018/06/06 20:14 編集

    この問題は色々なアプリ―チがある気がします。自分の回答は分割のため大きなマップだとマップを埋める手数が増えてしまう点が問題になると思います。最低限1マスを3分割しないといけないのですがそうすると全体の探索ステップは約9倍になります。3分割で充分「本当の最短経路が特定できるか」という問題もあるかも知れません。(自分には難しすぎてYES/NOがわかりません)

    なお、質問者さんが挙げておられるように「分割せずに可能な経路を求めその経路各々に対して幾何的な最短距離を求めそれを最終経路として比較する」のも悪くない方法であると思いました。大きなマップの場合、計算量的には有利な気がするのです・・・

    キャンセル

+2

トポロジーを利用して可能な経路を探す

可能な経路を考える場合、トポロジーを利用すると問題が単純化(見えやすく)できます。
図1と図2は形の異なる壁ですが、壁に沿ってSからGに進めるという性質は同じなので、図1の壁と図2の壁は同相(topological に同じ)です。
可能な経路は、経路を構成する要素を同相な図形で取り換えても変わりません(topologicalな意味で変わらなという事で、経路の距離が同じという事ではありません)。

質問の図(図3)の構成要素(外側の壁、中央の障害物)を同相な図形で取り換えてみたのが図4です。
可能な経路は、中央の障害物を右側から避けるルートと、左側から避けるルートの2つしか無いことが判ります。

障害物の数が増えると可能な経路が指数的に増加しますが、既に見つかっている経路うちの最短距離を超えたところで探索を止める事ができるので、極端な計算量爆発は起きないと思います。

最短経路については、Computational Geometry のスライドが参考になると思います。

経路を(可能な範囲で短くなろうとする)ゴムバンドと考えるのは直観的ですし、実用的です。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/07 20:50

    ありがとうございます。
    トポロジーがここで適用できるというのは盲点でした。
    この例のマップでは「ふたつの経路がある」というのを「上下左右移動の検索」を使って導き出せそうだと、おぼろげながら認識しつつあります。
    上下左右検索は使えないのではなく、他の要素と絡めて材料としては積極的に使っていくべき要素なのかもしれません。
    私の理解力が低い為、受付中のままをお許しください。

    キャンセル

check解決した方法

0

(2018/06/13)自己解決
上下左右の検索は、今回のこの例のような格子状に壁がある限定的な条件の場合には使えるかもしれないが、汎用的な検索ではない。
壁の端点は検索対象として使え、壁の末端と角を考えるのが良い。
中継点が決まれば、スタートからゴールまでの間に中継点を経由し、経路が壁に遮られず、同じ中継点を二度通過しない条件で組み合わせを作り、その内の最短経路を探せば目的の経路が得られる。

という所で計算をさせてみました
ルート検索と条件と不具合
中継点19個で40程度の経路が10秒ほど掛かって検索できた。その内の求めていたふたつの経路を表示してある
角と端点を計算対象にして、実際に有効な点(水色)以外にも使わない点(桃色)もあって、計算効率はあまり良くない
経路の壁との衝突判定が今ひとつしっくりこない為、端点から端点までが同じ座標の場合に経路が結べない不具合がある(右側の赤点同士の経路が出来ない)
経路を結ぶ場合は、端点の場合はrだけ離れた位置、角の場合はXとY共にrだけ離れた位置、を結ぶようにしてある(下側の赤線が経路)

壁にめり込んでしまう為、経路点の微調整が必要だけどとりあえずの目標は達成できました。
完璧に理想形にするにはまだまだ錬らなければならず、頭の整理と条件の精査が必要のようです。

中継点が少し増えただけで計算回数が増大する為、無闇に中継点を増やせない
半径rがゼロの場合に壁と接近しすぎていて経路が見つからない
最短ステップが必ずしも最短経路ではない為、経路の長さをチェックしながら、最短で見つかった物より長い経路を排除して短い経路の物だけを残して計算する必要がある

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.33%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • アルゴリズム

    428questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。