＜集大成＞アルゴリズム大辞典

＜集大成＞アルゴリズ ..

175:& ◆i.twkzJbf.
05/11/13 21:41:13
>>174

大変，ありがとうございます!
図書館にあるアルゴリズムの本をあさり，「こういうパターン
の時は単一回転」という図は掲載されていたのですが，明確に
文章で書かかれているものが，無かったんです．

上記のURL には明確に文章で記載されていたので，理解できました．
ありがとうございました．

176:デフォルトの名無しさん
06/02/05 09:40:09
2

177:デフォルトの名無しさん
06/02/05 09:41:09
今春、情報処理試験受けてきます

178:デフォルトの名無しさん
06/02/15 22:05:35
誰かイージスシステムのアルゴリズムうｐしてよ。

できればCASL2形式のソースコードで頼む。

179:デフォルトの名無しさん
06/03/06 23:50:20
GDIのArcToってどういうアルゴリズムで実装されているかご存知の方いませんか？
また、ArcToを実装する場合、Google等でそのアルゴリズムの名前を検索するとヒット
するようなメジャーなアルゴリズムってあるのでしょうか？

今、DirectXを使用してVRAMに直接弧を描画する関数を作っています。
楕円描画のアルゴリズムを使用して、弧を描く関数自体はできたのですが、問題点として、

①　条件分岐が多くスパゲッチーなコードになる
②　○○のアルゴリズム、とかの名前で、世間一般に知られているかが分からず、
　　　スパゲッチーなコードでも、その内容を見た人が調べて把握できるかが不安。

今後の保守性に不安があるので、弧の描画に用いられている一般的な
アルゴリズムがあるなら、そちらに揃えたいです。
ないなら、多少速度を犠牲にしてもGDIのArcToを使ってしまおうかと悩みちゅうです。

180:デフォルトの名無しさん
06/03/08 11:31:54
DDA を使ってるなら、Bresenham　アルゴリズムとでも書いておけば判るだろう

181:デフォルトの名無しさん
06/04/05 02:28:16
ヒープを使えば最小値（もしくは最大値）を迅速に取り出すことができます。
しかし、ある条件を満たしている間は最小値を、
そうでない場合は最大値を取り出すとなると、効率のいい方法が思いつきません。
線形探索で最大値を探し出すことになってしまいます。

（ソースコードは以下のURL）
URLﾘﾝｸ(anotherred.hp.infoseek.co.jp)

なにかいい方法は無いものなのでしょうか。

