文明盛世超能饮料谜题, 是号称价值百万年薪的题. 不过噱头太大了, 完全是炒作.

尊敬的投稿者，

您好，感谢您向文明盛世提交谜题解答方案。您的解答方案（收到时间：2014年03月31日，15点31分）(id为:2447)成功解决了谜题chemical

-如果有任何其他方面的疑问，请将您所碰到的问题详细描述清楚并发送到：puzzlerobot@wmsstech.com

再次感谢您的支持！

-The puzzle robot

有很多迷友痴迷于此题，我看到csdn有位仁兄自题目出生就一直在给出解答，却没有一个时间复杂度达标的。面试已经过去很长时间了，今天我把此题的一个解答贴出来，让所有深陷其中的谜友们解脱掉，也清醒一下。文明盛世不只需要一个有钻研能力与创造力的工程师，而是需要一个可以独当一面经验丰富的高级工程师。

我觉得这道题确实非常迷人，希望喜欢这道题的同学能各抒己见，让我看到另一种解答。

说一下谜题，其实谜题没什么特别高深的，就是一个更符合现实的NTSP问题。

本题我用过很多种非优化算法，但最终解决的是这个遗传算法。如果不考虑收敛速度，蚁群算法应该也可以，还有粒子群算法会更合适。

我对本题的解决思路就是要建立起一个可量化基因优良性的化合物组合，然后再通过能够保留优良基因的交配办法，最终经过多次杂交与灾变达到最优结果的目的。

遗传算法本身就是基于概率出来的，所以虽然本解决方案灾变数次，但仍然会有极小极小的概率得到局部最优。

其中灾变次数的设置应该可以根据化合物的数量确定灾变次数，本解答直接设置为常量, 因为应付本题足够。如果您也有好的解决思路，欢迎一起交流。

 

该份代码用我的笔记本经过数次测试, 16个化合物大约1.5-2.5分钟.而文明盛世的服务器非常快, 估计30秒钟就计算完毕.

源码附件下载

源码如下:

#!/usr/bin/python
import sys
import time
import re
import random
 
TMAP = {}
CS = []
C1MS = {}
C2MS = {}
P_LEN = 50
 
 
def read_data(fpath):
    f = open(fpath)
    cs_set = set()
    for line in f.read().strip().split('\
'):
        m, c1, c2, p = re.match(
            r'M(\d+)[\t ]+(C\d+)[\t ]+(C\d+)[\t ]+(\d+)', line.strip()).group(1, 2, 3, 4)
        m = Machine(m, p, c1, c2)
        TMAP[(c1, c2)] = m
        if c1 not in C1MS:
            C1MS[c1] = []
        C1MS[c1].append(m)
        if c2 not in C2MS:
            C2MS[c2] = []
        C2MS[c2].append(m)
        cs_set.add(c1)
    f.close()
 
    for ms in C1MS.values():
        ms.sort(key=lambda m: m.price)
    for ms in C2MS.values():
        ms.sort(key=lambda m: m.price)
 
    CS.extend(list(cs_set))
 
 
class Machine(object):
 
    def __init__(self, m, p, fc, tc):
        self.id, self.price = int(m), int(p)
        self.from_c, self.to_c = fc, tc
 
    def optimized_mlsts(self):
        i, j = , 
        while True:
            mt = C1MS[self.from_c][i]
            mf = C2MS[self.to_c][j]
            if mt.price + mf.price < self.price:
                yield mt, mf
            else:
                break
            if mt.price < mf.price:
                i += 1
            else:
                j += 1
 
    def __str__(self):
        return "Machine:%s, %s[%s>%s]" % (self.id, self.price, self.from_c, self.to_c)
 
 
