[アルゴリズム] タグが付いた質問

アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。

31 未回答やベストアンサーなし質問
絞り込み
並べ替え
タグ付けされた
6
0 回答
296 閲覧数

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 ...
nekketsuuu's user avatar
  • 2.3万
5
0 回答
61 閲覧数

Proof of Stakeのコンセンサスアルゴリズムで、validatorを選ぶノードは分散的に存在しているのでしょうか?

Proof of Stakeのコンセンサスアルゴリズムは、Stakeしているコインの量に応じてランダムにValidatorが選ばれ、ValidatorがTransactionを承認します。不正するとStakeしているコインが没収されてしまうため、不正をしないモチベーションが働きます。そのため、51%攻撃は実質不可能とされています。 色々な資料を読んでいても、...
tommy19970714's user avatar
5
0 回答
135 閲覧数

グラフ構造の探索に対応するデータ構造には法則があるのでしょうか?

グラフ構造、たとえばツリー構造を探索することを考えます。 ツリー構造の場合は、探索の例は幅優先探索や、深さ優先探索があります。 この時、 幅優先探索はしばしばキューを用いて 深さ優先探索はしばしばスタックを用いて それぞれ実装されます。 これはちょうど、 各ノードを訪問した時に、そこから見えるまだ未探索のノードについて適当な順序で push() を行う 次のノードを pop() ...
rugamaga's user avatar
  • 905
4
0 回答
134 閲覧数

R木系(特に PR 木)のアルゴリズムを理解したい

位置情報などを効率的にインデックスするための手法として、R木があります。 質問 R木(特に、 PR 木)をどうやって実装するのか、とくに、そのアルゴリズムを知りたいと思っています。当たれる書籍などはありますか?
Yuki Inoue's user avatar
  • 1.6万
3
0 回答
111 閲覧数

git で subtree strategy でのマージの挙動は?

git merge -s subtree とすると、 subtree の strategy でマージを行うことができます。このときのマージを計算するアルゴリズムの挙動が、いまいちわかっていないです。 疑似コードぐらいの粒度で、このマージアルゴリズムの挙動を説明すると、どのようなものになりますか?
Yuki Inoue's user avatar
  • 1.6万
3
0 回答
710 閲覧数

ウェーブレット変換とフーリエ変換の計算量

離散ウェーブレット変換の計算量はO(N)で、高速フーリエ変換の場合はO(N log N)になるそうですが 離散ウェーブレット変換の式も Σ(シグマ記号:summation)が2つのため二重ループになり O(N^2)になると思うのですが、なぜ、O(N)になるのですか?
user avatar
2
0 回答
80 閲覧数

レイティングを利用した推薦システムのアルゴリズム手法について