182:デフォルトの名無しさん
06/04/05 02:32:24
(181の続き）
某ソフトのある部分と流れがそっくりですが・・・
そっくりそのままコピペしたわけではないので、
そこらへんは目をつぶっていただけるとありがたいです。

183:デフォルトの名無しさん
06/04/05 05:54:32
>>181
ようするに、最大値と最小値の両方を高速に取り出せるデータ構造か。

両方 O(1) で出来るものはしらんが、両方 O(log n) でできるものならB木の類。

184:デフォルトの名無しさん
06/04/05 12:56:41
あとは、データを最初にソートしておくか。

185:デフォルトの名無しさん
06/04/05 13:19:15
>>183
木構造ですか・・・
たしか、木構造を使用したデーターベース関連のソースがあるので、
速度のことさえ気にしなければいけそうですね。
ちょっとベンチマークを取ってることにします。
わざわざ答えてくださりありがとうございました。

>184
二分ソートを使うとなると、かえって遅くなりそう・・・
適切な位置を探すのにO(log n)
データの移動に最悪でO(n)
平均はいくらぐらいか知らないけど。

186:デフォルトの名無しさん
06/04/23 23:18:33
質問です。
0<= x < N までの値を巡回する式を作りたいのです。

用途としては、選択肢を指すカーソルが一番下まで行った時、さらに下ボタンを押すと一番上を指すように。
一番上まで行った時にさらに上ボタンを押すと、一番下を指すように。
という使い方です。

x = (x + N) % N;
でとりあえず事足りているのですが、xが-N未満だった時によろしくありません。
Nが2の乗数なら、マスクをとるという方法も思いつくのですが…。

何か定型的な方法はありますでしょうか？
x = ((x % N) + N) % N;
でもとりあえず良いのですが、かなり冗長に見えます。

187:デフォルトの名無しさん
06/04/23 23:39:39
>>186
> でとりあえず事足りているのですが、xが-N未満だった時によろしくありません。
つか、xが-N未満になりうる時点でバグってると思うが？
0<= x < N なんでしょ？

188:デフォルトの名無しさん
06/04/23 23:51:29
もう面倒だから素直に分岐つかえば
x　%　n　+　(x　<　0　?　n　:　0)

189:デフォルトの名無しさん
06/04/24 00:08:33
>>187
説明が下手ですいません。
xになにかしらの数が代入され、それをうまく 0<=x<N に丸め込みたいのです。

int hoge(int x)
{
while(x < 0) x += N;
x %= N;
return x;
}
とお考えください。

>>188
その式だと、ちょっとやりたいこととは違うようです。
whileやifを使わずに綺麗にやる式があれば…と思っているのですが

190:デフォルトの名無しさん
06/04/24 00:46:26
>>188 それ負のとき0が5になる

191:デフォルトの名無しさん
06/04/24 00:50:35
188のもあってるが、
＞x = ((x % N) + N) % N;
のほうが分岐無いだけ速くねーか

192:デフォルトの名無しさん
06/04/24 06:33:35
xは負数としてもそんな極端な負数にはならないんでしょ？

NM=INT_MAX/N;
として
x = (x + NM) % N;
でいいんじゃないの？

193:デフォルトの名無しさん
06/04/24 16:25:32
いまいちやりたいことがわからんが、
UIなら計算量をケチる必要性はないので多少冗長でもかまわないのでは。

xの初期値として
x = (x + N) % N;
が計算できて、xは以降、0<=y<N、という値が足されたり引かれたりするだけという状況を仮定すると、
(>>186だとそういう状況ですよね。xに乗除算は入ってこない)

x-yを行うときはx<yならばNを足してからyを引くでいいんでないかい。
除算よりも比較の方が圧倒的に速いから。

194:デフォルトの名無しさん
06/04/24 16:36:30
いや、それなら基本的に　
xが-N未満になど、普通はなりようがないのだ。
x <-Nになる事はないのだから用途的には
x = (x + N) % N; で何の問題もない。
過剰仕様といえよう。

もし、xがEPROMとかに保存されてる間にゴミと化しても変な事にならないようにという事なら
x を　符号無数とすればいい

195:デフォルトの名無しさん
06/04/25 00:18:10
360度 0～4095の値をとる円の時に、この問題に悩むな。
-500000とか入れられたときに、0～4095に直すとどうなるか。みたいな。
DWORDにする手もあるんだが、Javaだと符号intしかないからなぁ・・

196:デフォルトの名無しさん
06/04/25 06:36:53
0～4095なら　4095とのand でいいんだから、悩まないぞ

197:デフォルトの名無しさん
06/05/16 22:52:10
テキストの類似度を判定するアルゴリズムって、なんかいいのないかな。

leveshteinとかsimilar_textだと、"abcdefgh"と"hgfedcba"の類似性を
かなり低く見積もってくれたりするんだけど、人間の直感にマッチするような
アルゴリズムってないもんですかね。

198:デフォルトの名無しさん
06/05/17 10:17:58
人の直感がそれぞれだからねぇ

199:デフォルトの名無しさん
06/05/17 16:01:49
>>197
俺の直感だと、その2つは似てない

200:デフォルトの名無しさん
06/05/20 21:35:30
Oliver [1993] とか。
similar_text
URLﾘﾝｸ(jp2.php.net)

201:デフォルトの名無しさん
06/05/23 17:06:12
SoundEx　とかはどうなの？

202:デフォルトの名無しさん
06/05/30 16:49:01
複数の候補からランダムに選択させたいんですが、
そこに重み付けを導入する場合って、どんなアルゴリズムがあります?

203:デフォルトの名無しさん
06/06/08 07:54:15
誰か解答を求む！

C で文字列を比較するのは
(*(int *)s1) == (*(int *)s2)
これのほうが早い？

204:デフォルトの名無しさん
06/06/08 07:57:42
>>203
ここで聞く前に試したほうが早いし確実だと思うのは気のせいでしょうか

205:デフォルトの名無しさん
06/06/08 09:25:22
速いっつーか，間違ってねえか？

206:203
06/06/08 09:29:08
すいません、ミスです

207:デフォルトの名無しさん
06/06/08 10:42:46
切れ目探しで鬱になったけど早い事は早かった
間違ってるの？

208:207
06/06/08 10:47:38
ミスｗ

209:デフォルトの名無しさん
06/06/08 13:58:46
なるほど、疾いよ、strcmpの1/10になれる
これどのCPUでもいけるの？

210:デフォルトの名無しさん
06/06/08 15:47:53
まだ続けるのか？

211:デフォルトの名無しさん
06/06/22 15:26:03
奥村先生は放送大学に出演している。

212:デフォルトの名無しさん
06/06/22 15:47:54
>>211
ナイス情報サンクス｡
LATEXとＪＡＶＡかー｡
アルゴリズムキボンヌだなぁ｡

213:デフォルトの名無しさん
06/06/22 16:02:00
>>212
「JAVAによるアルゴリズム事典」はpLaTeXで書いたとちゃっかり宣伝していた。

214:デフォルトの名無しさん
06/06/25 00:14:43
B+-treeに関して説明してあるお薦めサイトか、
理解しやすいオープンソースプログラムってあります？

215:デフォルトの名無しさん
06/07/06 08:08:55
B木までは説明してるサイトでもB+やB*は名前がでてくるかどうかって感じだな

216:デフォルトの名無しさん
06/07/06 15:40:55
奥村先生はJAVAが出て来たとき世界は統一されたと思ったらしい。

217:デフォルトの名無しさん
06/08/06 13:40:04
さすが学者先生だな。
何かで世界統一されることなんてないよ。

218:デフォルトの名無しさん
06/08/06 17:01:29
>>216
ソースは？
解釈が間違っている可能性がある。

219:デフォルトの名無しさん
06/08/06 20:40:34
>>218
放送大学で言っていた。

220:デフォルトの名無しさん
06/08/12 09:04:26
遺伝的アルゴリズムは？

221:デフォルトの名無しさん
06/09/02 16:52:02
　　（　・∀・）　　　|　|　ｶﾞｯ
　　と　　　　）　　 |　|
　　　Ｙ　/ノ　　　人
　　　　 /　）　　 < 　>__Λ∩
　　＿/し'　／／. Ｖ｀Д´）/
　　（＿フ彡　　　　　　　/

222:デフォルトの名無しさん
06/09/14 01:08:00
GA ってこと?

223:デフォルトの名無しさん
06/09/17 22:57:32
格子点を、原点からの距離が小さい順に数え上げていくアルゴリズムをしりませんか？

簡単の為、問題を２次元にします。
この時、
(0,0)
(1,0)
(0,1)
(1,1)
(2,0)
(2,1)
(1,2)
(2,2)
・・・・・・・
という配列を得たいのです。

思いついた単純な方法は、
for(i =1; i < N ; i++)
for(j = 1 ; j < N; j++){
d = i**2 + j**2
arry.push([i,j],d)
}
sort arry by d
aryy.each { a
printt a
}
という方法ですが、あまりスマートとはいえないし、
同じ距離d (= 1)をもつ点(1,0),(0,1)がこの順で並ぶとは限らないという欠点があります。
（同じ距離を持つ(x,y)なら　x>=yというを満足する点からで並んで欲しい)

224:デフォルトの名無しさん
06/09/17 23:03:57
>>223
「安定なソート」でぐぐれ。若しくはC++のstd:stable_:sortで関数オブジェクトに
x>=yという条件を含めれば簡単。

225:デフォルトの名無しさん
06/09/17 23:04:27
×std:stable_:sort
○std::stable_sort

226:デフォルトの名無しさん
06/09/17 23:33:51
おもしろいな
群論とか使えばいけそうだが。。。
俺の知識では無理ｗ

227:デフォルトの名無しさん
06/09/17 23:42:44
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

struct MyComp {
bool operator()(const std::pair<double, double>& p1, const std::pair<double, double>& p2)
{
double d1 = p1.first * p1.first + p1.second * p1.second;
double d2 = p2.first * p2.first + p2.second * p2.second;

if (d1 < d2)
return true;
else if (d1 > d2)
return false;
else { // d1 == d2
if (p1.first < p1.second && p2.first > p2.second)
return false;
else return true;
}
}
};

struct MyOut {
void operator()(const std::pair<double, double>& p)
{
std::cout << '(' << p.first << ',' << p.second << ')' << std::endl;
}
};

