計算アルゴリズム【Ⅱ】

計算アルゴリズム【Ⅱ ..

151:147
05/11/13 12:02:13
>>150
ドサ回りする都市の数は5くらいまででいいです。

152:デフォルトの名無しさん
05/11/13 17:16:00
>>151 入力データの仕様をください

153:デフォルトの名無しさん
05/11/13 18:28:11
>>147
入力の仕様がわからなかったので，以下の仕様に従うことにした．標準入力から読み込む．
「1行目: 都市の数，2行目から: 都市1 都市2 その間の距離，終端: EOF」

#include　<iostream>
#include　<vector>
#include　<algorithm>
using　namespace　std;
const　int　inf　=　1　<<　30;
//　brute　force　using　recursion　(　O(n!)　)
int　solve(int　pos,　int　start,　vector<　vector<int>　>&　adj,　vector<bool>&　used)　{
　　used[pos]　=　true;
　　int　d　=　inf;　
　　if　(find(used.begin(),　used.end(),　false)　==　used.end())　d　=　adj[pos][start];
　　for　(int　i　=　0;　i　<　used.size();　++i)　
　　　　if　(!used[i])　d　=　min(d,　adj[pos][i]　+　solve(i,　start,　adj,　used));
　　used[pos]　=　false;
　　return　d;
}
int　main()　{
　　int　n;　cin　>>　n;
　　vector<　vector<int>　>　adj(n,　vector<int>(n,　inf));
　　int　a,　b,　d;
　　while　(cin　>>　a　>>　b　>>　d)　adj[a][b]　=　adj[b][a]　=　d;
　　vector<bool>　used(n,　false);
　　int　start　=　0;　used[start]　=　true;
　　cout　<<　solve(start,　start,　adj,　used)　<<　endl;
}

154:147
05/11/14 06:25:03
>>153
ありがとうございます。仕様はそのとおりでいきましょう。
走らせるために
#define min(a,b) (((a)<(b))?(a):(b))
と
return 0;
を追加しましたが入力の仕方がいまいち分かりません。
都市a bがint型ですよね…。
--------------------------------------------------
3
a b 3
-1073741824
Press any key to continue
--------------------------------------------------
これ↓ではエラーが出て駄目ですし…
--------------------------------------------------
3
1 2 3
4 5 6
Press any key to continue
--------------------------------------------------
どう入力するんでしょうか？m(__)m

155:147
05/11/14 11:24:19
>>153
ダメダメな自分でもようやく分かりました。
Ctrl+Qで終了というのが渋いですね。
少し改良しました。

--------------------------------------------------
Number of Cities: 4
Source Destination Distance:
0 1 2
0 2 4
0 3 3
1 2 3
1 3 6
2 3 1
^Q
9
Press any key to continue
--------------------------------------------------

後はもう少しコメントなどを入れて改良してみます。(当然n数は10を超えない程度で)
ありがとうございました！

156:147
05/11/14 11:58:32
仕様を少し変更しました。パスの数をユーザーから求めて、その数だけ入力がされたら終了、としました。
#include <iostream>
#include <vector>
#include <algorithm>
#define min(a,b) (((a)<(b))?(a):(b))

using namespace std;
const int inf = 1 << 30;
// brute force using recursion ( O(n!) )
int solve(int pos, int start, vector< vector<int> >& adj, vector<bool>& visited) {
visited[pos] = true;
int d = inf;
if (find(visited.begin(), visited.end(), false) == visited.end()) d = adj[pos][start];
for (int i = 0; i < visited.size(); ++i)
if (!visited[i]) d = min(d, adj[pos][i] + solve(i, start, adj, visited)); //←ここで何か記録しないといけないんでしょうが…
visited[pos] = false;
return d;
}
void main() {
int cities, paths; cout << "Number of Cities: "; cin >> cities; cout << "Number of Paths: "; cin >> paths;
vector< vector<int> > adj(cities, vector<int>(cities, inf));
int a, b, d; cout << " S D Distance" << endl;
for (int i = 0; i < paths; ++i) {
cout << "Path" << i+1 << ": "; cin >> a >> b >> d; adj[a][b] = adj[b][a] = d;
}
vector<bool> visited(cities, false);
int start = 0; visited[start] = true;
cout << "The minimum distance is " <<solve(start, start, adj, visited) << endl;
}
あの、で、最短のルートを表示するにはどうしたらいいんでしょうか？本当にしつこくてすみません。m(__)m

157:デフォルトの名無しさん
05/11/14 17:58:34
いくつか手はあるけど，手っ取り早いのは「各 visited の状態から次何を選んだか」を
グローバルの map<vector<bool>, int> にでも覚えさせておくこと．
表示するときは適当な visited からスタートして，visited = 全部 true になるまで覚えさせた map を辿っていく．

具体的には下みたいな感じにやる．
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)

158:157
05/11/15 06:58:17
solve(i, start, adj, visited) を二回も呼んでるのが非効率なのでなんとかしといてください

159:147
05/11/15 15:43:57
>>157
ありがとうございます！m(__)mﾊﾊｧｰ　m(__)mﾊﾊｧｰ　m(__)mﾊﾊｧｰ　m(__)mﾊﾊｧｰ　m(__)mﾊﾊｧｰ
再帰の途中で覚えさせる方法が分からなくて困っていました。
なるほど、ああやって割り込むんですね。本当に勉強になります。
solve(i, start, adj, visited)を二回呼んでるのは後でなんとかします。

ああ、もっと賢くなりたい。←自分

160:フローチャート
05/11/23 20:25:34
価格Ａ，Ｂの商品をそれぞれＸ，Ｙ個、購入する場合の
支払い金額を計算するフローチャートを示せ。ただし、値引き率８％と
消費税５％を考慮すること

161:デフォルトの名無しさん
05/11/23 20:28:11
>>160
そりは難しい課題だねえ。
まずはフローチャートを描くルーチンを作成しないと。

環境は何？　まさか、線を引くルーチンから作らなくちゃいけない？

162:デフォルトの名無しさん
05/11/26 17:42:03
その前に有理数体での加減乗除を定義しないと。
また、有理数の円未満の端数処理をどうするか検討しないとな。
切捨て？切りage？四捨五入？設定で選択できるようにしないと
実用に耐えないかもよ。

