生成所有可能的天际(PC 游戏)药水组合的最有效方法是什么？

Question

所以每种成分有4种效果http://www.uesp.net/wiki/Skyrim:成分

如果我把两种成分混合。药剂将在两个集合相交的地方产生额外效果。我不能用同样的食材两次。为了生成所有两种成分的可能性，我只是制作了一个成分列表来影响配对。我取列表的头，并将其与列表中每个元素的其余部分进行比较，每次迭代删除头。这样可以避免受骗。

我被困住了。我不知道如何将三种原料组合在一起而不产生假象。有什么建议吗?

Answer 1

听起来像是每个人最喜欢的编程语言R的工作!

library(XML)
tables <- readHTMLTable('http://www.uesp.net/wiki/Skyrim:Ingredients', 
    stringsAsFactors=FALSE)
potions <- tables[[1]]
twoway <- data.frame(t(combn(potions$Name,2)))
threeway <- data.frame(t(combn(potions$Name,3)))

BAM !

> head(twoway)
               X1                  X2
1 Abecean Longfin          Bear Claws
2 Abecean Longfin                 Bee
3 Abecean Longfin        Beehive Husk
4 Abecean Longfin      Bleeding Crown
5 Abecean Longfin         Blisterwort
6 Abecean Longfin Blue Butterfly Wing
> head(threeway)
               X1         X2                  X3
1 Abecean Longfin Bear Claws                 Bee
2 Abecean Longfin Bear Claws        Beehive Husk
3 Abecean Longfin Bear Claws      Bleeding Crown
4 Abecean Longfin Bear Claws         Blisterwort
5 Abecean Longfin Bear Claws Blue Butterfly Wing
6 Abecean Longfin Bear Claws       Blue Dartwing

使用write.csv命令将表保存为csv文件

/编辑:解释我在做什么:XML包包含readHTMLTable函数，它从网站中提取所有的html表作为数据框架，并将它们保存为列表。这个列表中的第一个表是我们想要的。combn函数查找药剂名称的所有2向、3向和n向组合，并将结果作为矩阵返回。我用t函数来转置这个矩阵，所以每个组合都是一行，然后把它转换成一个数据帧。这很容易扩展到n种成分的组合。

/Edit 2:我编写了一个函数将n-way表保存到用户指定的csv文件中。我也重新做了一下，因为转置巨大的矩阵在计算上是很昂贵的。这个版本应该允许你计算4路表，尽管它需要很长时间，我不知道它是否与游戏相关。

nway <- function(n, filepath, data=potions) {
    nway <- combn(data$Name, n, simplify = FALSE)
    nway <- do.call(rbind,nway)
    write.csv(nway,filepath, row.names=FALSE)
}
nway(4,'~/Desktop/4way.csv')

/编辑3:这里有一些代码来找到实际的工作药水。这不是很有效，也许可以大大改进:

#Given an ingredient, lookup effects
findEffects <- function(Name) { #Given a name, lookup effects
    potions[potions$Name==Name,3:6]
}
#2-way potions
intersectTwoEffects <- function(x) {
    Effects1 <- findEffects(x[1])
    Effects2 <- findEffects(x[2])
    Effects <- unlist(intersect(Effects1,Effects2))
    Effects <- c(x[1],x[2],Effects)
    length(Effects) <- 6
    names(Effects) <- NULL
    c(Effects,sum(is.na(Effects)))
}
twoway <- lapply(twoway,intersectTwoEffects)
twoway <- do.call(rbind,twoway)
twoway <- twoway[twoway[,7]<4,-7] #remove combos with no effect
write.csv(twoway,'~/Desktop/twoway.csv',row.names=FALSE)
#3-way potions
intersectThreeEffects <- function(x) {
    Effects1 <- findEffects(x[1])
    Effects2 <- findEffects(x[2])
    Effects3 <- findEffects(x[3])
    Effects <- c(intersect(Effects1,Effects2),intersect(Effects1,Effects3),intersect(Effects2,Effects3))
    Effects <- unlist(unique(Effects))
    Effects <- c(x[1],x[2],x[3],Effects)
    length(Effects) <- 8
    names(Effects) <- NULL
    c(Effects,sum(is.na(Effects)))
}
threeway <- lapply(threeway,intersectThreeEffects)
threeway <- do.call(rbind,threeway)
threeway <- threeway[threeway[,9]<5,-9] #remove combos with no effect
write.csv(threeway,'~/Desktop/threeway.csv',row.names=FALSE)

Answer 2

这是一些c#。

它根据潜在作用的名称查找成分。然后，它使用该查找来确定哪些成分可以匹配当前配方。最后，它生成食谱，并在使用哈希集生成时丢弃重复的食谱。

