人に聞けない痔の悩み、これでスッキリ >>

どのようなアルゴリズムになるか教えてください!!
お願いします!!!!

見えにくいでしょうか。、

「どのようなアルゴリズムになるか教えてくだ」の質問画像

A 回答 (3件)

問題の文脈がよくわからんけれど、最短路を問う以上は、おそらく各arc (edge) aに何らか重みw(a)が対応づけられていて、かつ、どの重みw(a)も正の実数である、という話なのだろう。

また、この場合に最短路木と呼んでいる木は、Gの全てのvertexを要素とするグラフであろう。
 注意すべきは、最短路木を作るよう求めているのではなく、与た最短路木の検証(verification)を求めている、というところ。すなわち、
(1) その木によって決まる、vertex vのrootからの距離dを、全てのvertexについて計算したものを d(v) (v∈V) とする。特に, d(root) = 0。
(2) それぞれのvertex vについて、vに入ってくるarc a の集合をA(v)、そのarc aの出発点のvertexをf(a)とする。 すべての vertex v∈Vについて、
  d(v) = min { d(f(a)) + w(a) | a∈A(v) }
を確かめれば「与えられた木は最短路木だと思っても矛盾しない」と言えて、このとき、与えられた木が最短路木になってる。(「なってると言える」ということ自体は数学的証明を要するが。)
 すると、(1)と(2)の処理をそれぞれ、すでに与えられている木に沿った深さ優先探索でやれば良い。
 (特にw がすべて1という場合なら、木に沿った幅優先探索でやれば(1)と(2)を同時に処理できるだろうに、深さ優先でやれというのだから、wはイロイロなのだろう。)
…という話なのかしらん?それとも、f(a)が簡単には計算できない、という条件が付いているのかしらん?
    • good
    • 1
この回答へのお礼

そういうことです!!!!
ありがとうございます!!!れ

お礼日時:2018/11/28 10:15

s から他の頂点までの最短距離を全部計算してしまえば, T が最短路木かどうかは簡単にわかる.

    • good
    • 0

最短経路木の問題ですよね。

私は、工学修士を持っていますが、授業でやった記憶がありますが、忘れてしまいました。

教えて!goo >教育・科学・学問 >応用科学 >工学

で、再度質問されてはいかがでしょう。
    • good
    • 0
この回答へのお礼

ありがとうございます!
参考にします!

お礼日時:2018/11/25 20:34

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aと関連する良く見られている質問

Q√の整数部分を求める問題では √〇を少数に戻すと聞いたのですが、具体的にどう戻すんですか?

√の整数部分を求める問題では
√〇を少数に戻すと聞いたのですが、具体的にどう戻すんですか?

Aベストアンサー

前の質問の補足にもなりますが、√23のルートを外すには計算機に頼るか、開閉の筆算をするという方法などがあります。
でも筆算(機械に頼らない方法)はそのやり方自体複雑でマスターするのに手間がかかるかと思います。
そのような理由があるからなのか、高校で√23のルートを外す方法を教えている所は少ないと思います.。
ですので、
√23=4.○○○○○・・・ 
とうように小数部分は曖昧に書かせていただきました。
ちなみに、計算機によると√23=4.79583152 になるようです。
これを手で(筆算で)計算するとなると非常に面倒です。
また、暗記するのもナンセンス。
けれども
4<√23<5・・・①から
その整数部分は4であることは簡単に分かるのです。
4=4.000000・・・(以下どこまでも0が続く)
5=5.000000・・・(以下どこまでも0が続く)
ですから4<√23(4より√23の方が大きい)なら
√23は4.00000・・・01以上であるわけです。・・・(A)
(そうじゃないと4より√23の方が大きい とはならないから
→→√23も√23=4.000000・・・(以下どこまでも0が続く)なら √23は4とまったく同じで√23=4という事になってしまいますし、まして√23=3.●●●・・・●(●には0から9までの数字のいずれかが入る)だとすれば √23は4より小さいとなってしまうのでいずれの場合も①に不適合です)
また、√23<5(√23より5の方が大きい)なら
√23=5.●●●・・・●(●には0から9までのいずれかの数字が入る) では前記同様に考えて①に不適合なのです。
√23<5(√23より5の方が大きい)なら
√23は4.99999・・・(以下9がどこまでも続く)以下という事になります。・・・(B)
(A)(B)をあわせ考えると√23=4.●●●・・・●(●には0から9までのいずれかの数字が入る。ただし●すべてが0ということではない)
ということになり、小数部分は曖昧ですが整数部分は4であることがはっきりします。