163:デフォルトの名無しさん
05/11/26 20:15:28
意地悪なやつらめ。そんなおまえらが好きではあるけど。

164:デフォルトの名無しさん
05/11/26 21:21:57
まあ 137 あたりの経緯があるからな

165:デフォルトの名無しさん
05/11/27 18:06:06
>>162
有理数体上の加減乗除は自明じゃねーの？

166:デフォルトの名無しさん
05/11/27 21:26:38
ていうかコンピュータ上では有理数全てを表現できないし

167:デフォルトの名無しさん
05/11/27 21:35:56
ディジタルコンピュータ上ではできないね。

168:デフォルトの名無しさん
05/11/27 21:45:26
全ては表現できなくても適当な位相さえ入れば十分でしょ

169:デフォルトの名無しさん
05/12/01 12:06:34
てか、実数から見たら表現できる数値なんて穴だらけだよな。

170:デフォルトの名無しさん
05/12/01 18:13:16
つ区間演算

171:デフォルトの名無しさん
05/12/04 01:41:03
配列nに対してn-1個の値があり、残りひとつはNULLでも0でもいいのでデータとしては何も入ってない状態。
その配列nの中のn-1個の数列を配列nの中だけでソートしたいのですが何かいいアイデアないでしょうか？
つまりデータ構造やポインタは勿論、
二分木や多分木を使ってヒープも駄目ということです。

172:デフォルトの名無しさん
05/12/04 02:00:23
バブルソートなりクイックソートなり

173:デフォルトの名無しさん
05/12/04 03:54:54
>171
状況がよくわからん。
具体的に。

174:デフォルトの名無しさん
05/12/05 16:33:28
カタカナの「ノ」の形の離散データの極率を求める数値計算法ってありますか？
書物で調べたりググったりしていますが、見つかりません。

175:174
05/12/05 16:35:59
極率　ではなく　曲率　でした。

176:デフォルトの名無しさん
05/12/05 16:40:06
二次回帰分析とかって話?

177:174
05/12/05 16:58:41
>>176
レスありがとうございます。
二次回帰分析ですと、y=a(x^2)+bx+c のa,b,cを決定するとこになると思われます。

今やりたいことは、例えば y = exp(-3*p)+q^2 に対応する離散データから
(p, q)を求めるというものです。
exp(x)は２次関数ではありませんが、例えばテイラー展開等で近似をすれば、
適応出来る物なのでしょうか？

178:デフォルトの名無しさん
05/12/05 19:46:30
最小二乗フィッティングだね．
理論的には，s_1, ..., s_n をパラメータとする関数 f(x; s_1, ..., s_n) を
データ列 (x_1, y_1), ..., (x_N, y_N) にフィッティングするときは誤差の二乗和
φ(s_1, ..., s_n) = Σ(f(x_i; s_1, ..., s_n) - y_i)^2
を最小化する s_1, ..., s_n を求めてやればいい．

で，それは結構難しくて，凸関数とか条件付かないと最良解が出る保証は無い．
ある程度の解でいいなら，「勾配法 + アニーリング」くらいで，それなりに求まってくれるはず．

179:デフォルトの名無しさん
05/12/05 19:50:09
画像調整のガンマをスクロールバーで実装したいのですが、
イマイチ正確な定義が分かりません。

それか、組み込めるライブラリどこかに落ちてないでしょうか？

180:174
05/12/05 20:15:07
>>178
詳しいレスありがとうございます。
今現在では、範囲と精度を与えて、全部の(p, q)について調べ、その誤差の二乗和が
最小になる(p, q)の組を解としています。

勾配法、アニーリングを調べてみて、検討してみます。

181:デフォルトの名無しさん
05/12/05 20:17:32
>>179
質問の意味がわからないけど多分スレ違い。

・言語と開発ツールは何を使ってるのか
・具体的にやりたいことは何か
・今自分は何がわからないのか

この三点をはっきりさせて、適切なスレに行って聞いてください。

182:デフォルトの名無しさん
05/12/05 21:10:48
あるデータ列に
Y = (A(X^3)+B(X^2))/(CX+D)
の最小自乗法を適応するばあい、
残差の２乗和 S に対して
A, B, C, Dそれぞれで偏微分したもの = 0
の連立方程式を解いて、
A = Σを含む式
B = ...
C = ...
D = ...
とすれば良いのでしょうか？

簡単な式の最小自乗法しか使っていなかったので、
そのまま適応して良いものかどうかが分かりません。
お願いします。

183:デフォルトの名無しさん
05/12/05 21:18:39
>>182
OK．

ただ偏微分したもの = 0 が陽に解ける保証はどこにもないし，解けたとしても解は一般に複数存在するので
出した解が本当に良いフィッティングになってるかは十分議論する必要がある．

184:182
05/12/05 21:30:11
>>183
ありがとうございます。勉強になります。

185:アルゴリズム
05/12/06 10:20:52
N人分のデータ（氏名、体重、身長、年齢）がＤＡＴＡ文で入力されているプログラムが
ある。これを用いて次のプログラムをＢＡＳＩＣで作成しなさい

年齢が３０歳以下の人の、体重と身長の平均値を計算し表示する

186:デフォルトの名無しさん
05/12/06 10:59:37
select average(weight), average(height) from DATA where (age <= 30);

187:デフォルトの名無しさん
05/12/06 12:50:40
>185
スレタイくらい嫁。
くだ質スレか宿題スレ池や。

188:デフォルトの名無しさん
05/12/06 20:36:58
>177
エクセルにデータを叩き込んでexpの形で近似曲線出すのが一番手軽な希ガス。

ところでexp（）の形になると判ってるなら、logを取ったらどうなる？

189:デフォルトの名無しさん
05/12/06 21:51:46
プチ統計学講座だなｗ

190:デフォルトの名無しさん
05/12/06 22:09:54
>>188
ヒント：Windowsとは限らない

191:デフォルトの名無しさん
05/12/06 22:28:03
ひんと：Excel以外にも統計処理できるソフトはあるし、そもそもMacでもExcelは動く。

192:デフォルトの名無しさん
05/12/06 22:34:45
>>190-191
ヒント：そもそも汎用機とも限らない　例：宇宙計算用スパコン

だからこそのアルゴリズムスレだろ？

