計算アルゴリズム【Ⅱ】

計算アルゴリズム【Ⅱ ..

665:デフォルトの名無しさん
08/06/12 15:26:15
>>663
大まかな話、例えば10,000個のデータをソートする場合、データの比較や交換を行う平均的な操作回数は、
挿入法なら1回当たり2～10,000個のデータの操作を行うループを10,000回行うから50,000,000回程度の操作が必要。
クイックソートは10,000個のデータをピボットに対する大小で2グループに分けるということを行うのに10,000回の操作が必要。
さらに2つに分けたグループごとに同じことを行うので両方のグループ合わせてやはり10,000回の操作が必要。
この分割をどんどん進めて最終的にグループ内のデータ数が1個になるまで行うと分割回数はlog10,000/log2=13回程度。
つまり全部で約130,000回の操作が必要になる。
50,000,000回と130,000回の操作では比べるべくもないということ。
しかもクイックソートは挿入法に比べて全体的に複雑なことをやっているように見えても、
データの比較や移動という基本的な操作にかかる時間が変わるわけではないから、
操作回数の極端な減少はソート時間の減少に繋がるということになる。

666:デフォルトの名無しさん
08/07/04 23:20:30
エクスポゼのような敷き詰めとGraphVizのようなほかの四角とかとぶつからないように関係する四角を近くにレイアウトしてさらに関係線を四角にかぶらないように線を引くアルゴリズムがわかりません(´・ω・｀)

667:デフォルトの名無しさん
08/07/27 08:46:19
>>666
おまい自身が手で線を引くなら、そういうときは
どういう手順で何を基準に線を引いてるんだ？

668:デフォルトの名無しさん
08/08/30 18:14:43
あげ

669:デフォルトの名無しさん
08/10/11 22:27:10
URLﾘﾝｸ(www.forest.impress.co.jp)
↑テキスト比較ツール「DF」のように２つのテキストファイルを比較して
お互い一致しない行を探し出すプログラムを自前で組みたいとおもっています。
（C#を予定）

この手のプログラムを組むにはどのようなアルゴリズムを調べれば実現できる
ようになるでしょうか？

670:669
08/10/11 22:29:00
失礼。↓こちらのスレで質問した方が適切でしたね。よく調べずに質問してすいません(´･ω･｀)

プログラミングの為の数学と算数 vol.3
ｽﾚﾘﾝｸ(tech板)

671:デフォルトの名無しさん
08/10/11 23:04:05
>>670
こっちでいいよ
そのソフトウェアをダウンロードする気が無いから確認だけど
aaa
bbb
ccc
ってテキストと
aaa
ccc
ってテキストを比較するとどうなるの？

672:669
08/10/11 23:11:15
>>671
両者の「aaa」と「ccc」がそれぞれ一致したと見なされ、前者の「bbb」が不一致と表示されます。

673:デフォルトの名無しさん
08/10/11 23:16:47
>>669
手始めに ONP とか LCS とかでググレばいいんじゃね。

ONP とかだけだと、関係ないものがいっぱいヒットするから
「ONP アルゴリズム」とかでググルが吉。

674:デフォルトの名無しさん
08/10/12 01:23:58
どうでもよさげだがDFの説明だとしたら>>672はちょっと言い方が適当過ぎないか？
diffっぽく聞こえる。　いや、やりたいことはdiffなんだろうけど。

675:669
08/10/12 01:54:11
>>674
オリジナルの文のうち、消えた部分を特定できれば十分です。

aaa　aaa
bbb　ccc
ccc　ddd

左がオリジナル、右が比較用としますとオリジナルから消えた部分として
bbbを特定できれば満足です。

676:デフォルトの名無しさん
08/10/12 02:27:20
>>675
あくまでアルゴリズムが知りたいなら>>673のとおりに。

外部ソフトの起動初心者じゃなくて、手軽にやりたくて、
２ファイル間の比較でいいならDOSにFCというコマンドがあるからC#からそれを呼んでその結果を解析すればおｋ

677:デフォルトの名無しさん
08/10/12 07:27:56
> 手軽にやりたくて、

今時 FC はないだろ。

って言うか、それなら DF 呼び出すようにするだろうし。

単に楽したいだけなら、C# で LCS の実装例とかも見つけられるでしょ。

参考 URL: URLﾘﾝｸ(d.hatena.ne.jp)

678:デフォルトの名無しさん
08/10/12 12:10:51
>>677
DFってそういう出力する方法あるのか？

わざわざ実装したいくらいだから結果をプログラム中で使いたいのだと思ったんだが。

あとFCなら配布時に別途導入してもらう必要が無いし。

あと>>673のキーワードで見つけられない人が実装例みて実装できるのかちょっと疑問。

679:デフォルトの名無しさん
08/10/12 13:30:35
> わざわざ実装したいくらいだから結果をプログラム中で使いたいのだと思ったんだが。

FC 勧める理由がわからん。

比較するテキストファイルの書式が決まってるならまだしも任意のテキストファイルを
想定すると、FC の出力の解析は結構大変だよ。

680:669
08/10/12 14:19:04
動的計画法と配列アラインメント
URLﾘﾝｸ(www.ibm.com)

↑LCSのプログラムに関して概念を説明しているサイトがありました。
これにそってLCSテーブルを作り、LCSを見つけてみようと思います。

681:デフォルトの名無しさん
08/10/12 15:09:12
>>679
勧めた理由はその次の行に書いたが？

ぶっちゃけそれ以上の理由は無い。

解析が大変だと思うのは同意。

>>680
>>677のソースをコピペでいいのに。

682:デフォルトの名無しさん
08/10/12 15:26:58
>>681
> 勧めた理由はその次の行に書いたが？

配布の容易さと解析の容易さの比較は状況次第だから議論は避けるよ。

> >>677のソースをコピペでいいのに。

>>669 は、アルゴリズムを理解しようとしてるんだろうと思うし、コピ
ペでは得られないものがあると思うよ。

頑張れ > >>669

683:デフォルトの名無しさん
08/10/12 16:11:41
確かにプログラム書くことが目的なのかアルゴリズム知ることが目的なのかもはっきりしてなかったね。

とはいえスレとしては後者として考えるべきだった。　ｽﾏﾝｶｯﾀ

684:669
08/10/12 16:18:39
みなさん暖かい支援どうもですm(_ _)m

> >>669 は、アルゴリズムを理解しようとしてるんだろうと思うし、コピ
> ペでは得られないものがあると思うよ。