画像の問題の場合も同様に考えられます。
2<√6<3・・・② であることを突き止める方法はマスターされたと思います。
②(2より大きく3より小さい)なら√6は
2.0000・・・01以上、2.99999・・・9以下ということになりますからその小数部分ははっきり分からずとも
整数部分は2ということは分かるのです。
(ちなみに、 √2≒1.41421356・・・ひとよひとよにひとみごろ
√3≒1.7320508・・・ひとなみにおごれや
√5≒2.2360679・・・ふじさんろくおーむなく
√6≒2.44949・・・・  によよくよく
√7≒2.64575・・・  なにむしいない
受験生なら、これらはごろ合わせで暗記しておくべきです)

前の質問の補足にもなりますが、√23のルートを外すには計算機に頼るか、開閉の筆算をするという方法などがあります。
でも筆算(機械に頼らない方法)はそのやり方自体複雑でマスターするのに手間がかかるかと思います。
そのような理由があるからなのか、高校で√23のルートを外す方法を教えている所は少ないと思います.。
ですので、
√23=4.○○○○○・・・ 
とうように小数部分は曖昧に書かせていただきました。
ちなみに、計算機によると√23=4.79583152 になるようです。
これを手で(筆算で)計算するとなると非常...続きを読む

Q”収束する無限積の積の順序変え”

退職した数学好きの年寄りが、家で頭をひねっています。
よろしく願います。

添付した系1.5の証明についての質問になります。(素数とゼータ関数という本のp12です)

ζ(2)はπ^2/6に収束しています。
この時、Π(1+1/p)が発散するので、Π(1-1/p)が0になる事が必要条件だと何となく分かるのですが、ネットを検索しても、中々でてきません。
又、無限積について取り上げている書籍も多くみあたりません。

私は、
ζ(2)はπ^2/6に収束 → Π(1+1/p)=♾でΠ(1-1/p)=0
”Π(1+1/p)=♾でΠ(1-1/p)=0” は ”ζ(2)はπ^2/6に収束"の必要条件と考えています。

この考えが正しい考えか?
と、無限乗積について書かれたwebsiteと書籍をご存知の方
ご回答をよろしくお願いします。

Aベストアンサー

あなたがお気づきの通り考え過ぎですよ。
無限積=部分積という数列の極限値、というもとの定義にかえればよいのです。
表題の無限積の部分積
=1/(ζ(2)に収束する無限積の部分積×無限大に発散する無限積の部分積)
に気づけばp→∞のときにどうなるかはおわかりですね。

Qドップラー効果を考えていてふと疑問に思ったのですが、音源の速度が音速を超えた場合、観測者の聞こえ方は

ドップラー効果を考えていてふと疑問に思ったのですが、音源の速度が音速を超えた場合、観測者の聞こえ方はどうなるのでしょうか?

Aベストアンサー

衝撃波となって伝わってきます。
参考:戦闘機が頭上を通過する場合などを思い起こしてください

Q複素数の参考書をやっていたらこんな問題がありました 複素数で解くとそこまで難しくはないのですが 「ぱ

複素数の参考書をやっていたらこんな問題がありました
複素数で解くとそこまで難しくはないのですが
「ぱっと見がベクトルの問題です」

なのでベクトルで解く方法はありませんか?

(京大なので複素数じゃないと解き難いという引っ掛けなのかもしれませんが....)

Aベストアンサー

厳密にいうと線分AB に対して「三角形ABC が正三角形になる」ような C は 2個あるので, 単純に
三角形 ABC' が正三角形になる
では不十分ではないでしょうか>#1.

とはいえ #1 のように
当該ベクトルで与えられる点が C と一致する
という方針で行けばそんなに難しくなかったりします.

Q論文

数学の論文を書きました
以下、すべて自分がワードに書いたもののコピペしたものです
きちんとしてると思いますか?

