5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

線形計画問題

1 :名前は開発中のものです。:2006/06/07(水) 08:14:17 ID:372w22Y7
物理エンジンの土台となる線形計画問題ソルバーについて語ろう。
お奨めの良書や参考ソースがあったらどんどん書きこんでください。
最近のお奨めはLEMKE-HOWSON法かしら?

2 :名前は開発中のものです。:2006/06/07(水) 09:02:41 ID:7E+h7XTy
ぬるぽ ガッ

3 :名前は開発中のものです。:2006/06/07(水) 09:05:49 ID:7E+h7XTy
ていうか、
>物理エンジンの土台となる線形計画問題
ってなに?

「線形計画問題とは, 与えられた線形な等式および不等式制約のもとで,
線形目的関数を最大化あるいは最小化する問題である。」

物理エンジンと一体あなたどういう関係?

4 :名前は開発中のものです。:2006/06/07(水) 10:02:41 ID:62i33Qbg
最近どっかのスレに質問書き込んでたな。
あさましい奴だな。

5 :晒しage:2006/06/07(水) 15:45:13 ID:ju60AjQb
物理エンジンの土台となる足し算引き算掛け算割り算について語ろう。
お奨めの良書や参考ソースがあったらどんどん書きこんでください。
最近のお奨めは交換・結合・分配法則かしら?

6 :名前は開発中のものです。:2006/06/07(水) 22:02:19 ID:7E+h7XTy
ちんころよろしく=ちんこ×ろ×(よ+ろ+し+く)
          =ちんこ×(よろ+ろろ+しろ+くろ)
          =よろちんこ+ろろちんこ+しろちんこ+くろちんこ

ちんこの分配法則

7 :名前は開発中のものです。:2006/06/08(木) 12:16:22 ID:7PH6zLFJ
線形計画問題の定義

Ax <= b;
f = cx;
x >= 0;

(ベクトルx,b,c,行列A)

上の条件でfを最大化するxを求める

LEMKE-HOWSONの解法

式の定義

w = q + Mz;

w o z = 0;

w >= 0, z >= 0;

( oの演算の定義 : ( w[0]*z[0], w[1]*z[1], ... , w[k]*z[k] ) = (0,0,...,0) )

8 :名前は開発中のものです。:2006/06/08(木) 12:29:42 ID:7PH6zLFJ
   | -c |
q=| -- |
   | b |

   | 0 | At|
M=|--+-- |
   |-A| 0 |

   | u |
w= | - |
   | s |

  | x |
z=| - |
  | y |

( At は 行列Aの転置 )



9 :名前は開発中のものです。:2006/06/08(木) 12:34:30 ID:7PH6zLFJ
式を次のようにする

w = q + Mz + zo1 (式1:ベクトルの式です)

(1は(1,1,...,1)のベクトル)


1. 式1で q[k] が負で最小となる式を選択する。
2. 選択した式で、zoを左辺に移動し、左辺のw[k]を右辺に移動する。
w[k]が右辺に移動したのでz[k]を探索変数とする。
zo=...の形になるように-1で式を割る。
zo=...の式を残りの式1のzoに代入して、式1を更新する。
3. 式1で探索変数の係数が負で、q[k]/探索変数の係数が最大となる式を選択する。
4. 選択した式で探索変数(z[k]またはw[k])を左辺に移動し、元の左辺の変数を右辺に移動する。
探索変数(z[k]またはw[k])の(-係数)で割り、探索変数=...(z[k]=...,またはw[k]=...)の形に整える。
探索変数=...の式を残りの式1の探索変数に代入して、式1を更新する。
5. 4の移動で式1の左辺にzoがなくなったら、解が存在して終了となる。
それ以外は、4の移動で右辺に移動した変数(w[k]またはz[k])のwとzを入れ替えた変数を探索変数として3に戻る。
 (4で右辺に移動した変数がw[k]なら次の探索変数はz[k]、z[k]なら次の探索変数はw[k])

参考文献
Game Physics (Morgan Kaufmann Publishers )
Chapter7.2 THE LINEAR COMPLEMENTARITY PROBLEM

10 :名前は開発中のものです。:2006/06/08(木) 12:49:21 ID:7PH6zLFJ
1です。
プログラムを晒してみようと思うのですが、無料で置ける場所でよさげなところはございますか?

11 :名前は開発中のものです。:2006/06/08(木) 17:44:36 ID:XWRQu1aZ
http://gamdev.org/up/

12 :名前は開発中のものです。:2006/06/12(月) 12:29:28 ID:hbR+ePFA
内容をまとめて、プログラムと実行ファイルを置いてみました。

http://www17.plala.or.jp/lcpsolver/

人工変数に対応した後、2次計画問題のソルバーのプログラムを製作してみたいと思います。

2次計画問題は次のような問題について解こうと思っています。

条件
c-b >= Ax >= -b
x>=0

問題
|Ax+b|^2を最小化するxを求める

c,bは定数でベクトル、Aは定数で行列、xは未知数でベクトル

2次計画問題の日本語の良書がありましたら、どなたか教えてくださいませ。

13 :名前は開発中のものです。:2006/06/12(月) 20:49:13 ID:CBrfPEjZ
>>12
それってどんなゲーム?

14 :名前は開発中のものです。:2006/06/14(水) 10:23:18 ID:8c4i5cY9
ゲームではありませんが、剛体の物理の問題を解く場合に、必要となる計算です。

http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/SE.html

こちらのホームページの内容を参考に、共役勾配法で2次計画問題を解いてみようと思います。

15 :名前は開発中のものです。:2006/08/04(金) 16:43:45 ID:ay1u+h4s
拘束条件のある二次計画問題を解いてみました。

条件
c-b >= Ax >= -b
x>=0

問題
|Ax+b|^2を最小化するxを求める

c,bは定数でベクトル、Aは定数で行列、xは未知数でベクトル

アルゴリズムとプログラムを下記の場所に置きました。

http://www17.plala.or.jp/lcpsolver/

実戦に投入するには計算誤差の問題を片付ける必要があると思います。

デバッグがまだ不十分ですが、この方法で上の問題は解けると思います。

16 :名前は開発中のものです。:2006/08/13(日) 09:19:34 ID:XM0Vhk+x
日本語話してくれ。

6 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)