はい、>>680のサイトでO(NM)の単純なアルゴリズムに関してはおおよそ把握することができました。

可能ならば
URLﾘﾝｸ(hp.vector.co.jp)
で紹介されていますO(ND)アルゴリズムや、さらに進化したO(NP)アルゴリズムも
理解したいと思っています。

さっそくO(ND)とO(NP)を解説した原著論文をDLしてきたのですがなかなか全体像を
把握するのが難しいです(´･ω･｀)
もう少し優しくかみ砕いて説明してくれているサイト、できましたら日本語で、があれば
嬉しいのですがそういうサイトは無いでしょうか？

685:669
08/10/12 16:19:20
>>677さんに紹介していただいたサイトに掲載されていましたC#のコードを早速試してみました。
URLﾘﾝｸ(d.hatena.ne.jp)

aaa　aaa
bbb　bbb
　　　 ccc
（左がオリジナル、右が比較対象）

早速この二つを比較してみたところ。
オリジナルの"aaa"はCommon（共通）と判断されたものの、オリジナルの"bbb"はModified（変更）
と判断されました。ぱっと見た目では"aaa"も"bbb"も変更点は無いように思えるのですが・・・。

686:デフォルトの名無しさん
08/10/12 16:22:21
>>685
もっとPCの全般的な基礎知識を得た方がいいような希ガス。
おそらく、左のbbbには行末に改行文字がないのではないか?

687:669
08/10/12 16:35:39
>>686
左のbbbには\nを付けましたが、やはりModifiedが返されるようです。

あと
aaa　aaa
bbb　ccc
　　　 bbb
だと

Common
Modified
Common

と返されるようです。
オリジナルが2行なのに返される行が3行だと後々の処理がちょっとややこしくなるかもしれません・・・

688:デフォルトの名無しさん
08/10/12 17:10:18
> ぱっと見た目では"aaa"も"bbb"も変更点は無いように思えるのですが・・・。

C# のソースがあるんだから、ステップ実行しながら見てみればいいと思うんだが。

あと、それはそれとしてバイナリエディタを１つ使えるようになっておいた方がいいと思う。
テキストエディタ上では同じ改行に見えても片方は 0x0d のみで、もう一方は 0x0d 0x0a
なんてこともあるから。

689:デフォルトの名無しさん
08/10/12 17:48:14
>>687
鈍らな比較ツールだと、「挿入された」ことを理解できないから>687のようなことになる。
逆に言えば、「挿入された」ことを考慮しないアルゴリズムでは、目的に合っていないと言うことだけ。
それにしても、>685では右の2行目はbbbなのに>687ではcccにするなど、
意図的に釣ろうとしているのでなければ余程の間抜けか説明下手にしか見えない。

690:669
08/10/12 17:56:39
>>689
> それにしても、>685では右の2行目はbbbなのに>687ではcccにするなど、
> 意図的に釣ろうとしているのでなければ余程の間抜けか説明下手にしか見えない。

釣りとかでは無いです（；´∀｀）・・・

>>685も>>687もどちらもオリジナルが2行なのに対して
比較対象の文字列（どちらも3行）をいじるだけで出力が
2行になったり3行になったりと変わってしまうと後々の
処理がややこしくなるかなと思った次第です

691:だから、無駄なことはやめておけと
08/10/12 18:14:36
>>690
読解力のない間抜けだということはよく判りました。

692:デフォルトの名無しさん
08/10/12 18:47:39
何で>>690みたいなゴミみたいな奴がアルゴとかやってんの？

693:デフォルトの名無しさん
08/10/12 19:52:19
>>685
> >>677さんに紹介していただいたサイトに掲載されていましたC#のコードを早速試してみました。
> URLﾘﾝｸ(d.hatena.ne.jp)

そこのコードは最長共通部分とか返してくれない。
「とにかくO(NP)の最速で動くdiffコードを作ってみました」
ということを実証するためのコードだからあまり実用的じゃないぞ。
あるいはコードに手を入れてちょっとした改造を施すか汁。

694:デフォルトの名無しさん
08/10/12 20:58:19
>>689
>それにしても、>685では右の2行目はbbbなのに>687ではcccにするなど、
なんか勘違いしてね？
その二つの例が別の話題だということは>>687が「あと」と言っていることから分かる
自分の読解力を過信して、ろくに理解せずに他人にいちゃもんを付けるのは格好悪いよ

695:デフォルトの名無しさん
08/10/12 21:04:24
>>691
> 読解力のない間抜けだということはよく判りました。

読解力の無いマヌケはお前の方だったようだなｗ

696:デフォルトの名無しさん
08/10/12 21:07:15
面白そうだから黙ってたのに。

697:デフォルトの名無しさん
08/10/12 21:07:29
頭おかしくなっちゃうと屁が出るんだよねｗ