class DNA(object):
 
    def __init__(self, cs):
        self.cs = cs[:]
 
        self.cost = 
        self.fit_rate  = 
        self.optimized_ms = [TMAP[(cs[i-1], cs[i])] for i in range(len(cs))]
        self.get_cost()
        self._ms = None
 
    def get_fitness(self):
        return 1.0/self.get_cost()
 
    def get_cost(self):
        if self.cost == :
            for m in self.optimized_ms[:]:
                for m1, m2 in m.optimized_mlsts():
                    if self.instead(m, m1, m2):
                        break
            self.cost = sum([m.price for m in self.optimized_ms])
        return self.cost
 
    def instead(self, m, m1, m2):
        if m.from_c != m1.from_c:
            m1, m2 = m2, m1
        i = None
        for j, m0 in enumerate(self.optimized_ms):
            if m0 == m:
                i = j
                break
        if i is None:
            return True
        i = self.optimized_ms.index(m)
        new_ms = list(
            set(self.optimized_ms[:i] + self.optimized_ms[i+1:] + [m1, m2]))
 
        track_d = {}
        for m in new_ms:
            if m.from_c not in track_d: track_d[m.from_c] = []
            track_d[m.from_c].append(m)
        ps = set([m1.to_c])
        end_p = m2.from_c
        tracked_ps = set()
        while end_p not in ps:
            nps = set([m.to_c for p in ps-tracked_ps for m in track_d[p]])
            tracked_ps.update(ps)
            if not nps:
                return False
            ps = nps
        self.optimized_ms = new_ms
        return True
        #TODO
        fms = [m for m in track_d[m1.to_c] if m != m1]
        tms = [m for m in new_ms if m.from_c == m2.from_c and m != m2]
        mgps = [(m1, m2, TMAP[(m1.from_c, m2.to_c)]) \
            for m1 in fms for m2 in tms if (
                m1.from_c!=m2.to_c and \
                TMAP[(m1.from_c, m2.to_c)].price<m1.price+m2.price)]
        ms = sorted(mgps, key=lambda mg: mg[2].price)
        if ms:
            m1, m2, m = ms[]
            new_ms.append(m)
            new_ms.remove(m1)
            new_ms.remove(m2)
 
    def get_ms(self):
        if not self._ms:
            self._ms = sorted([m.id for m in self.optimized_ms])
        return self._ms
 
    def __str__(self):
        return ' '.join(map(str, self.get_ms()))
 
    def __hash__(self):
        self.get_cost()
        return hash(str(self.get_ms()))
 
    def __eq__(self, dna):
        return isinstance(dna, DNA) and self.get_ms()==dna.get_ms()
 
variation_rate = 0.4
 
 
def variate(dna):
    cs = dna.cs[:]
    if random.randint(, 100) < variation_rate*100:
        mi = 
        while mi < 4:
            mi += 1
            i = random.randint(1, len(cs)-1)
            j = i
            while i==j:
                j = random.randint(1, len(cs)-1)
            cs[i], cs[j] = cs[j], cs[i]
        return DNA(cs)
 
 
class Selector(object):
 
    def __init__(self, dnas):
        self.dnas = dnas
 
    def next(self):
        r = random.random()
        m = 
        for n in self.dnas:
            m += n.fit_rate
            if m>=r:
                return n
 
 
def mate(dnas):
 
    sel = Selector(dnas)
    ns = set(dnas[:1])
    c = int(P_LEN * 1.5)
 
    while c > :
        d1 = sel.next().cs
        d2 = sel.next().cs
        k = random.randint((len(CS)-1)/4, 3*(len(CS)-1)/4)
        nd11, nd12 = d2[:k], d1[k:]
        nd21, nd22 = d1[:k], d2[k:]
        r1 = [i for i, a in enumerate(nd11) if a in nd12]
        r2 = [i for i, a in enumerate(nd21) if a in nd22]
        for i in range(len(r1)):
            nd11[r1[i]], nd21[r2[-i]] = nd21[r2[-i]], nd11[r1[i]]
        ndna1, ndna2 = DNA(nd11+nd12), DNA(nd21+nd22)
        ns.update([ndna1, ndna2])
 
        for n in [ndna1, ndna2]:
            nn = variate(n)
            nn and ns.add(nn)
        c -= 1
    return list(ns)
 
 
def count_fit_rate(dnas, Record, max_len=P_LEN):
    dnas = sorted(dnas, key=lambda dna: dna.get_cost())[:P_LEN]
    s = sum([dna.get_cost() for dna in dnas])
    for dna in dnas:
        dna.fit_rate = dna.get_cost()*1.0/s
    Record.set_best(dnas[])
    return dnas
 
 
def get_gp_dnas(l=P_LEN):
    dnas = []
    while len(dnas) < l:
        random.shuffle(CS)
        dnas.append(DNA(CS))
    return dnas
 
 
