6

私は C# で (疑似個人的な使用のための) ソフトウェアを作成するアイデアをいじっていましたが、実装の問題に遭遇しました。うーん... 多分それらは私が気付いていない設計上の問題ですが、私は単に理解できません.

アイデア、期待、および一般的な疑似アルゴリズム

次の「データベース」があるとします。

Foo + Bar = Foobar
Baz + Qux = Bazqux
Foobar + Bazqux = Foobarbazqux

上記のアイテムを作成するためのレシピです。oneと oneを使用して、さらに別のレシピの材料となる結果を作成します。FooBarFoobar

ここで、アイテムの完全なレシピを把握する必要があると考えてくださいFoobarbazqux。人間の心と知性にとって、それは比較的簡単です。

We need Foobarbazqux
Foobarbazqux = Foobar + Bazqux
    Foobar = Foo + Bar
    Bazqux = Baz + Qux

Foobarbazqux = Foo + Bar + Baz + Qux

もちろん、すべての材料を自由に使用できる場合は、レシピを「実行」し、各レシピを数段落上の順序で実行してアイテムを作成できます。(つまり、最初に を作成しFoobar、次にを作成し、次にBazqux2 つを組み合わせて最終結果を取得します。)

しかし、リアルタイムでは、データベースははるかに大きくなります。そこで、コンピュータの出番だと思います。動作するソフトウェアがあれば、マシンはすべての構成要素と実行 (作成) ステップを簡単に見つけて、ユーザーに渡すことができます。手。

実装 (... 試行)

このソフトウェアを実現するために C# を使用することを考えました。コマンドライン プロジェクト、光沢も何もなく、純粋なstdio.

もちろん、最初にitemを定義する必要がありました。(注:今は構造体の使用を考えていますが、必要に応じてそれらをクラスに「アップグレード」できます。「データベース」は、後で作成される何らかのシーケンシャル テキスト ファイルから初期化されます。「データベース」は変更されません。または、実行中または実行後に任意の方法で記述され、ロードされると読み取り専用になります。)そしてもちろん、レシピを定義する必要がありました。

struct Item
{
    public string Name;
}

struct Recipe
{
    public Item Result;
    public Item[] Ingredients;
}

これら 2 つの構造体は、 (デフォルト クラス)の汎用static List<>フィールドに保持されます。Program

エントリ ポイントで、テスト用のいくつかのアイテムといくつかのレシピを定義します。

items.Add(new Item { Name = "Foo" });
items.Add(new Item { Name = "Bar" });
items.Add(new Item { Name = "Baz" });
items.Add(new Item { Name = "Qux" });
items.Add(new Item { Name = "Foobar" });
items.Add(new Item { Name = "Bazqux" });
items.Add(new Item { Name = "Foobarbazqux" });

recipes.Add(new Recipe
{
    Result = GetItem("Foobar"),
    Ingredients = new Item[] { GetItem("Foo"), GetItem("Bar") }
});

recipes.Add(new Recipe
{
    Result = GetItem("Bazqux"),
    Ingredients = new Item[] { GetItem("Baz"), GetItem("Qux") }
});

recipes.Add(new Recipe
{
    Result = GetItem("Foobarbazqux"),
    Ingredients = new Item[] { GetItem("Foobar"), GetItem("Bazqux") }
});

Name項目はフィールドによって主キーが設定されるため、GetItem単純なList.Find<>ショートカットです:

private static Item GetItem(string _name)
{
    return Program.Items.Find(match => match.Name == _name);
}

これで、データベースが設定されました。すべての成分を取得するには、ある種の再帰的な方法を作成する必要があることに気付きましたが、ここで問題が発生しました。

次の最初の試行を検討してください (これは再帰的ではなく、「1 レベルの深さ」でのみ行われます)。

string search = "Foobarbazqux";
SearchRecipe(search);

private static void SearchRecipe(string _search)
{
    List<Recipe> item_recipes = Program.Recipes.FindAll(match => match.result.Name == GetItem(search).Name);

    foreach (Recipe recp in item_recipes)
    {
        Console.WriteLine("-------------");
        Console.WriteLine("Ingredients: ");

        foreach (Item ingredient in recp.Ingredients)
        {
            Console.WriteLine(ingredient.Name);
        }
    }
}

