[アルゴリズム] タグが付いた質問
アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。
31
未回答やベストアンサーなし質問
6
票
0
回答
332
閲覧数
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 ...
5
票
0
回答
64
閲覧数
Proof of Stakeのコンセンサスアルゴリズムで、validatorを選ぶノードは分散的に存在しているのでしょうか?
Proof of Stakeのコンセンサスアルゴリズムは、Stakeしているコインの量に応じてランダムにValidatorが選ばれ、ValidatorがTransactionを承認します。不正するとStakeしているコインが没収されてしまうため、不正をしないモチベーションが働きます。そのため、51%攻撃は実質不可能とされています。
色々な資料を読んでいても、...
5
票
0
回答
151
閲覧数
グラフ構造の探索に対応するデータ構造には法則があるのでしょうか?
グラフ構造、たとえばツリー構造を探索することを考えます。
ツリー構造の場合は、探索の例は幅優先探索や、深さ優先探索があります。
この時、
幅優先探索はしばしばキューを用いて
深さ優先探索はしばしばスタックを用いて
それぞれ実装されます。
これはちょうど、
各ノードを訪問した時に、そこから見えるまだ未探索のノードについて適当な順序で push() を行う
次のノードを pop() ...
4
票
0
回答
141
閲覧数
R木系(特に PR 木)のアルゴリズムを理解したい
位置情報などを効率的にインデックスするための手法として、R木があります。
質問
R木(特に、 PR 木)をどうやって実装するのか、とくに、そのアルゴリズムを知りたいと思っています。当たれる書籍などはありますか?
3
票
1
回答
138
閲覧数
gurobi からpyomoへの変換
pythonでgurobiからpyomoへ二次制約付き問題であるため、変更したいのですがやり方がわからなくて困っています。
from gurobipy import *
import pandas as pd
import numpy as np
import csv
from pyomo.environ import SolverFactory
opt = SolverFactory("...
3
票
0
回答
112
閲覧数
git で subtree strategy でのマージの挙動は?
git merge -s subtree とすると、 subtree の strategy でマージを行うことができます。このときのマージを計算するアルゴリズムの挙動が、いまいちわかっていないです。
疑似コードぐらいの粒度で、このマージアルゴリズムの挙動を説明すると、どのようなものになりますか?
3
票
0
回答
717
閲覧数
ウェーブレット変換とフーリエ変換の計算量
離散ウェーブレット変換の計算量はO(N)で、高速フーリエ変換の場合はO(N log N)になるそうですが
離散ウェーブレット変換の式も Σ(シグマ記号:summation)が2つのため二重ループになり
O(N^2)になると思うのですが、なぜ、O(N)になるのですか?
2
票
0
回答
82
閲覧数
レイティングを利用した推薦システムのアルゴリズム手法について
現在、レビューサイトにおける商品推薦システムのアルゴリズム改善に携わっております。
検索者が希望条件(例えば、機能、価格、使いやすさなど)とその重視度を入力すると、商品の利用者であるレビュアーが入力した各要素のレイテイングをもとに検索者の希望条件に合致すると思われる商品をランキング形式で提示し、商品詳細とレビューが見れるようなサイトです。
そこで質問なのですが、...
2
票
1
回答
195
閲覧数
OpenGLにて、図形をマウスで引いた直線で切断したいがアルゴリズムが分からない。
OpenGLで図形をマウスで引いた直線で切断するようなプログラムを実装したいと考えています。
OpenGLのversionは4.6ですが、こちら(http://wisdom.sakura.ne.jp/system/opengl/)のver1.1に基づいたチュートリアルを勉強しています。
ユーザーが何も手を加えていない初期状況は、...
2
票
0
回答
236
閲覧数
クイックソートにおけるデータ列のソートの仕方について
はじめまして。
アルゴリズム初心者でクイックソートでつまづいております。
{5,3,2,6,4,1,3,7}というデータ列で、真ん中の4を基準値(ピボット)とした場合(6と4の間にパーテーションを設けた場合、)どのように(昇順)ソートされていくか順を追ってご説明頂けますと幸いです。
※自分で試した場合、なぜか昇順でソートすることができませんでした。(1が最左端に来ず、並び順が{3,3,2,1,:...
1
票
1
回答
188
閲覧数
SNSのアカウント価値の計算アルゴリズムについて
アルゴリズムの相談なんですがやや抽象的な話で
純粋なプログラミング技術の話ではなくここでしていい質問かわからないんですが
(だめなら消します)
SNSのアカウントクオリティみたいなのを数値化したいと思っています
例えばツイッターを例にあげると
フォロー数 フォロワー数 開始日時
の3つがすぐ手に入り
一応時間をかければ ツイート数 やリプ数 RT数
...
1
票
1
回答
73
閲覧数
楽天市場で検索したときにサイドバーにある商品価格の分布はどのようなアルゴリズムで表示されてますか
楽天市場で検索したときにサイドバーにある商品価格の分布はどのようなアルゴリズムで表示されてますか
ぱっと思いつくのはSQLのGROUP BYを使うことですが、
数十万件ヒットする結果でも、非常に高速に表示されていて、
なにか集計用の高速に実行できるようなアルゴリズムがあるのではないかと思っています。
1
票
0
回答
220
閲覧数
バケツソートの最低ケースを改善するためには
バケツソート(Bucket Sort)の平均計算量はO(n)ですが、もしデータが均一に分布してない場合、最悪計算量はO(n^2)になってしまいます。しかし、その場合他のアルゴリズムと組み合わせることによって計算量は改善できるのでしょうか?
教科書からの問題なのですが、二分探索を使用できるというヒントを与えられました。しかし、二分探索を使用する意味がよくわかりません。Merge ...
1
票
0
回答
76
閲覧数
ベクトルで表せる能力値を持ったキャラクター(個体)たちのうち、上位互換が存在しないものたちを選びたい
たとえば、 RPG のキャラクターは、いろいろな能力値をもっています。(体力・素早さ・etc...)
つまりは、それぞれのキャラクター能力は、ベクトルで表せる、と表現できます。
# 例えば、 pandas を用いてキャラクター能力値を表現する
chara1 = pd.Series({'power': 1, 'speed': 2, 'magic': 3})
chara2 = pd.Series({...
1
票
0
回答
764
閲覧数
BPE (Byte Pair Encoding、バイト対符号化)の効率のいい実装について
お世話になっています。さて厳密にはBPEではないと思いますが、類似のアイディアを文字列に適用したものがあります。
辞書に3つの単語があるとします(本番はもっと巨大な辞書を使います)
我
喜欢
水果
そして次の入力を取ります。
我喜欢水果
これを1文字ずつに分解します。
我 喜 欢 水 果
隣り合う2つの文字を連結して辞書引きをします。
我喜
喜欢 <- in the dic
...
1
票
0
回答
1,641
閲覧数
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
回答
312
閲覧数
キューの末尾の判定について~リングバッファ~ アルゴリズムとデータ構造
現在、こちらの記事を読んでいてリングバッファの際の末尾の判定基準が分かりません。
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 100000; // キュー配列の最大サイズ
int qu[MAX]; // キューを表す配列
int tail = 0, head = 0; ...
0
票
1
回答
303
閲覧数
区間が重なるタイミング
それぞれある周期で循環する0と1の数列があります。
例:
010101010101...(周期2)
001100110011...(周期4)
000111000111...(周期6)
ここで、縦列が全て1になる最初の列番号やその割合を求めたいです。
上の例では最初に4列目(次に12列目)で1が揃い、無限数列全体の1/6が揃っています。
最初の列番号を求める方法は今のところ、...
0
票
1
回答
383
閲覧数
三目並べ、三つの盤面で同時、✖のみ使用 先手の必勝法を考える
このゲームでは先手に必勝法がある。参照Youtube:Numberphile 3 board tic tac toe
ただし、プログラミングに落とし込むぐらいの簡単な必勝法がみつからない。
目標はその必勝法を利用して疑似AIを作ること。
ルール:
このゲームの盤面は基本的に三つの三目ならべのボードで構成されている
参加者二名が使う印は”X”で共通
ひとりずつ任意の格子に印をつける
...
0
票
2
回答
219
閲覧数
集合当てクイズの解法
次のようなゲームを考えます。
アルファベット 'A'~'Z'を全体集合とし、その部分集合が一つ与えられているとします。これを答えと呼びます。
プレイヤーは1ターンにつき次の問い合わせを一回出来ます。
問い合わせ:アルファベット'A'~'Z'の集合を一つ入力とし、答えと入力の積集合が空集合であるか否かがYes/Noで返ってくる。
これで答えが確定するまでのターン数を競います。
...
0
票
1
回答
117
閲覧数
pythonで、intersectionの位置を調べる方法を教えて下さい。
#条件:データに重複は、ありません。
x = {"a", "b", "c"}
y = {"c", "b", "e"}
z = {"f", "b", "c"}
result = x.intersection(y, z)
...
0
票
0
回答
101
閲覧数
Atcoder abc165_c 期待する答えが出力されません
以下のコードで Atcoder abc165_c (https://atcoder.jp/contests/abc165/tasks/abc165_c)の入力例を試したのですが、すべてで 0 が返ってきます。どなたか理由を教えていただけたら嬉しいです。
方向性としては、func 内でDFS的にAが求まるたびに得点を求め、その最大値を更新しています。
Atcoder abc165_c
問題概要
Q ...
0
票
0
回答
173
閲覧数
ASCIIで記述した回路を図面に変換するアルゴリズムを探す
現在ASCIIで記述したノードとノードとのつながりを図面に変換するアルゴリズムを探します。
特に、Synopsys VerdiのようにVerilog HDL/VHDLコードからきれいな理解しやすい回路図を生成したい。どんなアルゴリズムでこれを果たすことができますか。
ノードの形は何でも構いません。
0
票
1
回答
308
閲覧数
二次元配列に条件付きで数字を代入
与えられた数字を二次元で保存したいです。例えば、数列{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
回答
115
閲覧数
2つのいくつかのノードを共有する連結リストをソートしたい
最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか?
たとえば
-900->120->200->230
\
452->700
/
-10->200
...
0
票
0
回答
155
閲覧数
分析のためにゲーム木を描写したくなったとき、利用可能なライブラリ・フレームワークは何がありますか?
ターン制の対戦ゲームは、基本的にゲーム木を構築できます。たとえば○×ゲーム(tic-tac-toe)のゲーム木はこちらです。
Game tree for Tic-Tac-Toe game using MiniMax algorithm.
今、ふとした分析のために、このようにゲーム木を描写したくなりました。
質問
ゲーム木を描写する機能を持った、つまり、ゲーム木の可視化ができる、...
0
票
0
回答
188
閲覧数
1枚の画像からワールド座標を取得する
F地点の座標(xL,yF,zo)を求めたいです.ただし,L,F,Cの座標はわかっているものとします.
何かよい導出方法ありませんか?
考えたこととして,
カメラの外部パラメータから回転並進行列を求めるP3P問題があり,求めようとしましたが,
ワールド座標と画面座標の3つの対応付けが必要で行き詰りました.
よろしくお願いします.
0
票
0
回答
466
閲覧数
安定な比較ソートでの最高速アルゴリズムはなんですか?
安定な比較ソートを開発しています。
平均計算時間で最速なものを目指しています。
ソートされるデータ以外の格納領域が O(n) ぐらいは使用して良いと思っています。
安定でない比較ソートであれば、クイックソートが最速なのだと思っています。
glibc の qsort は
malloc に成功すれば 16*n バイトぐらい O(n) 格納領域を使用し
マージソートを実行します。なので安定です。
...
-1
票
0
回答
93
閲覧数
leetcode 345. Reverse Vowels of a String:Inputがrace carの時、"raca cer"が出力される(期待値は"race car")
現在、leetcode 345. Reverse Vowels of a Stringを解いています。
下記が問題文(*1)と例題(*2)です
事象は、与えられる文字列が"race car"の時、"raca cer"が出力されてしまうことです。
期待値は、"race car"が出力されることです。
コードは'(*3)にあります。
raca ...
-1
票
1
回答
276
閲覧数
Atcoder ATC001 A 深さ優先探索をC++で再帰を用いて実装したがTLEになってしまう
ATC001 A 深さ優先探索をC++で以下のように実装しましたが、88個中12個TLE、2個MLEになってしまいました。
再帰を用いています。
goalの座標も引数に渡して、v=goalとなったらreturnするというのも試しましたが、ダメでした。
どう直せば良いでしょうか。
#include <bits/stdc++.h>
using namespace std;
vector&...
-1
票
2
回答
488
閲覧数
なぜこのコードは非効率なのか?
F - ヘビの JOI 君に挑戦したのですがTLEになります。
しかし、なぜ自分のコードが非効率なのかがわかりません。コードの問題点などを教えていただけないでしょうか。下が自分のコードです。
int N, M,X,T[10000];
struct edge{
int to,cost;
};
struct situ {
int cost,v,dist,type;
...