698:デフォルトの名無しさん
08/10/12 21:17:48
>>689
(ﾉ∀`)ｱﾁｬｰ

699:デフォルトの名無しさん
08/10/12 22:11:35
basicのほうが早くね

700:　
08/10/14 00:07:37
文字列照合アルゴリズムでSIGMAてのがあるらしんですけど
詳しいアルゴリズムを解説したページありませんか？
なんか宣伝のようなページしか見つかりません。

701:デフォルトの名無しさん
08/10/14 18:55:04
URLﾘﾝｸ(hdl.handle.net)
ここにたどり着いた
あってるかは知らん

702:デフォルトの名無しさん
08/10/14 19:06:55
management system だから違うんじゃなかろうか
>>700 はどこでSIGMAという名前を知ったの？

703:
08/10/15 18:43:09
>>701
エラーがでます。

>>702
シュンサクとかいうデーターベースで使われてると読んだのです。

704:アラフＯＯ.ｏ（笑）
08/10/15 23:21:58
>>703
オモローな記事があるぞ。兄弟。

いまさらアルゴリズムを学ぶ意味
Page1
アルゴリズムを学ぶ意味
世界のナベアツのアルゴリズム
世界のナベアツのアルゴリズムの実装
Page2
ナベアツアルゴリズムを理解してみる
そのほかのナベアツアルゴリズム
あらためてアルゴリズムを学ぶ意味
Page3
フローチャートを学ぶ
UMLを学ぶ
さまざまなアルゴリズムを知っておこう
URLﾘﾝｸ(www.atmarkit.co.jp)

705:デフォルトの名無しさん
08/10/16 20:09:11
>>703
URLﾘﾝｸ(pr.fujitsu.com)
> 九州大学の有川節夫氏（現在、理事・副学長）と研究グループが
> 1981年に発表した、一方向逐次処理方式による
> 超高速パターンマッチングエンジン・SIGMA（シグマ）を基に開発・実装されている。

アルゴリズムじゃなくてシステムじゃないか。
人物から見ても >>701 であってるんだな。

あと、エラーが出るならどんなエラーが出るかくらい書こうよ。
少なくとも俺の環境では問題なく見られるけど。

706:
08/10/17 03:43:42
>>701 >>705
失礼しました。前見たときはWebのエラーがでて見れませんでしたが今見れました。
大変ありがとうございました。

707:デフォルトの名無しさん
08/10/18 18:41:25
範囲のリストに新しい１つの範囲を追加するアルゴリズムをお願いします。
例えば、[1,2][5,7][8,15]という範囲のリストがあります。
上記のリストに[3,5]という範囲を追加すると
[1,2][3,5][5,7][8,15]に。

上記のリストに[1,6]という範囲を追加すると
新しく追加する範囲が常に優先されて、
[1,6][6,7][8,15]に。

上記のリストに[10,13]を追加すると[8,15]が２つに分割されて
[1,2][5,7][8,10][10,13][13,15]。

リストは常にソートされているものとして、各範囲は重なって
はいけません。上記で範囲[Start,End]でEndは含まれません。

範囲のリストに1万件とか２万件を高速に連続追加できれば幸いです。

よろしくお願いします。定石のアルゴリズムがありそうですが、私の実力ではわかりません。

708:デフォルトの名無しさん
08/10/18 18:46:16
あ、後、範囲のリストのデータ構造は配列・リストでお願いします。後でインデックスによる
アクセスをしたいので。

709:デフォルトの名無しさん
08/10/18 18:53:28
多めに確保して置いて、存在するところのビットを立てておけ。

710:デフォルトの名無しさん
08/10/18 19:14:08
データ構造はリストでお願いします。聞きたいのはアルゴリズムです。
実際は、各範囲にオブジェクトが関連付けられていますというより、
あるクラスに開始範囲を表すStartIndex,EndIndexフィールドがあります。
考えたのは、まず、追加する範囲の開始インデックスをキーにリストをバイナリ
サーチして追加位置決定？
んー。

711:デフォルトの名無しさん
08/10/18 19:14:40
ふと思いついたもの。

範囲を示すインデックスにどの範囲に属するかという情報を持たせる。

上の例で実際にやってみる。
[1,2][5,7][8,15]に[3,5]を追加する。
範囲を示すインデックスがどの範囲に属するかという変数 = ID (0,1,0,0,0,2,2,0,3,3,3,3,3,3,3)
[3,5]を追加。(0,1,0,4,4,2,2,0,3,3,3,3,3,3,3)

[1,6]を追加。(0,4,4,4,4,4,2,0,3,3,3,3,3,3,3)

[10,13]を追加。(0,1,0,0,0,2,2,0,3,3,4,4,4,3,3)

以上。追加は高速だと思う。
範囲のリストへのアクセスはIDからリストを作るので、そこは作る処理の時間だけ遅くなる。

712:デフォルトの名無しさん
08/10/18 19:19:05
そして、追加位置からリストを後方に向かって１つずつ追加範囲と比較？
追加範囲と比較対象の範囲が重なり合う部分があれば、比較対象の範囲を調整？
完全に含まれていれば、削除？

713:デフォルトの名無しさん
08/10/18 19:24:57
あー。すみません。データ構造とアルゴリズムは関係があるので、データ構造はリスト
でお願いしますといいましたが、撤回します。すみません。
ある程度高速であればいいです、自分が考えたコードが醜く読みずらくなっていくので
何かいいシンプルなアルゴリズムないのかなと思った次第です。
>>711
ありがとうございます。ちょっと考えてみます。

714:デフォルトの名無しさん
08/10/18 19:39:07
>>711
なるほど、おもしろいですね。塗りつぶしていくイメージですね。追加する場合の
アルゴリズムは単純ですね。必要であればIDの伸張と指定範囲の塗りつぶし(データ転送)。

715:デフォルトの名無しさん
08/10/18 21:13:16
範囲の列を、pより小さい部分とp以上の部分に分ける操作を考えて「値pによる分割」と呼ぶことにする
例えば[1,2][5,7][8,15]を3で分割すると[1,2]と[5,7][8,15]に、
10で分割すると[1,2][5,7][8,10]と[10,15]になる(このように列の分割が範囲そのものの分割を伴うことがある)

範囲の列Sに[start, end]を挿入するには、Sをstartで分割してS1とS2を得、S2をendで分割してS3とS4を得、
S1とS4の間に[start, end]を挟んだものを結果とすればいい

Sをpで分割するには、まずS中の範囲でendがpを越えるもののうち一番左にあるものを探す
そういうものがなければ、SはSと空列に分割される
あれば、それのbeginをpと比較して、それを分割するか全部右側に入れるか決める

多分この手順でいけるけど、これが高速に実行できるようなデータ構造は何があるだろう
2-3 Finger Treesとかならindexとappendとsplitが全部O(log n)だから、O((log n)^2)で挿入できるかな

716:デフォルトの名無しさん
08/10/18 21:47:34
>>702 >>713
データ構造を弄ってよいなら，
できるべき操作をちゃんと指定してほしい．
たとえば

(1) 範囲の追加
(2) 範囲 [x,y] に含まれる全ての範囲を小さい順に出力
(3) 小さいほうから数えて k 番目の範囲の出力
(4) ある点を含む区間の有無の判定
(5) ...

みたいな感じで列挙してください．

あと，>>710 に関して質問なのだけど，
いまある区間が分割された場合（>>707 の [10,13] の例），
オブジェクトとしてはどうなっているの？

(a) オブジェクトが複製されて [8,10] と [13,15] が別物として管理される
(b) [8,10] と [13,15] は同じオブジェクトに対応する

どっち？

717:デフォルトの名無しさん
08/10/18 23:22:08
>>707
範囲が狭いなら、>>709 の言うようにビットマッブでいいと思うけど、
２万件とか言ってるなら、
struct {
　unsigned int StartIndex;
　unsigned int EndIndex;
};
みたいなノードを StartIndex をキーにして BTree とかで管理して、
挿入とか削除は自前で好きなように実装にするな、俺なら。

718:デフォルトの名無しさん
08/10/18 23:25:14
>挿入とか削除は自前で好きなように
まさにその部分を質問してるんじゃね？

719:デフォルトの名無しさん
08/10/19 00:17:17
>>713,714
反応してくれてどうもです。

最近はあまりやらないんですけど、前はパズルを解くプログラムを作ったりしていました。
ポイントは簡単な問題を数多くこなす事だと思っています。
すると、どういう処理が効率がいいのか分かってきます。

こういう場合の為におすすめです。あまり無いと思いますが。。。

720:デフォルトの名無しさん
08/10/19 00:52:35
＞上記のリストに[10,13]を追加すると[8,15]が２つに分割されて
＞[1,2][5,7][8,10][10,13][13,15]。
これだけどさ、なんで
[1,2][5,7][8,15]
じゃないの？　そういうルールだからと言われたらそれまでだけど
こういう処理が必要な実例が思いつかない。

721:デフォルトの名無しさん
08/10/19 00:59:37
>>720
想像力不足

722:デフォルトの名無しさん
08/10/19 01:38:10
俺は動画のフレーム編集を想像しながらスレを見てた

723:デフォルトの名無しさん
08/10/19 01:42:24
だとしたら>>716のa,bはa？

あと>>721はどんなもの想像してたんかな？

724:デフォルトの名無しさん
08/10/19 10:05:09
>>707です。
>>716
>(a) オブジェクトが複製されて [8,10] と [13,15] が別物として管理される
オブジェクトを複製して別物で管理します(範囲以外のプロパティをコピーして)
>できるべき操作をちゃんと指定してほしい．
外部に公開する機能は
・範囲の追加(1個ずつ)
・リストの先頭から末尾への連続アクセス
・リストの全削除
以上です。
>>717
なるほど、上で書いた外部に公開する機能みてもB-Treeでいいのかもしれませんね。
ちょっと実装してみます。
>>715
わ。ありがとうございます。すごいわかりやすいです。

もうちょっと色々もだえてみます。

725:デフォルトの名無しさん
08/10/19 10:12:56
・リストの先頭から末尾への連続アクセス
だとリストでデータ構造固定しちゃうような意味にとられるかもしれないので
正確には、
範囲の列に昇順に連続アクセス
かな。途中からアクセスすることはありません。

726:デフォルトの名無しさん
08/10/19 12:23:29
>720
URLﾘﾝｸ(icpcres.ecs.baylor.edu)
こんな感じの問題解くときにはそういう処理でやってもいいかもしれない。

727:デフォルトの名無しさん
08/10/22 23:08:31
8≦Nを満たす正の整数Nを3と5の和の組み合わせで表すにはどうすればいい？
3が何個、5が何個って分かればいいんだけど
あと表せない数はあるんだろうか

最初の5つはこんな感じ
8=5+3
9=3+3+3
10=5+5
11=5+3+3
12=3+3+3+3
13=5+5+3

728:デフォルトの名無しさん
08/10/22 23:37:07
N = 3m+5nでしょ。　互いに素ならいけるんではなかったか? m,nが整数なら

729:デフォルトの名無しさん
08/10/22 23:37:40
単に3と5の個数をデータとして持てばいいんじゃないの?

8,9,10,11,12が書き表せている時点で、次の5つ組
13,14,15,16,17はそれぞれさらに5を足せば作れ、
以降5つ組ごとに足す5を増やしていけばすべて作れるので、
8以上の正の整数でつくれないものはない。

730:デフォルトの名無しさん
08/10/22 23:39:21
ax+by=1を満たす整数x,yが存在する

URLﾘﾝｸ(d.hatena.ne.jp)

731:デフォルトの名無しさん
08/10/22 23:41:50
そしたら連続する3つ作れればそれ以降、全てつくれるってことだな

732:デフォルトの名無しさん
08/10/23 00:01:14
その日のうちに答がもらえるとは思わなかった
とりあえず列挙できることが分かったので、個数の組はあらかじめ計算して持つようにしよう
というか>>729の通り5を足せばいいんじゃん、気づかなかった
ありがとうございました

733:デフォルトの名無しさん
08/10/23 00:50:53
どうもおかしいと思った。

＞最初の5つはこんな感じ

6つあったのねw

734:デフォルトの名無しさん
08/10/25 01:09:36
A Small and Fast IP Forwarding Table Using Hashing.
これ何度みても計算できねぇ助けて

735:デフォルトの名無しさん
08/10/25 01:53:54
一緒に考えてやるからその論文を見る方法を教えろ

736:デフォルトの名無しさん
08/10/25 02:07:20
URLﾘﾝｸ(cial.csie.ncku.edu.tw)
URLﾘﾝｸ(cial.csie.ncku.edu.tw)
ぐぐった
合ってるかは知らん

737:デフォルトの名無しさん
08/10/26 11:10:39
>>736
それっすそれっす

738:しろうと
08/10/26 16:22:55
突然すみません。しろうとです。
バイナリーサーチの計算量はO(log n)ですが、その導き方について。
T(n)=O(1) n<=1
T(n)=T(n/2)+O(1) n>1

以上から、T(n)=T(n/2)+1=T(n/4)+2=T(n/8)+3...=T(n/2^k)+k。
ここまではわかるんだが、解説によると(n/2^k)=1とおいて、T(n)=log n+1
したがってT(n)=O(log n)となっている。なぜ、(n/2^k)=1とおくのでしょうか。
また、(n/2^k)=1をkについて解けばlog nにわかりますがlog n+1の1って何なんでしょうか？

739:デフォルトの名無しさん
08/10/26 18:18:41
アルゴリズムをよく考えてみ
k=１のとき、つまり1回分割したときはn/2
k=2のとき、つまり2回分割したときはn/4 = n/2^2
k=3のとき、つまり3回分割したときはn/8 =n/2^3
といって、求めたいのは、つまりnをk回分割したときの計算量だから
k=???のとき、つまりk回分割したときにn/2^k　→ ???を求める為には
数式頼みはよろしくないよ

740:デフォルトの名無しさん
08/10/26 18:49:12
>>738
ひどい導出だ．O(1) の扱いが雑すぎる．
T(n) = O(1) (n <= 1) なんて意味不明すぎる記述．

もし本当に本にこう書いてあるなら捨てたほうがいい．

741:くまさん
08/10/26 18:59:21
プログラムの初心者です。
アルゴリズムの流れ図について、自然数ｍ、ｎに対して、
ｍのn乗を計算する効率の良いアルゴリズムのフローチャ
ート書くという問題です。
どなたかご教授ください。

742:デフォルトの名無しさん
08/10/26 19:37:22
流れ図の問題なんだな？そうなんだよな？
ではまず、効率の良いアルゴリズムを言ってくれ。

743:くまさん
08/10/26 22:23:58
ヒントと書かれていたのはｎ＝64のときは乗算はの回数は6回で済む。

n＾２＊ｎ＾２＊ｎ＾２
これがヒントだそうです。
どうしたら、よろしいのでしょうか？
お願いします。

744:くまさん
08/10/26 22:44:42
ｎの４乗はｎの２乗×ｎの２乗です。　ｎの８乗はｎの２乗×ｎの４乗ですから、展開するとｎの２乗×ｎの２乗×ｎの２乗です。

従い、ｎの６４乗はｎの２乗×ｎの３２乗ですから、ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗となります。
の2乗
これを利用して、ｍのｎ乗のアルゴリズムのフローチャートを書くみたいです。

745:デフォルトの名無しさん
08/10/26 22:45:56
よくわからんな、何だろ
ビット演算を絡ませたアセンブラ的な問題なのかな？
お前らどうする？これ放置していいん？

746:デフォルトの名無しさん
08/10/26 22:53:29
罠じゃねえの?

説明がデタラメだし。

747:デフォルトの名無しさん
08/10/26 23:18:56
>>744
＞ｎの８乗はｎの２乗×ｎの４乗
ダウト。乗数は足し算です。

n^8
= n^(4+4)
= n^4 * n^4
= (n * n * n * n) * (n * n * n * n)
ね？

＞ｎの６４乗はｎの２乗×ｎの３２乗
同様に、ｎの３２乗×ｎの３２乗がｎの６４乗で
あえて言うなら（ｎの３２乗）の２乗がｎの６４乗

つまり
>>745
問題のヒントが出鱈目だから放置していい。

748:デフォルトの名無しさん
08/10/26 23:20:45
>>736の問題助けてくれｗまじでｗ

749:デフォルトの名無しさん
08/10/26 23:27:51
要するに>>736を分かりやすく翻訳してくれって言ってる？
サマリー読む限り、別に問題提起ってわけではなさそうだけど……？

750:デフォルトの名無しさん
08/10/26 23:35:16
>>749
4bitの集合を考え、具体例として以下で計算した場合
0000, 1100　0011, 0100, 0110, 0111, 1011, 0001.

1100まで計算した場合のV0とV1って
V0: 0 0 0 0
V1: 4 3 1 1
になりますかね？

751:デフォルトの名無しさん
08/10/27 00:12:25
４ページのExample 1の話？

752:デフォルトの名無しさん
08/10/27 20:28:44
うん

753:デフォルトの名無しさん
08/10/28 20:57:21
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
上記は疑似コードで書かれていますが、アルゴリズム１もアルゴリズム２も
配列の中から最小値を探し出す処理をしているそうですが、アルゴリズム１の
０２行目では配列をどうやってtempにぶちこめるのでしょうか？配列Aが例えば
{2, 6, 3, 7}だとすると、tempには最初に何が入るのですか？再帰なので、
A[1, 4]を呼び出そうとして、tempに値が入る前にA[1, 3]が呼び出され、やっぱり
A[1, 2]が呼び出され、最終的にA[1, 1]になって、A[1]の２が返されて処理が
終了しそうな気がするのですが、間違っているところを教えて下さい。

754:デフォルトの名無しさん
08/10/28 21:06:35
>>753
リンク先は見ていないが、再帰の仕組みを勉強しなおし給え。
要は、a[1]の結果が返されるのはa[1, 2]の呼び出しのtempへの代入なのだろ。

755:デフォルトの名無しさん
08/10/29 00:57:04
再帰の仕組みって勉強すればなんとかなるもんじゃないだろ
何と言うか、考え方がピンと来るか来ないか、脳みそにマッチするかしないかみたいなもんだ

>>753
間違ってない、でも再帰の考え方をそうやって深部に潜ってく物だと考えるのは良くない
君の配列の書き方を使って書くと

A[1,4]の最小値は・・・A[1,3]の最小値とA[4]の小さい方！
じゃあA[1,3]の最小値って何さ　→　同じやり方で済むじゃん

みたいな考え方を適用すべき

756:デフォルトの名無しさん
08/10/29 01:01:16
LISP学んだり、フラクタル図形書いてみたり
だまし絵とか見に行くといいんじゃないかな

757:755
08/10/29 01:09:03
>>753
おっと、質問に答えてなかったので答えます
最初にtempに入るのは、A[1,3]の最小値なので2です。

758:デフォルトの名無しさん
08/10/29 14:22:29
n個の要素から上位3つを選ぶアルゴリズムで速いのはなんですか？

ソートして先頭3つでやるのはなんかもったいない気がして・・・

759:デフォルトの名無しさん
08/10/29 14:41:45
端から舐めて上位3個を取り出す方法だろうなぁ

760:デフォルトの名無しさん
08/10/29 14:47:31
それだと比較回数3n？

761:デフォルトの名無しさん
08/10/29 14:50:26
ヒープ

762:デフォルトの名無しさん
08/10/29 14:53:24
20000個のデータで上位100なら、クイックソートとかしたほうが早いですかね？

763:デフォルトの名無しさん
08/10/29 15:30:41
>>757
ありがとうございました。

764:デフォルトの名無しさん
08/10/29 15:31:13
nth_element, partial_sort

765:デフォルトの名無しさん
08/10/29 18:05:02
>>762
上から k 個欲しかったらサイズ k のヒープを作って次々に突っ込むのがよい．
計算量は全データ数を n とすれば O(n log k)．
k は高々 n なので，計算量はデータ数によらずソートするよりも良い．

実用的にはデータの分布に依存するので，実測しないと何とも．

766:デフォルトの名無しさん
08/10/29 18:16:37
>>765
全体ソートするのとオーダーかわらんじゃん

767:デフォルトの名無しさん
08/10/29 18:31:52
っ「選択アルゴリズム」

768:デフォルトの名無しさん
08/10/29 18:33:23
選択アルゴリズムはk番目の値しか探せないぞ

769:デフォルトの名無しさん
08/10/29 18:38:05
>>768はまったくプログラミングの才能が無いな。

770:デフォルトの名無しさん
08/10/29 18:41:47
partial_sort使うのがいいんじゃない？

771:デフォルトの名無しさん
08/10/29 18:43:47
>>770
それ、なんのこと言ってるの? C++前提なの?

772:デフォルトの名無しさん
08/10/29 18:50:02
「部分ソート」と呟いておく。

773:デフォルトの名無しさん
08/10/29 19:03:55
たとえば2万個から100個選ぶ場合、値の分布が0点-100点だとして
93点以上が100個程度であるとわかっていれば、93点以上を選べばいい。

774:デフォルトの名無しさん
08/10/29 19:09:33
もしくは、一回目の探索で分布を調べて、100個選ぶにはいくつ以上かを特定する。
次のループでそれ以上を選ぶ。

775:デフォルトの名無しさん
08/10/29 21:53:17
v[0]が4にならねーよ
わからねー

776:デフォルトの名無しさん
08/10/30 06:19:01
>>766
全体ソートは　O(n log n) だから log の値が違う

777:デフォルトの名無しさん
08/10/30 13:30:13
Nは100～10000程度で、double x[N]; に適当な数が入っているとします。
任意の数aに最も近いx[k]を知りたいとき、普通はO(N)の時間がかかりますが、
あらかじめx[]をソートしておけば二分法を使ってO(log N)でできます。

ここからが質問なのですが、2次元の座標としてx[N],y[N]があるときに、
任意の直線との距離が最も小さい(x[k],y[k])を知りたいとします。
（与えられたa,bに対してa*x[k]+b*y[k]-1.0 の値が最も小さくなるkが知りたいということ）
このときに上の二分法のようなアルゴリズムはあるでしょうか？
普通にやるとO(N)が必要ですが、O(N)より速い方法を探しています。

778:デフォルトの名無しさん
08/10/30 13:54:09
ないな　O(N)で困る例はなんだよ

779:デフォルトの名無しさん
08/10/30 15:30:46
>>778
ないこと証明できる？

困る例なんていくらでも思いつくでしょ。
まさか二分探索は不要だとか主張するつもり？

780:デフォルトの名無しさん
08/10/30 15:43:21
a,bの存在範囲毎に最小点を計算しておけば定数時間

781:デフォルトの名無しさん
08/10/30 16:07:07
>>777
URLﾘﾝｸ(i11www.iti.uni-karlsruhe.de)
のイントロに書いてあるけど，
[CY84]: 前処理 O(n^2)，問い合わせ O(log n)
[LC85]: 前処理 O(n^2)，問い合わせ O(log n)
[MC95]: 前処理 O(n log n)，問い合わせ O(n^0.695)
[Mu03]: 前処理 O(n^1+ε)，問い合わせ O(n^{1/2 + ε})
くらいの結果はあるみたいね．

一通り目を通してみたけど，LC85 は特に簡単．双対変換すると
「直線 l に一番近い点 p」⇔「点 l* の真上にある直線 p*」
という関係になることに注意して，点位置決定問題に帰着するだけ．

782:デフォルトの名無しさん
08/10/30 17:50:08
>>781
あるんですね。双対変換を使うという発想はなかったです。嬉しいです。
この方法はイメージがついたので、これからちゃんと考えてみます。

追加ですみませんが、
他の方法について、やり方または論文をネット上で見られるものはありますか？

783:デフォルトの名無しさん
08/10/30 19:16:37
そもそも何に必要なんだよ?

784:デフォルトの名無しさん
08/10/30 19:34:27
>>782
私の大学からだとCY84以外は契約論文誌なので，Webから取れた．
もし必要ならどっかにアップロードするよ．

Mu03はciteseerからも取れたので，論文名で検索してみると良い．

785:デフォルトの名無しさん
08/10/30 19:47:13
前処理って言うのが、一回限りだったら logn < √nだから、はじめので十分では?

786:デフォルトの名無しさん
08/10/30 19:50:29
最後のやつだとこの辺に関連情報あるぞ
URLﾘﾝｸ(scholar.google.com)

787:デフォルトの名無しさん
08/10/30 20:04:09
>>784
Mu03を見ることができたので、
これまでの材料で頑張ってみます。
ありがとうございました。

>>785
点を一個追加するとか、色々やりたくなるかもしれないので、
いくつかの方法を知っておきたいと思いました。

788:デフォルトの名無しさん
08/10/30 20:29:11
>>785
O(n^2) は大規模なデータを相手にするには重過ぎるという感覚。
n < 2^32 程度でも前処理しきれない。

なので、クエリ時間を増やしても n^2 より安い手法が存在する。

789:デフォルトの名無しさん
08/10/31 16:28:46
マス目に二種類の記号を置いていった時、

AAA　　　　ABA
ABB　　　　ABA
AAA　　　　AAA

というような回転させたら同じ場面を見つける為にいい方法は無いでしょうか？

790:デフォルトの名無しさん
08/10/31 17:43:56
>>789
問題が不明瞭

マス目に記号が入ったものが二つ与えられたとき、
それが回転で移りあうかどうかをチェックしろということ？

791:デフォルトの名無しさん
08/10/31 17:54:59
簡単な方法はない。
地道に全回転・反転パターン（8通り）を網羅してチェックする。

プログラムが見通しよくなるように工夫がひつようかも。

792:デフォルトの名無しさん
08/10/31 18:21:54
行同値的を出してそれを比較すれば・・・駄目か

793:デフォルトの名無しさん
08/10/31 18:37:25
トランザクションメモリの実装
ここでやる夫的に説明してくれよ

794:デフォルトの名無しさん
08/10/31 19:41:21
　　　 .　'　　　_ 二二 _ .､
　　　　　　／　　　 /´ -‐…‐- .｀＼
　　　　　　 /　　　　 /´　　　 i　　 !｀ヽﾄ､
.　　　 ,ﾍ　 ,' 　 i　　 !　 !　 |　|i　　|ﾊ　i　ヽ　ｷﾘｯ
　　　/　ゝ!　ﾉ|　　! !::__!::ノ ´　￣　 i::.i ｜!
　　　＼　 .|　.:i i :i　i |´　　＼　　／　｀!､ﾊ:!　　
　　　｀ヽi　从 i　i | ニﾆﾐ　　　 .ﾆニ !:::::|　　＜トランザクションメモリの実装
.　　　　　 | 　ＹﾊｉﾊN　 {r::ﾘ｀　　´{r::ﾘ '::::N　　　　ここでやる夫的に説明してくれよ
.　　　　　 |　　ヽゝ　　 ´´　　　　　｀｀ﾊ!｀　
.　　　　　 |∧ 　 Ⅵ!　　　　　 ′　,':::|
　　　　　ｊ/∧　 _!::｝　、　　 ⊂'　..ｲ:::::|
　　　　　 ///∧´ ∨　　｀　,.... ィ´ﾞY:::::|
.　　　　 /////∧　ヽ　　　　{ﾄ､∧　|::::::!
　　　　 ,＜￣￣∧　 } ｀ヽ　　＞''}　{￣｀ヽ
.　　　 / 　｀ヽ:::::::::Y´ヽ　　　　　 i´｀∨::::∧
　　　/　　　 ∨:::::| .:: !　　　　 i .:.: !::::/　i

　　　　　　　　　　　＿＿＿_
　　　　　　　 ,. :'´: :,.　-―‐-ミ:ヽ、
　　　　　　／: : : :厶ｨ': ´￣￣ヾ : :＼
　　　　　 /: : : : : :.!: :M: : : : : }､: ヽﾄ､:.＼　　　＜じゃっておｗｗｗ
　　　　　ｉ: : :.!: : : ﾚ‐'　｀￣⌒　⌒" ﾄﾍ:ﾊ!
　　　ﾄ--|: : :.!: : ､|　　ｰ‐'' ´ ｀'ｰ　　}: :.ﾄ
　　ﾐ　ﾐ　ﾐ : :!: : : :!　z=≡　　　≡z.{: :.ﾊ　　　　ﾐ　ﾐ　ﾐ
　/⌒)⌒)⌒.ﾊ :_Nとつ　＼＼＼ C VVﾘ　　/⌒)⌒)⌒)
　|　/　/　/:弋こ　＼ヽ　＿＿,.　　　}　(⌒)/　/ / /／
　|　:::::::::::(⌒) : :}＼　　/　　　1　／　　ゝ　　:::::::::::/
　|　　　　　ノくf⌒Y ｀　{_　　_,ﾉイ| 　　　/　　）　　/
　ヽ　　　　/　ヽ　ﾍ,､　　_｢　|::!:::::} 　　/　　　　／　　　　バ
　　|　　　　|　　 l||l　从人 l||l.!::|ｲ:::ヽ_./ l||l 从人 l||l　　バ　　ン
　　ヽ　　　 -一''''''"~~｀`'ー--､/:::::ｲ;　 -一'''''''ー-､　　　　ン
　　　ヽ＿＿＿＿(⌒)(⌒)⌒)　):::/}　 (⌒＿(⌒)⌒)⌒))