193:デフォルトの名無しさん
05/12/06 23:14:51
だからlogとったらどうなるかと聞いてみたんだけど

194:デフォルトの名無しさん
05/12/06 23:30:44
だから前半にだけ突っこんだんだけど

195:デフォルトの名無しさん
05/12/07 19:22:24
まぁまぁ、次のネタを待ちましょう

196:デフォルトの名無しさん
05/12/07 19:55:37
上にも最小自乗法の話題が出ていますが･･･

y=(A(x^3)+B(x))/(C(x^2)+D)
の関数に最小自乗法を適応することは出来ますか？
残差の２乗和が最小になる(A,B,C,D)を見つけるわけですが、
例えばCで偏微分して=0となるCは、単なる極地のCであり、
それが極小かつ最小となるわけではありませんよね？

197:196
05/12/07 19:57:51
あれ！？
よく見たら>>182とまったく同じ式でした･･･。
当方、学生ではないので課題とかでもないのですが。
同じ書物を読んでいるのかしら。

>>183を参考にします。
無視してください。

198:デフォルトの名無しさん
05/12/07 20:29:05
フローチャートしか知らない

199:デフォルトの名無しさん
05/12/08 10:14:07
二次元配列と、
その中の３つの点で定義される三角形があって、
ある点がその中か外か判定するアルゴリズム教えて下さい。

200:デフォルトの名無しさん
05/12/08 11:58:18
>>199
(0,0), (0,2), (2,0) という要素数3個の2次元配列が与えられた場合、
(1,1) という点がその三角形の中にあるかどうかということだよな？

1)与えられた3点が三角形を構成するかどうかを吟味。
2)その3点から各々2点を取り出し(3通り)、2点を通る直線の式を求める。
3)その3本について、直線で座標平面を分割した場合、残りの頂点を含む領域を不等式(3通り)であらわす。
4)中か外かを判定したい点について、その3つの不等式を同時に満たせば中、そうでなければ外。

201:デフォルトの名無しさん
05/12/08 12:26:41
そのまんまじゃん

202:デフォルトの名無しさん
05/12/08 13:04:30
ナップザックを背負ったバックパッカー*がいるとする。ナップザックの中は、
できるだけ使い勝手の良いもので満たさなければならない。ナップザックの大きさは限られているので、
どのような荷物で満たすかが非常に大事な問題となる。ナップザック問題とは、ある目的のコストが
最大となるように限られたスペースにアイテム(item)を配置する問題のことである。次の問いに答えよ
*リュックサックに全ての荷物を入れて旅行する人のこと。
問1
0/1 ナップザック問題とは何か？
問2
全てのアイテムが(1)同じコストあるいは(2)同じサイズであればナップザック問題はどん
な問題となるのだろうか？
問3
アイテムのコストが大きさに比例する場合は、ナップザック問題はどんな問題となるの
か？
問4
ナップザックの大きさがアイテムに比べて非常に大きい場合は、一体何が起こるか？参考
書にあるプログラムを使って調べ、現象から生じた問題を指摘し、それが何故生じるのか
記述せよ．

203:デフォルトの名無しさん
05/12/08 15:35:02
>>202
ここは君が来るべきスレでは無いよ。

204:デフォルトの名無しさん
05/12/08 15:59:27
>>203
いいじゃんべつに。
お前の個人的な感情は出さなくてもいいよ。
そんなもの読んでいる人間には全く価値がないから。
文句があるならどのスレにいけ、ぐらいは言えよ。
あ、頭悪スレとかに誘導するのは全く無意味だからやめてね。

205:デフォルトの名無しさん
05/12/08 18:15:33
>>204
つまんないﾈﾀ書くのも自由だし
それを批判するのも自由。

206:デフォルトの名無しさん
05/12/08 18:37:18
座標３つ（どれがどの位置か不明）から、３角形の面積を計算する方法はありますか？

207:デフォルトの名無しさん
05/12/08 18:40:49
>>205
自重しろよ。
自由ではないんだよ？あまりひどいとアク禁だ。

208:デフォルトの名無しさん
05/12/08 19:52:21
>>206
3点から辺の長さ求めてHeronの公式、とか。

209:デフォルトの名無しさん
05/12/08 20:01:43
三点のベクトルが v1, v2, v3 のとき
[v1-v2, v3-v2]/2 の絶対値が面積になるね。

[x,y] は x と y の外積ね。

210:デフォルトの名無しさん
05/12/08 20:02:07
>>206
ある点を原点に移動させるように全体を並行移動させて、
(0,0),(a,b),(c,d)の三角形の面積が(1/2)*|a*d - b*c| であることを
使った方が簡単かも。

３点が三角形が作られない位置に無いことを確かめてからね。

211:デフォルトの名無しさん
05/12/08 20:03:50
実は
（>>182の式）≠（>>196の式）
である件について

212:デフォルトの名無しさん
05/12/08 20:55:54
>>206
URLﾘﾝｸ(www.tensyo.com)
の多角形の面積でやれば？

213:デフォルトの名無しさん
05/12/08 23:07:36
>>199
>>99,>>107-108

>>204
>>187

てか、質問する前にスレ内くらいは読もうぜ？

214:デフォルトの名無しさん
05/12/13 18:24:45
>>206
でも、3点とも座標がわかってて位置不明ってどゆこと？

215:デフォルトの名無しさん
05/12/13 19:24:25
>214
「固定座標じゃない」って意味だろ。
確かに意味は解らないが、気持ちは伝わってきた。

216:デフォルトの名無しさん
05/12/13 20:30:04
ヘロンの公式のことをたずねているの？

217:デフォルトの名無しさん
05/12/13 20:39:02
辺の長さが与えられてるわけじゃなく、頂点座標だから
ヘロンの公式をわざわざ使うより
素直に台形公式による閉曲線積分

218:デフォルトの名無しさん
05/12/13 20:56:04
>>217
頂点座標？閉曲線積分？言葉はちゃんと使おうぜ

219:デフォルトの名無しさん
05/12/14 01:18:24
>>214
任意の三点ってことだろ。

220:デフォルトの名無しさん
05/12/14 11:53:04
三角形なんだから、3点を P, Q, R として、
2つのベクトル a ＝ PQ、b ＝ PR を定義。
(1/2) |a × b|
ただし、×は3次元ベクトルの外積、|| はベクトルの絶対値。

