要素数を最大化するような組合せ最適化問題(線形計画問題)を解こうとしていますが、
要素数を一度に計算したり、ソートしたりすることはできません。
(そのような関数を線形式で定義するのは難しいと思いますので。)
一方、2つの要素が同一かどうかのみの計算は簡単にできるので、
全ての2要素間で一致/不一致を判断し、不一致の数が最大となるように目的関数を設定して、この問題を解こうかと思っています。
この方法は正しいでしょうか。
例えば、
ある変数の組合せにおいて、
A1=X, A2=Y, A3=X
といった結果になるとすると、
bin1=|A1-A2|(=1、不一致)
bin2=|A1-A3|(=0、一致)
bin3=|A2-A3|(=1、不一致)
という風に要素の一致/不一致を計算し、
不一致数(=bin1+bin2+bin3)を最大化するという風に目的関数を定義しようかと思っています。
当然、不一致数と要素数は一致しないわけですが、
不一致数が最大のときに、必ず要素数が最大となるのであれば、
目的関数として問題ないと考えています。
なんとなく正しい気もしますが、本当に正しいのかよくわかりません。
よろしくお願いします。
A 回答 (2件)
- 最新から表示
- 回答順に表示
No.2
- 回答日時:
一応補足を受けたので追加しますが、
まず、目的はなんなのか、問題は何なのかがはっきりしてないのでなんとも言えません。
どうしても線形計画問題として解きたいならその形式で問題を記述する必要があります。
少なくともあなたの書いている式は日本語の内容との兼ね合いが理解できません。
あなたが理解しているならそれで良いしやってみれば良いと思いますが、他人に理解させたいなら明確な形での記述をお願いします。
ちなみに、手段を問わないならバブルソートもどきでやれますね。
第一要素に一つめの値を入れる。次の要素を比較して大きければ後ろに、小さければ全体をずらして入れる、同じ値なら何もせず終了。
これをクイックソートもどきでやればオーダーは nlognでしょう。
まあ、規模が小さいならオーダーは気にしないでいいです。
とりあえず、問題を共有できる状態にして下さい。
No.1
- 回答日時:
とりあえず、問題をわかりやすく説明したほうがいいと思います。
制限だけ書かれてもちょっと困ります。
>要素数を一度に計算したり、ソートしたりすることはできません。
>(そのような関数を線形式で定義するのは難しいと思いますので。)
私はそのように思いません。そうなるような条件があるのかも分かりませんし。
あと、数式を書いていますが、多分間違っていますよ。
線形計画問題と言うものを取り違えて解釈しているのではないでしょうか。
とりあえず、多数の整数要素があって、それらの値がかぶらない最大の要素数と言うことであれば、アホなやり方でもn^2のオーダーで出せるでしょう。
内容的にはLPじゃなくてソートの問題に見えます。
なので、一旦内容を整理して欲しいです。
私が無知で理解できていないのであれば反省致します。
この回答への補足
説明不足ですみません。
今回の問題は線形計画問題でないかもしれませんが、
線形計画問題に落とし込めないかということを考えています。
背景として、
CPLEXを使って評価したいが、
CPLEXではif文などの条件式などが恐らく使えないからです。
ご指摘の通り、問題自体は、
ソートのアルゴリズムと関連がありそうな気はするのですが、if文を使わずに記述する方法がわかりませんでした。
この辺りも勉強不足かもしれません。
私が検討している方法もオーダーはn^2になりますので、
アホな方法だということはわかっているのですが、
検討している目的関数の設定が正しければ、
式の記述は簡単にできるのでうれしいわけです。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
0から1になった時の増加率を教...
-
不定積分の答えをどこまで出す...
-
任意定数を消去して微分方程式...
-
ちなみに、画像の赤い下線部の...
-
1/3乗などの計算方法
-
9X2乗-6X+1 はどうやった...
-
改良土のCBR
-
また線形代数なのですが
-
1/1+1/2+1/3+...+1/100
-
y=xを回転軸とする回転体の体積...
-
(X^2+1/3x)^8の展開式におけるx...
-
教えてください。
-
中学数学 a※b=1/3(a+b)とする...
-
数学1の問題について
-
時定数の計算を教えてください
-
逆関数の求め方
-
2の6乗の答えと計算方法
-
電卓の使い方 乗数はどうした...
-
15%増しの計算方法
-
積分で1/x^2 はどうなるのでし...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報