795:デフォルトの名無しさん
08/10/31 21:00:10
かんなぎは評価されすぎ。

796:デフォルトの名無しさん
08/11/13 03:17:29
無向グラフG=(V, E)の隣接リストがGが接続してようとなかろうとO(V+E)であることを証明せよ。
って意味のわかる人教えて下さい。

797:デフォルトの名無しさん
08/11/13 06:37:03
意味が分からんな。
「隣接リストが O(V+E)」 ← これはまともな言い方じゃない。

798:796
08/11/13 06:40:40
>>797
無向グラフG=(V, E)が隣接リストの配列で表現されるとき、Gが接続していようと
なかろうとO(V+E)であることを証明せよ。だったらどうですか？

799:デフォルトの名無しさん
08/11/13 07:13:30
やはり意味不明。
今度は日本語としてもひどくて、何が O(V+E) なのかが分からん。

800:796
08/11/13 07:25:04
そうですか。失礼しました。忘れてもらって結構です。

801:796
08/11/13 07:31:12
別のやつですが、ダイクストラアルゴリズムは経路に負の数があった場合はうまく動作しない例ってのは
例えばどういうときかわかりますか？

802:デフォルトの名無しさん
08/11/13 07:42:43
>>801
G = (V,E) を 3点 a,b,c からなるグラフとし，
頂点間距離を d(a,b) = 0, d(a,c) = 1, d(b,c) = -2 と設定し，
頂点 a から b への最短路を求めようとすると破綻する．

