[アルゴリズム] タグが付いた質問
アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。
31
未回答やベストアンサーなし質問
5
票
0回答
184 件の閲覧数
Git のマージ戦略 “resolve” とはどのような戦略ですか?
git merge のマージ戦略には resolve というものがあります。
resolve
This can only resolve two heads (i.e. the current branch and another branch you pulled from) using a 3-way merge algorithm. It tries to carefully ...
4
票
0回答
180 件の閲覧数
ランダムに複数引いた通路の幅が同じになるように整形する方法
ランダムでダンジョンのマップを作成しようとしています。
上の画像のように2つの部屋があり、その間を、2マスの幅がある通路でつなぎます。
通路の始点、終点や折れ曲がる地点はランダムで決まります。
さらに通路を追加します。
二度目以降に通路を追加する際、以前に引いた通路を気にせずに引くので、以前に引いた通路と一部が重なったり、隣り合ったりする場合があります。
こうして2、3回通路を引いた後で、...
4
票
0回答
102 件の閲覧数
git で subtree strategy でのマージの挙動は?
git merge -s subtree とすると、 subtree の strategy でマージを行うことができます。このときのマージを計算するアルゴリズムの挙動が、いまいちわかっていないです。
疑似コードぐらいの粒度で、このマージアルゴリズムの挙動を説明すると、どのようなものになりますか?
3
票
0回答
77 件の閲覧数
R木系(特に PR 木)のアルゴリズムを理解したい
位置情報などを効率的にインデックスするための手法として、R木があります。
質問
R木(特に、 PR 木)をどうやって実装するのか、とくに、そのアルゴリズムを知りたいと思っています。当たれる書籍などはありますか?
3
票
0回答
136 件の閲覧数
AIで顔のパーツを認識するライブラリ
最初にAI系のプログラムをかいたことはなくて
大学の講義で分類器とか Deep Learning の仕組みを少しかじった程度なんですが
やりたいことは2次元のキャラ画像を入力に与えたときにその属性を自動抽出したいです
まずは簡単そうなところで髪色と瞳の色あたりを認識したいんですが
画像を入力して顔のパーツを自動抽出するようなフリーライブラリはありますでしょうか
...
3
票
0回答
114 件の閲覧数
グラフ構造の探索に対応するデータ構造には法則があるのでしょうか?
グラフ構造、たとえばツリー構造を探索することを考えます。
ツリー構造の場合は、探索の例は幅優先探索や、深さ優先探索があります。
この時、
幅優先探索はしばしばキューを用いて
深さ優先探索はしばしばスタックを用いて
それぞれ実装されます。
これはちょうど、
各ノードを訪問した時に、そこから見えるまだ未探索のノードについて適当な順序で push() を行う
次のノードを pop() ...
3
票
0回答
610 件の閲覧数
ウェーブレット変換とフーリエ変換の計算量
離散ウェーブレット変換の計算量はO(N)で、高速フーリエ変換の場合はO(N log N)になるそうですが
離散ウェーブレット変換の式も Σ(シグマ記号:summation)が2つのため二重ループになり
O(N^2)になると思うのですが、なぜ、O(N)になるのですか?
2
票
0回答
44 件の閲覧数
matlabでnsga2を実装.目的関数の範囲指定,設計変数と目的変数の最大化を行いたい.
NSGA2をmatlabで動かせるよう以下のURLからダウンロードし実装.
https://jp.mathworks.com/matlabcentral/fileexchange/10429-nsga-ii-a-multi-objective-optimization-algorithm
実際に動かしてみて,成功はしたのですが
目的変数はすべて最小化
設計変数の範囲のみが指定可能
...
2
票
0回答
73 件の閲覧数
0-1整数2次計画問題に関する数理最適化のアルゴリズムについて
数理最適化に関するアルゴリズムに関して学習しています。
0-1整数2次計画に関して分岐限定法で厳密解などを解くらしいのですが、
調べても連続変数の2次計画の問題に関する内容が多く、私の検索能力が低くて見つけられません。
0-1整数2次計画問題に関して
https://www.letsopt.com/entry/2019/08/18/131125
...
2
票
0回答
109 件の閲覧数
バケツソートの最低ケースを改善するためには
バケツソート(Bucket Sort)の平均計算量はO(n)ですが、もしデータが均一に分布してない場合、最悪計算量はO(n^2)になってしまいます。しかし、その場合他のアルゴリズムと組み合わせることによって計算量は改善できるのでしょうか?
教科書からの問題なのですが、二分探索を使用できるというヒントを与えられました。しかし、二分探索を使用する意味がよくわかりません。Merge ...
2
票
0回答
225 件の閲覧数
クイックソートにおけるデータ列のソートの仕方について
はじめまして。
アルゴリズム初心者でクイックソートでつまづいております。
{5,3,2,6,4,1,3,7}というデータ列で、真ん中の4を基準値(ピボット)とした場合(6と4の間にパーテーションを設けた場合、)どのように(昇順)ソートされていくか順を追ってご説明頂けますと幸いです。
※自分で試した場合、なぜか昇順でソートすることができませんでした。(1が最左端に来ず、並び順が{3,3,2,1,:...
1
票
0回答
63 件の閲覧数
ノードの長さを自由に持てるツリーの最適配置アルゴリズム
現在、マインドマップを自作しようとしておりますが、ノードの配置のアルゴリズムについて困っています。
作ろうとしているツリーの条件は以下を考えています。
Y軸のトップにルートノードを1つ持つ
親ノードから、子ノードを複数持つことができる
ノードとそれを連結する線は重ならないが、可能な限り近くに配置される
親ノードのX軸の位置は、その子ノードの中央になる
X軸方向で、...
1
票
1回答
65 件の閲覧数
楽天市場で検索したときにサイドバーにある商品価格の分布はどのようなアルゴリズムで表示されてますか
楽天市場で検索したときにサイドバーにある商品価格の分布はどのようなアルゴリズムで表示されてますか
ぱっと思いつくのはSQLのGROUP BYを使うことですが、
数十万件ヒットする結果でも、非常に高速に表示されていて、
なにか集計用の高速に実行できるようなアルゴリズムがあるのではないかと思っています。
1
票
0回答
195 件の閲覧数
要素数nのヒープの深さと各深さにおける要素数を求める方法について
ヒープの深さと各深さにおける要素数を求める方法について調べていますが、関数などを見つけることができず、どのように求めるべきかわかりません。
import heapq
a = [6, 3, 2, 4, 5]
heapq.heapify(a)
例えば上記の場合、手で図を描いてみると、ヒープの深さ(0始まりとする)は最大で2となり、各深さにおける要素数は深さ0で1, 深さ1で2、深さ2で2となります。...
1
票
0回答
70 件の閲覧数
ベクトルで表せる能力値を持ったキャラクター(個体)たちのうち、上位互換が存在しないものたちを選びたい
たとえば、 RPG のキャラクターは、いろいろな能力値をもっています。(体力・素早さ・etc...)
つまりは、それぞれのキャラクター能力は、ベクトルで表せる、と表現できます。
# 例えば、 pandas を用いてキャラクター能力値を表現する
chara1 = pd.Series({'power': 1, 'speed': 2, 'magic': 3})
chara2 = pd.Series({...
1
票
0回答
627 件の閲覧数
BPE (Byte Pair Encoding、バイト対符号化)の効率のいい実装について
お世話になっています。さて厳密にはBPEではないと思いますが、類似のアイディアを文字列に適用したものがあります。
辞書に3つの単語があるとします(本番はもっと巨大な辞書を使います)
我
喜欢
水果
そして次の入力を取ります。
我喜欢水果
これを1文字ずつに分解します。
我 喜 欢 水 果
隣り合う2つの文字を連結して辞書引きをします。
我喜
喜欢 <- in the dic
...
1
票
0回答
1,266 件の閲覧数
Levenberg-Marquardt法の結果がEigenとGnuplotで異なるのはなぜでしょうか
C++の数値計算ライブラリEigenに含まれる、非線形最小二乗法(Levenberg-Marquardt法)で関数フィッティングを実行してみました
開発環境はVisual Studio 2015です
フィッティング対象の関数は、y = a×cos(x)^b で、ノイズを含む観測データx,yからパラメータa,bを求めます
#include <iostream>
#include <...
0
票
1回答
49 件の閲覧数
エラー: 'closure' 型のオブジェクトは部分代入可能ではありません
Bootstrap法によって機械学習アルゴリズムの精度を検証するプログラムを作っています。
以下のコードをテキストで作成し、CSVdataをread.csvで読み込んで、以下のように実行すると
> source("text.txt")
> exdata=read.csv("final_output.csv",header=TRUE)
> ...
0
票
0回答
77 件の閲覧数
Atcoder abc165_c 期待する答えが出力されません
以下のコードで Atcoder abc165_c (https://atcoder.jp/contests/abc165/tasks/abc165_c)の入力例を試したのですが、すべてで 0 が返ってきます。どなたか理由を教えていただけたら嬉しいです。
方向性としては、func 内でDFS的にAが求まるたびに得点を求め、その最大値を更新しています。
Atcoder abc165_c
問題概要
Q ...
0
票
0回答
86 件の閲覧数
平叙文(穴埋め問題)から疑問文(一問一答問題)を作成したい
教科書の文から作った穴埋め問題を一問一答形式の問題にしたいです。
例)(文)メフメト2世はビザンツ帝国を滅ぼした (空所単語)ビザンツ帝国
→(問)メフメト2世が滅ぼしたのはどこ。(答)ビザンツ帝国
現実的に可能かどうか教えてください。
以下のような手順で作成しようと思っています。
品詞分解(形態素解析)
↓
単文・複文・重文の判別(主語述語の個数、並べ方から判別。...
0
票
0回答
85 件の閲覧数
ASCIIで記述した回路を図面に変換するアルゴリズムを探す
現在ASCIIで記述したノードとノードとのつながりを図面に変換するアルゴリズムを探します。
特に、Synopsys VerdiのようにVerilog HDL/VHDLコードからきれいな理解しやすい回路図を生成したい。どんなアルゴリズムでこれを果たすことができますか。
ノードの形は何でも構いません。
0
票
0回答
45 件の閲覧数
クロスオーバー試験におけるSAS proc glm 2段階の解析方法:absorbステートメントについて
「SASによる実験データの解析(初版)」を参照しています。「8-2分散分析」の項で、「2段階にGLMプロシジャを分割する」方法が紹介されています。一般的な方法(分割しない)でできますが、クロスオーバー試験における分散分析を勉強するため確認しています。2段階の方法で分からないことが以下2点あります。どなたかアドバイスをお願いしてもよろしいでしょうか。
1.1段階目のproc ...
0
票
0回答
46 件の閲覧数
backlog 的なウェブアプリを開発する際に、そのイベントと永続化のモデルはどう実装するのが良い?
シンプルな todo リストに、任意に順番を付与できるようなウェブアプリを開発するとします。さらに、その順番は Drag & Drop で移動可能であるとします。
今、この機能を、 UX の目的で、フロントとバックエンドの処理を非同期に行いたいとします。つまり、フロントの状態は Drag の後の Drop の際に update してしまい、...
0
票
1回答
203 件の閲覧数
二次元配列に条件付きで数字を代入
与えられた数字を二次元で保存したいです。例えば、数列{3,12,4,1,5,8}を与えられたとして、一番目の数字3を配列1に挿入、二番目の数字12は、3より大きいので別の配列2に挿入、左から走査し、4は12より小さいので配列2に挿入、1は左から走査し3より小さいので配列1に挿入...ということを行いたいです。
構造的には、二次元リスト
int s = {3,12,4,1,5,8}
int ...
0
票
2回答
93 件の閲覧数
2つのいくつかのノードを共有する連結リストをソートしたい
最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか?
たとえば
-900->120->200->230
\
452->700
/
-10->200
...
0
票
0回答
107 件の閲覧数
分析のためにゲーム木を描写したくなったとき、利用可能なライブラリ・フレームワークは何がありますか?
ターン制の対戦ゲームは、基本的にゲーム木を構築できます。たとえば○×ゲーム(tic-tac-toe)のゲーム木はこちらです。
Game tree for Tic-Tac-Toe game using MiniMax algorithm.
今、ふとした分析のために、このようにゲーム木を描写したくなりました。
質問
ゲーム木を描写する機能を持った、つまり、ゲーム木の可視化ができる、...
0
票
0回答
111 件の閲覧数
1枚の画像からワールド座標を取得する
F地点の座標(xL,yF,zo)を求めたいです.ただし,L,F,Cの座標はわかっているものとします.
何かよい導出方法ありませんか?
考えたこととして,
カメラの外部パラメータから回転並進行列を求めるP3P問題があり,求めようとしましたが,
ワールド座標と画面座標の3つの対応付けが必要で行き詰りました.
よろしくお願いします.
0
票
0回答
301 件の閲覧数
安定な比較ソートでの最高速アルゴリズムはなんですか?
安定な比較ソートを開発しています。
平均計算時間で最速なものを目指しています。
ソートされるデータ以外の格納領域が O(n) ぐらいは使用して良いと思っています。
安定でない比較ソートであれば、クイックソートが最速なのだと思っています。
glibc の qsort は
malloc に成功すれば 16*n バイトぐらい O(n) 格納領域を使用し
マージソートを実行します。なので安定です。
...
0
票
0回答
93 件の閲覧数
関数呼び出しを用いたプログラムから動的計画法のプログラムを書く時に用いる再帰関係について
配列が与えられ、連続する1の最も長い個数を出力するプログラムを書いています。
例えば、入力が[1,1,0,0,0,1,1,1,1,0,0]なら、4が出力されます。
困っていること
再帰表現を用いたプログラムは正しい出力が得られるのですが、関数countones(A, i)内の再帰関係を以下のように分割し、動的計画法で書いたプログラムも正しく動いたのですが、...
0
票
2回答
321 件の閲覧数
なぜこのコードは非効率なのか?
F - ヘビの JOI 君に挑戦したのですがTLEになります。
しかし、なぜ自分のコードが非効率なのかがわかりません。コードの問題点などを教えていただけないでしょうか。下が自分のコードです。
int N, M,X,T[10000];
struct edge{
int to,cost;
};
struct situ {
int cost,v,dist,type;
...
-1
票
0回答
46 件の閲覧数