Итак, у меня возникла мысль: «Какой самый экономически эффективный способ получить все знания об ингредиентах?»то есть я хочу, чтобы все ингредиенты были известны в игре, но я не хочу тратить на это двенадцать сердец даэдра.
Если вы используете традиционное поисковое решение (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..."
Входной файл - copy-pastaЕсли вы используете мод или что-то еще, вы можете зайти прямо сюда. Отсюда вы импортируете все данные и сгенерированные эффективные зелья, так что делайте что хотите!
Для моей первоначальной цели (эффективное «обучение») я использовал следующий код.В основном это начинается с самого дорогого оставшегося ингредиента, исчерпывает его эффекты как можно дешевле, а затем движется вниз.Некоторые более редкие ингредиенты дешевы (форекс. Человеческая плоть), поэтому я «нашел» файл данных, чтобы искусственно завышать их стоимость.В общем, эта программа работает на моем ноутбуке за 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