803:796
08/11/13 07:49:21
なるほど。素早い回答ありがとうございます。

804:デフォルトの名無しさん
08/11/13 08:36:21
>>802
その例では破綻しないぞ

805:デフォルトの名無しさん
08/11/13 11:31:33
>>804
kwsk

806:デフォルトの名無しさん
08/11/13 21:00:49
>>802の例だとd(a, b) = 0で探索終わらね？

正答が得られないって意味で破綻なんじゃね？

807:デフォルトの名無しさん
08/11/14 22:07:03
ユークリッド互除法の最悪時間計算量をLameの定理の結果を用いずに解析せよという問題がさっぱりわかりません。
ぜひ解答お願いしたいです。
スレチでしたらすみません。。

808:びぎなぁ
08/11/16 05:22:26
アルゴリズムの勉強を始めたのですが、用語が色々あって混乱しています。
（どの用語がどの用語の中に含まれているのかとか）
ヒープと二分ヒープという言葉があるのですが、同じ意味でしょうか？

木構造--------二分木---------------二分探索木・・・左の子<=親<=右の子
木構造--------二分木---------------二分ヒープ・・・（１）根に最大値がくる、
　　　　　　　　　　　　　　　　　　　　　　　　　（２）N[a],N[2a],N[2a+1]のデータでは必ずN[a]のデータが一番大きい
木構造--------二分木---------------ヒープ・・・二分ヒープと同義？
木構造--------多分木

