queuekousuke.hatenablog.com以前、この記事で最大出次数を最小にする順序は難しいかもと書いたけどできるらしい。Wikipediaアルゴリズムも載っていたのだけれど、優先度を変更できる優先度付キューをつかうと簡単にできそうだった。Rubyの優先度付キューを探してみると標準では優先度付キューはないようだ。quueuというgemがあって、この中でベンチマークがある。Rubyならlazy_priority_queueがよいよとのこと。heapでは、値としては下がる方向)はサポートできるみたいな感じっぽい。ヒープのデータ構造に違いがあり、lazy_priority_queueは2項ヒープとのこと、フィボナッチヒープと比べると、フィボナッチヒープの方が平均的には早いけど、ワースト時間で遅いものがあるみたいな感じっぽい。さきのC++拡張の2つともフィボナッチヒープ。Wikipedia多分2007年度の卒業論文(学部生)じゃないかと思うんだけど、グラフの彩色アルゴリズムの内容も基本的にはk-degenerationグラフの順序を求めているのと一緒だった。あげるならば、なるべく次数降順に並ぶように順序を決めていた。自分としてはここに安定結婚問題をもってきたいとおもっていて、適当につくったのが、結構いい値がでてて、精度保障できないかなとか思ってるけど、全然証明とかできない。貪欲法と違うのは基本的に1色で塗れるだけ塗るというのをやってる。安定結婚問題に合わせて色を男性、頂点を女性とすると、貪欲法だと女性優先で、下記のコードだと男性優先なんじゃないかとおもっているが実際には貪欲法と変わらない。なんというか、うまいこと頂点毎の順序や色ごとの順序つくれないかなとおもっている。なんで安定結婚問題でやりたいかといえば、マッチングの質に関しての研究が進んでいるからというのが理由。意外と順序決めるのが早かったりしないかなとおもっている。基本的には前書いた内容。Vacation月別アーカイブはてなブログをはじめよう!tinsep19さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。