1:最小公倍数
aとbの最小公倍数を(a,b),aとbとcの最小公倍数を(a,b,c)などと表記することにする。
(a,b,c)=1 (aとbとcが互いに素)だとすると,
次の性質が成立する
法則1-a: (ab,c)=(a,c)(b,c)
法則1-b: (a,bc)=(a,b)(a,c)
以下、このことを証明する。

法則1-a,法則1-bの証明:
aとb,bとc,cとaの最小公倍数をそれぞれa´,b´,c´とする。
(a,b,c)=1から、a=pa´c´,b=qa´b´,c=rb´c´((p,q)=1,(q,r)=1,(r,p)=1,a´≠b´,b´≠c´,c´≠a´,(a´,r)=1等)と表せる。
よって(ab,c)=(pqa´^2 b´c´,rb´c´)
ここで(pq,r)=1でないといけない(もし1じゃなかったら先述の条件に矛盾するから)ので
(ab,c)=b´c´=(a,c)(b,c)となり法則1-aが成立する
法則1-bも同様に証明できる
 2:逆関数
以下関数f(x)についてその逆関数をrevf(x)と表記する。
また、関数f(x)の逆関数が定まらない場合、その関数には逆関数がないとし、f(x)のx=aでの微分係数をd f/d x (a),f(x)の積分にaを代入したものを∫f(x) d x (a)などと表記する
関数f(x)に次の法則が成り立つ
法則2-a: f(revf(x))=x
法則2-b: revf(f(x))=x
法則2-c: revrevf(x)=f(x)
法則2-d: d revf/d x (x)=1/(d f/d x (revf(x))) (ただし分母は0ではないとき)
法則2-e: ∫revf(x)dx=xrevf(x)- ∫f(x) d x (revf(x))
これらの法則を証明する。

法則2-a,b,c,d,eの証明:
法則2-aはf(x)=yとすると
逆関数の定義から
x=revf(y)となり
f(x)=yに代入すると
法則2-aが証明される
法則2-bは
y=revf(x)と置き,法則2-aと同等な動作をすることで
証明される
法則2-cは逆関数の定義から明らかである
法則2-dはf(revf(x))の導関数を二通りに計算することで得られる
法則2-dはx=f(t)と置いて置換積分し,法則2-bを適用して更に部分積分することで得られる
3:商
商において次の定理が成立する
法則3-a:aがn≦t≦mをみたす整数tで割り切れるとき,商はa/m以上a/n以下
特にn=(2+a)/2,m=a-1の時
法則2-b:aはa/2<t<aをみたす整数tで割り切れない
証明を記す
法則3-a,bの証明:
まずaはtで割り切れるので、商をQとすると
a=Qt
となる
これに不等式を代入すると
Qn≦a≦Qmとなり,それぞれの不等式を商について解くと
法則3-aが得られる
またn=(2+a)/2,m=a-1の場合
tが整数であることからa/2<t<aとなる
先ほどと同様に割り切れる条件に不等式を解くと次の結果が得られる
1<商<2
しかしこれは商が整数であることに矛盾するので
背理法によって法則2-bが示された
4:行列
2次正方行列A1,A2,…,Anが存在し,それらの逆行列および実数(複素数でもよい)a,b,c,d,…を係数として足し合わせたものの逆行列を仮定して任意の行列Pの行列式をdetP,逆行列をP^-1とすると次が成り立つ

法則4-a:det(aA1+bA2+…)(aA1+bA2+…)^-1=adet(A1)(A1)^-1+bdet(A2)(A2)^-1+…
つまり、detA・A^-1は線形性をもつことがわかる
法則4-aの証明
Akを適当に文字を設定し、具体的な行列にしてから左辺と右辺を計算していけば証明される


以上の論文、もう一度聞きますがきちんとした論文ですか?

数学の論文を書きました
以下、すべて自分がワードに書いたもののコピペしたものです
きちんとしてると思いますか?

1:最小公倍数
aとbの最小公倍数を(a,b),aとbとcの最小公倍数を(a,b,c)などと表記することにする。
(a,b,c)=1 (aとbとcが互いに素)だとすると,
次の性質が成立する
法則1-a: (ab,c)=(a,c)(b,c)
法則1-b: (a,bc)=(a,b)(a,c)
以下、このことを証明する。