809:デフォルトの名無しさん
08/11/16 06:29:55
>>808
ヒープとは，木であって各頂点でヒープ条件『自分の値が子の値以上』
を満たすもののことをいう．よって．一般の木上のヒープがありうる．
例えば多分木上のヒープとしてはd分ヒープはたまに使われるし，
より一般の木上のヒープとしてはフィボナッチヒープが有名．

ただ，最もよく使われるヒープは完全二分木上のヒープで，
何も断らずにヒープと言ったときこれを指す場合も多い．

場合によっては配列実装まで含めてヒープと言う場合もあるけど，
フォーマルには構造と実装は別に考えるので，
>>808 の二分ヒープの説明は本当はちょっとよろしくない．

810:デフォルトの名無しさん
08/11/16 06:53:51
>>807
どれくらいの精度で解析すればいいの？

あと，Lameの定理の結果を用いないというのは
Lameの定理を証明して用いるのは良いということ？
それとも，フィボナッチ数で抑えること自体が禁止されるの？

811:デフォルトの名無しさん
08/11/16 09:19:57
>>810
どの程度の制度かまでは問題に書いてないので、わかりません。
Lameの定理を証明してもダメだと思います。
フィボナッチ数を用いても良いかまでもわかりませんが、使わないでできるのなら使わないで解いてもらいたいです。

