- 締切済み
グラフの最長パスの求め方
graphaffineの回答
- graphaffine
- ベストアンサー率23% (55/232)
#2の補足は一般的に言うパスには成っていません。あなたのパスの定義は何でしょう。 >パスの意味が分かってるのかな。 これは無視ですか。
関連するQ&A
- 最長経路探索
グラフの最長経路(クリティカルパス)を求めたいのですが、 ・閉路無し有向グラフ ・重み付きグラフ（辺ではなくノードの方に重みがある） ・スタートとゴールのノードが各々1つ与えられている ・スタートからどの経路を辿ってもゴールには辿り着く 以上のような条件の時に、どのようなアルゴリズムを用いれば良いのでしょうか？ 幅優先探索で求められそうな気がしたのですが、どうも上手くいきません。 言語はVBAで、そもそも詳しくないのですが、 考え方など教えて頂けないでしょうか。 お願い致します。
- ベストアンサー
- その他（プログラミング・開発）
- 重みなしの有向グラフのある点からある点までの最短経路を求める方法として
重みなしの有向グラフのある点からある点までの最短経路を求める方法として、優先度付きキューにまだ追加していないノードを追加していく方法がありますが、2番目に短い経路を求めるにはどうすればいいのでしょうか。 キューへの追加は一度だけという条件を取っ払って、何度も追加してもいいように変更すると、求めることができますが、計算に時間がかかってしまいます。
- ベストアンサー
- 数学・算数
- 最長の共通部分
はじめて質問させていただきます。 二つのデータの最大長の共通部分を求めるための、 なるだけ高速なアルゴリズムを探しています。 たとえば、 データ1:『EFGABCDEFGABCDEFGHAABCDEFG』 データ2:『EFGHABCDEFGABCDEFGAABCDEFG』 ですと データ1の4バイト目のAから始まる14バイトと データ2の5バイト目のAから始まる14バイトが一致。 が求めたい答えです。 細かい条件をならべると、 1) 文字列ではなくバイナリデータである。 2) データサイズは、最大で数MB程度を想定。 3) 同じ並びの繰り返しなどを多く含んでいる可能性を否定できない。 4) 連続した１つのバイト列で最長なものが知りたい。 5) まれに最長ではなく、最長から二番目が出力されてしまう程度の、 誤差はあってもよい。 6) 一定長(例えば全体の10%)以下の共通部分であれば、無視してもよい。 といった感じなのですが。 ソートを使う、ハッシュを使う、飛び飛びに探索する等、 いろいろアルゴリズムを考えてみましたが、どれもパッとしません。 先ほどグーグルで検索していて、どうやらかなり難しいらしい ということに気づきました。 なにか、ご存知の方いらっしゃいましたら、 アドバイスをお願いいたします。
- ベストアンサー
- C・C++・C#
- 項目とグラフの重なりをなくす
エクセルでグラフを作成した際に 下の画像のようなグラフが出来上がりました。 マイナスのパーセントが出てしまったので 社名とグラフのパーセンテージが重ねってしまい すごく見にくくなってしまいます。 どうにか割合と社名がかぶらないように変更できませんでしょうか？ また左のグラフでは赤が上で青が下になりますが 右のグラフでは青が上で赤が下になります。 左右とも青が上で赤が下にしたいのですが 可能なのでしょうか？ 詳しい方、教えてください。
- ベストアンサー
- その他MS Office製品
- Excel 折れ線と棒グラフ
Excelで折れ線と縦棒グラフが混在したグラフを作りたいのですが、 下から伸びる縦棒と左側面から出る横棒しかありません。 そこで、上から下に向かって伸びるグラフで 右にグラフの目盛(上から0)というようなグラフの作成方法をご教授下さい。 折れ線は左目盛の普通の折れ線グラフです。 折れ線も棒グラフもx軸の値は同じです。 よろしくお願い致します。
- ベストアンサー
- オフィス系ソフト
- エクセルのグラフでの目盛りについて
今，散布図で折れ線グラフを書いているのですが，出来上がったグラフの上下左右(X軸，Y軸)に目盛りを付けたいんですが(目盛り線ではなくてちょっとだけ印しみたいなもの。←これでわかってもらえますか？) 数値軸目盛り線と背景の色を同じにすることで左/下はできたんですが右/上はでないいんです。どうすればいいんですか？特に対数グラフだと左/上に印ができてしまい非常に不恰好なんです・・・。
- ベストアンサー
- オフィス系ソフト
- アローダイアグラムの描画について
計画系のXMLデータを使用し、PERT図（アローダイアグラム）の作成をするプログラムを書こうとしています。 各ノードがもっている情報は以下のとおりです。 ・ノード名 ・先行ノード名 理論的には、上記の情報のみでアローダイアグラムが完成するはず（と考えています） 元データがXMLということもあり、画像はSVGを予定しています。ここで、わからないことがあるので教えてください。 XY座標上にノードを配置し、線で結ぶロジックまでは比較的簡単にできたのですが、ノードをどのように座標配置するかで行き詰まっています。 ノードの枝分かれ、再結合などが発生したときに、XY座標（無限空間とします）上のノード位置が重複しないよう、位置をうまくずらしてあげる必要があります。 （全ての座標を計算したあとに、一括して描画します） 通常、こういった計算はどのようなロジック、アルゴリズムに基づいて行うものなのでしょうか？それとも、開発環境の描画ライブラリなどにおまかせするのが一般的な方法なのでしょうか。 一般的なアルゴリズムがあれば、がんばって実装しますが、特定の描画ライブラリを使う必要があるのであれば、あきらめようと考えています。 情報をお持ちの方は教えてください。。
- ベストアンサー
- その他（プログラミング・開発）
- グラフ構造のアルゴリズムの問題です。
グラフ構造のアルゴリズムの問題です。 頂点間の最短距離を求める問題ですが、どうすれば良いかわかりません......。ダイクストラ法などを使うのでしょうか？ 何のアルゴリズムを利用するのかという点と、解法の手順を解説していただけると幸いです。 以下、問題文です。 v1,v2,v3,..., v9,v10 の 10 個の頂点からなる重みつき無向グラフ G の全頂点間の最短距離を計算したい。こ こで dk(i,j) を頂点 vi から頂点 vj への「経由してよい頂点を v1,...,vk に限定した」最短距離とする。例えば, d3(i,j)は「経由してよい頂点が v1,v2,v3 に限定された」vi から vj への最短距離となる。 ただし,v1,...,vk までの頂点のみを経由するような vi から vj への経路がない場合は dk(i,j)を∞とする。 いま,「経由してよい頂点を v1～v6 に限定した」全頂点間の最短距離がそれぞれ d6(1,2)=3 d6(1,3)=12 d6(1,4)=∞ d6(1,5)=4 d6(1,6)=6 d6(1,7)=∞ d6(1,8)=4 d6(1,9)=8 d6(1,10)=9 d6(2,3)=5 d6(2,4)=∞ d6(2,5)=2 d6(2,6)=3 d6(2,7)=∞ d6(2,8)=1 d6(2,9)=6 d6(2,10)=3 d6(3,4)=∞ d6(3,5)=5 d6(3,6)=2 d6(3,7)=∞ d6(3,8)=6 d6(3,9)=9 d6(3,10)=5 d6(4,5)=∞ d6(4,6)=∞ d6(4,7)=2 d6(4,8)=∞ d6(4,9)=∞ d6(4,10)=4 d6(5,6)=5 d6(5,7)=∞ d6(5,8)=3 d6(5,9)=4 d6(5,10)=8 d6(6,7)=∞ d6(6,8)=4 d6(6,9)=9 d6(6,10)=3 d6(7,8)=3 d6(7,9)=∞ d6(7,10)=1 d6(8,9)=4 d6(8,10)=7 d6(9,10)=12 であった。この情報をもとに以下のそれぞれの値を求めよ。 (1)d7(1,10) (2)d7(4,8) (3)d7(4,10) (4)d8(1,10) (5)d8(4,5) お手数お欠けしますが、どうかよろしくお願い致します。
- ベストアンサー
- 数学・算数
お礼
補足の通りです。
補足
元々の質問を整理しますが、 ・－・－・－・ ／ ＼ ・－・－・ 上記のようなグラフの場合、 １ ６ ７ ・－・－・－・ ２／ ＼５ ・－・－・ ３ ４ このようにカウントして最大パス長は７として計算したいということです。 ========== 普段はわざわざこのようなことは書かないのですが、 回答いただけたのも何かの縁ですので。。。 質問を読んでいただいて理解されているとは思いますが、 この質問は最大パス長の定義を問うものではありません。 前述したとおりの方法で最大パス長を求める方法に関する質問です。 それは質問自体と、No.2の補足で説明した通りです。 ですので、 > > パスの意味が分かってるのかな。 > これは無視ですか。 お礼のコメントを無視したわけではなく、どのように計算するのか具体例を示すことで、 最大パス長（この例では７）の求め方を示したつもりです。 グラフ理論における典型的な最大パス長が、例えばループがないものとかその他のどのようなものであれ、 今回の質問に関してはまったく興味がありません。 質問や補足に記載の方法で最大パス長を求めるためにはどうしたらいいか知りたいのです。 どのように最大パス長を計算すればよいか、アルゴリズムやあるいは検索キーワードを教えていただけませんか。 それでもなお、質問自体に回答せず、 「その定義は一般的な最大パス長ではない」とか「正しい最大パス長の定義を理解していますか？」とか、 「質問文に『最大パス長』という文言が含まれているのに勝手な定義をしないでください」とおっしゃるのであれば、 それはお互い工数の無駄になるだけですので、私の質問に回答していただかなくてかまいません。