我一直在C#中考虑创建一个软件(用于伪个人用途(的想法，但遇到了实现问题。好也许它们是我不知道的设计问题，但我就是搞不清楚。
概念、期望和一般伪算法
假设我们有以下"数据库"：
Foo + Bar = Foobar
Baz + Qux = Bazqux
Foobar + Bazqux = Foobarbazqux
这些是配方，用于创建所述项目。使用一个Foo和一个Bar，我们创建了Foobar结果，它可以进一步成为另一个配方的成分。
现在想想，我们需要找出Foobarbazqux项目的完整配方。对于人类的心智和智力来说，这相对容易：
We need Foobarbazqux
Foobarbazqux = Foobar + Bazqux
Foobar = Foo + Bar
Bazqux = Baz + Qux
Foobarbazqux = Foo + Bar + Baz + Qux
当然，如果我们拥有所有成分，我们可以"运行">配方并按照上面几段的顺序执行每个食谱来创建项目。(就像：我们首先创建Foobar，然后创建Bazqux，然后将两者结合以获得最终结果。(
但在实时情况下，数据库要大很多。我想，这就是计算机应该发挥作用的地方。有了一个可工作的软件，机器可以很容易地找到所有的成分和执行(手工制作(步骤，并将其提供给用户，所以我们不需要手动阅读all条目。
实施(…尝试(
我曾考虑过使用C#来实现这一软件。命令行项目，没有任何闪亮的东西，只是纯粹的stdio。
当然，首先，我需要定义项。(注意：现在我考虑使用structs，但如果需要，我可以将它们"升级"为类。"数据库"是从稍后创建的某种顺序文本文件初始化的。"数据库"在执行过程中或执行后不会以任何方式更改或写入，一旦加载，它就是只读的。(当然，我需要定义配方。
struct Item
{
public string Name;
}
struct Recipe
{
public Item Result;
public Item[] Ingredients;
}
这两个结构保存在Program(默认类(的通用static List<>字段中。
在入口点，我们定义了一些项目和一些测试配方：
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);
}
所以现在，数据库已经设置好了。我已经意识到我需要做一些递归方法来获取所有的成分，但这就是我遇到问题的地方。
考虑以下第一次尝试(这不是递归的，只进行"一级深度"(：
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.
这就是我所说的分解物品创建链食谱。。。或我不调用，但想象一下是这样的，参考问题的标题。因此该程序的工作方式为：
- 用户输入他们正在搜索的"最终">项目(在我们的示例中，这是
Foobarbazqux( - 该程序破坏数据库的次数足够多，因此首先找到搜索到的项目的components，然后它更深入地递归(？(，直到它只找到无法从其他项目"精心制作"的亚原子components：它们不是任何
Recipe的Result - (在这样工作时(显示输出
注意：更适合真实场景，但会造成额外的实现差距：许多项目都有多个可以创建它们的食谱。
我想向寻求的是建议和帮助。我慢慢地想说服自己，这个程序是不可写的(这只是某种绝望的抗议(，我的想法有设计的问题。但我仍然希望，在边界内，我们不需要花哨的、尚未创建的人工智能系统来解决这个问题。。。有点被低估了。
谢谢。
第二个答案，针对"从头开始重写"方法。如果只是给出没有先前代码的问题语句，我或多或少会这样做。
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和Recipe s之间的差异。之后，所有内容都被视为Item。这意味着递归变得简单得多，因为我们不在乎当前项的Ingredients是原子的、recipies还是它们的混合。这也意味着您可以在任何事情上调用SearchRecipe()，而无需首先检查它是否是Recipe(注意，在这种情况下，为了更好地输出，我稍微编辑了上面的代码。(
对于struct，这是不可能的，因为它们不能相互继承，因此不能被视为父类型。您可以声明一个它们都将实现的interface，但根据这一点，当您将其强制转换到接口时，struct将失去大部分内存优势，而我们一直在这样做。
在求解时，我会将所有component=component[]加载到内存中。我认为这应该不是什么大问题。
首先想到的是，你需要一个最短路径算法：由于一个食谱可以分为多个其他食谱，你可能正在寻找数量最少的食材，并希望确保它完成。
Dijkstra算法的标准实现将所有叶子都作为目标来解决，我想这会很好(或者这是一种变体？(，也会确保你不会绕圈跑。
然后。。。我想你可以使用路径来生成你想要的输出。
我相信总体上有一个更好的设计，但这里有一个小的修改，可以产生你想要的输出(或多或少(：
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