初心者のFileMaker pro Q&A (旧掲示板)

msk

Member

ナップサック問題について

いつもお世話になっております。

mac osx FM12 advanceを使用しています。

業務の中で計算して計算結果の最適化を考えています。
MAX = 120の時、右の数列｛22,22.15,15,8,8,40,40,33,33,21,21,48,48,14,14｝の中で
MAX以下で、MAXに近くなる、最適な組み合わせを求めたくてweb上で検索したところ、
ナップサック問題を利用すれば求める解が得られるとは思うのですが、filemaker上でどのような計算式を書けばいいかわかりません。

どなたかご教授よろしくお願いいたします。

Shin

Member

Re: ナップサック問題について

複合条件での最適化ではないので、3^8 通り（約6400）を全例を計算させてしまってもいいのでは。（汎用のものは後日）
処理は3-4分で終わりましたよ。
https://www.dropbox.com/s/1udr7pskbi6sx … 7.zip?dl=0

ナップザック問題のを動的計画で求めるアルゴリズムの式もありますが、公開されているものは、数と価値を最適化するものですので、すこし方向が違います。

計算させてちょっとびっくりしたのですが、120 ぴったりの組み合わせが 21 もあるのですね。

Last edited by Shin (2019-02-12 13:36:52)

wader

Member

Re: ナップサック問題について

単純な計算式で解が得られるようなものではないでしょう。

データの数が少ないので、MAX/最大値～MAX/最小値の個数の全組み合わせを生成してチェックすればできるかな。

Hiro

Member

Re: ナップサック問題について

Shinさんの解析アイデアをベースにお借りして、
>#1『MAX以下で、MAXに近くなる、最適な組合せ一覧を求たい』に、
ボタン一発で応えるサンプルをアップしましたので、ご覧ください。

●サンプル「単次元ナップザック問題.fmp12」 → https://yahoo.jp/box/adT-qN

【デモ画面】

Shin

Member

Re: ナップサック問題について

数列の解析を行う、汎用性の高いものです。候補数は、繰り返し数を変更すれば、数十くらいまでは実用的に増やせます。（展開した全レコード数次第かな）
最終結果は、上限以下のものを抽出して、降べきでソートしてあります。
https://www.dropbox.com/s/1udr7pskbi6sx … 7.zip?dl=0

Last edited by Shin (2019-02-12 15:15:48)

msk

Member

Re: ナップサック問題について

お世話になっております。
Shinさん、Hiroさん、waderさんありがとうございます。
作成していただいたデータ大変勉強になります！

MAX = 120の時、右の数列｛22,22.15,15,8,8,40,40,33,33,21,21,48,48,14,14｝の中で
MAX以下で、MAXに近くなる、最適な組み合わせを求めたくて・・・

と書いたのですが・・・条件が間違っていました。
内容としては、「ナップサック問題×」「ビンパッキング問題○」でして・・・
組み合わせた条件が減っていかないといけない場合はどのようにしたらいいでしょうか？

すみません。よろしくお願いします。

Shin

Member

Re: ナップサック問題について

ビンパッキングは、総当たりするしか無いです。ある程度当たりをつけてから当たっていくのがいいでしょう。
総計が602ですから、おそらく6でしょうね。
私のサンプルで、数を引いていって繰り返せばいいでしょうが、結構時間はかかるでしょう。

msk

Member

Re: ナップサック問題について

Shinさんありがとうございます。
総当たりは時間がかかりすぎるので、マンパワーでやろうと思います。
みなさんありがとうございました。

Hiro

Member

Re: ナップサック問題について

>#8『マンパワーでやろうと思います。』
それは大変過ぎる力業で、非現実的でしょう。
それならば、後で別途一般公開しようと思っていた「ビンパッキング問題解析」
テンプレートを急遽 先出でアップしますので、利用ください。

●テンプレート『ビンパッキング問題解析.fmp12』 → https://yahoo.jp/box/_-Yi0A

ビンパッキング問題は総当たり以外、絶対正解を得る方法はありませんが、
絶対保証は無いものの近似解なら、効率的なアルゴリズムが幾つか紹介されています。
テンプレートでは、絶対解が担保されない対策として、最善の３つの解を提示します。
   解１．論理的にこれ以下は絶対にあり得ないという単純計算ビン数（単純計算で直ぐ出る）
   解２．小さい荷物から順に、空きの大きなビンに先入れ
   解３．大きな荷物から順に、空きの小さなビンに先入れ
この3つの解から最善解答を比較検討できるようにしてあります。

【デモ画面】

Shin

Member

Re: ナップサック問題について

最初から気になっていたのですが、22.15 は、正しいですか。それとも 22,15 ですか。

総当り、と言っても、全部の組み合わせは数千ですが、実際に候補となるものは1500ほどです。
第1の候補を決めた後は、使った品物をみて候補はさらに絞れるので、ある程度の自動処理は可能で、この例のようなゆるい正解ですと、最後まで自動でいけると思います。
例えば、総計600で120×5に、という問題ですと、少し人手をかりないといけないかもしれません。（それでも、人手より計算させた方が早いと思いますが）

Hiro

Member

Re: ナップサック問題について

>#10『総当り、と言っても、全部の組み合わせは数千ですが、実際に候補となるものは1500ほどです。』

うむ！
例示16個の数列の順列組合せ総数は、20,922,789,888,000 組では？
なので『非現実的！』かと？

そのため、あるルール（アルゴリズム）を決めて、サンプル検査で対処する以外ないのでは？
テンプレートの場合で安定的に成績の良いアルゴリズムは、

●アルゴリズム降順(最も空きが少ないビンに重い荷物から詰めてゆく解法）
・荷物の総量を求め、最低限必要な数のビンを用意する。（例示数列の場合４本）
・荷物を重い順に並び変える。
・荷物を空いている容量が最小のビンに詰める。
・どのビンにも荷物が入らないとき、新しいビンに詰める。

Last edited by Hiro (2019-02-25 13:53:08)

Shin

Member

Re: ナップサック問題について

いや、書き方が悪かったです。総当たりの対象となる元になる組み合わせ、です。その1500から6個を選び出すのですよね。

himanine

Guest

Re: ナップサック問題について

わざわざ同じ数字を2個ずつ並べた例を出しているというのは、22.15ではなく22,15なんだと思いますが、
2個ずつ8種類で16個を詰める、というのが前提条件としてあるんでしょうかね？
（それだったらいい方法がある、というわけではないんですが＾＾；組み合わせ数はランダムに16個より大幅に減りますよね）

msk

Member

Re: ナップサック問題について

>最初から気になっていたのですが、22.15 は、正しいですか。それとも 22,15 ですか。
後者の22,15でした。

昨年はこのスレを確認していませんで、返信していませんでした。申し訳ありません。
本日確認してところ、HIROさんのテンプレートは、まさに私が想像していた方法と、処理がなされていました。大変勉強になりました。ありがとうございます。
また、Shinさんhimanineさんありがとうございました。