3

グリッド (10x10) があり、それを 0 から 99 までの数列で埋めたいとします。いくつかの条件は次のとおりです。

  1. シーケンス内の各番号は、グリッドに 1 回だけ表示される必要があります。
  2. (シーケンスからの) 各番号の配置は、ランダム (x、y 座標) にする必要があります。
  3. シーケンスの後続の番号 (5 と 6 など) は、互いに隣接する (または半径内にある) グリッドに表示できません。

条件 1 と 2 は問題なく処理できます。条件3は（私にとって）難しいです。ブルートフォースを使用してグリッドを埋めましたが、これにはいくつかの問題があります。まず、グリッドが大きい (100x100) と遅くなります。第 2 に (そして最も重要なことに)、総当りは解を保証しません (つまり、シーケンスの最後の 2 つの数字は互いに隣接しているため、許可されません -> 解はありません)。

誰かが適切なアルゴリズム（またはいくつかの数学/論理リソース）で私を助けることができれば、それは役に立ちます。解決策を提供できる場合、理想的には条件 3 を定義できるようにする必要があります (つまり、ユーザー/コーダーが、隣接する数値が表示されない半径を決定します)。最後に、ラップアラウンドの問題はありません (つまり、行の最後の列に数値 5 がある場合、次の行の最初の列に 6 が表示される可能性があります)。

たくさんの言葉がありますが、これは現実世界の必要性 (ニューロンの「ランダムな」光励起) を伴うかなりクールな問題だと思います。

よろしくお願いします。

ピート

4

4 に答える 4

3

各セルにランダムな有効な数値を入れる再帰的なバックトラッキング アルゴリズムを使用できます。有効なセルがない場合は、バックトラックして前のセルの別の番号を選択します。列挙子メソッドを使用すると、バックトラッキング システムを簡単に構築できます。

class Generator
{
    public int Width { get; private set; }
    public int Height { get; private set; }
    public int Radius { get; private set; }

    private List<int> _numbers;
    private bool[] _picked;
    private int[] _grid;
    private Random _rnd;

    public Generator(int width, int height, int radius)
    {
        Width = width;
        Height = height;
        Radius = radius;

        _rnd = new Random();
        _numbers = Enumerable.Range(0,Width*Height).OrderBy(_ => _rnd.Next()).ToList();
        _picked = _numbers.Select(n => false).ToArray();
        _grid = new int[width*height];
    }

    public int[] Generate()
    {
        return Generate(0)
            .Select(a => a.ToArray()) // copy
            .FirstOrDefault();
    }

    private IEnumerable<int[]> Generate(int index)
    {
        if (index >= Width * Height)
        {
            yield return _grid;
            yield break;
        }

        int xmid = index%Width;
        int xlow = Math.Max(0, xmid - Radius);
        int xhigh = Math.Min(xmid + Radius, Width - 1);
        int ymid = index/Width;
        int ylow = Math.Max(0, ymid - Radius);
        int yhigh = ymid;

        var validNumbers = _numbers
            .Where(n =>
                !_picked[n] &&
                Enumerable.Range(xlow, xhigh - xlow + 1).All(x =>
                    Enumerable.Range(ylow, yhigh-ylow+1).All(y =>
                        y*Width + x >= index // Not generated yet
                        || Math.Abs(x - xmid) + Math.Abs(y - ymid) > Radius // Outside radius
                        || Math.Abs(_grid[y*Width+x] - n) > 1 // Out of range
                    )
                )
            )
            .ToList();

        foreach (var n in validNumbers)
        {
            _grid[index] = n;
            _picked[n] = true;
            foreach (var sol in Generate(index + 1))
            {
                yield return sol;
            }
            _picked[n] = false;
        }
    }
}

50 ミリ秒で生成された半径 4 の 10x10 グリッド:

74   6  72   1  82  64  41  66  96  17 
61  24  12  93  35  86  52  19  47  10 
42  48  69  45  79  88  31  43  28  36 
15  38   4  40  54  33  13   7  90  68 
34  67  62  83  99  59  50  22  73  77 
44  18   0   8  20  81  26  37  98  87 
29  71  58  75  14  65  55  85  57  80 
84  32  91  25   5  78  95   9   2  53 
60  23  11  63  49  39  70  89  27  46 
97  16   3  30  56  92  76  51  21  94

