グラフ理論入門 | DevelopersIO
こんにちは、ドイツのモナでございます〜 いろんなサイエンスにおいてグラフ理論がとても重要な用具となっていますが、グラフ理論ってそもそも何なのかご存知ない方も少なくもないですね。 ということで、今日は簡単にグラフ理論の基本や用語など紹介したいと思います！なお、入門のため誰にでも分かるように数学的な定義は避けるようにします。 また、グラフ理論の応用は別の話ですので今回は応用の話しません〜 なぜグラフが面白いのか 具体的な応用の話はしませんが、たくさんの分野においてグラフ理論が重要となっています。 ネットワーク（例：トポロジー、ルーティングアルゴリズム） AI（例：ニューラルネットワーク） コンピューターサイエンス（例：ファイルシステム） 社会科学（例：ソーシャルネットワーク分析） 皆さんの生活の中（例：カーナビの最短ルートの計算） グラフ理論とは？ ここで議論するグラフというのは、よく思い浮か
Python言語による実務で使える100+の最適化問題 | opt100
指針 厳密解法に対しては、解ける問題例の規模の指針を与える。数理最適化ソルバーを使う場合には、Gurobi かmypulpを用い、それぞれの限界を調べる。動的最適化の場合には、メモリの限界について調べる。 近似解法に対しては、近似誤差の指針を与える。 複数の定式化を示し、どの定式化が実務的に良いかの指針を示す。 出来るだけベンチマーク問題例を用いる。OR-Libraryなどから問題例をダウンロードし、ディレクトリごとに保管しておく。 解説ビデオもYoutubeで公開する． 主要な問題に対してはアプリを作ってデモをする． 以下，デモビデオ： 注意 基本的には，コードも公開するが， github自体はプライベート そのうち本にするかもしれない（予約はしているが， 保証はない）． プロジェクトに参加したい人は，以下の技量が必要（github, nbdev, poetry, gurobi); ペー
桃太郎電鉄の「いけるかな」を実現する高速なアルゴリズムの実装と考察 - Qiita
この記事は「データ構造とアルゴリズム Advent Calendar 2020」16日目の記事です。 15日目の記事はyurahunaさんの「木分解上の動的計画法」で、 17日目の記事はtsukasa__diaryさんの「Lawler の K-Best 列挙アルゴリズム」です。 この記事内で使用しているプログラムやそのテストプログラムは全て以下のGitHubリポジトリで閲覧可能です。プログラムの詳細に興味がある方はこちらをご覧ください（ついでにStarを押していってくれると喜びます🙂）。 Github: ashiba/Imprementation_of_IKERUKANA: Momotaro Dentetsu is a game. 変更履歴 2020/12/21に「最終的に貧乏神が付かない移動方法 ～貧乏神持ちの場合～」, 「最終的に貧乏神が付かない移動方法 ～貧乏神がついていない場合～
競技プログラミングで解法を思いつくための典型的な考え方 | アルゴリズムロジック
競技プログラミングの問題を解くためには２つのステップがあります。 問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く 必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。 しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。 そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。 問われていることを、計算しやすい同値なことに置き換える方法アルゴリズムを思いつくための考え方競技プログラミングで「典型的」と思われる考え方 ※一部問題のネタバレを含むので注意 ※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。 入力の大きさ(制約)
ぷよぷよのアルゴリズムとMSX BASIC
再帰が現実的でないBASICで「盤面が与えられた時にどのぷよが消えるか」を計算するアルゴリズムが当時どうしても思いつかず「ぷよぷよ」にハマった時からずっと考えていました。 そしてある授業中に突然アルゴリズムがひらめきました。 以下がそのアルゴリズムのご紹介です。 フィールドが以下の様になっていると想定します。形だけ見ると「連鎖を作ろうとしてたけどやらかしちゃった」形ですね。 この場合、赤い「ぷよ」が消えることになります。 基本的な方針としては「左上から注目する場所（セル）を右下まで走査する」「注目したセルにある「ぷよ」がいくつつながっているか調べる」です。 1. まず、左上のセルに注目します。 2. 左上のセルには何も無かったので次のセルに注目します。 このセルには赤い「ぷよ」が居ました。 これ以降はこの赤い「ぷよ」がいくつつながっているか（=消せるか）をチェックします。 3.「この「ぷよ
エレベータに見るアルゴリズムの性能と公平性のバランス｜Rui Ueyama
現実世界でもコンピュータの中でも、何らかの性能指標だけを追求すると参加者にとって極端に不公平になってしまうことがある。例えばエレベータとHDDは共通点がありそうに思えないが、この2つは性能特性的にとてもよく似ていて、リーズナブルな性能と公平性を両立させるために同じ制御方法が使われている。これについてちょっと説明してみよう。 1基しかない場合のエレベータの動き方は単純だ。一度上に動き出すと、上で待ってる人や降りる人がいる限り上昇し続ける。同じように、一度下に動き出すと、下で待っている人や降りる人がいる限り下降し続ける。これ以外の動き方をするエレベータはまず存在しないので、これが唯一の制御方法のように思えるけど、別にこうしなければいけないというルールはない。 エレベータの平均待ち時間を最適化することを考えてみよう。そうすると、一方向に動き続ける代わりに、エレベータが現在存在する階に一番近い人の
私たちはいかにして環状線で”悪さをする列車”を捕まえたか | プログラミング | POSTD
文：Daniel Sim 分析：Lee Shangqian、Daniel Sim、Clarence Ng ここ数ヶ月、シンガポールのMRT環状線では列車が何度も止まるものの、その原因が分からないため、通勤客の大きな混乱や心配の種となっていました。 私も多くの同僚と同じように環状線を使ってワンノースのオフィスに通っています。そのため、11月5日に列車が止まる原因を調査する依頼がチームに来た時は、ためらうことなく業務に携わることを志願しました。 鉄道運営会社SMRTと陸上交通庁（LTA）による事前調査から、いくつかの電車の信号を消失させる信号の干渉があり、それがインシデントを引き起こすことが既に分かっていました。信号が消失すると列車の安全機能である緊急ブレーキが作動するため、不規則に電車が止まる原因となります。 しかし8月に初めて発生した今回のインシデントは、不規則に起こっているように見えるた
高速なハッシュテーブルを設計する | POSTD
(訳注：2016/9/28、頂きましたフィードバックを元に記事を修正いたしました。) はじめに 本稿では、高速で汎用的なハッシュテーブルを作るために行う、設計についての多くの意思決定事項を紹介します。最終的に、私の emilib::HashSet とC++11の std::unordered_set の間のベンチマークが出来上がりました。もし、ハッシュテーブルに興味があって、自分で設計したいなら（どのプログラミング言語かに関わらず）、本稿がヒントになるかもしれません。 ハッシュテーブル は、素晴らしい発明です。 ならし計算量O(1) ( O(√N)時間 )で、挿入、削除、検索を行うことができます。ならし計算量とは、ハッシュテーブルの計算に平均でO(1)の計算量がかかることを意味しますが、時々、これよりも多くの時間がかかる場合があります。具体的には、ハッシュテーブルに空きがない場合で、挿入の
機械学習のためのPython入門 クラスとメソッド編 - Beginning AI
機械学習にどのようなPythonの知識が必要かは、Python機械学習プログラミングの監訳者福島 真太朗（ふくしま しんたろう）さんが以下のように述べられています。 Pythonの文法については、リスト、タプル、ディクショナリなどの基本的なデータ構造、forループ、print関数、zip関数、enumerate関数、関数やクラスの作成方法などが理解できていれば十分です。 thinkit.co.jp そこで今回はPythonで書かれた機械学習のコードを読めるように、リスト、タプル、ディクショナリなどの基本的なデータ構造、forループ、print関数、zip関数、enumerate関数、関数やクラスの作成方法について学んでいきます。 従ってこの記事は、Pythonを一度もやったことがなく、機械学習のためにPythonを学びたいという人向けです。 今回読み解くPythonコードについて 今回は題
Linuxカーネルのコードを読んで勉強になったこと - φ(・・*)ゞ ｳｰﾝ カーネルとか弄ったりのメモ
Linuxカーネルのコードを読んでて、なるほど〜と思うことはよくあるけど、その中でも特に今までの考え方をぶち壊してくれたのはなんだっけと思ったところ、やっぱりリスト構造かなと言うところ。 c言語でリスト構造を作る場合、一般的な教科書方式だと↓のようにデータとnextポインタは密結合になってると思います。これの場合、struct foobarのポインタをnext要素に使っているので、他の構造体（例えば、struct hogehoge）で同じことをしようとすると、その構造体ではstruct hogehoge *nextというメンバ変数を持つ必要があります。 ヘッド要素はstruct foobarです。 struct foobar { int n; char s[64]; struct foobar *next; }; struct foobar head; Linuxカーネルの場合、データとリ
ITエンジニアなら知っておきたい、今更聞けないアルゴリズムの種類一覧 - paiza times
Photo by Oferico 皆さんはアルゴリズムやデータ構造について勉強したことはありますか？そして、基本的なアルゴリズムについて、どのようなものがあって、どのようなときに使うとよいかといったことを説明することができますか？ 仕事をしていると、プログラミング言語等の勉強や業務に忙しくて、正直アルゴリズムどころではないという場合がほとんどでしょう。しかし、いつか勉強しようと思っていたけど、基本的なアルゴリズムにどんなものがあるのかなんて今更聞けないな……ということもあるかと思います。 今回はそんな方に向けて、基本的なアルゴリズムの一部の概要に加え、アルゴリズムの勉強に役立つサイト、書籍をご紹介したいと思います。 ■アルゴリズムを学ぶ意味 例えば、ソート等については、通常はすでにソート関数があるので、自分で作らなくても済む＝アルゴリズムも勉強しなくていいと思ってしまうかもしれません。しか
ゲームAI -基礎編- 『知識表現と影響マップ』
みなさん、こんにちは! 突然ですが…皆さんには、ひいきにしている ゲームのキャラクターはいらっしゃいますでしょうか。 手ごわいボス敵や頼れるパートナー、愛嬌のある動きをするモンスター達は 一体どのような仕組みで動いているのでしょう？ 今回の記事ではそんなゲームの中のキャラクター達を 魅力的に動かす仕組み、AIについて御紹介したいと思います。 改めまして本記事を担当させて頂きます、Cygamesエンジニアの佐藤です。 これまでコンシューマ機でのゲームAI開発に携わり、 ゲームならではのキャラクター表現の楽しさを追いかけてきました。 このブログを通じて、皆さんのゲームのキャラクターを より表情豊かに魅力的なものにする方法について、皆さんと一緒に考えていければ幸いです。 今回はゲームのAIをデザインするにあたって重要となる、 「知識表現を定義する」というステップと、 知識表現の一つである影響マッ
本当に実用的なたったひとつのソートアルゴリズム - CARTA TECH BLOG
コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。 突然ですが、皆さんの好きなソートアルゴリズムはなんですか？ 私は基数ソートのスマートでストイックな雰囲気に惹かれます。 とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。 ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。 選手紹介 今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 1 挿入ソート シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！ 2 クイックソート 「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！ 3 マージソート 安定感のある隠れた実
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
強くなるためのプログラミング -プログラミングに関する様々なコンテストとそのはじめ方-#pyconjp