ビンパッキング問題 - Wikipedia
ビンパッキング問題（ビンパッキングもんだい）とは、離散数学の組合せ論の中のNP困難問題で、与えられた「荷物（重さや個数がついている）」をつめる「箱（ビンやコンテナなど）」の最小数を見つけるものである。問題を解くためにビン型（筒状型）の模型を使うのでこのように呼ばれる。 様々な解決方法（アルゴリズム）が考案されているが、あらゆる場合の箱の最小数を効率的に見つけることができるような万能なアルゴリズムはない（NP困難問題）。 8台の新車をトラックで移動する。新車の重量はそれぞれ100キログラム単位で 33, 61, 58, 41, 50, 21, 60, 64 である。各トラックが、12,000 kg の重量まで運べるとき、全ての新車を一度に移動させるのに必要とされるトラックの最小数は、いくつであるか考える。まず、トラックを容量120のビンとし、新車は、そのビンに詰める荷物とする。具体的に調べる
最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー
部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言います。 X = <A, B, C, B, D, A, B> Y = <B, D, C, A, B, A> という二つの系列から得られる LCS は <B, C, B, A> で、その長さは 4 です。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列ですが、最長ではないのでこれらは LCS ではありません。また、LCS は最長であれば位置はどこでも良いので、この場合 <B, D, A, B> も LCS です。 LCS は動的計画法 (Dynamic Prog
PythonでA*(A-Star)アルゴリズム - Pashango’s Blog
今回はA*アルゴリズムをPythonでやってみます。 ゲームプログラマの間では、もはや常識となりつつある最短経路問題解決アルゴリズムです。 A*は、古典的手法である「ダイクストラ法」を改良したものです。 スタート地点からノードnを通ってゴールに辿り付くとき、最短距離をf(n)とすると、 f(n) = g(n) + h(n) とすることができます、g(n)は「スタートからノードnまでの最短距離」、h(n)は「ノードnからゴールまでの最短距離」です。 でも、最初から適切なg(n)とh(n)が判ってるなら苦労しませんよね。 だから、テキトーな予測値を使って、最短経路をある程度予測して効率的に経路探索をしてみようという事です。 テキトーな予測値を使った最短経路距離をf*(n)とすると f*(n) = g*(n) + h*(n) となります、f*(n)を求めるためにテキトーなg*(n)とh*(n)を
正規表現で素数判定 - NO!と言えるようになりたい
追記：ハッキリ言ってこの正規表現はネタなので，実際に素数判定を行いたい場合は，もっと別な賢いアルゴリズムを使ったほうが良いです 正規表現で素数が判定できるという記事を見たので試してみた． http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/ この記事によると /^1?$|^(11+?)\1+$/ という正規表現を使うと，素数判定が出来るらしい．ある整数 n が素数かどうか判定したい場合は，"1" * nという文字列がこの正規表現にマッチするかどうかを調べればよく，マッチすれば非素数，マッチしなければ素数となる．ただし，"1" * n は，例えば，n が 4 ならば "1111" と 1 が 4 回連続して続く文字列となる． Rubyで書いた素数判定プログラムはこん
blog.alumican.net » Blog Archive » 遺伝的アルゴリズムで歩行動作獲得への道 ～１歩目～
僕の大好きな、「マッチ箱の脳」という本があります。 この本を書いたの「がんばれ森川君2号」や「アストロノーカ」とか、人工知能が組み込まれたゲームを作ったすごい人です。 » マッチ箱の脳(AI)―使える人工知能のお話 僕はアストロノーカしかやったこと無いのですが、人工知能が自然にゲームに組み込まれていてすごいなあと当時思ってました。中ではすっごい難しいことをやっているのに。その影響か、僕も人工知能を組みたいと思ってこれまで何度もチャレンジしては挫折してきましたが、懲りずにまたチャレンジすることにしました。 シャクトリムシの進化をやってみることにします。 いくつかの棒状のパーツが繋がった体をシャクトリムシと見立てます。体の繋ぎ目である関節を適当に動かすと、シャクトリムシがウニョウニョ動きます。でもこれだけだと、ただ暴れているだけで全然前へ進みません。前へ歩かせるためには、全ての関節が連携しな
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
Chapter.2 巡回セールスマン問題に対するGAの応用 - 田中雅博監修・日高正博製作補助 知能情報Web教材
巡回セールスマン問題(TSP)とは？ 巡回セールスマン問題 (the Traveling Salesman Problem) は，N個の都市すべてを1度ずつ訪問した後に最初の都市に戻る巡回路のうち、 最小の距離のものを求める問題である。 この巡回セールスマン問題に対してGAの応用を考えよう。 Partially Matched Crossover [PMX] 通常の交叉では、都市の重複が考えられるため、工夫する必要がある。ここでは連続した組の遺伝子対に着目し、交叉するPMXの手順を簡単に説明する。 一対の親染色体が以下のように与えられているとき、ある連続した部分列の組（この例では(3,7),(6,2),(1,5)の３組）に注目する。
JavaScript でハッシュアルゴリズム
Hash algorithm of JavaScript CRC16/32, MD2, MD4, MD5, SHA-1, SHA-256, RIPEMD-128, RIPEMD-160, RIPEMD-256, RIPEMD-320 IE4+, NN4.06+, Gecko, Opera Download CRC16/32 MD2 MD4 MD5 SHA-1 SHA-256 RIPEMD Sample CRC16 CRC32 MD2 MD4 MD5 SHA-1 SHA-256 RIPEMD-128 RIPEMD-256 RIPEMD-160 RIPEMD-320 Input Hash Memo マルチバイト文字から生成されるハッシュ値に疑問を持つかもしれませんが 内部では入力文字の文字コードは Unicode ですので あしからず。 ありえないと思われるので入力データが 0xFFFFFFF
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
kikuzone on Twitter: "「同じ著者の小説をつなげてzip圧縮したら、複数の著者の小説をつなげて圧縮するよりも圧縮率がいいから著者推定に使える！」って論文が見つかった。キワモノかと思ったら精度いいし。論文探してるとしばしば「その発想はなかったわ」な物が見つかって面白いが俺は数日前にこれをやっとくべきだ。"