現在、レビューサイトにおける商品推薦システムのアルゴリズム改善に携わっております。 検索者が希望条件(例えば、機能、価格、使いやすさなど)とその重視度を入力すると、商品の利用者であるレビュアーが入力した各要素のレイテイングをもとに検索者の希望条件に合致すると思われる商品をランキング形式で提示し、商品詳細とレビューが見れるようなサイトです。 そこで質問なのですが、...
Yamazaki Ken's user avatar
2
1 回答
118 閲覧数

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("...
炎天下修羅's user avatar
2
1 回答
189 閲覧数

OpenGLにて、図形をマウスで引いた直線で切断したいがアルゴリズムが分からない。

OpenGLで図形をマウスで引いた直線で切断するようなプログラムを実装したいと考えています。 OpenGLのversionは4.6ですが、こちら(http://wisdom.sakura.ne.jp/system/opengl/)のver1.1に基づいたチュートリアルを勉強しています。 ユーザーが何も手を加えていない初期状況は、...
Hirose's user avatar
  • 23
2
0 回答
234 閲覧数

クイックソートにおけるデータ列のソートの仕方について

はじめまして。 アルゴリズム初心者でクイックソートでつまづいております。 {5,3,2,6,4,1,3,7}というデータ列で、真ん中の4を基準値(ピボット)とした場合(6と4の間にパーテーションを設けた場合、)どのように(昇順)ソートされていくか順を追ってご説明頂けますと幸いです。 ※自分で試した場合、なぜか昇順でソートすることができませんでした。(1が最左端に来ず、並び順が{3,3,2,1,:...
user26303's user avatar
  • 131
1
1 回答
176 閲覧数

SNSのアカウント価値の計算アルゴリズムについて

アルゴリズムの相談なんですがやや抽象的な話で 純粋なプログラミング技術の話ではなくここでしていい質問かわからないんですが (だめなら消します) SNSのアカウントクオリティみたいなのを数値化したいと思っています 例えばツイッターを例にあげると フォロー数 フォロワー数 開始日時 の3つがすぐ手に入り 一応時間をかければ ツイート数 やリプ数 RT数  ...
user avatar
1
1 回答
71 閲覧数

楽天市場で検索したときにサイドバーにある商品価格の分布はどのようなアルゴリズムで表示されてますか

楽天市場で検索したときにサイドバーにある商品価格の分布はどのようなアルゴリズムで表示されてますか ぱっと思いつくのはSQLのGROUP BYを使うことですが、 数十万件ヒットする結果でも、非常に高速に表示されていて、 なにか集計用の高速に実行できるようなアルゴリズムがあるのではないかと思っています。
or1ko's user avatar
  • 11
1
0 回答
196 閲覧数

バケツソートの最低ケースを改善するためには

バケツソート(Bucket Sort)の平均計算量はO(n)ですが、もしデータが均一に分布してない場合、最悪計算量はO(n^2)になってしまいます。しかし、その場合他のアルゴリズムと組み合わせることによって計算量は改善できるのでしょうか? 教科書からの問題なのですが、二分探索を使用できるというヒントを与えられました。しかし、二分探索を使用する意味がよくわかりません。Merge ...
Avril's user avatar
  • 107
1
0 回答
75 閲覧数

ベクトルで表せる能力値を持ったキャラクター(個体)たちのうち、上位互換が存在しないものたちを選びたい

たとえば、 RPG のキャラクターは、いろいろな能力値をもっています。(体力・素早さ・etc...) つまりは、それぞれのキャラクター能力は、ベクトルで表せる、と表現できます。 # 例えば、 pandas を用いてキャラクター能力値を表現する chara1 = pd.Series({'power': 1, 'speed': 2, 'magic': 3}) chara2 = pd.Series({...
Yuki Inoue's user avatar
  • 1.6万
1
0 回答
753 閲覧数

BPE (Byte Pair Encoding、バイト対符号化)の効率のいい実装について

お世話になっています。さて厳密にはBPEではないと思いますが、類似のアイディアを文字列に適用したものがあります。 辞書に3つの単語があるとします(本番はもっと巨大な辞書を使います) 我 喜欢 水果 そして次の入力を取ります。 我喜欢水果 これを1文字ずつに分解します。 我 喜 欢 水 果 隣り合う2つの文字を連結して辞書引きをします。 我喜 喜欢 <- in the dic ...
Keisuke Ueda's user avatar
1
0 回答
1,612 閲覧数

Levenberg-Marquardt法の結果がEigenとGnuplotで異なるのはなぜでしょうか

C++の数値計算ライブラリEigenに含まれる、非線形最小二乗法(Levenberg-Marquardt法)で関数フィッティングを実行してみました 開発環境はVisual Studio 2015です フィッティング対象の関数は、y = a×cos(x)^b で、ノイズを含む観測データx,yからパラメータa,bを求めます #include <iostream> #include <...
stlz's user avatar
  • 11
0
1 回答
218 閲覧数

キューの末尾の判定について~リングバッファ~ アルゴリズムとデータ構造

現在、こちらの記事を読んでいてリングバッファの際の末尾の判定基準が分かりません。 #include <iostream> #include <vector> using namespace std; const int MAX = 100000; // キュー配列の最大サイズ int qu[MAX]; // キューを表す配列 int tail = 0, head = 0; ...
Shun Takahashi's user avatar
0
1 回答
299 閲覧数

区間が重なるタイミング

それぞれある周期で循環する0と1の数列があります。 例: 010101010101...(周期2) 001100110011...(周期4) 000111000111...(周期6) ここで、縦列が全て1になる最初の列番号やその割合を求めたいです。 上の例では最初に4列目(次に12列目)で1が揃い、無限数列全体の1/6が揃っています。 最初の列番号を求める方法は今のところ、...
nazratt's user avatar
  • 31
0
1 回答
377 閲覧数

三目並べ、三つの盤面で同時、✖のみ使用 先手の必勝法を考える

このゲームでは先手に必勝法がある。参照Youtube:Numberphile 3 board tic tac toe ただし、プログラミングに落とし込むぐらいの簡単な必勝法がみつからない。 目標はその必勝法を利用して疑似AIを作ること。 ルール: このゲームの盤面は基本的に三つの三目ならべのボードで構成されている 参加者二名が使う印は”X”で共通 ひとりずつ任意の格子に印をつける ...
geocentric's user avatar
0
2 回答
218 閲覧数

集合当てクイズの解法

次のようなゲームを考えます。 アルファベット 'A'~'Z'を全体集合とし、その部分集合が一つ与えられているとします。これを答えと呼びます。 プレイヤーは1ターンにつき次の問い合わせを一回出来ます。 問い合わせ:アルファベット'A'~'Z'の集合を一つ入力とし、答えと入力の積集合が空集合であるか否かがYes/Noで返ってくる。 これで答えが確定するまでのターン数を競います。 ...
Jogenara's user avatar
  • 588
0
1 回答
113 閲覧数

pythonで、intersectionの位置を調べる方法を教えて下さい。

#条件:データに重複は、ありません。 x = {"a", "b", "c"} y = {"c", "b", "e"} z = {"f", "b", "c"} result = x.intersection(y, z) ...
mrrclb48z's user avatar
  • 387
0
0 回答
99 閲覧数

Atcoder abc165_c 期待する答えが出力されません

以下のコードで Atcoder abc165_c (https://atcoder.jp/contests/abc165/tasks/abc165_c)の入力例を試したのですが、すべてで 0 が返ってきます。どなたか理由を教えていただけたら嬉しいです。 方向性としては、func 内でDFS的にAが求まるたびに得点を求め、その最大値を更新しています。 Atcoder abc165_c 問題概要  Q ...
user avatar
0
0 回答
153 閲覧数

ASCIIで記述した回路を図面に変換するアルゴリズムを探す

現在ASCIIで記述したノードとノードとのつながりを図面に変換するアルゴリズムを探します。 特に、Synopsys VerdiのようにVerilog HDL/VHDLコードからきれいな理解しやすい回路図を生成したい。どんなアルゴリズムでこれを果たすことができますか。 ノードの形は何でも構いません。
Light's user avatar
  • 273
0
1 回答
295 閲覧数

二次元配列に条件付きで数字を代入

与えられた数字を二次元で保存したいです。例えば、数列{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 ...
Avril's user avatar
  • 107
0
2 回答
109 閲覧数

2つのいくつかのノードを共有する連結リストをソートしたい

最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか? たとえば -900->120->200->230 \ 452->700 / -10->200 ...
Avril's user avatar
  • 107
0
0 回答
153 閲覧数

分析のためにゲーム木を描写したくなったとき、利用可能なライブラリ・フレームワークは何がありますか?

ターン制の対戦ゲームは、基本的にゲーム木を構築できます。たとえば○×ゲーム(tic-tac-toe)のゲーム木はこちらです。 Game tree for Tic-Tac-Toe game using MiniMax algorithm. 今、ふとした分析のために、このようにゲーム木を描写したくなりました。 質問 ゲーム木を描写する機能を持った、つまり、ゲーム木の可視化ができる、...
Yuki Inoue's user avatar
  • 1.6万
0
0 回答
171 閲覧数

1枚の画像からワールド座標を取得する

F地点の座標(xL,yF,zo)を求めたいです.ただし,L,F,Cの座標はわかっているものとします. 何かよい導出方法ありませんか? 考えたこととして, カメラの外部パラメータから回転並進行列を求めるP3P問題があり,求めようとしましたが, ワールド座標と画面座標の3つの対応付けが必要で行き詰りました. よろしくお願いします.
jun j's user avatar
  • 1
0
0 回答
450 閲覧数

安定な比較ソートでの最高速アルゴリズムはなんですか?

安定な比較ソートを開発しています。 平均計算時間で最速なものを目指しています。 ソートされるデータ以外の格納領域が O(n) ぐらいは使用して良いと思っています。 安定でない比較ソートであれば、クイックソートが最速なのだと思っています。 glibc の qsort は malloc に成功すれば 16*n バイトぐらい O(n) 格納領域を使用し マージソートを実行します。なので安定です。 ...
t-kawa's user avatar
  • 1
0
0 回答
330 閲覧数

要素数nのヒープの深さと各深さにおける要素数を求める方法について

ヒープの深さと各深さにおける要素数を求める方法について調べていますが、関数などを見つけることができず、どのように求めるべきかわかりません。 import heapq a = [6, 3, 2, 4, 5] heapq.heapify(a) 例えば上記の場合、手で図を描いてみると、ヒープの深さ(0始まりとする)は最大で2となり、各深さにおける要素数は深さ0で1, 深さ1で2、深さ2で2となります。...
NPP's user avatar
  • 421
-1
1 回答
211 閲覧数

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&...
Tom's user avatar
  • 1
-1
2 回答
478 閲覧数

なぜこのコードは非効率なのか?

F - ヘビの JOI 君に挑戦したのですがTLEになります。 しかし、なぜ自分のコードが非効率なのかがわかりません。コードの問題点などを教えていただけないでしょうか。下が自分のコードです。 int N, M,X,T[10000]; struct edge{ int to,cost; }; struct situ { int cost,v,dist,type; ...
Ranger's user avatar
  • 71