2

編集: 「シマウマの所有者」をプログラムで解決するを参照してください。同様のクラスの問題に対して

LSAT には、次のような論理問題のカテゴリがあります。

時系列順に I から 7 までの番号が付けられた放送の 7 つの連続したタイムスロットは、G、H、L、O、P、S の 6 つの歌のテープと、ちょうど 1 つのニュース テープで埋められます。各テープは異なるタイム スロットに割り当てられ、どのテープよりも長いテープはありません。ブロードキャストには次の制限が
あります。L は O の直前に再生する必要があります。
ニュース テープは L の少し後に再生する必要
があります。 G は P の後に来ます。

テストの勉強方法として、またプログラミングの課題として、条件を満たす順列のリストを生成することに興味があります。ただし、これがどのクラスの順列問題であるかはわかりません。型の問題を次のように一般化しました。

長さ n の配列 A が与えられた場合:

  1. n 個の一意のアイテムのセットを A 内に配置する方法は何通りありますか? 例えば。ABCDEFG を並べ替える方法はいくつありますか?
  2. 一意のアイテムのセットの長さが A の長さよりも短い場合、セット内のアイテムが複数回出現する可能性がある場合、セットを A 内に配置できる方法はいくつありますか? 例えば。ABCDEF => AABCDEF; ABBCDEFなど
  3. セットの項目が「ブロッキング条件」の対象である場合、一意の項目のセットを A 内に配置できる方法はいくつありますか?

私の考えは、制限をエンコードしてから、Python の itertools のようなものを使用して順列を生成することです。考えや提案は大歓迎です。

4

2 に答える 2

1

これは、整数プログラムとして (数行のコードで) 簡単に解決できます。GNU Linear Programming Kitのようなツールを使用して、宣言的な方法で制約を指定し、ソルバーに最適なソリューションを考え出させます。GLPKプログラムの例を次に示します。

Python のような汎用プログラミング言語を使用してこれをコーディングすることもできますが、これは整数プログラミングの教科書の最初の数章で見られるタイプのものです。最も効率的なアルゴリズムは、他の人によってすでに解決されています。

編集：Merjitの質問に答えるには：

定義：

  1. 行列 Y ここで、テープ i がテープ j の前に再生される場合は Y_(ij) = 1、それ以外の場合は 0 です。
  2. ベクトル C、ここで C_i は i が再生されるタイムスロットを示します (例: 1,2,3,4,5,6,7)
  3. 大きな定数 M (最適化の教科書で「大きな M」の用語を調べてください)

次の制約に従って、ベクトル C の合計を最小化します。

Y_(ij) != Y_(ji) // If i is before j, then j must not be before i
C_j < C_k + M*Y_(kj) // the time slot of j is greater than the time slot of k only if Y_(kj) = 1
C_O - C_L = 1 // L must be played immediately before O
C_N > C_L // news tape must be played at some time after L
|C_G - C_P| = 2 // You will need to manipulate this a bit to make it a linear constraint

それはあなたをそこに連れて行くはずです。上記の制約を MathProg 言語の構文 (リンクに示されているように) に記述し、制約を省略していないことを確認します。次に、制約に対して GLPK ソルバーを実行し、結果を確認します。

于 2010-04-25T09:04:35.533 に答える
0

さて、私の見方では、この問題に取り組むには 2 つの方法があります。

  1. この問題に真っ先に取り組むプログラムを書き始めてください。これは難しいでしょう。

  2. しかし、組み合わせ論は、これを行うより簡単な方法は、すべての順列を数え、制約を満たさない順列を差し引くことだと教えてくれます。

私は番号2で行きます。

このアルゴリズムを使用して、特定の文字列またはリストのすべての順列を見つけることができます。このアルゴリズムを使用すると、すべての順列のリストを取得できます。問題のさまざまな制約をチェックすることで、このリストにいくつかのフィルターを適用できるようになりました。

def L_before_O(s):
    return (s.index('L') - s.index('O') == 1)

def N_after_L(s):
    return (s.index('L') < s.index('N'))

def G_and_P(s):
    return (abs(s.index('G') - s.index('P')) == 2)

def all_perms(s):    #this is from the link
    if len(s) <=1:
        yield s
    else:
        for perm in all_perms(s[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + s[0:1] + perm[i:]

def get_the_answer():
    permutations = [i for i in all_perms('GHLOPSN')] #N is the news tape
    a = [i for i in permutations if L_before_O(i)]
    b = [i for i in a if N_after_L(i)]
    c = [i for i in b if G_and_P(i)]
    return c

私はこれをテストしていませんが、これはそのような質問をどのようにコーディングするかについての一般的な考えです。

お役に立てれば

于 2010-04-25T08:56:13.120 に答える