Q&A
> 複雑な経路を求めよう
と
> 〈条件〉
の関係性が分からないのですがどう関連しているのでしょうか？
> pythonで実現可能なのであれば
答えの導出はできるがPythonで書けないという課題でしょうか？
実現したいこと
現在pythonを使用して、添付の画像のような複雑な経路を求めようとしています。
経路を作成する際の条件は以下の通りです。
〈条件〉
・START位置とGOAL位置の座標は決まっている
・2つ経路を作成する場合、2つの経路の長さが同じになるようにしたい
・経路同士が交差してはならない
・経路同士は1mm以上間隔を空けなければならない
・上記の条件を満たせば、どのような経路を通っても良いものとする。（最短でなくても良い）
発生している問題・分からないこと
上記のようなプログラムをpythonで実現したいのですが、どのようなアルゴリズムを使用すれば実現できるのかが分かりません。
pythonで実現可能なのであれば、どのようなサイトが参考になるか、どのようなアルゴリズムを使用すれば良いか等の情報を教えていただきたいです。
該当のソースコード
特になし
試したこと・調べたこと
- teratailやGoogle等で検索した
- ソースコードを自分なりに変更した
- 知人に聞いた
- その他
上記の詳細・結果
いろいろと調べたりしましたが、似たような事例を見つけられず、アルゴリズム等にも詳しくないので、まずどのようなアルゴリズムを使用すれば良いか調べてもよく分かりませんでした。
知識不足で申し訳ありませんが、もし何か情報をお持ちの方がいたらぜひご享受いただきたいです。
よろしくお願いいたします。
補足
特になし
説明が分かりづらく申し訳ありません。
>> 複雑な経路を求めよう
と
> 〈条件〉
の関係性が分からないのですがどう関連しているのでしょうか？
画像は例がある方がイメージしやすいかと思い載せたもので、基本的には<条件>を満たす経路を作成したいというのが目的となります。
画像に示した複雑な経路（緑線）は、〈条件〉を満たしている経路の一例となります。（経路の数が異なる、都合上一部カットしている等で分かりづらくなっており申し訳ございません）
> pythonで実現可能なのであれば
答えの導出はできるがPythonで書けないという課題でしょうか？
いえ、そもそも画像で示した経路は手作業（ツール）で作成したものであり、関数やアルゴリズム等を用いている訳ではありません。
そのため答えの導出等もできていない状況で、アルゴリズム等もどのようなものを使用すれば<条件>を満たせるのか調べても分からなかったため、こちらで質問させていただきました。
申し訳ありませんがよろしくお願いいたします。
特定の言語を用いた具体実装の話でないならば，質問につけるタグを python とかに限定しないほうが質問が人目に付きやすい可能性
（…とか思ったけど，例えば「アルゴリズム」とかにしたところでマイナーすぎて微妙かな？）
自分がpythonくらいしか触っておらず、他の言語での実装が自信がなかったので、今回はpythonでタグ付けさせていただきました。
もし何かプログラムを例示してくださる方がいればと思い。。
確かにもう少し分かりやすいタグを設定するべきでしたね。
アドバイスいただきありがとうございます。
回答1件
0
ベストアンサー
質問文を読んでの単なる思い付きですが……
まず START と GOAL を結ぶ経路 p( x ) を何かしら乱数などを用いて生成する手段を用意する．
ここで x は経路の形状を決めるパラメタ群である．
（例えば，経路がいくつかの点群を結ぶ折れ線だとか，点群を制御点とするパラメトリック曲線だとかであれば， x は点群の座標になる）
つぎに，既存の経路 p( x ) を，特定の長さになるように変形させる手段を用意する．
（条件を満たすように x を更新する最適化問題みたいなものになるか）
上記が用意できたならば，あとは
- まず経路を１つ適当に作る
- 経路をもう一つ作り，長さが１個目の経路と同じになるように変形させる
- 交差とか「1mm～」の条件を満たしているかをチェック．ダメなら 1. or 2. かららやり直し
という，てきとーすぎる処理をぶん回す．
（もちろん，2.の変形の処理において，交差などの条件も入れ込んで最適化することも考えられるが，難易度の面とかで，ぶん回すほうが楽かな，と）
投稿2025/12/10 01:41
編集2025/12/10 01:43総合スコア12318
なるほど、具体的にイメージを記述していただきありがとうございます！
そのような処理を実行できるプログラムをpythonで作成すれば良いのですね。
一度実現できるか自分で作成して試してみたいと思います。
またプログラム作成時に不明点が出てきたらteratailで再度質問させていただこうと思います。
ご丁寧にありがとうございました！
そんなスピーディに質問を閉じなくてもよいのでは（もうちょっとほかの話が出てこないか待てばいいのに感）．
経路の表現次第では「経路の長さ」を求めること自体の難易度が問題になりそうな気もするので，最初はそのへんに苦労しないような経路の表現を用いてやってみるのが良いのかな？ とか思う．
「ぶん回す」がなかなかうまくいかない場合には
例えば
【START と GOAL の２点を通る直線で世界を2分割し，両方の側に経路を１つずつ生成した状態から開始】
とかすれば，「交差しない」とか「1mm～」の条件を満たしやすいかもしれない．
（ただし，そういうことをすると得られる結果が似たり寄ったりになりそうだけど）
申し訳ありません、teratailではあまり多くの回答が来るイメージではないことと、一度自分の方でもプログラムを作成してから再度質問した方が良いと思い一度閉じさせていただきました。
いただいた回答で自分の方でも少しイメージができそうだったので。。
アドバイスいただきありがとうございます。
>経路の表現次第では「経路の長さ」を求めること自体の難易度が問題になりそうな気もするので，最初はそのへんに苦労しないような経路の表現を用いてやってみるのが良いのかな？ とか思う．
なるほど、まず経路の表現を工夫する必要があるということですね。
ありがとうございます。
>「ぶん回す」がなかなかうまくいかない場合には
例えば
【START と GOAL の２点を通る直線で世界を2分割し，両方の側に経路を１つずつ生成した状態から開始】
とかすれば，「交差しない」とか「1mm～」の条件を満たしやすいかもしれない．
（ただし，そういうことをすると得られる結果が似たり寄ったりになりそうだけど）
こちらもぜひ参考にさせていただきます。
プログラムを一度作成してみてまたうまくいかない点があったら再度質問を投稿させていただきますね。
ご丁寧にありがとうございます。
> プログラムを一度作成してみてまたうまくいかない点があったら再度質問を投稿させていただきますね。
あなたの今後の検討が うまくいった 場合には
可能であればその方法の話をここに自己回答の形とかで教えていただきたく．
（これ系の話は「こうやったら→こうなったよ」っていうのを知りたいので）
条件を満たすことが自明な「複雑でない」経路ペアであればなにかしら用意することは簡単だと思うので，
そこを出発点にして（常に条件を満たす範囲で）変形させていく的な方向のやり方とかもあるかもしれませんね．
（最も単純な形状から再分割を繰り返していくみたいな感じ？）
あなたの回答
tips
プレビュー
