締切済み 正五角形の最短シュタイナー問題 2009/05/29 01:58 一辺が1の正五角形の頂点を結ぶ最短経路は図のようになるそうですが、実際に最短経路の長さはどうなるのでしょうか? 画像を拡大する みんなの回答 (1) 専門家の回答 みんなの回答 Tacosan ベストアンサー率23% (3656/15482) 2009/05/29 02:11 回答No.1 適当に座標を与えれば, Q の座標に関する最小化問題となる. それを解けばいいはず. 通報する ありがとう 0 広告を見て他の回答を表示する(0) カテゴリ 学問・教育数学・算数 関連するQ&A 最短路問題について はじめまして。 「データ構造とアルゴリズム」を独学で勉強中の学生です。 当方、周りより指導していただける環境が無く どうにも行き詰まってしまったのでここに書き込みをさせていただきました。 お聞きしたい問題なのですが 「最短路問題について問題の定義と解法(アルゴリズム)を説明せよ。次に図1においてpから全ての頂点への最短路を求めよ。」 というものです。 * 図1はhttp://www.geocities.co.jp/Hollywood-Stage/3151/g/g.gifにupしてあります。 最短路問題を解く方法としてダイクストラのアルゴリズムやFloydのアルゴリズムがありますが、これらは書籍などを参考にして理解しているつもりです。 しかし実際、問題を解く手順といいますか、解答を書くことができないのでどなたかおわかりになる方がいらっしゃいましたらご指導をいただきたいと思い書き込みをさせていただきました。 学習不足で怠慢な学生の質問で大変申し訳ありませんが ご指導のほどよろしくお願いいたします。 最短距離を求める問題(ダイクストラ法)の原理 グラフ(経路)の情報があり、それを用いて最短距離を探索するアルゴリズムにダイクストラ法というものがあります。 このアルゴリズムでは常に正しい解を導けるということなのでしょうか。調べてみると負の距離があったらダメというのがありましたが、これは除外しての話ですが。 また、このアルゴリズムがなぜ正しいだろうと思えるのかについて理解できればなんとなくわかるような気がします。そこで、wikipediaを読んでみたのですが、さっぱり分かりませんでした。ちょっと引用します。 ”最短経路問題は、ビー玉と紐を用いて解くことが出来る。 まずビー玉を頂点、紐を辺にするグラフを工作する。 グラフを板の上に置き、スタートの頂点にあたるビー玉だけをつまむ。 グラフが置かれている板を取り除くと、グラフは自由落下を始めるが、 スタートにあたるビー玉を持っているので、スタート地点から近いビー玉から順に落下が止まる。 ゴールにあたるビー玉が止まったとき、ゴールにあたるビー玉はスタートにあたるビー玉まで紐で一直線で結ばれている。 この直線が最短経路である。” ビー玉が経路の構成点で紐が経路なのかなということはわかりますが、それを板の上にのせて板がを取り除く、あたりから何が何だかさっぱりわかりません。板は水平に置かれているなら板が消えたら全部落下するだけのように思えますし。でもこれが理解できるとアルゴリズムの思想が理解でき、その妥当性とか限界について予想がつくのだろうと思います。 他に何かイメージがつかみやすい説明があるでしょうか。 また、ダイクストラ法は情報処理としては初等的なものなのでしょうか。それとも結構アドバンスドなものなのでしょうか。 サンプルプログラムを調べてみたらC・C++が多いようなのでこちらにお尋ねしてみました。 よろしくお願いします。 斜方二十・十二面体の頂点を最小数で移動する方法 数学の図形の問題なのですが、 斜方二十・十二面体(構成面:正三角形20枚、正方形30枚、正五角形12枚、辺:120、頂点:60)について、ある頂点から出発し、全ての辺を通ることを考える際の、最短移動数(通過する辺の最小数)の求め方は、どのように考えればよいでしょうか?複数回同じ辺を通ると思いますが、考え方がわかりません。 全ての辺が正方形に属することから、正方形の展開図で考えてみようと思いましたが、考えかたがわからず解けない状況です。 数学の、立体図形の問題です。 下の図のような1辺の長さが4の正四面体がある。頂点Bから、AC上の点E、AD上の点Fを通ってBDの中点Mまでを線で結ぶ。 BE+EF+FMが最短となるとき、その長さは2√13(2ルート13)になるが、このとき三角形AEFの面積を求めなさい。(解説もよろしくお願いします) 確率の問題がわかりません 写真のような正四面体OABCがあり、図のように6つの辺に(1)-(6)までの番号が付いてます。3個のサイコロを振り、出た目と同じ番号の辺を取りのぞく(ただし、頂点は残す)。 例えば、出た目が1,2,3の時は辺OA,OB,OCを取りのぞき、1,1,2のときは辺OA、OBを取りのぞく。 この時、4つの頂点全てが残っている辺でつながっている確率を求めよ。です。 よろしくおねがいします。 中学数学図形の問題です 教えてください 底面が1辺4の正三角形ABCで、OA=OB=OC=8の三角すいO-ABCがある 頂点Aから辺OB上の点D、辺OC上の点Eを経てまた点Aまで戻るように糸をはる。 最短となる糸の長さを求めよ 下の図は解説です。 どうしてOAが3a ABが2a となるのでしょうか また△OAB∽△ABDとなるのはどうしてですか? よろしくお願いします 長さが最短となる経路について 最小経路問題というのがありますが、それとは違ったものです。 いくつかの点をとり、そのうちの任意の二つの点が直線を介して行き来できるように直線を引きます。 そのとき、描いた直線の合計の長さが最小となるようにするにはどのようにひけばよいか?という問題です。 仮に添付した画像では4つの点を正方形状に取ってみます。 このとき、正方形の1辺を1とすると、左の図は2+√2ですが、右の図は2√2なので、右のほうが直線の長さの合計が短いことになります。 そこで、教えてほしいのですが、これに類似するような問題を調べている分野ってないんですか?また、こういった問題を扱ってる本や専門書を知っていたら教えてください。お願いします。 最短距離の問題です 最短距離の問題です 座標空間において,x, y, z 座標の少なくとも1つが整数であるような点の集合 A を考える. (0,0,0) から (3,3,3) まで,A に属する点だけを通って移動する 最短経路の長さを求めよ. 答えは√41 です 正五角形の問題です。 問題)一辺の長さがaの正五角形ABCDEについて,次の問いにこたえよ。 (1)BEの長さを求めよ。 (2)外接円の半径を求めよ。 (3)正五角形ABCDEの面積を求めよ。 (1)はなんとか出せたのですが、 (2)で引っかかってしまって…。 (2)は第二余弦を使って解いてみようと試みたのですが、できなくて…。どのようにすればいいのでしょうか?お願いします。 最短経路問題のアルゴリズム 最短経路問題のアルゴリズムにはどのようなものがありますか? ダイクストラくらいしか知りません。教えてください。 カテゴリー違いだったら書き直します。 この問題は最短経路の考え方でいいのでしょうか? この問題は最短経路の考え方でいいのでしょうか? さいころを振って、xy平面上に置かれた駒を次の規則にしたがって動かす。 出た目が1または2ならばx軸方向に1だけ移動させ、 出た目が3または4ならばy軸方向に1だけ移動させ、 出た目が5または6ならば駒はその点にとどめる。 (1)OからAへの最短経路は全部で何通りあるか? (2)さいころを7回振ったとき駒が初めてAに到達する確率を求めよ。 (3)さいころを9回振ったとき駒が初めてAに到達する確率を求めよ。 最短経路を計算するプログラム 下の図のようなものを用いて、スタート(S)からゴール(G)までいく最短経路を計算するプログラムをVisual Studio 2005のC++で作ったアルゴリズムが知りたいです。 正五角形の対角線の長さ 正五角形の1辺の長さが「1」であるとき、その対角線の長さ φ を簡単に求める方法はないでしょうか? また、頂点から、対角線が交差するまでの長さ 1/φ を導き出す方法も、ぜひ教えて下さい。 解は、φ = (1 + √5) / 2 であるようですが。 正五角形の書き方 一辺が9cmの正五角形を書くには、どうすればいいのでしょうか。 家には、分度器なるものがありません。 (これは、勉強でなく趣味です。) よい方法を教えて下さい。お願いします。 正四面体の最短距離 昨日、高校入試受けてきました。(^^;) この問題が解けずとても悔しかったです。 答えと解き方が気になってしょうがないので教えてください。 正四面体A-BCDのAB、BCの中点をそれぞれP、Mとする。ACとADを通り点PからMまでひもを引くとき、その最短距離を求めなさい。 図がないと分かりにくいですが、辺ADからMは立体の中を突っ切るような感じになると思います。よろしくおねがいします<(_ _)> 数学の図形の問題です 妹に勉強を教えていたのですが、以下の問題が分かりません。 教えて頂けるとうれしいです(>_<) 正二十面体の1つの頂点に集まる5つの辺の3等分点をとり、そのうち頂点に近いほうの三等分点を結んでできる正五角形を含む平面で、正二十面体の角を切り落とします。これを全ての頂点で行うと、切頭二十面体(切頭二十面体ともいう)という立体ができます。この立体は正五角形の面の数が12、正六角形の面の数が20です。また、どの頂点にも面が3つずつ集まっています。このことから切頭二十面体の辺の数と頂点の数を求めなさい。 以上です。 よろしくお願いします。 この数学の問題を解いて下さい。お願いします! この図のように1辺の長さが4cmの正四面体ABCDがあり、辺ACの 中点をМ、辺ADの中点をNとする。次の問いに答えよ。 (1)△ABCの面積を求めよ。 (2)頂点Aから底面BCDに直線AHをひくとき、AHの長さを求めよ。 (3)点B,M,Nを通る平面でこの立体を切ったとき、 切り口の三角形BMNの面積を求めよ。 (4)頂点Aから切り口の平面BMNにひいた垂線の長さを求めよ。 中学受験の算数問題で辺の比がわかりません 正六角形の頂点と対辺の中点を通る直線と中点のある辺の両端の頂点のうち一方の点を六角形の外側に延長した直線との交点で出来る図形(ちょうちょう形)の辺の比を求める問題で、答えが2:5になるのですが、理由がわかりません。言葉で書くのは難しいので図を添付します。皆様宜しくお願いします。 立体幾何の問題 図に示すように,一辺の長さLの正四面体の辺の中点を 5 個用いて正四角錐 (P-ABCD)をつくる。この四角錐の底面 ABCD から頂点 P までの距離hを, Lを用いて表せ。 補助線とか引いていろいろやりましたが、結局できませんでした。 分かる方がいらっしゃいましたら、ご指導よろしくお願いします。 名古屋-大阪間最短経路について 名古屋ー大阪の高速を使わない最短経路はどのルートなんでしょうか? 時間的に最短経路です 1号でもなく25号でもなく、県道を使うと最短と聞いたこともありますが、どの道がご存知でしょうか? 注目のQ&A 「前置詞」が入った曲といえば? 緊急性のない救急車の利用は罪になるの? 助手席で寝ると怒る運転手 世界がEV車に全部切り替えてしまうなら ハズキルーペのCMって…。 全て黒の5色ペンが、欲しいです 長距離だったりしても 老人ホームが自分の住所になるのか? 彼氏と付き合って2日目で別れを告げられショックです 店長のチクチク言葉の対処法 カテゴリ 学問・教育 人文・社会科学 語学 自然科学 数学・算数 応用科学(農工医) 学校 受験・進学 留学 その他(学問・教育) カテゴリ一覧を見る あなたにピッタリな商品が見つかる! OKWAVE セレクト コスメ化粧品 化粧水・クレンジングなど 健康食品・サプリ コンブチャなど バス用品 入浴剤・アミノ酸シャンプーなど スマホアプリ マッチングアプリなど ヘアケア 白髪染めヘアカラーなど