1

誰かが剰余算術で線形方程式を解くためのアルゴリズムを手伝ってくれませんか (!)。「最小」のソリューションだけが必要です。最小とは、辞書式順序が最初であることを意味します。

このシステムを考えてみましょう:
3x1+2x2=3
4x1+3x2+1x3+2x4=4
x の隣の数字はインデックスです。

モジュロ 5 を使用するこのシステムの行列 (0<=x<=p、p はモジュロ) は
3 2 0 0 0 |です。3
4 3 1 2 0 | 4

これに対する最小の解は (0,4,0,1,0) です。その解決策を提供するアルゴリズムを作成する必要があります。p<1000なので、ブルートフォースについて考えていました。しかし、この状況では、最初の行で x1=0 ... p-1 を解決し、次に x2 を解決する必要があるため、2 行目で x3= 0 ... p-1 を選択する必要があるため、方法はわかりません。そして x4 を解いてください。その連立方程式が成立するまでこれをしなければなりません。0 .. p-1 から行くと、最初に得られる解は最小の解になります。

PS:次のような行列の多くの形式があります:
3 2 4 0 0 | 3
4 3 1 2 1 | 4


1 2 0 0 0 | 3
3 0 3 0 0 | 3
4 3 1 2 3 | 4
等

英語で申し訳ありませんが、私はアジア出身です。

編集:どの変数がパラメーターであるかを判断する方法を考えていました。しかし、それを理解することはできません....

4

2 に答える 2

1

ああ、なんてこった、ほら、どうぞ

#include <stdio.h>

#define L 2
#define N 5
#define MOD 5

static int M[L][N] =
{       { 3, 2, 0, 0, 0 }
,       { 4, 3, 1, 2, 0 }
};

static int S[L] =
{       3, 4
};

static void init(int * s)
{
        int     i;
        for (i = 0; i < N; i++)
        {
                s[i] = 0;
        }
}

static int next(int * s)
{
        int     i, c;
        c = 1;
        for (i = N-1; i >= 0 && c > 0; i--)
        if ( (++s[i]) == MOD)
        {
                s[i] = 0;
        }
        else
        {
                c = 0;
        }
        return c == 0;
}

static int is_solution(int * s)
{
        int     i, j, sum;

        for (i = 0; i < L; i++)
        {
                sum = 0;
                for (j = 0; j < N; j++)
                {
                        sum += M[i][j]*s[j];
                }
                if (sum % MOD != S[i])
                {
                        return 0;
                }
        }
        return 1;
}

int main(void)
{
        int     s[N];

        init(s);
        do
        {
                if (is_solution(s))
                {
                        int     i;
                        for (i = 0; i < N; i++)
                        {
                                printf(" %d", s[i]);
                        }
                        printf("\n");
                        break;
                }
        } while (next(s));
        return 0;
}
于 2013-03-22T14:40:48.187 に答える
0

これは、線形代数およびガウス消去法 mod p の問題として扱うことができます。

Mx = y mod p の解を見つけようとしています。必要に応じて 0'x = 0 の行を追加して、正方形 M から始めます。ここで、ガウス消去 mod p を使用して、M を可能な限り上三角形式に縮小します。次のような連立方程式になります。

ax + by + cz = H

 dy + ez = G

ただし、方程式が不足しているか、すべての方程式の特定の列にゼロがあるため、対角線にいくつかのゼロがあります。0z = 1 またはそれに類するものがある場合、解決策はありません。そうでない場合は、通常どおりボトムアップで解いて、対角線上の z の係数がゼロでない方程式が残っていない場合は z=0 を入れることで、おそらく多くの解の 1 つを導き出すことができます。

最も重要な未知数がベクトルの底に対応する場合、辞書編集的に最小の答えが得られると思います。以下は、任意の解を辞書編集的に最小にする方法を示しています。上記のように生成された解は変更されないことがわかると思います。

http://en.wikipedia.org/wiki/Kernel_%28matrix%29を見てください。Mn = 0 となるベクトル n の線形空間があり、方程式のすべての解は x + n の形式になります。ここで、n はこの空間 (ゼロ空間) のベクトルであり、x は特定の解です。あなたが解決したものとして。

x を見つけたのと同じように、Mn = 0 の解を見つけることによって、ゼロ空間の基礎を見つけることができます。対角にゼロ以外のエントリがない列を見つけ、その列の対角があるべき行に移動し、その列の未知数を 1 に設定し、そこから行列を上に移動して、他の未知数を選択します。 Mn = 0 の解があるとします。

これから取得するすべてのベクトルには、そのベクトル内のある位置に 1 があり、そのベクトルの下に 0 があり、上にゼロ以外のエントリがある可能性があることに注意してください。これは、それらの倍数をソリューションに追加する場合、最も下が 1 つのベクトルから始めて、後のベクトルは常に下が 1 つのベクトルに追加したソリューションのコンポーネントを乱すことは決してないことを意味します。そこの。

したがって、辞書編集的に最小のソリューションを見つけたい場合は、最初に辞書編集的に最大のエントリを持つヌル スペースの基礎を使用するように調整できます。任意の解から始めて、可能な限りヌル空間ベクトルを辞書順に追加して、解ベクトルを減らします。最終的には辞書編集的に最小の解ベクトルになるはずです。ヌル空間からの基底ベクトルの組み合わせを追加することで、他の任意の解から任意の解を生成できます。上記の手順から、辞書編集的に最小のそのような結果が生成されることがわかります。各段階で、最も重要なコンポーネントは可能な限り小さくされており、代替は辞書的に大きくなければなりません。

于 2013-03-22T21:18:54.180 に答える