Pythonで線形計画法を解いてみる
線形計画法（Linear Programming; LP or linear optimization）は，目的関数も制約関数も線形であるときの最適化問題を解く手法です．SciPy + GLPK + CVXOPT + OpenOpt + FuncDesignerで実装されているのを使ってみました．説明はWikipediaから抜粋． 線形計画法は以下のようにある制約関数のもとである目的関数を最大化あるいは最小化するもの． maximize or minimize （目的関数） subject to （制約関数） xは変数，A,b,cは係数．制約関数の形が凸多面体であるので目的関数は最適化可能． たとえば ある農夫がL [km^2]の広さの農地を持っているとき小麦と大麦を育てて売上を最大化させたい．農夫は肥料をF [kg]と農薬をP [kg]だけ持っている．小麦を育てるためには肥料F1 [kg
無料でGrowlをソースからインストールする
Growl 1.3.1の通知がうるさいのでアップデートする．App Storeで$1.99で手に入れることができますが，ソースからコンパイルしてインストールしちゃう．1.3だけど． Growl - Growl Mercurial Accessを参考に．必要な環境は以下． OS X Lion - 10.7 Xcode Mercurial 手順 Growl 1.2.2のアンインストール アンインストーラは http://growl.info/downloads ちなみに古いバージョンのインストーラもおなじところに． Mercurial SCMのインストール http://mercurial.selenic.com/ Google Code repositoryからソースを取得 http://code.google.com/p/growl/source/checkout ターミナルから hg c
PythonでA*アルゴリズムを実装してみる
PythonでNexworkXを使ってA*アルゴリズムを実装してみます。まあNetworkXではA*アルゴリズムは実装されているのですが。 NetworkXは複雑ネットワークでいろいろやるためのPythonのパッケージ。easy_installでインストールするのが楽。 A*（A-star, エースター） アルゴリズムは、経路探索アルゴリズムの一つ。Wikipediaの解説がわかりやすい。(→Wikipedia ja, Wikipedia en) ここではWikipediaにある疑似コードをほぼそのままの形で実装してみます。ランダムな重みつきエッジで構成される3x3のグリッドにおいて(0,0)から(2,2)への最短ルートを探索します。 以下ではヒューリスティック関数h*(n)として直線距離を使います。 が、上の設定では直線距離は を満たさないので、最短経路であることは保証されません…。 な
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
PythonでMapReduceっぽいものを実装してみる