228:デフォルトの名無しさん
06/09/17 23:43:16
int main()
{
double a[][2] = {{0, 0}, {1, 0}, {0, 1}, {1, 1}, {2, 0}, {2, 1}, {1, 2}, {2, 2}};
std::vector<std::pair<double, double> > dp;

for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
dp.push_back(std::make_pair(a[i][0], a[i][1]));
std::sort(dp.begin(), dp.end(), MyComp());
std::for_each(dp.begin(), dp.end(), MyOut());
}

(1, 0), (0,5, 0) なんてペアがある場合は考慮してない。

229:デフォルトの名無しさん
06/09/18 00:43:40
ヴォースゲー！

230:デフォルトの名無しさん
06/09/20 15:41:34
複数の矩形が存在するときに、それぞれの重複を求めるアルゴリズムを考えています。
最終的には、与えられた領域を重複の無い横に細長い形の矩形で表現したいと思っているのですが、
これを表現するための良いアルゴリズムはあるでしょうか？

231:デフォルトの名無しさん
06/09/20 22:14:34
>>230
スキャンラインコンバージョン？

232:デフォルトの名無しさん
06/09/20 23:44:29
>>230
おれは力技でやった

233:デフォルトの名無しさん
06/09/24 15:55:30
This is a pen!

234:デフォルトの名無しさん
06/09/24 17:39:47
>>230
平面走査で解ける．計算量は　O(　n　log　n　+　k　)，
ただし　n　は矩形の数，k　は分割線の個数．

簡単のため，どの矩形の上下の　y　座標にも，同じものはないとする．
アルゴリズムを述べた後にこの制限は外す．

1.　すべての矩形の上側の辺と下側の辺を，
　　　y　座標の昇順に並べられたキュー　Q　に突っ込む．
2.　while　Q　が空でない:
3.　　　e　=　Q.pop()
4.　　　if　e　が下辺
　　　　　　　　then　T　に対応する矩形を挿入
　　　　　　　　else　T　から対応する矩形を削除
5.　　　T　に入っている矩形で，e　と交わるものを切断する．