っつーか、ぐぐれ。
URLﾘﾝｸ(homepage2.nifty.com)

221:BASIC
05/12/14 15:57:56
次のプログラムをＢＡＳＩＣで作成しなさい

データを１件ずつ、ユーザ定義関数を利用して
「公共料金」を計算させることにします
＜水道料金の計算＞
基本料金：1250円定量制料金単価は
・使用量が10立方米以下であれば80円／立方米
・〃 10立方米超20立方米以下であれば185円／立方米
・〃 20立方米超50立方米以下であれば205円／立方米
・〃 50立方米超100立方米以下であれば240円／立方米
・〃 100立方米超200立方米以下であれば275円／立方米
・〃 200立方米超であれば310円／立方米
（計算例）
使用量が8立方米であれば、1250＋8×80
使用量が15立方米であれば、1250＋10×80＋(15－10)×185
＝2050＋(15－10)×185
使用量が40立方米であれば、1250＋10×80＋10×185＋(40－20)×205
＝3900＋(40－20)×205
使用量が75立方米であれば、1250＋10×80＋10×185＋30×205＋
(75－50)×240＝10050＋(75－50)×240
使用量が120立方米であれば、1250＋10×80＋10×185＋30×205
＋50×240＋(120－100)×275＝22050＋(120－100)×275
使用量が230立方米であれば、1250＋10×80＋10×185＋30×205
＋50×240 ＋100×275＋(230－200)×310 ＝49550＋(230－200)×310

222:デフォルトの名無しさん
05/12/14 15:58:42
作成しなさい、だってさ↓

223:デフォルトの名無しさん
05/12/14 16:01:00