これにより、次の出力が生成されます。これは、再帰がなければ、非常に適切で期待どおりです。

-------------
Ingredients:
Foobar
Bazqux

したがって、再帰のために、次のようにコードを変更しました。

    foreach (Item ingredient in recp.Ingredients)
    {
+++     if (recipes.FindAll(match2 => match2.Result.name == Ingredient.name).Count != 0)
+++     {
+++         SearchRecipe(ingredient.Name);
+++     }

        Console.WriteLine(ingredient.Name);
    }

出力は次のようになります。

| -------------
| Ingredients: 
* -------------
* Ingredients: 
* Foo
* Bar
| Foobar
@ -------------
@ Ingredients:
@ Baz
@ Qux
| Bazqux

今自分のコードを理解すると何が起こるかがわかります。でマークされた行*は の再帰でありFoobar、の@再帰でBazquxあり|、元のメソッド呼び出しの出力です。しかし、これは...私が実装したい出力ではありません。簡単に理解できず、...一般的に正しくないからです。

期待される出力と質問

私が視覚化した出力は次のようなものです (もちろん、「余分な」ステータス行は無視できます)。

Searching for: Foobarbazqux
1 recipe found.
-----
1 Foobarbazqux = 1 Foobar + 1 Bazqux
1 Foobar = 1 Foo + 1 Bar
1 Bazqux = 1 Baz + 1 Qux
1 Foobarbazqux = 1 Foo + 1 Bar + 1 Baz + 1 Qux

1 Foo + 1 Bar => 1 Foobar
1 Baz + 1 Qux => 1 Bazqux
1 Foobar + 1 Bazqux => 1 Foobarbazqux
-----
Exit.

これは、アイテム作成レシピのチェーンを分解するものとして私が呼んでいるものです... または... 私は とは呼びませんが、質問のタイトルを参照してそう想像してください。したがって、プログラムは次のように機能します。

  1. ユーザーが検索する「最終」アイテムFoobarbazquxを入力します (これはこの例です)
  2. プログラムはデータベースを十分な回数破壊するので、最初に検索されたアイテムの成分が見つかり、次に他の人から「作成」できない亜原子成分のみが見つかるまで再帰 (?)します。ResultRecipe
  3. （作業中）出力が表示されます。

注:実際のシナリオによりよく適合しますが、追加の実装のギャップが生じます: アイテムの多くには、それらを作成できる複数のレシピがあります。

お願いしたいのは、アドバイスとヘルプです。私はゆっくりと、このプログラムは書き込み不可能であり (これはある種の必死の抗議にすぎません)、私のアイデアには設計上の問題があることを自分自身に納得させたいと思っています。しかし、境界内で、この問題を解決するためにまだ作成されていない派手な AI システムが必要ないことを願っています...ちょっと過小評価されている問題です。

ありがとうございました。

4

3 に答える 3

1

2番目の答えは、「最初から書き直す」アプローチです。これは多かれ少なかれ、前のコードなしで問題のステートメントが与えられた場合に行う方法です。

abstract class Item
{
    public string Name { get; private set; }
    public abstract IEnumerable<Item> Ingredients { get; }
    public abstract IEnumerable<Item> ParseRecipe();

    protected Item(string name)
    {
        Name = name;
    }

    public static Item GetItem(string _name)
    {
        return items.Find(match => match.Name == _name);
    }
}

class Atom : Item
{
    public Atom(string name) : base(name) { }

    public override IEnumerable<Item> Ingredients { get { return null; } }
    public override IEnumerable<Item> ParseRecipe()
    {
        return new[] { this };
    }
}