812:デフォルトの名無しさん
08/11/16 11:41:06
>>811
互除法のアルゴリズムを
gcd(a,b) = if b == 0 then return a else return gcd(b, a mod b)
として解析する（mod は割り算の余り）．a, b ≧ 0 の場合のみ考える．

補題．
a > b ≧ 0 について，gcd(a,b) が k (≧ 1) ステップで終わるならば
a ≧ 1.1^{k+1}, b ≧ 1.1^k が成立する．
証明．
k = 1 のときは自明．k-1 まで正しいと仮定．
gcd(a,b) が k ステップで終わるとき，
gcd(b, a mod b) は k-1 ステップで終わるので帰納法の仮定から
b ≧ 1.1^{k-1}, a mod b ≧ 1.1^k，したがって
a ≧ 1.1^k + 1.1^{k-1} = 1.1^{k-1}×2.1 ≧ 1.1^{k-1}×1.21 = 1.1^{k+1}．
系．
gcd(a,b) のステップ数は O(log min{a,b})．
証明．
a > b としてよく，log b = m とおけば補題より O(m) 回以下のステップ数で終わるため．

813:811
08/11/16 17:41:20
ありがとうございます

a ≧ 1.1^{k+1}, b ≧ 1.1^k

この式をなぜ持ち出したのかがわかりません。
あと、系の証明が補題より証明できるあたりがいまいちわかりません。
よろしければ教えてください。