　　　　　　　　　　　｜　　　　　∧＿∧
　　　　　　　　　　　｜.　　　　(･ω･` )ｽﾙｰ
　　　　　　　　　　　｜ｽｽ…　/J　　 J
　　　　　　　　　　　↓　　　,,, し―-J

224:デフォルトの名無しさん
05/12/14 16:51:10
アルゴリズムじゃねえな

225:デフォルトの名無しさん
05/12/14 19:15:46
アゴリズムだな

226:デフォルトの名無しさん
05/12/15 00:36:36
アルゴリズムじゃねえって！

227:デフォルトの名無しさん
05/12/15 04:40:03
アルゴリズム体操！アルゴリズム体操！

228:デフォルトの名無しさん
05/12/16 15:42:28
立方米って一般的なのか。
m^3と書かないの。

229:デフォルトの名無しさん
05/12/16 15:51:32
>>228
メートル=米、だからね。
他にも糎とか粍とか。
でも、普通は立方米と書かずに立米(りゅうべい)と書く希ガス。
#平米は割と一般的でしょ。

230:デフォルトの名無しさん
05/12/17 12:32:02
口頭ではよく「へーべー」と言うな。
俺の父親が。

231:デフォルトの名無しさん
05/12/17 12:34:10
なんでメートルが米なの？？その由来は？

232:デフォルトの名無しさん
05/12/17 12:58:32
亜米利加　と同じじゃないの？　メの元の漢字だと思ってたけど
URLﾘﾝｸ(www.fudemojiya.com)
によると　女　らしい

233:デフォルトの名無しさん
05/12/17 13:05:23
明治時代か江戸末期に「メートル(或いはメーター)」という音に似ているから当てたんじゃないの?
他にもグラムやインチなどにも当てられた漢字があることだし。

234:デフォルトの名無しさん
05/12/17 19:27:50
URLﾘﾝｸ(freett.com)
発案した人も途中からヤケクソになっていったのだと推測

235:デフォルトの名無しさん
05/12/17 22:42:29
>>234
そこまでして漢字にせんでもええやん…とおもた。

236:デフォルトの名無しさん
05/12/18 03:23:45
当時ハ送リ仮名ガ片仮名デアッタタメ
外来語ヲ片仮名ニ割リ当テルトイウ
発想ハ無カッタンダロウナ

237:デフォルトの名無しさん
05/12/18 04:08:19
質問なのですが、例えば、
1、２、３、４、５、４０、５０、６０、７０　といった代表値である数字があるとします。

で、例えばXがその代表値のどれに一番近いかを求めるとき
すべてを探索すれば答えはわかると思いますが、できるだけ高速に
求めたいと考えたとき、代表地を木にすればいいのではと私は考えました、

例えばXが6だとするとまず、5が一番近いことがわかります
これをどうやって木にしたらいいのかがわかりません。
また１，２、３・・・・といっていましたが
（X,Y,Z)と三次元に増えた場合、一番近い点を見つけるにはどうしたらいいのでしょう？
一致するのを探すのではなく一番近いものを探すので苦労しています。
近さの判定としてはユークリッド距離を用います。
どうぞよろしくお願いいたします

238:デフォルトの名無しさん
05/12/18 04:13:08
代表値の数列が整列されている前提ならバイナリサーチでいいのでは？

239:デフォルトの名無しさん
05/12/18 04:32:56
>>238
ありがとうございます。
バイナリサーチですと完全に一致する場合は問題ありませんが
完全に一致せず一番近いものを選択するときに問題がおきます

237の例で6に一番近いものをバイナリサーチで探そうとすると
40になると思われます

240:デフォルトの名無しさん
05/12/18 04:46:58
バイナリサーチで最終的に 40 がヒットするわけだけど、
この 40 と X を比較することによって 5 < X < 40 という関係はすぐにわかる。
あとはどちらに近いかを計算するだけじゃないのかな。

241:デフォルトの名無しさん
05/12/18 04:54:28
>239
最終段でヒットしなかった時、left/rightどちらの方が近いかチェックしろ。
n次の場合は、a=f(X,Y,...)で、aの値でソート。

242:デフォルトの名無しさん
05/12/18 05:01:13
>>240
>>241
ありがとうございます。
ｎ次の場合はうまくいかないように感じるのですが
できれば具体例を出していただけないでしょうか？
241さんのを自分なりに解釈すると、まずはXについてどれが一番近いか
しらべて次はY、Z・・・というふうなことだと感じているのですが
例えばXがかなり近くてもZ,Yがかなり遠いと総合的な距離は遠いわけで
Xが多少遠くてもY,Zが近ければ総合的な距離は近くなるので
あまりうまくいかなようなきがします。
間違っていたらすみません

243:241
05/12/18 05:37:33
>242
スマソ、完全に寝ぼけてた。
1次以上の距離で探したいのなら、総当りで検索するしかないんじゃね？

244:デフォルトの名無しさん
05/12/18 05:40:16
>>243
ありがとうございます。

総当りですか・・・それですと時間がかかるので
何かいい方法がないかなと思いまして

245:デフォルトの名無しさん
05/12/18 07:16:28
>>241
２次元（平面）ならボロノイ図・近傍で似たような問題がある
３次元以上だとできるかどうか知らない

総当りにしたら

246:245
05/12/18 07:17:31
>>245 の >>241 は >>237 の間違いですｽﾏｿ

247:デフォルトの名無しさん
05/12/18 07:55:24
>>245
ありがとうございます。
ボロノイ図については知っていまして、三次元でも可能のようです。
ですが、これをどう木にすればいいのかよくわからなかったもので
何かいい方法があればと思って相談してみました、。

248:デフォルトの名無しさん
05/12/18 09:03:12
>>237
空間データベースって分野のお話だね．

望んだ形でデータを持ってていいなら，k-d tree を使うのが手軽かな．
空間に一点が追加されるたびに，その一点を通る超平面を引き，その超平面のどちら側に
点があるかで二分木を作る．探索は木を手繰りながら範囲を絞り込んで，
その中で全探索をする．最悪 O(n) だけど，適当にばらけてれば O(log n)．

ほかにも SR-tree とか SS-tree とか色々あるので，参考になりそうなのを挙げとく：
URLﾘﾝｸ(www.kecl.ntt.co.jp)
URLﾘﾝｸ(vision.unige.ch)
H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley

249:デフォルトの名無しさん
05/12/18 10:00:28
>>248
ありがとうございます
望んだ形でデータを持っていても大丈夫です。
K－ｄ　tree　についてなのですが、これでは一番近い代表値に近似することはできないと
考えられます。
例えば
URLﾘﾝｸ(www.kecl.ntt.co.jp)
のｋ－ｄ　ｔｒｅｅ　のところの図で説明しますと
代表地がＰと考えると、Ｐ４とＰ５の線の中に点があるのですがＰ９に
一番近い点（一番近い代表地に近似したい点）があったとすると
これはＰ４かＰ５に近似されることになります。
実際はＰ９に一番近いのにこれには近似されないとおいうことです
木を作る際にＰ７からでなくＰ６からはじめたとしても同様の問題はおきると考えられます
しかしＲ－ｔｒｅｅというのは使えそうな気がします
ちょっと読んでみますがいかんせん説明が少ないので理解できるかわかりませんが
なんとかがんばってみます
ありがとうございました

250:デフォルトの名無しさん
05/12/18 10:04:36
URLﾘﾝｸ(www.kecl.ntt.co.jp)
のＲ－ｔｒｅｅを読んでみましたがこれでも正確に一番近い代表地に
近似されないように感じます。
うーんどうしよう

251:デフォルトの名無しさん
05/12/18 10:05:18
一番近い点は一回では求まらないだろう。
　求めた点までの距離を半径とした点で総当りをその後ですればいいだろう。

　たとえば2次元なら　x 座標がその範囲にある条件、次にy座標がその範囲にあるという条件で絞りこんで
　　矩形で絞り込めばいいでしょ

252:デフォルトの名無しさん
05/12/18 10:07:59
あと、この問題は、最悪の場合は、全数検索が必要になる。

たとえば円周上に点が並んでいて、中心に近似しようとした場合など

253:デフォルトの名無しさん
05/12/18 10:17:52
>>251
>>252
ありがとうございます。
自分の中で何か新しいアイデアが浮かんできそうな気がします
が、もう少し具体的にお願いできませんか。何かわかりそうな木がするんです
どうかおねがいします

254:デフォルトの名無しさん
05/12/18 10:25:28
データ構造として、各母点に、母点を中心に、一番遠いボロノイ点までの距離半径の円内にある
母点までのリンクを距離順に並べて持たせておいて
最初に検索した母点までの距離内にあるリンクだけ全検索する
検索する過程で、それより近い点を見つけたら、母点を移して同じ事をする

255:デフォルトの名無しさん
05/12/18 10:35:34
>>254
ありがとうございます
私の理解力不足のためわからなかったです　すいませんが
もう少し簡単な説明をしていただけないでしょうか　どうかお願いします

256:248
05/12/18 10:53:05
>>249
二つ目に挙げたテクニカルレポートも読んでね．ちゃんとそっちに作った木から kNN を絞り込む方法について
コメントが入ってるから．参考文献にもそれっぽいのが沢山あるので子引き，孫引きしましょう．

257:デフォルトの名無しさん
05/12/19 09:08:38
長いですが、NP完全について質問です。
アルゴリズムの本に
「図のどれがP、NP、NP完全(NPCと呼びます)のクラスについての私たちの知識と矛盾しているか？
"=Which of the diagrams do not contradict the current state of our knowledge
about the complexity classes P, NP, and NPC (NP-complete problems)"」
という質問があってヒントに
「これらのうちの二つのみが現在の私たちの知識と矛盾している
"=Just two of them do not contradict the current state of our knowledge about the complexity classes."」とあります。
「私たちの知識」とはその本に載っている
「もしP≠NPなら、PでもNP完全でもないNP問題があるはずだ
"=It is known that if P≠NP, there must exist NP problems that neither are in P nor are NP-complete."」
っぽいです。

図は五つあって、そのうち
aはP=NP=NPCで、bはNPCがP=NPの部分集合になっており、dはPとNPCが重なった形でNPの部分集合になっており、
これらは明らかに矛盾しているので除外です。
eは↓のサイトにも載っている一般的に知られているベン図ですから矛盾していません。

URLﾘﾝｸ(www.jyi.org)

で問題のcなんですが、これは↑のサイトに載っている図のPとNPCが
NPを真っ二つにして占めており、まったく隙間がありません。(想像できますか？)
これも矛盾してますよね？PでもNP完全でもないNP問題がないといけないんですから。
そうだとしたらこの本の間違いなんですが…。
ここの賢い人、どうか答えてください。せめてヒントだけでも…。

258:257
05/12/19 09:19:37
あまりの必死さに図を描いてしまいます。m(__)m

c.　　　　　　　　ＮＰ
┌───┬───┐
│　　　　　　　│　　　　　　　　│
│　　　Ｐ　　　│　　ＮＰＣ　　　│
│　　　　　　　│　　　　　　　　│
└───┴───┘

てな感じです。

259:257
05/12/19 09:23:48
度々すみません。訳し間違えました。正しくは
「図のどれがP、NP、NP完全(NPCと呼びます)のクラスについての私たちの知識と矛盾して『いない』か？」
と
「これらのうちの二つのみが現在の私たちの知識と矛盾して『いない』」
です。もう後で逝ってくるつもりです。m(__)m

260:デフォルトの名無しさん
05/12/19 10:19:49
>>188
すみません

261:デフォルトの名無しさん
05/12/19 13:34:18
>>257
「PでもNP完全でもないNP問題がないといけない」はあくまで「P≠NPならば」
であって、「P≠NP」とは限らない。

262:257
05/12/20 12:17:51
>>261
ありがとうございます。
なるほど、「P≠NP」とは限りませんよね。
もしそうだとすれば選択肢は「P＝NP」しかない訳で
その場合は「PでもNP完全でもないNP問題があろうがなかろうが関係ない」
と解釈してよいのでしょうか？

友達の一人は「『P＝NP』は『現在の私たちの知識』に矛盾していないか？
図a, bはP=NPだから簡単に矛盾していると判断できたんじゃないか。
cがP=NPとするなら矛盾していると判断するべきだろう？」と問いかけてきました。うーむ。

すみません、自分、人より脳が少し足りないようです。
また説明お願いします。m(__)m

263:デフォルトの名無しさん
05/12/20 14:31:12
>>262
現在の多くの人たちの『考え』には矛盾しているが、それは『知識』ではない。
P=NPは、我々が馬鹿なだけですべてのNP問題は実は多項式時間で
とくことが出来ると言うこと。そんなことはないだろうと思うかもしれないが、
多項式時間で解くことの出来ない問題があることを証明できていない現在、
P=NPは矛盾しているとはいえない。

264:257
05/12/21 12:01:14
>>263
なるほど、ようやく分かりました。
すべてのNP問題が(近似解とかではなく)
多項式時間で解けるようになったら面白いでしょうね。
天寿を全うするまでに見たいものです。
ありがとうございました！

265:デフォルトの名無しさん
06/01/09 00:12:14
age

266:BASIC
06/01/09 16:12:52
N人分のデータ（氏名、体重、身長、年齢）がＤＡＴＡ文で入力されているプログラムが
ある。これを用いて次のプログラムをＢＡＳＩＣで作成しなさい
体重が６０ｋｇ以上で、身長が１５０ｃｍ未満の人の名前を表示する

267:デフォルトの名無しさん
06/01/09 17:34:00
宿題は自分でやれ

268:デフォルトの名無しさん
06/01/09 17:54:08
BASICなんて記憶の彼方だな

269:デフォルトの名無しさん
06/01/09 18:15:01
何ベーシックかは指定していないな。
VBとかでもいいとすれば随分アレだ

270:デフォルトの名無しさん
06/01/09 19:08:23
>>266
URLﾘﾝｸ(www.sagami.ne.jp)

271:デフォルトの名無しさん
06/01/11 03:29:11
ヤコビ行列の計算を効率良く行う工夫は何かあるでしょうか？
(n*m)回の微分演算という時間を喰う処理を少しでも短くしたいです

もしくは優れたJacobianMatrixクラスの例をご存じであれば是非！

272:デフォルトの名無しさん
06/01/11 06:49:10
Jacobian の成分が nm 個ある以上，本質的にそれよりオーダーが落ちることはありえない．
定数オーダーでの最適化は計算モデルに依存するので議論できん．そもそもおまいが微分をどう実装してるかもわからんし．

O(nm) すら許せないなら，問題に応じてアドホックに解決するっきゃ無いと思うがなあ．どんな問題解いてるんだ？

273:デフォルトの名無しさん
06/01/11 10:57:45
>271
LZのスライド辞書みたいに、演算した組み合わせを辞書に登録しておいて、
次回以降は演算を省くってのはどうだろう？
辞書の検索にかかる時間を何らかの方法（連想配列とか）で短縮する必要はあるだろうけど。

274:271
06/01/12 12:31:26
>>272-273
早いレスどうもです！

>>272
やはりO(nm)回は「本質的に」避けられないわけですよねー・・・
微分の差分近似をループでnm回やるつまらない実装なんで、
工夫できないかなと思った次第だったのですが。
ちなみに問題は非線形関数の最小値探査みたいな感じです

>>273
んー、いいアイディアなんですが今回は
適用できないような気がします、ゴメンナサイ
ただ、そのうち他の問題で使えそうな気がするんで、
そのネタはもらって覚えておきます！　ありがとう！

275:デフォルトの名無しさん
06/01/14 00:48:34
>>274
最小化したい非線型関数になんか条件付けないと定数レベルの最適化もつらいような

276:デフォルトの名無しさん
06/01/31 17:55:55
最小二乗法のライブラリきぼんゅ。

277:デフォルトの名無しさん
06/02/01 03:14:47
>>276
ライブラリも何も、大した計算じゃないじゃん。

278:デフォルトの名無しさん
06/02/01 12:32:21
>>277
世の中に存在するアルゴリズムの中で複雑と言えるものがどれだけある？

279:276
06/02/01 12:44:24
最小二乗法おしえて欲しいぉ。

280:デフォルトの名無しさん
06/02/01 13:38:16
残差平方和が最小になるようにパラメータを決定するのです
このスレでも簡単な例がいくつか
>>178
>>182
>>196

非線形になってくるとちょっとめんどい
URLﾘﾝｸ(en.wikipedia.org)
URLﾘﾝｸ(en.wikipedia.org)
ここら辺を参考に

281:デフォルトの名無しさん
06/02/02 02:20:31
>>278
FFTになると、ライブラリが欲しい程度には複雑だと思う。

282:デフォルトの名無しさん
06/02/02 08:51:05
>>281
どれだけある？という問いにＦＦＴ１個かよ。

283:デフォルトの名無しさん
06/02/02 09:25:21
>>282
世の中に存在するアルゴリズムがどれくらいあるのか教えてくれたら答えてあげるよ。

284:デフォルトの名無しさん
06/02/02 13:43:21
行列計算もだいたい書く気がしないな．条件数が悪い場合とか考え出すと相当面倒くさい．

285:デフォルトの名無しさん
06/02/02 14:58:57
あとは圧縮＆展開と多倍長演算あたりかね？　汎用的なのは。
各分野毎にはいろいろとあるだろうけど。
画像エフェクト、サウンドエフェクト、3D系演算とか。

286:デフォルトの名無しさん
06/02/02 15:52:22
>>281
難しくはないが複雑ではあるよな。

287:デフォルトの名無しさん
06/02/02 22:26:58
各種関数なんかは、大概簡単なことをやっていても、実装は面倒だなぁ。

288:デフォルトの名無しさん
06/02/05 09:27:32
最小二乗法は
円に適用するだけでも、厄介だし、
直線に適用しようとしたって、実はけっこう難しいよ。
たとえば、2次元画像から直線部を取りたいとしたら、学校でやるようなXとかYでの偏微分じゃ、それこそ偏る。

　残差って何って所から取り掛からないとね。

そして、余程単純じゃないと、たいていは方程式1発で解けるという事にはならない。
数値解で求める事になるだろうな

289:デフォルトの名無しさん
06/02/06 07:09:38
>>288
ただの偏微分でしか説明しないのって，相当ひどい学校だと思う

290:276
06/02/06 10:04:37
>>288
じゃ、何を使うのさ？？？？？

>>289
詳しく！！！！！

291:デフォルトの名無しさん
06/02/06 14:14:46
>>288
最小二乗法はロバストでないのでそのあたりは考慮しないと。
例えば、y=x上に完全に点が並んでいる状態で、
たった一点(1,10000)が入ってきただけでy=2xとかになると困るわけだ。

292:276
06/02/06 14:22:51
今回の開発では点の数に関しては、決めウチできます。

293:288
06/02/07 06:30:36
>>290
だから、最小2乗法を使うなら、何を最小にするのかって所が肝心って事さ
直線を求めるのにしたって、数表上と2次元データとは誤差の意味が違う
数表上なら結果の誤差を最小にしたいし
2次元なら直線からの誤差を最小にすると同時に回転変換で結果が変わらない必要がある

294:デフォルトの名無しさん
06/02/09 11:57:07
最小2乗法ｱｹﾞ

295:sage
06/02/09 21:45:42
sage

296:デフォルトの名無しさん
06/02/11 17:31:27
n個の要素の2番目に小さい要素は最悪n+logn－2回の比較で求められることを証明しなさい。

順序統計量を使うのだと思うのですが、帰納法を使って証明するのかどうか分かりません。
どなかか説明してもらえないでしょうか？よろしくお願いします。
高校の時に教師が言っていたんだけど急に思い出して・・・・おねがいします。

297:デフォルトの名無しさん
06/02/11 18:07:41
　／￣￣￣￣＼
／　　　　 ●　　 ●　
|Y　　Y　　　　　　　　＼
| |　　 | 　　　　　　　 ▼　| ﾊﾟｸｯ
| ＼／　　　＿＿＿＿人__|
|　　　　　　|∨∨∨∨∨　←296
＼　　　　　＼∧∧　　　）
　｜｜　|＼　￣￣＼＼＼
　｜｜　|　　￣￣￣しし/
　（_＿）＿）

298:デフォルトの名無しさん
06/02/11 18:33:39
最悪 n - 1じゃないか? 何番目でも最悪 n - 1回でいけそうだ。
今適当に考えただけだから間違ってるかもしれないけど。

299:デフォルトの名無しさん
06/02/11 18:40:59
違った、最悪 n回か。

300:デフォルトの名無しさん
06/02/11 18:45:05
>>298
いや、漏れが覚えている限りでは違うと思われ。
MITだかどっかの教科書の奴に載ってた。二番目を求めるけども一番最小を求めてからだったはず
院試にでてたかも。

301:デフォルトの名無しさん
06/02/11 18:57:23
>>300
やっぱり違ってた。考え直したら、
nが偶数なら (3/2)*n - 2,
奇数なら (3/2)*n - 3/2 回だった。

302:デフォルトの名無しさん
06/02/11 20:58:20
>>296
ソートアルゴリズムのところとかかな？学部生の時に必死こいてやったけどもう忘れた・・・。
あの教科書は原書で読んだ方がいいかもしれんな。英語だからかなりめんどくさいが。半期でやるのを英語でやったら一年半かかったよ。

303:デフォルトの名無しさん
06/02/12 00:24:16
証明になってないｗ

304:デフォルトの名無しさん
06/02/12 03:01:20
>>296
完全二分木でトーナメントを考えよう。
一番小さい要素を見つけるのにn-1回の比較が必要。
二番目に小さい要素は一番小さい要素の対戦相手のどれか。
木の高さはceil(log n)で木の一番上には対戦相手はいないから、
二番目に小さい要素の候補たりえるものはceil(log n)-1個
この中から一番小さいものをみつけるのにceil(log n)-2回の比較が必要。
したがって比較回数は、
(n-1)+ceil(log n)-2<n+logn-2
ただし、ceil(x)はxの小数点以下切り上げの関数

305:デフォルトの名無しさん
06/02/13 00:39:26
>>304
なるほど。
それは比較は少ないけどコピーがメモリが多く必要になりそうなんだけど
どうなんだろう。

306:デフォルトの名無しさん
06/02/13 06:11:40
２分木にする必要性が感じられないってかなってないｗ

307:デフォルトの名無しさん
06/02/14 10:30:15
>>305
実装の話はしてないんだよね。実際にこの比較回数で動くプログラムを作るのは
結構困難な気がするし、普通の 2n 回比較に定数倍で負けそう。

308:デフォルトの名無しさん
06/02/27 09:33:06
３２ビットの符号無整数型で３２個のビットのうち
N個をランダムに選んで１にするアルゴリズム。
（残りの３２－N個は０）
賢い人教えて。

309:デフォルトの名無しさん
06/02/27 11:33:45
>>308
そのサイズの乱数を一個生成するだけじゃいかんの？ C なら rand() とかで。

それとも乱数生成のアルゴリズム自体を聞いてるの？

310:デフォルトの名無しさん
06/02/27 12:12:40
たぶん
１）組み合わせの数の計算方法が判らない
２）乱数と、その全部の組み合わせを対応させる方法が判らない

のだろうと思うんだけどね

311:デフォルトの名無しさん
06/02/27 12:28:33
1U << (rand() & 31)
とか、そういうことではないの？

312:デフォルトの名無しさん
06/02/27 12:35:07
>>311
rand って完全にランダムじゃなくて、
下位ビットほど短い周期性持ってるから、
rand() & 31 はあんまりよくない。
(rand() >> 16) & 31 とか、何ビットかシフトするの推奨。

313:デフォルトの名無しさん
06/02/27 12:38:20
分かってて書いてたつもりだけど…アルゴリズムの質問だし。
random()でもMTでも好きなの使えばいいんじゃない？

314:デフォルトの名無しさん
06/02/27 12:41:56
>>313
まあそうだけどね。

>>308 がそんな判断できると思えなかったんで、一応補足のつもり。

315:308
06/02/27 13:09:41
MTとかで生成された乱数の立っているビットの数は
１６本を中心にした正規分布になってると思うんだけど、
必ずN本になるようにしたい。
３本とか３０本とかってのはたまにしか発生しないし。
N回ループで一度使った数は記憶させとくとかっていう
愚直なのは思いついたんだけど遅そうなので聞いてみた。

316:デフォルトの名無しさん
06/02/27 15:31:21
32個の数字から N個取り出して順不同というのと　問題は同じでしょ

317:デフォルトの名無しさん
06/02/27 20:50:08
>>316
ですね。
1～32の間で離散一様乱数発生させたものをa_0、
1～31の間の乱数をa_1、1～30の間をa_2として、
初期値は0で左からa_0番目のビットを1にする。
以降左からa_k番目の0のビットを1にする。
　　　　　　　　　　　　　~~

318:308
06/02/28 09:54:13
>>317
今はそれでやってます。
みなさん聞いてくれてありがとう。

319:308
06/02/28 09:58:33
あ、ついでに言っとくとNが17以上の場合は32-N個のビットを立てて反転してる。
連投ごめん。

320:308
06/03/01 16:40:57
やっぱりもっと速いのないかな。

321:デフォルトの名無しさん
06/03/01 17:19:36
>>320
これ以上議論するなら，「速い」をきっちり定義してもらわないと．

特に乱数生成のコスト，各ビットを参照するコストなどが無いと，
どっちが速いかなんて比較できんよ．

322:デフォルトの名無しさん
06/03/02 11:59:32
もっと早い方法は、全部の組み合わせのテーブルを作っておいて
それの配列番号を乱数で選ぶ事だね

323:デフォルトの名無しさん
06/03/02 12:53:16
>>322
2^32 / 2 (0≤N≤16 だから半分) = 2G×4Byte = 8GB
何を使って動かすつもり？

324:デフォルトの名無しさん
06/03/02 16:39:38
>>317
それは、順番を考慮した場合のアルゴリズムだから違うようだけど
結果はN個のビットだから、どの組み合わせも等確率で発生するから問題ないのか

>>323
Nを固定すれば　最大の組合せ数は N=16の時でその1/4程度の容量だから最近のPCなら入るんじゃないの？

組み合わせの数ってどの程度だろ？
32!/N!/2^N では大きすぎるな

325:デフォルトの名無しさん
06/03/02 16:43:14

たとえば32個中3個が１の組み合わせを F(32,3) のように書くと

先頭ビットが0 なら残りは F(31,3)
先頭ビットが1 なら残りは F(31,2)

という事で
F(N,M)=F(N-1,M)+F(N-1,M-1)

326:デフォルトの名無しさん
06/03/02 17:23:15
>>324,325 高校数学の教科書読み直したら？
URLﾘﾝｸ(ja.wikibooks.org)

327:デフォルトの名無しさん
06/03/02 18:34:31
という事は 32 C 16
URLﾘﾝｸ(www.google.co.jp)(16!*16!)
601 080 390
って事か

Σ M C n =2^M って事になるんだな

328:デフォルトの名無しさん
06/03/02 18:39:51
で 32個中16個の組み合わせ　は　32!/(16!*16!)
なのに >>317の方法は　順列　で　32!/16!　という事で、16! の重複があるから、なんか重そうに見えるという事？

329:デフォルトの名無しさん
06/03/03 07:29:43
配列のソートではなく、上位2者と下位2者を高速にシークするアルゴリズムを教えて＞＜

330:デフォルトの名無しさん
06/03/03 07:50:10
var max1,max2 min1,min2;

max1:=data[0];
max2:=data[1];

if max2> max1 then swap(max1,max2);
min2:=max1;
min1:=max2;

for i:=low(data)+2 to High(data) do begin
　 if data[i] > max2 then begin
　　if data[i] > max1 then max1:=data[i] else max2:=data[i];
　 end;

　 if data[i] < min2 then begin
　　if data[i] < min1 then min1:=data[i] else min2:=data[i];
　 end;
end;

こんな感じでは？

331:デフォルトの名無しさん
06/04/18 07:42:35
いわゆる○×。ただし、ちょっと特殊。
ban(0) ban(1) ban(2)
ban(3) ban(4) ban(5)
ban(6) ban(7) ban(8) //盤面　位置関係はこんな感じ
turn //ターン数　最初は1

プレイヤーＡのターン開始
↓
Ａが指定しかつその場所に当たる変数（真ん中ならban(4)）が0であるならばそれに（turn×１０）＋プレイヤーの番号
（Ａは１、Ｂは２とする。）を代入。
↓
turn>6ならば、次のことを行う。
　banの中で下１桁がプレイヤーの番号と等しいもののなかで、一番小さいものに0を代入
↓
banに縦横斜めに自分の番号が並んでいるならば勝利
↓
turnに１を足し、Ａのターンを終了、Ｂのターンになる。

で、できるだけ強いCOMのアルゴリズムを考えてほしいのです。
お願いします。

次ページ