ここで　T　は平面走査構造．x　でソートされた平衡二分探索木を用いると
4　が　O(log　n)　で行える．5　は　e　の左側の点で二分探索し，交わる領域を
線型に探すと　O(log　n　+　k')　で行える．ただし　k'　は　e　と交わる矩形の数．

同じ y 座標を許す場合は，一括に処理できる辺を蓄えておいて，
一度しか切断しないようにすれば対応できる．

235:デフォルトの名無しさん
06/09/30 15:33:44
斜め楕円の描画
void DrawEllipse(HDC hdc, double dFx1, double dFy1, double dFx2, double dFy2, double dLen )
{
double a,b,c,d,A,B,C,L,M,x;
int sx,sy;a = dFx1;
c = dFx2;L = dLen;
A = L*L-(a-c)*(a-c);
BOOL bFlg = TRUE;

for(int y=0; y<300; y++){
b = y-dFy1;d = y-dFy2;

M = L*L-a*a-b*b-c*c-d*d;
B = -2*(a*(c*c+d*d)+c*(a*a+b*b))-M*(a+c);
C = (a*a+b*b)*(c*c+d*d)-M*M/4;
if(B*B-4*A*C>0){
x = (-B+sqrt(B*B-4*A*C))/(2*A);
if( bFlg ){
bFlg = FALSE;
sx = x;sy = y;
MoveToEx(hdc,x,y,NULL);
}
LineTo(hdc,x,y);
}
}

236:デフォルトの名無しさん
06/09/30 15:34:17
続き
for(int y=300; y>0; y--){
b = y-dFy1;d = y-dFy2;

M = L*L-a*a-b*b-c*c-d*d;
B = -2*(a*(c*c+d*d)+c*(a*a+b*b))-M*(a+c);
C = (a*a+b*b)*(c*c+d*d)-M*M/4;
if(B*B-4*A*C>0){
x = (-B-sqrt(B*B-4*A*C))/(2*A);
LineTo(hdc,x,y);
}
}
if( !bFlg ){
LineTo(hdc,sx,sy);
}
}
あげちまたスマソ

237:デフォルトの名無しさん
06/09/30 15:35:42
標準に存在しないからって力技で自作したんだがどうだろう
ベジエ勉強したほうが良いのかな

238:デフォルトの名無しさん
06/09/30 19:41:45
せめて入力変数の意味くらい書いてくれ

239:デフォルトの名無しさん
06/09/30 23:01:13
>>237
ベジエ曲線で完全な楕円は表現できない
近似はできるけどな

240:デフォルトの名無しさん
06/09/30 23:20:49
>>238
HDCはおいておいて、残りの5つは
焦点の座標（２つ）と長径

>>239
実用に耐えるなら近似で良いんだけどね

241:デフォルトの名無しさん
06/09/30 23:59:26
用途にもよるが、俺ならサンプル点の密度が極端に偏るアルゴリズムは使わないな。

242:デフォルトの名無しさん
06/10/22 19:47:46
最大遅れ最小スケジューリング (minimization of the maximum lateness) ってあるけど、
この最大遅れの「最大」ってなんなの?

遅れの合計を最大化したものを最小化? 意味がわからん。
エロい人教えて

243:デフォルトの名無しさん
06/10/22 19:51:50
最大の遅れを最小にする．たとえば

・最初の仕事で30分遅れてあとの仕事はジャスト．（最大遅れ30分）
・全部10分づつ遅れる．（最大遅れ10分）

の二つだったら，後者のほうが良いとするスケジューリング．

244:242
06/10/22 19:55:00
>>243
なるほど!トンクス

245:デフォルトの名無しさん
06/10/31 16:55:59
$a=array('red','blue','yellow','green');
$b=array('white','blue','yellow','green');
$c=array('green','red','yellow','cian','black');

$a,$b,$cのどれにも存在する要素の'yellow','green'を取得するソースをPHPで。

246:デフォルトの名無しさん
06/11/02 01:42:06
PHPで何？

247:デフォルトの名無しさん
06/11/02 11:51:23
>>245
array_uintersect

248:デフォルトの名無しさん
06/11/02 19:21:30
二つのソート済みの配列が与えられていて（合計の要素数はN）
N個の要素からメディアンを計算量O(LogN)で求めるアルゴリズムを教えてください。
URLﾘﾝｸ(ocw.mit.edu)
URLﾘﾝｸ(www.cse.ust.hk)
検索して出てきたこの二つのPDFにある擬似コードをCで実装してみたんですけど
何度かテストしたらどちらも時々スタックオーバーフローが発生してしまいました。
（正しい結果を返すときもありました）
二つの配列の長さが同じ場合にしか使えないコードでもいいのでお願いします。

249:デフォルトの名無しさん
06/11/02 20:57:41
>>248
2つのソート済み配列をA,Bとする。
Aの中央値とBの中央値を比較する。
Aの方が大きいとすると、Aの小さいほうの集合とBの大きいほうの集合を残す。
以下これを反復する。1回の反復は配列の要素を指定して比較するだけだから定数オーダー。
反復ごとに要素数が半分になるから反復回数はlog N回

250:248
06/11/03 03:05:44
>>249
ありがとうございます。こんな感じになりました。
int median_search(const int *A,const int *B, int n){
　　int m;
　　if(n==1)
　　　　return A[0]>B[0]?A[0]:B[0];
　　m = n>>1;
　　if(A[m]>B[m])
　　　　return median_search(A,B+m,m);
　　return median_search(A+m,B,m);
}
nは配列AとBの長さです。
ソート済みの配列AとBをマージした長さ2nの配列をCとするとこの関数はC[n]を返します。
A[0]>B[0]?A[0]:B[0];の部分を、A[1]<B[1]?A[1]:B[1];にすればC[n+1]を返します。

251:248
06/11/03 03:14:48
連続投稿すみません・・。
>>250は配列の長さnが２のべき乗の場合しか使えないようですね・・。
もうちょっと考えてみます・・。

252:デフォルトの名無しさん
06/11/04 02:07:10
バルブソートの検索結果約 98,900 件中 1 - 10 件目 (0.75 秒)

253:デフォルトの名無しさん
06/12/01 10:57:06
"バルブソート" の検索結果約 73 件中 1 - 6 件目 (0.04 秒)
最も的確な結果を表示するために、上の6件と似たページは除かれています。

254:デフォルトの名無しさん
06/12/26 19:17:24
バルブソートの検索結果約 87,100 件中 1 - 10 件目 (0.29 秒)

255:デフォルトの名無しさん
06/12/27 11:18:50
"パブルソート" の検索結果 2 件中 1 - 2 件目 (0.25 秒)

256:デフォルトの名無しさん
06/12/28 09:05:20
ラストリゾートの検索結果のうち日本語のページ約 159,000 件中 1 - 10 件目 (0.14 秒)

257:デフォルトの名無しさん
06/12/30 16:37:47
桃太郎電鉄の「いけるかな？」の判定アルゴリズム教えてくれ。

258: 【吉】
07/01/01 12:18:14
ただの幅優先探索じゃね

259:デフォルトの名無しさん
07/01/05 00:45:08
使える素子に制限がある、ある動作をする組み合わせ回路の探索アルゴリズムって何かの本にかいてますか？

例えば、NOT2個とAND複数、OR複数個だけで並列な独立した3つのNOT回路と等価な回路を探すアルゴリズム。
「思考する機械コンピュータ」という本に載っていた問題です。(この条件が)

この間バックトラックでやったらあっさりできましたが・・・

260:デフォルトの名無しさん
07/01/05 07:45:57
>>259
加算器ぐらい合成できないと意味はない

261:デフォルトの名無しさん
07/02/13 08:13:38
総当たりなんじゃ・・・

262:デフォルトの名無しさん
07/02/13 08:54:07
>>261
証明

263:デフォルトの名無しさん
07/02/13 15:00:13
素子の種類の条件を満たす真理値表を小さい方から総当たりだな。

ちなみに「条件を満たす回路が存在しない」ことの証明は
総当たりで調べても見つからなかったことを言う以外に方法はない。
典型的なNP問題。

264:デフォルトの名無しさん
07/02/13 19:51:44
>>263
総当りでしか証明できないならNPに入っていないじゃん。
探査空間Pで十分だからPSPACEには入っているけど。

265:デフォルトの名無しさん
07/02/14 16:25:03
＞総当りでしか証明できないならNPに入っていないじゃん。

？

266:デフォルトの名無しさん
07/02/14 18:10:31
>>265
NP=ある多項式長の補助入力が存在してPで解ける
総当り→補助入力は多項式長でないからダメ
補問題であるある場所にいけるかは
道順の例を補助入力として与えればこれは多項式長であり、明らかにPで検証可能。
したがって補問題はNP。
補問題がNPだから、PSPACEよりも狭いco-NPに入る。

267:デフォルトの名無しさん
07/02/15 03:59:35
むずかしいはなしはきらいです

268:263
07/02/15 06:14:34
間違った。
等価な回路を探すアルゴリズムがNPで、存在しないことの証明はNPじゃない。

269:259
07/02/15 16:03:39
もしアレでしたらソースコードUPしますけど・・・

270:デフォルトの名無しさん
07/02/16 00:56:55
いらね

271:デフォルトの名無しさん
07/02/16 04:04:04
いる

272:259
07/02/16 04:34:16
見たら吐くかも
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)

273:デフォルトの名無しさん
07/02/16 07:39:57
#define NOTA まで読んだ。

274:デフォルトの名無しさん
07/02/16 07:40:39
なんだよ、ノタって。ふつーNOT_Aだろ。

275:デフォルトの名無しさん
07/02/18 16:31:13
某板よりコピペ
多数のオブジェクトの衝突判定を並列化する方法

移動後の座標をボクセルに振り分ける。
1つのボクセル内に存在するキャラを総当たりで衝突判定。

処理の順序としては、移動、振り分け、衝突判定、衝突処理。
これで処理を並列化できる。

もう少し詳しく言えば、衝突判定をしやすくするために、
ボクセルに振り分ける時点で座標値などをボクセルごとの一時バッファに複製しておく。
これにより巨大なバッファをLSにロードする必要がなくなる。

衝突の連鎖については次フレームに回す。それで結果的には再帰処理になる。

普通は移動後に振り分けるというより
ボクセル内のオブジェクトを管理するバッファを常設しておいて
移動でボクセル外に出たときだけバッファの更新をするでしょ。

276:デフォルトの名無しさん
07/02/19 01:19:29
類似の手法は物理計算では常識。
ボクセルよりも適当な空間木を用いたほうがよいと思う。
オブジェクトの分布や座標空間にもよるが、計算量の
意味で速度が改善されることも珍しくない。

277:デフォルトの名無しさん
07/02/20 03:50:22
>>274
ふつーNOT_Aなのは分かる
しかし、Shiftを押しながら「ろ」キーを押す手間が面倒なのも分かってしまうんだな
俺はどっちを応援すればいいんだ？

278:デフォルトの名無しさん
07/02/20 06:10:11
ふつーSHIFT+-

279:デフォルトの名無しさん
07/02/20 16:04:22
その点以外の感想が欲しい今日このごろ

