タグ 近似アルゴリズム が登録されている動画 ： 7 件中 1 - 7 件目
種類:
- タグ
- キーワード
対象:
【近似アルゴリズム】動的計画法でナップザックを解きます
動的計画法は最適解を求めるために色んなところで使われるフレームワークです
最適解を求める動的計画法は一見近似アルゴリズムとは相性が悪そうですが、実は近似アルゴリズムの中で使うこともできます
今日はナップザック問題を使ってその紹介をします
今回はbeamerを使ってスライドを作ってみました
【近似アルゴリズム】たくさん点をつなげるゲーム！ (貪欲でEdge disjoint path)
前回に引き続き貪欲アルゴリズムの解析です
貪欲はアルゴリズムは単純でも解析はややテクニカルというか、こういう方針でいけばだいたいの問題が解析できるといったものがない印象です
でも素朴な初等数学で証明ができるというのは面白いです
※ちなみにedge disjoint pathはネットワーク最大流問題に帰着することができます やり方は考えてみてください～
今回はbeamerを使ってスライドを作ってみました
【近似アルゴリズム】仕事を割り振る問題(min makespan)を解析します
Job schedulingとも呼ばれる実用的にも重要なmin makespan問題
すごくすごくシンプルな貪欲で定数の近似が得られます
シンプルすぎて動画が５分になりました
【近似アルゴリズム】Set Coverを貪欲で解きます
今日紹介する近似アルゴリズムは驚くほどシンプルな貪欲です
テキトーにSet coverを解こうと実装したらこの実装になるかもってくらいにシンプルです
しっかり解析をするとシンプルな貪欲でも近似率が得られるという例として紹介します
【近似アルゴリズム】貪欲による近似：Min Multiway Cutの場合
近似アルゴリズムを作るフレームワークの一つに貪欲アルゴリズムがあります
貪欲アルゴリズムはあまり解の質が良くないイメージかもしれませんが、うまくデザインしてやると割と良い近似率が得られることがあるのです
【近似アルゴリズム】巡回セールスマン問題を解きます
【初回】 近似アルゴリズムってなに？ sm36142972
前回の動画に引き続き近似アルゴリズムのお話です
今回は巡回セールスマン問題の近似アルゴリズムを紹介します
【近似アルゴリズム】近似アルゴリズムってなに？
【次回】 巡回セールスマン問題 sm36172146
近似アルゴリズムを使えば非常に難しいとされる問題でもさくっと解けることがあります
今日はそんな近似アルゴリズムの魅力とデザインの仕方についてお話します
【近似アルゴリズムを使わないと、とんでもないことになりますよ...】http://www.youtube.com/watch?v=Q4gTV4r0zRs