投資家とプール -

Question

をバックトラックは、私はバックトラックの概念をより深く学ぶことを決めたと私は、タスク次き：

考えるとNの投資家、Mの都市、N投資家の好みのM行列Pによって（P [I、J P [i、j] = 0、P [i、j] = -1のときはニュートラルであり、受諾レベルL（与えられた場所の選択肢については、投資家の嗜好の合計がL以上であれば、彼は確信していると考える）。確かめることができる投資家の最大数とプールを建設すべき都市を探しましょう。

私はバックトラックを使用しようとしましたが、それ以上の最適化が可能かどうかは疑問です。今のところ、各回帰レベルでは、どれくらいの人が確信できるかを把握しています。この数字が現在の最大値以下であれば、私は戻ってきます（良い答えはありません）。

Answer 1

これはあなたが探しているものかどうかは分かりませんが、ちょっとしたトリックで、整数リニアプログラム（ILP）として問題を表現できます。次に、整数線形計画法ソルバ（たとえばGLPK）を使用して最適解を見つけることができます。

はs[i]は0-1整数変数（投資家の上に及ぶi）、および都市の上に及ぶc[j] 0-1整数変数とするとKは多数（L + the number of investorsが行います）こと。

次に、それぞれi、sum(P[i, j]*c[j]) + s[i] * K >= Lのように、sum(s[i])を最小にすることが問題です。最適解でのsum(s[i])の値は不満投資家の数であり、c[j]は都市にプールを構築するかどうかを示しますj。

この問題の定式化は、ILPの標準的な形式になっています。