完整代码(不完整成分表)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Combinations
{
    public class Ingredient
    {
        public List<string> Effects { get; set; }
        public string Name { get; set; }
        public Ingredient(string name, params string[] effects)
        { Name = name; Effects = new List<string>(effects); }
    }
    public class Recipe
    {
        public List<Ingredient> Ingredients {get;set;}
        public Recipe(IEnumerable<Ingredient> ingredients)
        { Ingredients = ingredients.OrderBy(x => x.Name).ToList(); }
        public override string ToString()
        { return string.Join("|", Ingredients.Select(x => x.Name).ToArray()); }
    }
    class Program
    {
        static void Main(string[] args)
        {
            List<Ingredient> source = GetIngredients();
            ILookup<string, Ingredient> byEffect = (
                from i in source
                from e in i.Effects
                select new { i, e }
                ).ToLookup(x => x.e, x => x.i);
            List<Recipe> oneIng = source.Select(x => new Recipe(new Ingredient[] { x })).ToList();
            List<Recipe> twoIng = oneIng.SelectMany(r => GenerateRecipes(r, byEffect)).ToList();
            List<Recipe> threeIng = twoIng.SelectMany(r => GenerateRecipes(r, byEffect)).ToList();
            Console.WriteLine(twoIng.Count);
            foreach(Recipe r in twoIng) { Console.WriteLine(r); }
            Console.WriteLine(threeIng.Count);
            foreach(Recipe r in threeIng) { Console.WriteLine(r); }
            Console.ReadLine();
        }
        static IEnumerable<Recipe> GenerateRecipes(Recipe recipe, ILookup<string, Ingredient> byEffect)
        {
            IEnumerable<string> knownEffects = recipe.Ingredients
                .SelectMany(i => i.Effects)
                .Distinct();
            IEnumerable<Ingredient> matchingIngredients = knownEffects
                .SelectMany(e => byEffect[e])
                .Distinct()
                .Where(i => !recipe.Ingredients.Contains(i));
            foreach(Ingredient i in matchingIngredients)
            {
                List<Ingredient> newRecipeIngredients = recipe.Ingredients.ToList();
                newRecipeIngredients.Add(i);
                Recipe result = new Recipe(newRecipeIngredients);
                string key = result.ToString();
                if (!_observedRecipes.Contains(key))
                {
                    _observedRecipes.Add(key);
                    yield return result;
                }
            }
        }
        static HashSet<string> _observedRecipes = new HashSet<string>();
        static List<Ingredient> GetIngredients()
        {
            List<Ingredient> result = new List<Ingredient>()
            {
                new Ingredient("Abecean Longfin", "Weakness to Frost", "Fortify Sneak", "Weakness to Poison", "Fortify Restoration"),
                new Ingredient("Bear Claws", "Restore Stamina", "Fortify Health", "Fortify One-handed", "Damage Magicka Regen"),
                new Ingredient("Bee", "Restore Stamina", "Ravage Stamina", "Regenerate Stamina", "Weakness to Shock"),
                new Ingredient("Beehive Husk", "Resist Poison", "Fortify Light Armor", "Fortify Sneak", "Fortify Destruction"),
                new Ingredient("Bleeding Crown", "Weakness to Fire", "Fortify Block", "Weakness to Poison", "Resist Magic"),
                new Ingredient("Blisterwort", "Damage Stamina", "Frenzy", "Restore Health", "Fortify Smithing"),
                new Ingredient("Blue Butterfly Wing", "Damage Stamina", "Fortify Conjuration", "Damage Magicka Regen", "Fortify Enchanting"),
                new Ingredient("Blue Dartwing", "Resist Shock", "Fortify Pickpocket", "Restore Health", "Damage Magicka Regen"),
                new Ingredient("Blue Mountain Flower", "Restore Health", "Fortify Conjuration", "Fortify Health", "Damage Magicka Regen"),
                new Ingredient("Bone Meal", "Damage Stamina", "Resist Fire", "Fortify Conjuration", "Ravage Stamina"),
            };
            return result;
        }
    }
}

Answer 3

所以我想到，"获得所有成分知识的最有效方法是什么?"也就是说，我想让玩家知道所有成分的效果，但我不想为此花费12颗Daedra Hearts。

如果你使用传统的搜索解决方案(a *等)，分支因素是可怕的(有22000种可能有效的药剂)。我尝试了退火方法，但没有得到好的结果。最后，我做了一个知情的搜索;这不是最理想的，但它会完成工作。

下面是导入并组合的代码:写着"进口原料……"