280:デフォルトの名無しさん
07/02/22 07:38:32
C言語のソースは読むきしねぇ
コメントぐらいかこうね

281:デフォルトの名無しさん
07/07/03 15:59:46
整数のリストを入力とし整数のリストを出力する関数nayose を、
Minimal を用いて次のように定義する。(ただしプログラム中、A or B 　はA とB のうち少
なくともどちらか一方がtrue のときtrue を返し、それ以外のときはfalse を返す論理演算
である。) 以下の問に答えよ。
fun member x lst =
case lst of
[] => false
| hd::tl => hd=x or (member x tl)
end;
fun nayose lst =
case lst of
[] => []
| hd::tl => if (member hd tl) then (nayose tl) else hd::(nayose tl)
end;
(1) 関数nayose はどのような計算を行う関数か簡潔に答えよ。
(2) 長さがn のリストに関数nayose を適用したときの計算量をO(f(n)) の形で表せ。
(3) あらかじめ整列された整数のリスト（重複があってもよい）を入力とし、関数nayose と
同様の結果を出力する関数で、入力リストの長さがn のときの計算量がO(n) となるよ
うな関数nayose2 を、Minimal プログラムで示せ。関数nayose2 がnayose と同様の結
果を出力する理由を簡単に説明すること。
(関数nayose2 は、整列されていない入力についてはnayose と異なる結果を返しても良
い。）

282:デフォルトの名無しさん
07/07/05 07:23:15
宿題は宿題スレへ

283:デフォルトの名無しさん
07/09/08 02:49:46
age

284:デフォルトの名無しさん
07/09/10 15:56:14
反駁環境における生成器
% 何も生成しない生成器
repeat.
repeat :- repeat.
% 類型リストからの生成
member(A,[A|_]).
member(A,[_|R]) :- member(A,R).
% 類型リストの分解
append([],X,X).
append([U|X],Y,[U|Z]) :- append(X,Y,Z).

285:デフォルトの名無しさん
07/09/11 03:52:19
% 生成器のつづき
% 連続整数の生成器(昇順)
for(N,N,E) :- N =< E.
for(S,N,E) :- S =< E,S2 is S+1,for(S2,N,E).

286:デフォルトの名無しさん
07/09/23 09:39:58
他所のHPの書きこみなんだけど
> よく知られている問題ですが、一般に、Ｎ個のもののソーティング(順序付け)の
> ための必要最少限の比較回数はlog2(Ｎ！) ≦ ｋを満たす最小の整数ｋです。
って本当?
ていうか必要だけど充分じゃないっていう意味で言ってるんだろうか.

287:アルゴリズム初心者
07/10/13 20:48:56
ツリー構造(あるディレクトリ以下のファイル・フォルダ群）同士の差分を取得したいのですが、
そういったアルゴリズムの解説お願いします。
もしくはためになりそうなキーワードやウェブサイトを教えてください。
３年くらいプログラミングはしているのですが、画面を作るばかりで
頭を使うようなことは一切やったことが無いので詰まってしまいました。。。

288:デフォルトの名無しさん
07/10/13 21:04:06
アルゴリズムも何も、diff -rじゃダメなのか?

289:デフォルトの名無しさん
07/10/14 00:14:49
>>287
WinMergeをダウンロードしてくるといいよ

290:デフォルトの名無しさん
07/10/14 00:39:33
WinMergeはサブフォルダごと一気に比較すると、全部一画面で表示するから
見にくくてしょうがない。
DFみたいにフォルダごとに見れるようにしてくれよ。

291:アルゴリズム初心者
07/10/14 07:53:31
プログラムの中で使いたいのでこのすれにきています。そういうライブラリがあれば教えてください。

292:アルゴリズム初心者
07/10/14 07:59:15
ちなみにJavaです。

293:デフォルトの名無しさん
07/10/14 08:56:05
diff のソース読めばいいんじゃないか？

294:デフォルトの名無しさん
07/10/14 09:55:04
>287
さすがに手作業で同じ事はできるよな？

じゃ、まずは簡単な例で手作業でやってみよう。
次に、どういう手順で行ったか書き下してみる。
で、人間なら分かるけど計算機には分からないといった about なところを詳細化する。
最後にコードに落としてやれば OK だ。

この程度で、アルゴリズムだとかライブラリだとか情報源とか探してるようだと
いつまでたってもそのレベルから抜け出せないよ？

295:デフォルトの名無しさん
07/10/14 10:34:59
>>291
system("diff -r dir1 dir2")

296:デフォルトの名無しさん
07/10/14 10:39:33
ある範囲内のユニークな乱数列を作る方法を教えてください

297:デフォルトの名無しさん
07/10/14 12:55:17
>>296
どういう範囲内でユニーク？
ユニークなことを確実に保障するのって難しいよ。

298:デフォルトの名無しさん
07/10/14 13:21:17
>>297
範囲というか、DBの正規化レコードのテストに使うので1～1000万ぐらいで。
乱数をハッシュテーブルに登録してユニークな乱数列を作れないかと
思ったんですが、目的レコード件数分まわしても、重複で抜け番号が
出てくるので、一気に全部埋まる方法ないかなと。

299:296
07/10/14 13:24:14
逆に、整列されたスカラ値の配列やリストを、
ランダムに混ぜる方法でもいいです。

300:296
07/10/14 13:28:03
あと、再現性が必要なのでシード値を取れる方法が好ましいです。

301:デフォルトの名無しさん
07/10/14 13:50:17
ユニークである必然性あるのかな？
全数チェックしたらｗ

302:デフォルトの名無しさん
07/10/14 16:24:11
>296
多分、ユニークな乱数列、の意味が人によって違っているような気がする。
「乱数列」がユニークであることを望んでいるのではなくて、乱数列中に表れる数値がユニーク(重複しない)
ってことなんだよね？
C++ で良ければ(アルゴリズムの説明にならないけど)、>299 で random_shuffle() 使うのが一番簡単かと。
あるいは、random(N) を 0～N-1 の整数を発生する(シード値をとれる)疑似乱数生成関数として、a[0]～a[N-1] にたいして、

for(i=0;i<N;++i) {
　　　　idx = random(N);
　　　　tmp = a[i];
　　　　a[i] = a[idx];
　　　　a[idx] = tmp;
}

で、いいんじゃない？

303:296
07/10/14 20:45:00
あー
その通りです。
ありがとうございました。

304:デフォルトの名無しさん
07/10/14 20:49:40
>>302
そのコードだと均等に混ざらない（すなわち、全ての可能なケースが等確率で出ない）。

正しくはこんな感じ

for(i=0;i<N;++i) {
　　idx = random(N-i) + i;
　　swap(a[i], a[idx]);
}

305:デフォルトの名無しさん
07/11/13 01:55:34
URIの一致箇所検出に
最適なアルゴリズムってどれですかね？

306:デフォルトの名無しさん
07/11/20 17:17:18
>>305
質問の意味がよくわからない
最長共通文字列？

ところで、良いアルゴリズムというかロジックが思い浮かばないんだけど何か良いの無いかな。
配列をPivotとの大小関係で三つに区切る。
C++っぽい擬似コードで書くとこんな感じ
under = partition( Begin
End
< Pivot )
partition( under
End
== Pivot )
これより計算量係数を下げたいんだけど。

307:デフォルトの名無しさん
07/11/23 08:28:25
>>306
係数を議論するなら計算モデルを出さないと普通不可能だし，
その擬似コードの partition の実装もわからないからなんともいえない．

308:デフォルトの名無しさん
07/11/24 19:00:09
306
携帯からでカンマが改行になってしまいました。

>>307
具体的に計算する必要はありません。
何か他の実装が
partitionの実装が分からなければSTLのソースでも見てください。

309:デフォルトの名無しさん
07/11/24 19:52:52
>>308
ちと文章が切れてるので何を言いたいか察しかねるが、

計算量係数ってことは O(n) で隠れてる定数部分を
評価したいんでしょ？そのためには、たとえば
　・対象はどう表現されているか（リスト，配列 etc）
　・n として何を数えるか（比較，イテレータの移動，スワップ etc）
　・それぞれどれくらいの計算コストの差があるか
なんか決まらないと、とても評価できない。

「実用上早い」ってのは知られてるけど、計算量の係数が
実際にどんくらい小さいかってのは不明。

あと、306 のコードは「C++ 風の擬似コード」じゃなかったの？
それで「実装は STL を見ろ」というのではあなたの言うところの
擬似コードの意味がよくわからないんだけれど。
それに STL の partition はアルゴリズムは全く決めてないから
例えば「gcc のどのバージョンの STL の実装」とか言わないと。

310:デフォルトの名無しさん
07/11/24 23:27:09
何がやりたいのかわからんので、
エスパーで問題を考えて回答しよう。

入力
*X;(1,2,4,4,4,5,6,7);//ソート済み配列,長さO(n)
Pivot=4;//比較する値
Begin=0;//探索範囲？
End==7;//
出力
(2,5);//(1,2),(4,4,4),(5,6,7)と分けたときの4と5のインデックス

アルゴリズム
B=Begin;E=End;
while(E-B&g;1)
if(X[(B+E)/2]>Pivot)
　　E=(B+E)/2;
else if(X[(B+E)/2]<Pivot)
　　B=(B+E)/2;
else
{　　N=(B+E)/2; break; }

以降はBとN間、NとE間の境界を通常の二分探索で見つける。
比較回数の最悪は明らかに1回目の比較でbreakして全体の1/2のサイズの二分探索を二回行わなければならないときで、
1+2(logn-1)=2logn-1回

311:デフォルトの名無しさん
07/11/25 02:31:58
>>310
それはエスパー失敗

ソートされていない配列をピボットよりも
「小さい・同じ・大きい」に分ける」のが問題でしょう。

312:デフォルトの名無しさん
07/11/25 16:45:03
>>311
そんなの順番に見ていくブルートフォースアルゴリズムが自明で最速ではないか。古典では。

313:デフォルトの名無しさん
07/11/25 17:58:59
>>312
ブルートフォースという意味がよくわからないけれど、
先頭から順に見ていき、ピボットとの小中大によって
対応するリストにコピーする、というアルゴリズムのこと？

もしそうであれば、普通の計算コストの設定では最速ではない。
なぜならば、そのアルゴリズムは、「要素のコピー」が
必ず n 回発生するが、普通はコピーは比較より数倍重い。

314:デフォルトの名無しさん
07/11/25 21:55:16
>>313
そのアルゴリズムが最速ではないというなら最速なアルゴリズムを記述してくれ。

コピーが重いならコピーせずにポインタで参照すればいいのでは。
二段参照になるからリストの性能は落ちるだろうが。

315:デフォルトの名無しさん
07/11/25 22:09:04
>>314
「最速」かどうかは知らないが次の論文を参照。

Jon Bentley and Robert Sedgewick,
"Fast Algorithms for Sorting and Searching Strings",
Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
New Orleans, January 1997

316:315
07/11/25 22:12:19
補足。
コピーが重いというのは、別にオブジェクトが重いとかそんなものではなく、
int の値のコピーと int の値の比較でもコピーのほうが数倍遅い。

本当に膨大なデータを処理しようと思ったときは、この定数倍が響くことがある。
（それに、上のアルゴリズムは余計な空間を使うのも痛い）

317:デフォルトの名無しさん
07/11/25 22:52:24
>>316
おｋ理解した。
swapで必要なところだけ入れ替えると。
swapでコピーが2重に発生するから
最悪上の単純なアルゴリズムの2倍かかってしまうが、
平均的には速いと。
クイックソートは最悪時間はバブルソートと同じになるが、
平均的にはマージソートよりも速いみたいなものと。

318:315
07/11/25 23:30:21
>>317
ちょっと理解できていないように見えるんだけどな。
計算コストをきちんと設定しないといけないと言っていて、例えば

　・スワップはコピーを2回実行する
　・どこへのコピーも同じ単位時間で行える

みたいなモデルを考えればあなたの言ってることはほぼ正しい
（というか「平均的」（何の平均かわからんが）にも単純アルゴリズムが早くなる）。

しかし、現実の CPU ではそんなことは全然無くて、実際は

　・値のスワップはコピー2回よりも若干高速に実行される
　・同一作業領域中でのスワップは、別領域へのコピーよりもはるかに高速

ということになっているから、「2倍かかる」という算定は全く間違い。
x86 あたりを前提に算定すると「10倍以上早い」という結論でも不思議じゃない。

このあたりはオーダにしちゃうと完全に隠れる部分だから
クイックソートを例に出すのは不適当だと思う。

319:デフォルトの名無しさん
07/11/25 23:54:19
具体例を見せてくれないかな。

320:315
07/11/26 00:33:18
>>319
何の具体例だい？「10倍以上遅くなる」ような実装の具体例？

そんなのは、Bentley-Sedgewick の論文からコードを引っ張ってきて、
手元で適当にコードを書けば簡単に具体例になるよ。

321:306
07/11/27 15:19:23
>>309
だらだらコード書くよりSTL使った方がやりたいことが分かり易いかと。
ﾌｧﾝｸﾀ書くのが億劫で擬似と言っただけです。
対象のデータ構造は特定しません。というかあわよくばデータ構造による差が分かれば尚良いです。…が面倒なのでﾗﾝﾀﾞﾑｱｸｾｽって事いいです。
STLは、書きながら思ったけど本当に突っ込まれるとは思いませんでした。一般に同じ様な実装だと思ってました。すみません。
確認したのはgcc3.4.4/4.2.2、VC8、bcc5.5、SGI3.3です。

>>311
補完ありがとうございます。

>>314
その最速が今揚げてる議題です。

322:デフォルトの名無しさん
07/11/27 23:05:25
>>321
で、コスト設定はどうするの？

少なくとも「イテレータの移動、比較、スワップ、スワップ」くらいのコスト比を
決めてくれないと、とても定数部分の違いは算定できないと思うんだけど。

現実のCPUみたいなキャッシュや分岐予測があるモデルだと、解析は
さらに面倒なことになるけど、それはどれくらい考えないといけないの？

あと、 Bentley-Sedgewick は読んでみた？

323:デフォルトの名無しさん
07/12/28 03:47:56
うざ

324:デフォルトの名無しさん
08/03/05 01:18:02
みんなアルゴリズムをどんな風に知っていったの？
ライブラリを主に使ってるから、ソート程度しか知らないんだけど、
今日、先輩プログラマにアルゴリズムも知らんのか？と言われた。

325:デフォルトの名無しさん
08/03/05 02:01:07
書籍

326:デフォルトの名無しさん
08/03/05 23:39:34
アルゴリズムを知っているかどうかは使い捨てプログラマかどうかの目安の一つだな

327:デフォルトの名無しさん
08/03/06 03:11:28
>>325
推奨書籍はありますか？

328:デフォルトの名無しさん
08/03/06 07:54:07
問題が解決出来るかどうか
であって、アルゴリズムを知ってるだけじゃ駄目だろ。
アルゴリズムを知ってるだけでは、Fizz-Buzz問題でさえ解けるのは半数なんだそうだ

329:デフォルトの名無しさん
08/03/06 07:55:37
奥村さんのアルゴリズム辞典が定番かね。

330:デフォルトの名無しさん
08/03/06 09:19:28
Introduction to Algorithms(MIT Press)

331:デフォルトの名無しさん
08/03/06 09:35:24
>>327
[CLRS] T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, Second Edition, MIT Press
[KT] J. Kleinberg, E. Tardos, Algorithm Design, Addison Wesley
[I] 石畑清，アルゴリズムとデータ構造，岩波書店
[S] R. Sedgewick, Algorithms in C, Addison-Wesley

[CLRS] はこの分野では定番で，標準的な教科書．和訳有．
[KT] は最近出た本で，現代的な記述がされている．
[I] は個人的にお勧めする本で，記述がやさしい．入門には適正．
[S] は実装中心に書かれていて，理論より実装という人向け．和訳有．

KT は最近和訳が進んでるって話もあるけど，きっとだいぶ先．

332:デフォルトの名無しさん
08/03/06 11:32:21
日経ソフトウェア買えばええやん

333:デフォルトの名無しさん
08/03/07 07:20:53
アルゴリズムＣや珠玉のプログラミングはどう？

334:デフォルトの名無しさん
08/03/07 07:24:48
>>333
[S] R. Sedgewick, Algorithms in C, Addison-Wesley やん
このあわてんぼさん。

335:デフォルトの名無しさん
08/03/07 18:40:37
「アルゴリズムC・新版」と「アルゴリズムC」って何が新版なの？

336: ◆JvckrUgJWM
08/03/07 18:43:11
>>327
つ URLﾘﾝｸ(d.hatena.ne.jp)

337:デフォルトの名無しさん
08/03/11 02:31:13
任意の26までの数値nが与えられたときに、Aからn番目のアルファベットまでを使ったN文字
の順列をぜーんぶ列挙するのになにかよい方法ってありますか？
つまりは任意の配列から総当りするためのネタ作りをしたい訳なのですが。。。

338:デフォルトの名無しさん
08/03/11 02:37:18
順列？同じものの重複利用は禁止？

339:デフォルトの名無しさん
08/03/11 08:06:36
permutation
でぐぐれ
いっぱいサンプルプログラムが転がってる

340:デフォルトの名無しさん
08/03/11 09:33:12
>>338
はい。2が入力だったAB,BA見たいな感じのものが生成されるような。。。

>>339
ありがとうございます。見てみますね。

341:デフォルトの名無しさん
08/03/11 22:47:15
アルゴリズムスレで言うのもなんだけど C++ だったら STL にある next_permutation 使うと割と簡単に書けると思う。

342:337
08/03/11 23:54:54
まだ詳細は調べ切れていないのですが、こういうのって自分で手書きするなら・・・・

並べ替えたいN個の要素のリストから一つ取っては、N-1人の自分にN-1個になったリストと自分の
ポインタをそれぞれ丸投げし、N-k番目の子はk番目の要素を一つとってさらに子に・・・取るものが
ラスト一個になったら、自分の親の取った要素をつなげて表示する。
みたいな実装イメージになるんでありましょうか。

343:デフォルトの名無しさん
08/03/12 23:07:29
書き方なんていくらでもあるだろうが、俺だったらリストにせずに配列を使って再帰的には書くと思う。
っちゅーかそれこそ調べればいいんじゃないの？と言いつつ安易に書いてみる。
後、26! = 403291461126605635584000000 なんで全部回してるとやってられないと思う。

#include <iostream>

int result[26];
void permutation_imp(int n, int m) {
　　if(m == n) {
　　　　for(int i=0;i<n;++i) for(int j=0;j<n;++j) if(result[j] == i) std::cout << ' ' << static_cast<char>('A' + j);
　　　　std::cout << std::endl;
　　} else {
　　　　for(int i=0;i<n;++i) if(result[i] == -1) { result[i] = m; permutation_imp(n, m+1); result[i] = -1; }
　　}
}
void permutation(int n) {
　　for(int i=0;i<n;++i) result[i] = -1;
　　permutation_imp(n, 0);
}
int main(void) {
　　permutation(3);
　　return 0;
}
出力結果：
　A B C
　A C B
　B A C
　B C A
　C A B
　C B A

344:デフォルトの名無しさん
08/03/13 21:43:11
参加してみた
#include<stdio.h>
#include<string.h>

void swap(char *a, char *b){
char c;
c=*a;*a=*b;*b=c;
}

void func_internal(char *buf, int bufsize, int left){
int i;
if(left<=0) printf("%.*s\n", bufsize, &buf[-bufsize]); // 気持ち悪いかな？
for(i=0;i<left;i++){
swap(&buf[0], &buf[i]);
func_internal(buf+1, bufsize, left-1);
swap(&buf[0], &buf[i]);
}
}

void func(char *buf, int bufsize){
func_internal(buf, bufsize, bufsize);
}

int main(void){
char buf[]="abcde";

func(buf, strlen(buf));
return 0;
}

345:337
08/03/14 03:01:52
>>333-334
これまた短いですね。。。なんでこんなのが思いつくのかが不思議です。
自分の思った方法でも無理ではないんだろうなとは思うのですが、擬似コードの段階で
だらだらしたものになってますからね。。。
再帰ですらすら考えられる人ってあたまよさそうです。

346:337
08/03/14 03:02:36
>>345
アンカーミス。。。
>>343-34
でした。

347:デフォルトの名無しさん
08/03/14 09:00:14
多くのアルゴリズムは定番とか定石がある。特に基礎的なものは。
このスレのタイトルの本もそういうものだわな

348:デフォルトの名無しさん
08/03/17 18:49:55
A/D変換データをソフト的な処理で安定させるやり方
として移動平均以外に何かありますか？
移動平均は平均回数をおおくとると、反応
が遅く（変化が鈍く）なるので、なるべくそうならな
い方法を探しています。

349:デフォルトの名無しさん
08/03/17 22:10:48
>>348
Ａ／Ｄ、Ｄ／Ａ半導体
ｽﾚﾘﾝｸ(denki板)

350:デフォルトの名無しさん
08/03/18 02:11:43
>>348
高次曲線近似とかベジェ曲線近似はどうかな？

351:デフォルトの名無しさん
08/03/18 09:17:19
移動平均はFIRフィルタ　LPFの一種だから係数をキチンと設計すれば応答性と安定性を両立出来る。
計算量の面では２次の IIRフィルタにすれば、応答性と安定性と計算量も両立出来る。

352:デフォルトの名無しさん
08/03/18 10:01:45
>>350
初めてききました。なんだかC言語で書くと難しそうですね。

>>351
係数って平均回数のことですよね？

353:デフォルトの名無しさん
08/03/18 11:45:53
平均回数じゃなくて、
FIRフィルタでするという場合は、それぞれに重みを付けて計算するわけ
だから、移動平均に比べて計算コストは非常に大きい

例えば、サンプリング間隔の1/5以上で変動するようなノイズを取りたいという時に
16個の移動平均をしてもノイズは1/16までしか減らないけど
0, 0.015270303
1, 0.048044002
2, 0.098545986
3, 0.151768713
4, 0.186370997
5, 0.186370997
6, 0.151768713
7, 0.098545986
8, 0.048044002
9, 0.015270303
と１０個の係数かけて累積すれば、サンプリング間隔の1/5以上の成分は1/200以下に減る

354:デフォルトの名無しさん
08/03/18 15:30:03
例えば
１０、１５、２０、１０
っていう４つのデータがある場合
10*0.4 + 15*0.2 + 20*0.2 + 10*0.2みたいに
するっていうことですか？
この重みの決め方がまた大変そうですね。
ちなみに353の例だとなんで1/200になるんですか？
なんかアルゴリズムとは関係なさげな話になって
申し訳ないです。

355:デフォルトの名無しさん
08/03/18 20:34:43
たとえば、　sin(i*1.3)*100+200 みたいな信号が入力されたとする。
入力　移動平均　>>353の方式それぞれの結果は
200.0 12.5 3.1
296.4 31.0 14.1
251.6 46.7 37.8
131.2 54.9 73.6
111.7 61.9 115.1
221.5 75.8 152.4
299.9 94.5 178.6
231.9 109.0 192.7
117.2 116.3 198.4
123.8 124.1 200.0　 <--　10個目から >>353 の方式はほぼ200に安定
242.0 139.2 200.0
298.7 157.9 200.1
210.8 171.0 200.0
107.1 177.7 199.9
139.5 186.4 200.0
260.6 202.7 200.1 <-- 移動平均は16個目以後でも±8程度変動する
292.9 208.5 200.0
189.1 201.8 200.0
101.3 192.4 199.9　ただしsin(i*w) のwの係数が　 2*PI/5=1.25 以上の時に >>353 は効く
158.1 194.1 200.0
276.3 204.4 200.1

356:デフォルトの名無しさん
08/04/13 22:37:03
ちょっと考えてる問題があるので意見を聞かせてください。

例えば300個の積み木があるとして、これらは様々な重さ・大きさがあり、5種の色のいずれかが
ついてたとします。
これらを山に積み上げて行くときに、なるべく重さのピークが高い山がたくさん欲しいけれど、以下
の条件を満たさないといけないとします。

１．大きいものほど下にある
２．一山は積み木は10個が限度だけど、赤い積み木が三つ含まれていたら8個が限度になる。
３．一山には2色しか存在してはいけないし、異なる色の境界は1箇所だけ(赤青赤はだめで、赤赤青は良いみたいな)

ものすごく簡略化してしまいましたが、ナップザック問題に条件が加わったようなものになるのかと
思います。

細々とした条件・・・特に色の条件のせいで欲張り法が使えない気がするのですが、こういったものを常識的
時間で解く方法を調べたいので、キーワード程度でも教えてもらえませんか？厳密、近似は問いません。

357:デフォルトの名無しさん
08/04/13 23:31:07
>>356
「重さのピークが高い」って言葉の意味が分からない．
あと，複数の山があったときにどう評価するかも分からない．
具体例をいくつか出してくれないかしら．

358:デフォルトの名無しさん
08/04/13 23:40:00
>>357
重さのピークについてですが、例えば価値＝重さが
1 2 2 3 4 5 6 7 8 9
のような9個があったとして、ここから>>356より少ないですが、2段まで積んでいいこととするならば
98 76 54 32 21
のような山できてほしくて、
19 82 27 36 45
のようにはできて欲しくないのです。
できた山の価値の標準偏差が一番でかい組み合わせになるんでしょうか・・・

書いてて思いつきましたが、>>356をさらにいうならば、300個から最大で10個（特例を除く）で構成される山
を例えば15個作るとき、最も15山の価値の合計が高くなる組み合わせ。

これだとまた全く別の問題になってしまうのでしょうか。

次ページ