多くの場合、それは迅速で、1 秒以内に完了します。場合によっては、最初は悪い選択をし、何度も後戻りしなければならないこともあります。

于 2013-06-14T07:44:42.100 に答える
0

私はグリッドをすばやく埋めます (塊を避けようとしますが、頑張りすぎないようにします)。グリッドがいっぱいになると、まとまった数字を見つけて移動します。後戻りはありません。このアプローチは、非常に大きなグリッドに対して非常に効果的です。

最初のフェーズの疑似コード:

int N = 100;
int minDistance = 10;
int maxCollisionCount = 5;
int saturationThreshold = N * N * 0.85;

grid[0,0] = 1;
int oldX = 0, oldY = 0;
int newX, newY;

for (i = 2; i <= N * N; i++)
{
    bool foundNewCell = false;

    for (collisionCount = 0; collisionCount < maxCollisionCount; collisionCount++)
    {
        newX = rnd(0, N - minDistance);
        if (newX >= oldX - minDistance / 2)
            newX += minDistance;

        newY = rnd(0, N - minDistance);
        if (newY >= oldY - minDistance / 2)
            newY += minDistance;

        if (grid[newX, newY] == 0)
        {
            grid[oldX = newX, oldY = newY] = i;
            foundNewCell = true;
            break;
        }

        if (i > saturationThreshold)
            break;
    }

    if (foundNewCell)
        continue;

    // Find newX and newY by some other way, even if there would be clumping.
    // For instance use already randomed newX and newY and circle around until
    // you find an empty cell
    ...

    grid[oldX = newX, oldY = newY] = i;
}
于 2013-06-14T09:19:14.133 に答える
0

これは、私がゲーム用のスター フィールドを生成するために使用したアルゴリズムのように思えます。デカルト平面上に配置された特定の次元の銀河と、必要な数の星がありました。星は同じ場所を占めることも、互いに n 単位で一緒にいることもできません。私はいくつかのものを盗みましたが、これは役立つはずです。

        for (int i = 0; i < u.StarCount; i++)
        {
            bool badStar = true;  //Assume failure
            do
            {
                //Create a star, get a random location, and where the rarity of its spectral type
                StellarBody sb = new StellarBody();
                sb.PositionX = r.Next(0, u.width);
                sb.PositionY = r.Next(0, u.height);
                int randomAbundance = r.Next(maxAbundance);

                //Test the location against previous stars added, disallow positions where the centers are within 8 units of one another
                if (!u.StellarBodies.Any(p => Math.Abs(p.PositionX.Value - sb.PositionX.Value) < minGap && Math.Abs(p.PositionY.Value - sb.PositionY.Value) < minGap))
                {
                    //Get the spectral types based on the abundance value of the spectral types compared to the random abundance number
                    List<Models.StellarClass> abundanceTypes = starTypes.FindAll(f => f.Abundance == starTypes.Where(p => p.Abundance > randomAbundance).Min(m => m.Abundance));

                    try
                    {
                        int index = r.Next(0, abundanceTypes.Count());
                        sb.StellarClassID = abundanceTypes[index].StellarClassID;                            
                        sb.CatalogDesignation = index.ToString() + u.StellarBodies.Count.ToString()
                                                + abundanceTypes[index].Code + "-" + CoordinateMath.GetMortonNumber((int)sb.PositionX, (int)sb.PositionY).ToString();

                        minOrbit = abundanceTypes[index].MinOrbitZone;
                        maxOrbit = abundanceTypes[index].MaxOrbitZone;
                    }
                    catch (Exception ex)
                    {
                        sb.StellarClassID = starTypes.First(p => p.Code.Equals("Dork", StringComparison.CurrentCultureIgnoreCase)).StellarClassID;
                    }


                    u.StellarBodies.Add(sb);
                    badStar = false;
                }
            } while (badStar);
        }
于 2013-06-14T01:45:13.580 に答える