不完全情報下での複数人の探索者によるグラフ探索問題
スポンサーリンク
概要
- 論文の詳細を見る
本研究では複数人の探索者によるオンライングラフ探索問題を扱う.探索の目的は,すべての頂点が少なくとも1人の探索者によって到達されることである.すべての探索者は同一の頂点を探索の始点とし,同一の移動速度で探索を行う.また,すべての探索者は他の探索者が新しく入手した情報を常に共有することが出来る.本稿では特にグラフクラスをサイクル,木とする問題に対するアルゴリズムをそれぞれ与え,競合比解析を行う.具体的には探索者数を2とするサイクルの探索に対して最適な競合比3/2を達成するアルゴリズムを与え,さらに探索者数をpとする木の探索に対して最適な競合比(p/(log p))+o(1)を達成するアルゴリズムを与える.
- 社団法人電子情報通信学会の論文
- 2010-03-05
著者
-
大崎 純
京都大学
-
加藤 直樹
京都大学工学研究科
-
谷川 眞一
京都大学工学研究科建築学専攻
-
大 崎純
京都大学工学研究科建築学専攻
-
東川 雄哉
京都大学工学研究科建築学専攻
-
ランガーマン ステファン
ブリュッセル自由大学
-
加藤 直樹
京都大学工学研究科建築学専攻
-
加藤 直樹
神戸商科大学
-
東川 雄哉
京都大学工学研究科
関連論文
- 実大4層鉄骨造建物のブラインド解析コンテストの総括と解析精度の検討
- (4)アジアへの技術援助と技術移転(VI 座談会,アジアのなかの日本建築,創刊1500号記念)
- 東京5区内のオフィスビルへのテナント入居と空室期間に関する分析
- 一様点要求を満たす根つき森分割と剛性理論への応用
- 1-D-8 動的ネットワークフローを用いた避難所の収容人数の評価(離散・組合せ最適化(3))
- 賃貸用オフィスビルのエントランスホールに対する感性評価のCAEPを用いた分析
- 分子構造に関する剛性予想の証明
- 分譲集合住宅の発注者支援リスクマネジメントシステムの開発(第4部 学術論文,都市・建築に関わる安全・安心のフロンティア)
- Enumerations of Non-crossing Geometric Graphs (Acceleration and Visualization of Computation for Enumeration Problems)
- DS-1-2 A Proof of the Molecular Conjecture
- 124 メカニズム最適化のための平面無交差静定構造列挙アルゴリズム
- 123 静定トラス列挙アルゴリズムを利用した柔構造物の最適設計
- 現実を読むレッスン : 初めて建築を学ぶ人たちへ(I 巻頭座談会,建築を学ぶ人たちへ)
- 柔な構造による免震デバイスモデルの形状最適化
- マルチグリッド法と可変複合モデルを用いた強風を受けるシェル構造物の屋根形状最適化
- 内向木による有向グラフの被覆 (21世紀の数理計画 : 最適化モデルとアルゴリズム)
- 凸性を有する有向グラフ上の独立有向木族の特徴付け
- 鋼構造建築骨組の弾塑性地震応答の高精度有限要素解析
- 局所探索法による鋼構造骨組の多目的最適化
- 発見的手法と非線形計画法の統合による離散構造の位相最適化
- 125 指定釣合い経路を有するトラス構造のトポロジー最適化
- 22417 実大4層建物完全崩壊実験の概要 : E-ディフェンス鋼構造建物実験研究 その21(骨組:その他(2),構造III)
- 22418 実大4層建物完全崩壊実験における弾性加振結果 : E-ディフェンス鋼構造建物実験研究 その22(骨組:その他(2),構造III)
- 22419 実大4層建物完全崩壊実験における弾塑性加振結果 : E-ディフェンス鋼構造建物実験研究 その23(骨組:その他(2),構造III)
- 2次錐計画問題による摩擦を有するケーブルネットの釣合形状解析法
- 2083 2次錐計画問題を用いた摩擦を有するケーブルネットの釣合形状解析法(構造)
- 20189 一様部材断面積を有する立体トラスの形状最適化
- 2017 一様部材断面積を有する立体トラスの形状最適化(構造)
- 3089 火災リスク評価手法に関する研究 : その2 焼損面積期待値の算定例(火災危険性評価(2),防火)
- 3088 火災リスク評価手法に関する研究 : その1 焼損面積期待値の算定方法(火災危険性評価(2),防火)
- 20167 最適化手法を用いたケーブル・ストラット構造の安定解析(応答制御・最適設計,構造I)
- 217 ケーブル・ストラット構造の安定解析のための最適化手法
- 126 非線形計画法を用いたケーブルドームの応力指定形状設計法
- 20161 非線形計画法を用いたケーブルドームの釣合形状解析法
- 20173 有限変形を考慮したケーブルネットのコンプリメンタリエネルギー最小化原理(振動と応力解析,構造I)
- 20146 E-Simulatorによる鋼構造超高層骨組の仮想震動実験と骨組解析の比較(極限解析・崩壊挙動解析,構造I)
- 構造美とデザイン(I 巻頭鼎談,建築形態の数理)
- 不完全情報下での複数人の探索者によるグラフ探索問題
- 5336 経路障害発生時の集団経路探索行動における情報共有の有効性に関する理論的研究(経路探索,建築計画I)
- 8083 東京23区内のオフィスビルへのテナントの入居期間の分析(オフィスビル・REIT,建築社会システム)
- 7386 CAEPを用いた京都市郊外におけるひったくりの空間分析(居住空間の防犯,都市計画)
- 20416 三角形パッチベジエ曲面による区分的可展シェルの形態創生(骨組の形態創生,構造I)
- 20409 異方性を有するフィルタ関数を用いた軸対称シェルのトポロジー最適化(連続体の形態創生,構造I)
- 20390 二面体群対称とテンセグリティ構造の安定性(テンセグリティ・ハイブリッド構造(1),構造I)
- 20200 数値震動台プロトタイプによる鋼構造超高層骨組および4層骨組の仮想震動実験(大規模解析,構造I)
- 20178 柔構造のトポロジー最適化による免震装置の設計(位相最適化,構造I)
- 20174 剛板ヒンジ構造の組合せ剛性(位相最適化,構造I)
- 建築構造学の夢と憂い(I 巻頭座談会,建築構造学の夢と憂い)
- 耐震構造の目標と課題-兵庫県南部地震から1年を経て-
- 地震被害に学ぶ構造物の挙動予測解析の役割 : どこまで予測すべきか、どこまで予測が可能なのか(構造部門(1)応力パネルディスカッション)(1995年度日本建築学会大会(北海道)の概況)
- 2874 多成分地震動応答歪・加速度制約設計 : トラスの順序集合生成法
- 20455 骨組膜構造物の定着金物の応力制約下での形状最適化(膜構造(1),構造I)
- 20454 骨組膜構造物の定着部拘束力最大化のための形状最適化(膜構造(1),構造I)
- 8043 超高層集合住宅のリスク情報共有システムの開発(生産情報・評価,建築社会システム)
- 20411 ラチスシェルの部材長一様化制約下でのひずみエネルギー最小化(形態創生・最適化(1),構造I)
- 木質構造デザインの可能性
- 2044 パラメトリック曲面の代数不変量を考慮した自由曲面シェルの形状最適化(構造)
- 2681 指定1次固有振動数を有する軸対称立体トラスの最適部材配置自然生成法
- 7505 大阪府の家電メーカー取引関連企業の移転に関する分析(人口分布・街区密度,都市計画)
- 118 幾何学的非線形性を考慮したトラスの形状・トポロジー最適化によるリンク機構の生成
- バイステーブルコンプライアントメカニズムの形状設計と不整感度解析
- 210 半正定値計画法を用いた重複固有値を有するトラスのトポロジー最適化問題
- (2)情報技術革命と構造設計者(V IT革命と技術者・建築家の役割,建築の情報技術革命)
- IT革命と技術者建築家の役割【○!2】 : 情報技術革命と構造設計者
- 8060 空間属性を考慮したオフィスビルの貸室の賃料推定に関する研究(マネジメント,建築社会システム)
- 建築構造物の非線形解析と形態最適化
- 空間構造物の最適設計に関する一連の研究(2008年日本建築学会賞(論文))
- 最適化のための反最適化
- 座談会 耐震偽装問題の背景と課題
- 重複座屈荷重の不整感度解析
- (3)構造設計でのコンピュータ利用の恩恵と弊害(III 建築設計のIT化に関する問題点や利点の具体例,情報化時代の建築設計のあり方)
- 伊東豊雄インタビュー--建築は自由でなければならない
- テンセグリティ入門
- 建築計算工学とは
- 数式処理(建築ソフトのフロンティア 第23回)
- 建築形態の数理(III 巻末論文,建築形態の数理)
- 曲線の滑らかさと力学
- 602 複数部材で支持された 2 次構造物の動的応答制約条件下での最適設計
- 125 反最適化手法による安定対称分岐点を有する構造物の座屈解析
- シェル・空間構造(研究レビュー)(構造系)
- 木質構造デザインの可能性((I 鼎談))(木質構造デザインの可能性)
- 最適化ソフトウェア(建築ソフトのフロンティア 第6回)
- 2551 逆問題的定式化による地震時応答制約設計梁の順序集合生成法
- 2690 振動数領域に対する最適アーチの順序集合生成法
- 2031 柔構造のトポロジー最適化による免震装置の設計(構造)
- 2564 極限点荷重係数制約条件下のトラスの最適設計
- 2105 柔な構造による免震デバイスモデルのトポロジー最適化(OS21.計算力学と最適化(2),オーガナイズドセッション)
- 2109 解経路探索による最適トポロジーの唯一性と対称性の検証(OS21.計算力学と最適化(2),オーガナイズドセッション)
- 2045 テンセグリティ構造の位相と形状の探索法(構造)
- 848 摩擦のない接触問題に対する内点法における線形問題への制約前処理付CG法の適用(OS7.大規模並列・連成解析と関連話題(2),オーガナイズドセッション)
- 847 Semismooth Newton法に基づく摩擦のない接触問題の実用的解法(OS7.大規模並列・連成解析と関連話題(2),オーガナイズドセッション)
- 1801 グラフデータ構造を利用した再定式化に基づくトラスの位相最適化手法(OS18.計算力学と最適化(1),ポスターセッションP-2)
- 2654 大規模弾性立体トラスの地震時応答制約設計
- 2379 設計歪分布の順序集合に対する地震時応答制約設計アーチの逆性成子
- 2647 推定1次固有振動数を有する平面トラスの最適部材配置の自然生成法
- 2089 振動数領域に対する最適耐震壁梁の順序集合成法
- 画像解析によるポリ塩化ビニル樹脂系防水シートの伸び保持率の推定
- 207 摩擦のない接触問題に対するウォーム・スタートを考慮した平滑化法
- 548 柔構造のトポロジー最適化による上下方向免震装置の設計(動力学問題の最適設計とその周辺技術と応用,OS-14 動力学問題の最適設計・制御とその周辺技術と応用,総合テーマ「伝統を,未来へ!」)
- 2200 振動数領域に対する最適サンドウィッチ : 平板の順序集合生成法