NetworkXで経路探索をやってみる。（グラフへコスト追加〜探索した経路の可視化） - Qiita
はじめに 前回、NetworkXでグラフの作成と、A*アルゴリズムによる経路探索をしました。 今回は、グラフにコストを追加して、経路探索してみます。 また、ノードとエッジに色をつけて、経路を可視化してみます 日常生活で、目的地への経路を考えるとき、近道 or 遠回り、混む道 or 空いている道などを考慮することもあります。 これらを、コストとして表現していきます。 通常、隣接するノード間の"距離"を、コストにすることが多いです。 今回のアウトプットは、下図です。 導出した経路を青色で塗りました。エッジ中央の数字がコストです。 コストのラベルに加え、各ノードの座標も描画しています。 見づらい気がしますが、ボスg... 重要な情報ですね。 コードを書いていく Step0. 準備 Python 3.8.6、NetworkX 2.6.2を使います。まず、import。 import numpy a
ダイクストラ法 - Wikipedia
ダイクストラ法の動作のアニメーション ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。 ダイクストラ法は、1959年エドガー・ダイクストラによって考案された。 応用範囲は広くOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されている。 ほかのアルゴリズムとして、 最短経路長の推定値を事前に知っているときは、ダイクストラ法の改良版であるA*アルゴリズムを用いて、より効率的に最短経路を求めることができる。 辺の重みが全て同一の非負数の場合は幅優先探索がより速く、線形時間で最短路を計算可能である。 無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズム[1]によって線形時間での計算が可能
補間やカーブフィッティングなどの最適化 - Qiita
実験などにより得られた観測値は、普通は飛び飛びの値になりますが、その間の値を求めたい時があります。その時に用いるのが、種々の補間法（補完ではありません）と、その他のカーブフィッティング（曲線近似）です。これらの解法は、プログラミング演習の題材としてよく使われますが、実用上は強力なライブラリが多数存在しますので、自作するよりも既存のライブラリを使ったほうが便利です。 計算機実験 ここでは、計算機実験として、以下の3つの数学関数 f(x), g(x), h(x) を用意します。 import numpy as np f = lambda x: 1/(1 + np.exp(-x)) g = lambda x: 1.0/(1.0+x**2) h = lambda x: np.sin(x)
曲線あてはめ - Wikipedia
曲線あてはめ（きょくせんあてはめ）またはカーブフィッティング（英: curve fitting）[1][2][3][4]は、実験的に得られたデータまたは制約条件に最もよく当てはまるような曲線を求めること。最良あてはめ、曲線回帰とも。一般に内挿や回帰分析を用いる。場合によっては外挿も用いる。回帰分析で曲線を求める場合、その曲線はデータ点を必ず通るわけではなく、曲線とデータ点群の距離が最小になるようにする。曲線あてはめによって得られた曲線を、近似曲線という。特に回帰分析を用いた場合には回帰曲線という。現実の実験データは直線的ではないことが多いため散布図、近似曲線を求める必要性は高い。 一般論[編集] 最小二乗法による最適関数の推定[編集] 我々が考えるべき問題は、実験データを実験を説明する「説明変数」と「目的変数」に分類した上で、説明変数 と、目的変数yの関係 を求めることである。説明変数とし
ノーフリーランチ定理 - Wikipedia
ノーフリーランチ定理（ノーフリーランチていり、no-free-lunch theorem、NFL）は、物理学者 David H. Wolpert と William G. Macready が生み出した組合せ最適化の領域の定理である。その定義は以下のようになる。 ……コスト関数の極値を探索するあらゆるアルゴリズムは、全ての可能なコスト関数に適用した結果を平均すると同じ性能となる — Wolpert and Macready、1995年 解説[編集] この定理の名称は、ハインラインのSF小説『月は無慈悲な夜の女王』（1966年）で有名になった格言の"There ain't no such thing as a free lunch."に由来する。かつて酒場で「飲みに来た客には昼食を無料で振る舞う」という宣伝が行われたが、「無料の昼食」の代金は酒代に含まれていて実際には「無料の昼食」なんてもの
【パターン認識】ＤＰマッチング - Qiita
はじめに 今日もパターン認識の一つ技術として重要なDPマッチングについて、コードを書いてみたので紹介します。DPは dynamic programmingで日本語では「動的計画法」と訳されています。これは、ナップサック問題のように、部分問題に分割して最適化問題を解く解法として紹介されることもありますが、ここでは時系列のマッチングに特化して話します。同じ内容をDTW(dynamic time warping)と呼ぶこともあります。要は、時系列の最適なマッチングを求める問題です。 最適な時系列のマッチング、って何？と思うかもしれませんが、例えば二つのテキストファイルを比較するdiff コマンドのようなものです。一致する行もあれば、抜けている行、余分に挿入されている行、文字が書き換わっている行、などがあるます。これらを含めて最適な行の対応付けは、ＤＰを用いて行えます。 どんな問題に使えるか？ 動
【Python】9.3.3：混合ベルヌーイ分布のEMアルゴリズムの実装【PRMLのノート】 - からっぽのしょこ
はじめに 『パターン認識と機械学習』の独学時のまとめです。一連の記事は「数式の行間埋め」または「R・Pythonでの実装」からアルゴリズムの理解を補助することを目的としています。本とあわせて読んでください。 この記事は、9.3.3項の内容です。混合ベルヌーイ分布に対するEMアルゴリズムによる最尤推定をPythonで実装します。 【数理編】 www.anarchive-beta.com 【他の節一覧】 www.anarchive-beta.com 【この節の内容】 はじめに ・Pythonで実装 ・MNISTデータセットの準備 ・初期値の設定 ・推論処理 ・コード全体 ・処理の解説 ・Eステップ ・Mステップ ・対数尤度の計算 ・推論結果の確認 ・パラメータの確認 ・学習の推移の確認 ・分類結果の確認 ・他の結果 参考文献 おわりに ・Pythonで実装 MNISTデータセットを用いて、混合
制約充足問題 - Wikipedia
制約充足問題（せいやくじゅうそくもんだい、英: Constraint satisfaction problem, CSP）は、複数の制約条件を満たすオブジェクトや状態を見つけるという数学の問題を指す。CSPは特に人工知能やオペレーションズ・リサーチで研究されている。多くのCSPでは、それなりの時間内に解くのにヒューリスティクスと組合せ最適化手法を組み合わせる必要がある。 制約充足問題の具体例: エイト・クイーン 四色問題 数独 充足可能性問題 制約充足問題を解くアルゴリズムとしては、AC-3アルゴリズム、バックトラッキング、制約違反最小化などがある。 参考文献[編集] Tsang, Edward (1993年). Foundations of Constraint Satisfaction. Academic Press. ISBN 0-12-701610-4 Dechter, Rina
マルコフ過程 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "マルコフ過程" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2018年1月) マルコフ過程（マルコフかてい、英: Markov process）とは、マルコフ性をもつ確率過程のことをいう。すなわち、未来の挙動が現在の値だけで決定され、過去の挙動と無関係であるという性質を持つ確率過程である。 このような過程は例えば、確率的にしか記述できない物理現象の時間発展の様子に見られる。なぜなら、粒子の将来の挙動は現在の挙動によってのみ決定されるが、この性質は系の粒子数が多くなり確率論的な解析を必要とする状態にも引き継がれるからである。 ロシア人
or58_6_311.dvi
c � M L 1. 1 M L 2. 1 113–8656 7–3–1 2.1 [ ] [ ] 2.2 2013 6 Copyright c � by ORSJ. Unauthorized reproduction of this article is prohibited. 3 311 (LP) [ ] 1 • —[ Conv] • —[ LocalOpt] • —[ DualPair] • —[ MinMax] • Farkas —[ Separ] 3. 1 1 1 2 R Z R, Z (+∞) R, Z (−∞) R, Z f : Z → R f(x − 1) + f(x + 1) ≥ 2f(x) (∀x ∈ Z) (1) (x, f(x)) 2 f : R → R 1 2 1 2 f(x) = f(x) (∀x ∈ Z) (2) f f f 2 3.1 (Conv) f : Z
参照の局所性 - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Locality of reference|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針に
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
最短経路 — 読書ノート 1.6dev documentation
Pythonで自立系移動計画を考えて見る
https://ocw.u-tokyo.ac.jp/lecture_files/engin_01/5/notes/ja/E1-DPmatching.pdf
ロボットの最適な設計をアルゴリズムが考えると、驚くほど「奇妙な形状」ができあがる
https://www.jstage.jst.go.jp/article/isciesci/49/4/49_KJ00003364261/_pdf