fd = File::open('ingr_weighted.txt', 'r')
dbtext = fd.read
fd.close
ingredients = []
cvg = []
id = 0
dbtext.each_line { |line|
    infos = line.split("t")
    ingredients << {:id => id, :name => infos[0], :effects => [infos[2],infos[3],infos[4],infos[5]],
                    :eff1 => infos[2], :eff2 => infos[3], :eff3 => infos[4], :eff4 => infos[5],
                    :weight => infos[6], :cost => infos[7].to_i+1}
    id += 1
    cvg << [false, false, false, false]
}

puts "Building potions..."
potions = []
id = 0
for a in 0..ingredients.length-2
    for b in a+1..ingredients.length-1
        # First try two-ingredient potions
        uses = ingredients[a][:effects] & ingredients[b][:effects]
        cost = ingredients[a][:cost] + ingredients[b][:cost]
        if (uses.length > 0)
            coverage = [ingredients[a][:effects].map{|x| uses.include? x},
                        ingredients[b][:effects].map{|x| uses.include? x}]
            potions << {:id => id, :effects => uses, :coverage => coverage, :ingredients => [a, b], :cost => cost}
            id = id + 1
        end
        # Next create three-ingredient potions
        for c in b+1..ingredients.length-1
            uses =  ingredients[a][:effects] & ingredients[b][:effects] |
                    ingredients[a][:effects] & ingredients[c][:effects] |
                    ingredients[b][:effects] & ingredients[c][:effects]
            cost = ingredients[a][:cost] + ingredients[b][:cost] + ingredients[c][:cost]
            if (uses.length > 0)
                coverage = [ingredients[a][:effects].map{|x| uses.include? x},
                            ingredients[b][:effects].map{|x| uses.include? x},
                            ingredients[c][:effects].map{|x| uses.include? x}]
                # Prune potions that contain a superfluous ingredient
                if (coverage.inject(true) { |cum, cvgn|
                                            cum = cum && cvgn.inject { |cum2,ef| cum2 = cum2 || ef}
                                            } )
                    potions << {:id => id, :effects => uses, :coverage => coverage, :ingredients => [a,b,c], :cost => cost}
                    id = id + 1
                end
            end
        end
    end
end
# 22451
puts "#{potions.count} potions generated!"
puts "Searching..."

输入文件是从其中一个wiki复制的，所以如果你正在使用mod或其他东西，你可以直接进入。从这里你已经导入了所有的数据并生成了有效的药剂，所以做你想做的吧!

出于我最初的目的(高效的"学习")，我使用了以下代码。基本上，它从最昂贵的剩余成分开始，尽可能便宜地耗尽其效果，然后向下移动。一些稀有的原料很便宜(外汇)。人肉)，所以我"操纵"了我的数据文件，人为地夸大了它们的价值。总的来说，这个程序在我的笔记本电脑上运行大约45分钟，但它是一种解释性语言…

puts "Searching..."
valueChain = ingredients.sort {|a,b| a[:cost] <=> b[:cost]};
while (valueChain.count > 0)
    # Grab highest-value ingredient left
    ingr = valueChain.pop;
    # Initialize the coverage and potion sub-set
    pots = potions.each_with_object([]) { |pot, list| list << pot if pot[:ingredients].include? ingr[:id] }
    puts "#{ingr[:name]}:t#{pots.count} candidates"
    if (cvg[ingr[:id]].all?)
        puts "Already finished"
        next
    end
    # Find the cheapest combination that completes our coverage situation
    sitch = {:coverage => cvg[ingr[:id]].dup, :solution => [], :cost => 0}
    best = nil;
    working = []
    working << sitch
    while (working.count != 0)
        parent = working.shift
        pots.each { |pot|
            node = {:coverage => parent[:coverage].zip(pot[:coverage][pot[:ingredients].index(ingr[:id])]).map {|a,b| a || b},
                    :cost => parent[:cost] + pot[:cost],
                    :solution => parent[:solution].dup << pot[:id]}
            # This node is useful if its cost is less than the current-best
            if node[:coverage] == [true,true,true,true]
                if (!best || best[:cost] > node[:cost])
                    best = node
                end
            elsif node[:solution].count < 4
                if (!best || best[:cost] > node[:cost])
                    working << node
                end
            end
        }
    end
    # Merge our selected solution into global coverage
    best[:solution].each{ |pIndex|
        potions[pIndex][:ingredients].each_with_index { |ingID, index|
            cvg[ingID] = cvg[ingID].zip(potions[pIndex][:coverage][index]).map {|x,y| x || y}
        }
    }
    # Report the actual potions chosen
    best[:solution].each { |pIndex|
        print "tPotion #{pIndex}"
        potions[pIndex][:ingredients].each { |iIndex|
            print "t#{ingredients[iIndex][:name]}"
        }
        print "n"
    }
#   IRB.start_session(Kernel.binding)
end