法則1-a,法則1-bの証明:
aとb,bとc,cとaの最小公倍数をそれぞれa´,b´,c´とする。
(a,b,c)=1から、a=pa´c´,b=qa´b´,c=rb´c´((p,q)...続きを読む

Aベストアンサー

互いに 素の、
最小公約数なら、

(ab,c)も、(a,bc)も、
abc.、

他方、
(a.c)は ac
('a,a)は ab
(a,c)(a,b)は ac×ab=(a^2)bc


未だ 読んでないですが、
抑もから 違いませんか?

Q因数分解する時、問題文に特に断りのない限り、有理数の範囲で因数分解すれば良いのですか。

因数分解する時、問題文に特に断りのない限り、有理数の範囲で因数分解すれば良いのですか。

Aベストアンサー

中高の数学の演算問題では一般常識的にはそういうことだと思います。

f:R→C
なんてかいてあったら、話は別ですけど、、、
ぶっちゃけ、見ないですね。

Qコンドームの定理

ネットで調べていたら、「コンドームの定理」と言うのを見つけました。
男女2人ずつ、4人が一回ずつ男女間でセックスするとき、何個のコンドームが必要か、という問題で、2×2の4個ではなく、2個でいいそうです。

大学院で数学を勉強している彼に知ってるかどうか聞いたら恥ずかしそうにしてました。知ってたそうで、組み合わせ論の問題じゃなかったかなあ、とのこと。行為(セックス)そのものではなく、数学の話をしようとしてました。

2重にして、取り外して別の人に就けて、、ということでなんとなく2個でいいような気はするんですけど、2重にコンドームを男の人のに一度つけて取り外したら、ビヨンビヨンになってて付け直すなんてできないよ、それに一度したら男の人のが出ちゃってるし・・・と思うのですが、本当にできると思いますか?

Aベストアンサー

(´・ω・`)
それは「男性が射精しないことを前提」とした問題です。
ですので、実際には男性が射精することが前提の性行為と比較してはいけません。

・・・
コンドームは繰り返し使用することを前提としていないので、ナンセンスな問題なんですよ。
むしろそこに突っ込んで欲しいと常々思ってるんだ。

Q「素数の逆数の和は発散する」の証明。本「素数とゼータ関数」共立出版p9について

私は60歳を越す老人です。
退職し、学生時代好きだった数学の本を読み出しました。
この本は難しですが、ゼータ関数と素数に興味があり一歩一歩理解していこうと思っています。
よろしく願います。

添付画像は「素数とゼータ関数」のP8にあります。
私が理解できないのは、添付画像の式で1段目から2段目への展開です。
1段目から2段目への展開が理解できません。
log(1-p^-s)から何故logが消えてしまうのかが、理解できまでん。

2段目から3段目への展開は理解できるのです。
(1-p^-s)^-1の等比級数の級数展開が関係しているとは思っているのですが、私の計算ではlogが消えません。
1度思い詰めると、そうだと思い込んで、発想の展開ができない性格です。

宜しくご回答願います。

Aベストアンサー

log(1+x)=x/1 - (x^2)/2 + ...
のように、マクローリン展開を使えば
変形できます。

Q5進数の足し算の筆算について。 画像の計算が分かりません。 4+4=8なので、くりあがって1の位は0

5進数の足し算の筆算について。
画像の計算が分かりません。
4+4=8なので、くりあがって1の位は0になると考えましたが、解答は3203(5)となっています。

計算の仕方を教えてください。

Aベストアンサー

>4+4=8なので、くりあがって1の位は0になると考えましたが

「繰り上がり」は その通りですが、8=5+3 ですから、くりあっがった残りの 1桁目は 3 になりますね。
2桁目は 繰り上がった 1 と 4 と 0 で 5 になりますから、3桁目に繰り上がって 2桁目は 0 になります。
3桁目は 繰り上がった 1 と 0 と 1 で 2 になりますから、 3桁目は 2 になります。
4桁目は そのまま 1 と 2 ですから、3 になります。
つまり、1044(5)+2104(5)=3203(5) です。

こんな計算は、この単元だけですから、頑張って。
(2進数は出てくるかもしれませんが、3進数や5進数は 今だけです。)

Qこの考え方は間違っていますか?

この考え方は間違っていますか?

Aベストアンサー

27^(1/3)=3
じゃないすかね?

27=3*3*3だから


人気Q&Aランキング