6

数理（最適化）問題の記述を取り込んで解析し、それを解決するコンパクトで効率的なCコードを生成するプログラムを書きたいと思います。私はPythonで、はるかに小さく、より具体的な問題に対するハックアップされたソリューションを持っていますが、それは醜く、Cコードのテンプレートに依存しているだけです-したがって、次のような文字列の混乱があります

for (k = 0; k <= %s; k += %s) a[k] = v[k]/%s * a[i];

そして、複雑な条件付きロジックの混乱があり、ある時点で、％sの正しい値を入力した後、上記の行がsolve_problem.cに書き込まれます。

通常、問題は特定の構造などの行列によってパラメータ化されるため、実際にははるかに複雑になります。上記のアプローチは実行可能ですが、自重で崩壊し始めています。

ですから、私が探しているのは、この種の問題をコードで表現する方法に関する高レベルのアドバイス、またはこれが解決された他のプロジェクトの単なる例だと思います。誰かがOCamlまたはF＃を使用してFFTWを見るように私に言いましたが、もっと簡単なものをいただければ幸いです。

はっきりしないのが残念ですが、自分が探しているものを自分自身に表現することすら難しいのです。それが問題の根源だと思います。

4

5 に答える 5

8 
for (k = 0; k <= %s; k += %s) a[k] = v[k]/%s * a[i];

上記のようなコードを表現する方法を求めています。これは、次の値で表すことができます。

For("k", Int 0, Leq(Var "k", a), Set("k", Add(Var "k", b)),
    SetElt(Var "a", Var "k",
           Mul(Div(GetElt(Var "v", Var "k"), c, GetElt(Var "a", Var "i")))))

次のようなタイプが与えられます：

type Expr =
  | Int of int
  | Var of string
  | Leq of Expr * Expr
  | Mul of Expr * Expr
  | Div of Expr * Expr
  | Set of string * Expr
  | SetElt of Expr * Expr * Expr
  | GetElt of Expr * Expr
  | For of string * Expr * Expr * Expr

HLVMと呼ばれる非常に単純な高レベルのVMを作成しました。これは、そのような表現を単純な方法で使用するため、啓蒙的であると思われるかもしれません。定義はここにあり、それらの定義を使用して書かれた一連のテストはここにあります。

Exprこの表現は、パターンマッチコンパイラが網羅性と冗長性のチェックを行い、最適化パスやコードジェネレータなど、このタイプの値に対して関数を簡単に記述できるため、文字列の変更よりもはるかに強力です。

于 2012-11-05T11:16:50.557 に答える
3

あなたはコンパイラを実装しようとしています、そしてこれはあなたがあなたの問題に取り組むべき方法です。最適化問題を説明する入力言語があり、出力言語はCです。

問題を次のタスクに分割できます（必ずしもこの順序で解決されるとは限りません）。

  1. 入力言語の抽象構文を表すデータ構造を設計します。
  2. 出力言語（この場合はC（のサブセット））の抽象構文を表すデータ構造を設計します。
  3. 入力言語の具体的な構文を設計します。
  4. 具体的な構文を抽象構文に変換するレクサーとパーサーを実装します。
  5. 出力言語の抽象構文を具体的な構文に変換するきれいなプリンターを実装します。
  6. 抽象構文で表現された最適化問題を、再び抽象構文で表現された出力に取り込むコンパイラを実装します。

言語やコンパイラの実装に慣れていない場合は、ショートカットを使用したくなるでしょう。たとえば、正規表現を使用して解析することを検討できます。または、抽象構文をスキップして、Cソースを直接生成することをお勧めします。これには強くお勧めします。抽象化はあなたの問題を管理しやすくするのであなたの友達です。

すべてを実装する言語を慎重に選択する必要があります。もちろん、Ocamlのようなものは仕事に最適です。しかし、Ocamlをまだ知らない場合は、最も使いやすい言語に固執する必要があります。パーサーを手動で実装しようとしないでください。パーサージェネレーターはたくさんあります。学ぶ価値があります。私のPL動物園がお役に立てば幸いです。

于 2012-11-03T02:41:54.207 に答える
2

あなたが最適化にどれだけのバックグラウンドを持っているかはわかりませんが、あなたが説明した道が進むべき道であるとは思えません。具体的には、特定のクラスの問題に制限されていない限り、最適化問題を解決するための効率的なCコードを記述できれば驚きます。最適化は通常、さまざまなタイプの問題（線形対非線形、整数対連続対混合整数計画法）を区別します。これらの問題は通常、ソリューションを解決するために非常に異なるアルゴリズムを使用します。

いくつかのアイデアについては、 MicrosoftSolverFoundationを調べてください。基本的に、MSFは一般的なAPIであり、問​​題を複数の形式（OML、最適化問題を指定するための宣言型言語、C＃およびF＃）で宣言し、その性質に応じて問題を適切なソルバーにフィードできます。問題の。

于 2012-11-03T00:17:55.900 に答える
1

より単純なことについてのDunno。数学的モデリングの既存の作業を確認することをお勧めします。これが単純だとは思いません。ソルバーコードは十分に難しく、それらを生成することはより困難です。

問題の詳細を指定する方法と、これらの詳細によって制御される回答の部分を組み立てる方法が必要です。

私はお勧め：

Sinapse、数学的モデリングコードを生成するためのシステム。このペーパーでは、知識がどのように編成され、有限差分コードの生成をサポートするかについて説明します。

と

有限差分方程式を解く、同じ静脈のMIT論文。

（私はSinapseシステムの初期開発中に作業しました）。

于 2012-11-02T21:41:19.177 に答える
1

記号計算のようなものが必要なようです。次のようないくつかの実装を調べてください。

一般に、最適化パッケージを見てみてください。多くは、ある種のシンボリック表現をサポートしています。

于 2012-11-02T22:18:27.480 に答える