class Record(object):
    dna = None
 
    rate_horizontal_rpt = 
    best_horizontal_rpt = 
 
    @staticmethod
    def set_best(dna):
        if dna and Record.dna and dna.get_cost() == Record.dna.get_cost():
            Record.best_horizontal_rpt += 1
        else:
            Record.best_horizontal_rpt = 
            if dna and Record.dna:
                Record.rate_horizontal_rpt = 
        Record.dna = dna
 
    @staticmethod
    def catastrophe():
        Record.rate_horizontal_rpt += 1
 
    @staticmethod
    def add_best_to_lst(dnas):
        if Record.best_horizontal_rpt > len(CS):
            dnas.append(Record.dna)
        return dnas
 
    @staticmethod
    def should_catastrophe():
        return Record.best_horizontal_rpt > len(CS)*1.5
 
    @staticmethod
    def is_best_enough():
        return Record.rate_horizontal_rpt >= len(CS)*1.5
 
 
def run():
 
    start_t = time.clock()
 
    dnas = get_gp_dnas(len(CS)*P_LEN)
 
    while not Record.is_best_enough():
        if Record.should_catastrophe():
            Record.catastrophe()
            best_dna = Record.dna
            Record.set_best(None)
            dnas = get_gp_dnas(len(CS)*P_LEN)
            best_dna and dnas.append(best_dna)
        dnas = count_fit_rate(dnas, Record)
        dnas = mate(dnas)
    print Record.dna.get_cost()
    print Record.dna
    #print time.clock() - start_t
 
 
if __name__=="__main__":
 
    if len(sys.argv)!=2:
        sys.exit(1)
    fpath = sys.argv[1]
 
    read_data(fpath)
    run()

 

 

附谜题内容:

原题网址: 文明盛世超能饮料谜题

原题内容:

超能饮料 (关键字: chemical)
文明盛世旗下的化工产品实验室一直在研究如何配制能够提高工程师生产效率、保持他们头脑清醒的新型兴奋剂。研究已经分离了一系列化合物，当它们和糖水混合在一起就成为了下一代超能饮料的活性成分。

这些化合物成分类似：任何一种化合物都可经由某一化学反应，成为其它任意一种化合物。实际进行化学反应的成本很低，但使反应发生的设备和催化剂成本相当高昂。把某一化合物转换为另一化合物时所使用的设备，也都必须单独定制。每件设备都会产生购置费用，并且需要投入某种化合物才能产出另外一种化合物。文明盛世实验室必须配备足够设备，确保无论市场上能买到哪些化合物，都能产出整个系列的化合物。

编写仅带一个命令行参数的程序。该参数必须是一个包括输入数据的文件名。此程序应该输出最便宜的方案到标准输出，使文明盛世公司能够利用源化合物或多个化合物生产其饮料（输出详情请参见下文）。我们假设设备目录中提到的所有化学品都是配制饮品的必要原料。我们不保证所有的化学反应都能一步到位，不过我们保证任何一种化合物都能经由反应，转变为其它任意一种化合物。参与者提交的谜题结果和程序方案都必须遵循下面的输入、输出规范，否则将会被视为不合格。参与者提交的程序将会在几个数据不同的设备目录上测试。此外，参与者提交的程序运行速度必须很快，能在数分钟内给出正确方案。


输入规范
输入文件中需要包含可用设备列表。文件的每一行都代表一个特定的设备型号。每一行的格式如下：
      （分别对应的中文意思是设备名称、源化合物、新化合物、价格）

设备名称要以字母‘M’开头（不要带引号）后跟一个非零整数。设备的名称可以是‘M1’、‘M2’、‘M13’等。

化合物名称要以字母‘C’开头（不要带引号）后跟一个非零整数。化合物的名称可以是‘C4’、‘C6’、‘C24’等。

价格请用简单的非零整数，请勿使用逗号、句号或单位符号（我们假设所有价格的单位都是美元）。如：‘987334’、‘13948295’等。

请在输入文件的段落之间用空格或制表符隔开。最后一项的行尾可以加入空格（也可以不加）。要确保所提交的程序能够通过数据格式正确的输入文件的运行验证。

输入文件示例：
M1      C1      C2      277317
M2      C2      C1      26247
M3      C1      C3      478726
M4      C3      C1      930382
M5      C2      C3      370287
M6      C3      C2      112344

输出规范
请严格按照以下说明进行输出：参与者的程序必须首先输出购买所需设备的总价（请勿插入逗号、句号或其它任何符号），这个总价请用简单整数表示，结尾另起一行。

然后参与者提交的程序需打印所购买的设备编号，以升序排列并省略标志字符’M’。设备编号之间必须用一个空格隔开。程序应该在最后一个设备编号后另起一行，而不能再加入空格。

输出示例（每行末尾需另起一行）
617317
2  3  6