class Recipe : Item
{
    public Recipe(string name, params Item[] ingredients) : base(name)
    {
        _ingredients = ingredients;
    }
    public Recipe(string name, params string[] ingredients) : base(name)
    {
        _ingredients = ingredients.Select(x => Item.GetItem(x));
    }
    private IEnumerable<Item> _ingredients;
    public override IEnumerable<Item> Ingredients { get { return _ingredients;} }
    public override IEnumerable<Item> ParseRecipe()
    {
        Console.WriteLine("1 " + this.Name + " = " 
                                 + String.Join(" + ", this.Ingredients.Select(x => "1 " + x.Name)));
        var components = new List<Item>();
        foreach(var ing in Ingredients)
        {
            components.AddRange(ing.ParseRecipe());
        }

        return components;
    } 
}

次のように使用します。

void Main()
{
    items.Add(new Atom("Foo"));
    items.Add(new Atom("Bar"));
    items.Add(new Atom("Baz"));
    items.Add(new Atom("Qux" ));
    items.Add(new Recipe("Foobar", "Foo", "Bar"));
    items.Add(new Recipe( "Bazqux", "Baz", "Qux" ));
    items.Add(new Recipe( "Foobarbazqux", "Foobar", "Bazqux" ));

    string search = "Foobarbazqux";
    var item = Item.GetItem(search);
    Console.WriteLine("1 " + item.Name + " = " 
                            + String.Join(" + ", item.ParseRecipe().Select(x => "1 " + x.Name)));

}

結果:

1 Foobarbazqux = 1 Foobar + 1 Bazqux
1 Foobar = 1 Foo + 1 Bar
1 Bazqux = 1 Baz + 1 Qux
1 Foobarbazqux = 1 Foo + 1 Bar + 1 Baz + 1 Qux

元のコードに対するこの方法の主な利点は、abstract class Item. Atomこれにより、初期化中の s とs の違いのみを気Recipeにします。その後、すべてが として扱われますItem。Ingredientsこれは、現在のアイテムがアトミック、レシピ、またはそれらの組み合わせであるかどうかを気にしないため、再帰がはるかに単純になることを意味します。SearchRecipe()また、それが実際にRecipe最初 のものであることを確認する必要なく、何でも呼び出すことができることも意味します。(この場合、出力を改善するために上記のコードを少し編集したことに注意してください。)

struct相互に継承できず、親型として扱うことができないため、これは aでは不可能です。両方とも実装する を宣言することはできますが、これにより、インターフェースにキャストすると、 a に対するメモリの利点のほとんどが失われます。これは常に行っています。interfacestruct

于 2013-01-17T15:29:20.523 に答える
0

解くときに、すべての材料=材料[]をメモリにロードします。それは私が思うにそれほど問題ではないはずです。

最初に頭に浮かぶのは、最短経路アルゴリズムが必要なことです。レシピは他の複数のレシピに分割できるため、おそらく最小数の材料を探して、それが確実に終了するようにします。

すべてのリーフをターゲットとして解決するダイクストラのアルゴリズムの標準的な実装は、私が推測すること（またはそれはバリエーションですか？）に対してうまく機能し、円を描いて実行しないようにします。

そして...あなたは私が思うにあなたが望む出力を生成するためにパスを使うことができます。

于 2013-01-17T14:43:53.370 に答える
0

全体的により良いデザインがあると確信していますが、必要な出力を生成するマイナーな変更を以下に示します (多かれ少なかれ):

public static IEnumerable<IEnumerable<Item>> SearchRecipe(string _search)
{
    List<Recipe> item_recipes = recipes.FindAll(match => match.Result.Name == Item.GetItem(_search).Name);

    var ingredients = new List<IEnumerable<Item>>();

    foreach (Recipe recp in item_recipes)
    {

        foreach (Item ingredient in recp.Ingredients)
        {
            if (recipes.FindAll(match2 => match2.Result.Name == ingredient.Name).Count != 0)
            {
                ingredients.Add(SearchRecipe(ingredient.Name).SelectMany(x => x));
            }
            else
            {
                ingredients.Add(new[] { ingredient });
            }
        }
        Console.WriteLine(recp.Result.Name + " = " + String.Join(" + ", ingredients.SelectMany(x => x.Select(y => y.Name))));
    }
    return ingredients;
}

プロデュース:

Foobar = Foo + Bar
Bazqux = Baz + Qux
Foobarbazqux = Foo + Bar + Baz + Qux
于 2013-01-17T15:06:14.687 に答える