最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。
様々な全域木問題
最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。
グラフを切る - ita’s diary
「最高のカレーを作れ」問題 https://codeiq.jp/ace/yuki_hiroshi/q210 面白いです。別の例に例えると、128人の集団を２つの組に分けます。仲のいいペアは、なるべく同じ組になるようにしたい、という問題。 128個の粒子を用意して、仲のいい同士が引き合い、それ以外は反発するようにして動かすと以下のようになりました。 なんとそういう設問でしたか。集団を二つに切るなら、左の太線で切れば11組の好き同士を分断するだけで済みます。これがおそらく最適解。右が12本でわずかに違うところが絶妙。 確実に最適解を求めるアルゴリズムも、複雑だけどあります。以前の自分の日記から引用 最大流/最小切断定理 たとえば東京都内から筑波に人が一斉に移動するというシチュエーションを考える。東京に核ミサイルが落ちてきて筑波にシェルターがあるとか。このとき何時間で避難可能か、という問題を解く
「解けない問題」を知ろう
「解けない問題」を知ろう 保坂 和宏 (東京大学 B2) 第 11 回 JOI 春合宿 2012/03/19 概要 • 計算量に関して • P と NP • NP 完全 • 決定不能 • いろいろな問題 • コンテストにおいて Turing 機械 • コンピュータの計算のモデル ▫ 「計算」を数学的に厳密に扱うためのもの • メモリのテープ (0/1 の列)，ポインタ，機械の 内部状態を持ち，規則に従って状態遷移をする • 本講義では C 言語等で，入力を受け取って何か 計算して出力を返すもの，とイメージしてよい ▫ 入力は適切な形式で 0/1 の列になっているとする 計算量 • 計算に必要な資源 • 入力のサイズ (0/1 のビット列の長さ) の関数と して表される • 時間計算量 ▫ 動作するステップ数 • 空間計算量 ▫ 使用するメモリの量 計算量 • 単位などは実はあまり気にしない
頂点被覆 - Wikipedia
グラフ理論において、グラフGの頂点からなるある集合VがGの頂点被覆（ちょうてんひふく、英: vertex cover）であるとは、Gのどの辺をとってもその端点のどちらかがVに含まれるという意味である。最小頂点被覆を求める問題は計算機科学における古典的な最適化問題であり、近似アルゴリズムのある典型的なNP困難な問題でもある。その決定問題版である頂点被覆問題は計算複雑性理論における古典的なNP完全問題である。さらに頂点被覆問題には固定パラメータ容易性 (fixed-parameter tractability) があり、パラメータ化計算量理論の中心問題の1つである。 最小頂点被覆問題は、整数計画問題に定式化でき、その双対問題は最大マッチング問題である。 グラフ G の頂点被覆とは頂点の集合 C であり、G の各辺は C 内の少なくとも1つの頂点と接合する。このとき集合 C は G の辺を「被覆
最大独立集合問題 - Wikipedia
最大独立集合問題（さいだいどくりつしゅうごうもんだい）は、グラフ理論において、与えられたグラフ G(V,E) に対して、頂点集合 V'⊆V のうち V' 内の頂点間に枝が存在しないようなもの（独立集合）で大きさが最大のものを求める問題。最大安定集合問題とも言う。この問題は、NP困難であることが知られている。 この問題は、補グラフに対する最大クリーク問題と等価である。また、独立集合に含まれない頂点は頂点被覆をなし、逆も成り立つので、最小頂点被覆問題とも等価である。 近似アルゴリズムについても、基本的に最大クリーク問題と同じである。グラフの頂点数を n とするとき、近似度 O(n / (log n)2) が達成されている。また、P=NP が成り立たないとき、任意の ε>0 について、近似度 n(1/2-ε) の近似アルゴリズムが存在しないことが示されている。NP=ZPPが成り立たない場合、近似
最大クリーク問題 - Wikipedia
このグラフは最大クリーク {1, 2, 5} を持つ 最大クリーク問題（さいだいクリークもんだい）は、グラフ理論において、グラフ中のクリーク（任意の二頂点間に枝があるような頂点集合）の中で最大のものを見つける問題[1]。NP困難であることが知られている。 この問題は、補グラフに対する最大独立集合問題と等価である。 近似アルゴリズムについても研究されているが、グラフの頂点数を n とするとき、近似度 O(n / (log n)2) が達成されているのみである。また、P = NP が成り立たないとき、任意の ε > 0 について、近似度 n1/2 − ε の近似アルゴリズムが存在しないことが示されている。NP = ZPP が成り立たない場合、近似度 n1 − ε の近似アルゴリズムが存在しないことも示されている。
最小クリーク被覆問題 - Wikipedia
この記事には参考文献や外部リンクの一覧が含まれていますが、脚注によって参照されておらず、情報源が不明瞭です。 脚注を導入して、記事の信頼性向上にご協力ください。（2016年9月） 計算量理論において、最小のクリーク被覆（クリークひふく、英: clique cover）を求めることは、グラフ理論的NP完全問題である。クリーク被覆問題はリチャード・カープによるオリジナルの21問題の1つで、そのNP完全性は1972年の論文 "Reducibility Among Combinatorial Problems"（「組合せ論的問題間の還元可能性」）に示されている。 クリーク被覆問題（クリーク分割問題と呼ぶこともある）とは、与えられたグラフの頂点集合を k-個のクリークへ分割できるかを決定する問題である。頂点集合の k-個の集合への分割が与えられたとき、その各集合がクリークを成すかは多項式時間で判定す
)
クリーク (グラフ理論) - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Clique (graph theory)|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針に
指数時間アルゴリズム入門
2. 自己紹介 TopCoder: ◎wata TCO2010Marathon優勝など Twitter: @wata_orz 東京大学情報理工学系研究科コンピュータ科学専攻 理論計算機科学 (アルゴリズムの理論的な解析とか) プログラミングコンテスト チャレンジブック 2 3. 本日の内容 NP困難問題を解くためのアルゴリズムを扱います 𝑂𝑃𝑇 𝐼 ≤ 𝐴 𝐼 ≤ 𝑐𝑂𝑃𝑇(𝐼) 近似アルゴリズム ヒューリスティック 𝑓 𝑘 𝑝 𝑛 FPT アルゴリズム max 𝑐𝑥|𝐴𝑥 ≤ 𝑏, 𝑥: 整数} { 𝑂∗ 𝑐 𝑛 整数計画 厳密指数時間アルゴリズム 3 4. 効率的な指数時間アルゴリズム 何の指数？ 頂点数? 辺の数? それとも… • 2 𝐸 のアルゴリズムはまず役に立たないが，2 𝑉 のアル ゴリズムならコンテストでもよ
補グラフ - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Complement graph|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説
古くて新しい自動迷路生成アルゴリズム - やねうらおブログ(移転しました)
最近、ゲーム界隈ではプロシージャルテクスチャー生成だとか、プロシージャルマップ生成だとか、手続き的にゲーム上で必要なデータを生成してしまおうというのが流行りであるが、その起源はどこにあるのだろうか。 メガデモでは初期のころから少ないデータでなるべくど派手な演出をするためにプロシージャルな生成は活用されてきたが、ゲームの世界でプロシージャル生成が初めて導入されたのは、もしかするとドルアーガの塔(1984年/ナムコ)の迷路の自動生成かも知れない。 なぜ私が迷路のことを突然思い出したのかと言うと、最近、Twitterで「30年前、父が7年と数ヶ月の歳月をかけて描いたA1サイズの迷路を、誰かゴールさせませんか。」というツイートが話題になっていたからである。 この迷路を見て「ああ、俺様も迷路のことを書かねば！俺様しか知らない(?)自動迷路生成のことを後世に書き残さねば！」と誰も求めちゃいない使命感が
External Memory - FC2 BLOG パスワード認証
ブログ パスワード認証 閲覧するには管理人が設定した パスワードの入力が必要です。 管理人からのメッセージ 閲覧パスワード Copyright © since 1999 FC2 inc. All Rights Reserved.
［SQEXOC 2012］FFXIVで使われているAI技術〜敵NPCはどうやって経路を探索しているのか？
［SQEXOC 2012］FFXIVで使われているAI技術〜敵NPCはどうやって経路を探索しているのか？ ライター：米田 聡 スクウェア・エニックスが2012年11月23日と24日の両日開催した「スクウェア・エニックス オープンカンファレンス」の最後には「AIセッション」が用意されていた。AIセッションは前半と後半に分かれ，前半は「ファイナルファンタジーXIV: 新生エオルゼア」（以下，新生FFXIV）における経路探索の実装に関する実践的な解説，後半はゲームAIの第一人者とも評される三宅陽一郎氏による，Luminous Studio用AIエンジンのやや概念的な話という構成だった。本稿では，まず前半の，より実践的なセッションから紹介してみたい。 テーマは，「MMORPGでマップ上を移動する敵NPCの経路をどう決めるのか」である。複雑で広いマップを有するMMORPGでは，移動する経路を賢く選択
マトロイドの凸構造 - けんちょんの競プロ精進記録
この記事は、Competitive Programming Advent Calendar Div2012の12日目の記事として書きました。 0. はじめに 今回はマトロイドについて書きたいと思います。 マトロイドはGreedyとの関連でよく耳にします。では、そもそもマトロイドがGreedy性を持つのは何故でしょうか？実は、マトロイドは単に「Greedyの一例」として出て来るばかりでなく、「現在効率的なアルゴリズムが知られている問題の殆どはマトロイドが何かしら関わっている」と言える程にイイ構造を持っています。以前、以下のようなツイートをしました。 dpやってていつも思うのが、なんか凸凹してるなーと。凸凹し過ぎてdpじゃなきゃ解けないよな、みたいな感じ。マトロイドは凹んでるところがない凸なイメージ。だから、局所最適狙う貪欲法だけで最適解に辿り着ける。焼き鈍しなんて必要ない。 本記事では、この
大規模ネットワークの性質と先端グラフアルゴリズム - iwiwiの日記
本日，PFI セミナーにて「大規模ネットワークの性質と先端グラフアルゴリズム」というタイトルで発表をさせてもらいました．スライドは以下になります． 大規模ネットワークの性質と先端グラフアルゴリズム View more presentations from iwiwi Ustream の録画もあります． http://www.ustream.tv/recorded/27531606 内容としては，以下のようになっています． 現実世界のネットワークの特徴量と性質 次数分布 平均距離 クラスター係数 その他の特徴量 木っぽさ それらの性質を活用したグラフアルゴリズム セオリー方面 近接中心性の近似 コンパクトルーティング 支配集合問題の近似 プラクティカル方面 最短路 密部分グラフ列挙 可視化 タイトルは 1 年前にやった PFI セミナーと似ていますが，内容はあまりかぶっていません．今回は，グ
東京を走る路線のデータを使って、最短経路問題をダイクストラ法で解く - imHo
ダイクストラ法が小さなサンプルデータで動いたら、実際のデータを使ってみたくなるのが人情。東京を走る地下鉄のデータでやってみたいと思った。 JavaScriptとPrototype.jsとGoogleMapsAPIとすったもんだしたあげく、なんとか動くものができた。 502 Bad Gateway テストアプリはこちら JavaScriptのソースはここのhtmlに 駅や路線のデータは駅データ．ｊｐのものを使わせてもらいました。 使ったのは東京メトロ＋都営＋山手線 駅（ノード）の数は、同じ駅でも路線ごとで別にカウントして 322 駅同士をつなぐ線路（エッジ）の数は、徒歩や乗換えを含め 912 体感もっさり感じるけど、経路の検索以外のところがかなりかかってる Tips Prototype.js Array.without は超重い、使うな！ Hash.keys で返ってくるキーはすべて文字列に
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Graph Complement -- from Wolfram MathWorld
Independent Vertex Set -- from Wolfram MathWorld
補グラフ