814:デフォルトの名無しさん
08/11/16 20:51:27
>>813
上：なんとなく．
1.1 に必然性はなくて，1.0001^k でも 1.0000000001^k でも何でもいい．
(1+ε)^k で示せれば系が示せるので，適当に不等式が成り立ちそうな値にした．

本当に解析しようとしたらギリギリの不等式評価を作るべきなんだけど，
この場合にギリギリに評価するとフィボナッチ数が出てしまうので，
わざとガバガバに評価しているという事情がある．

下：
> できるあたりがいまいちわかりません。
そういうときは具体的にここが分からないとか言うもんだよ．
ただ，補題が少し不十分な書き方だったね．補題は
「k (≧ 1) ステップ以上かかるならば」に置き換えてよい（同じ証明が動く）ので，
そう置き替えておいて，対偶を取ると
「a < 1.1^{k+1} もしくは b < 1.1^k ならば k ステップ未満で終わる」になるので
b < 1.1^m なる m を見つけられれば m ステップ未満で終わる．
そのような m としては log b (の切り上げ) にでも取れば十分(log は 1.1底)．

815:811
08/11/16 21:04:38
ありがとうございます。
もう一度問題と向き合って理解を深めたいと思います。

816:びぎなぁ
08/11/19 07:05:43
>>809
返事が遅くなりました。ありがとうございました。

ところで、最小全域木を求めるクラスカル法とプリム法の概要を理解出来たのですが、
計算量のところがウェブ（ウィキとか）で調べてもよく理解できません。
（１）クラスカル法
グラフの中で一番重みの小さい辺をMSTとして加えて行く。ただしその過程でcyclicに
なってしまうような辺は加えないようにする。計算量はO(E log E)またはO(E log V)

（２）プリム法
MSTに属する頂点とそうでないものの２グループに分け、まだMSTに属していない頂点から
最もコストの安く済む頂点をMSTに付け加えて行く。計算量は３種類あるみたい。
・隣接行列、探索→O(V^2)
・２分ヒープと隣接リスト→O(E log V)（←これはO((V+E)log(V))より）
・フィボナッチヒープと隣接リスト→O(E+V log (V))

ウェブの説明を読んでもわからないということはここで教えてもらってもわからないかも知れませんが
もしわかりやすい説明とかありましたら参考に教えて欲しいです

817:デフォルトの名無しさん
08/11/19 08:22:57
>>816
アルゴリズムの計算量を評価するためには
もっと正確にアルゴリズムを述べないといけないんだけど，
あなたの説明だと，良く分からない部分が多い．
（もちろん「普通の実装」というのがあるのだけれど，
　それがあなたの理解しているものと違う可能性もある）

なので，あなたが理解している形で，For やら If やらを使って
手続きが明確に分かるようにアルゴリズムを書いてくれるかな？
その計算量だったら評価するよ．

818:びぎなぁ
08/11/19 16:22:32
>>817
イントロダクショントゥアルゴリズム二版から抜粋です
---------------------------------------
MST-クラスカル（G, w）
A←0
for each vertex v∈ V[G]
do MAKE-SET(v)
sort the edges of E into nondecreasing order by weight w
for each edge (u, v) ∈ E, taken in nondecreasing order by weight
do if FIND-SET(u)≠FIND-SET(v)
then A←A∪{(u, v)}
UNION(u, v)
return A
---------------------------------------
MST-プリム(G, w, r)
for each u∈V[G]
do key[u]←∞
π[u]←NIL
key[r]←0
Q←V[G]
while Q≠0
do u ← EXTRACT-MIN(Q)
for each v∈Adj[u]
do if v∈Q and w(u, v) < key[v]
then π[v]←u
key[v]←w(u, v)
---------------------------------------

819:デフォルトの名無しさん
08/11/19 21:49:58
>>818
その本に計算量の説明が懇切丁寧に書いてあるよ

820:デフォルトの名無しさん
08/11/19 21:54:24
ならし解析ですね分かりません。

821:デフォルトの名無しさん
08/11/20 00:37:39
LC-Treisってどんな木なのですかね？

822:びぎなぁ
08/11/20 02:42:41
>>819
了解です！

823:びぎなぁ
08/11/20 02:46:49
「有向グラフで、開始点から離れて行く辺のweightが全て負の数で、その他の全ての辺が
正の数だった場合、ダイクストラ法は失敗することがあるか？」

あれば例を教えて欲しいです

824:デフォルトの名無しさん
08/11/20 21:21:36
「開始点から離れて行く辺」の定義が必要なんじゃね？

次ページ