做網(wǎng)站的幾個(gè)軟件app開(kāi)發(fā)公司哪家好
一.什么是動(dòng)態(tài)規(guī)劃算法
1.1總體思想
·動(dòng)態(tài)規(guī)劃算法與分治法類似,基本思想也是將待求解的問(wèn)題分成若干個(gè)子問(wèn)題
·經(jīng)過(guò)分解得到的子問(wèn)題往往不是互相獨(dú)立的,有些子問(wèn)題被重復(fù)計(jì)算多次
·如果能夠保存已解決的子問(wèn)題答案,在需要時(shí)再找出來(lái)已求得的答案,就可以避免大量重復(fù)計(jì)算,從而得到多項(xiàng)式時(shí)間算法(備忘錄)
1.2使用動(dòng)態(tài)規(guī)劃求解的問(wèn)題需要具備的基本要素
1)重復(fù)子問(wèn)題
·遞歸算法求解問(wèn)題時(shí),每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題,有些子問(wèn)題被反復(fù)計(jì)算多次,這種性質(zhì)被稱為子問(wèn)題的重疊性質(zhì)
·動(dòng)態(tài)規(guī)劃算法,對(duì)每一個(gè)子問(wèn)題只解一次,而后將其解保存在一個(gè)表格中,當(dāng)再次需要解此子問(wèn)題時(shí),只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。
·通常不同的子問(wèn)題個(gè)數(shù)隨問(wèn)題的大小呈多項(xiàng)式增長(zhǎng),用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間,從而獲得較高的解題效率。
2)最優(yōu)子結(jié)構(gòu)
·一個(gè)問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解,這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)
·分析問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì),首先假設(shè)由問(wèn)題的最優(yōu)解導(dǎo)出的子問(wèn)題的解不是最優(yōu),然后再設(shè)法說(shuō)明在這個(gè)假設(shè)下可構(gòu)造出比原問(wèn)題最優(yōu)解更好的解,從而導(dǎo)致矛盾
·利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì),以自底向上的方式遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解
·最優(yōu)子結(jié)構(gòu)是一個(gè)問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提
1.3動(dòng)態(tài)規(guī)劃求解的基本步驟
1)找出最優(yōu)解的性質(zhì),并刻畫其結(jié)構(gòu)特征
2)遞歸地定義最優(yōu)質(zhì)
3)以自底向上的方式計(jì)算出最優(yōu)值
4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息,構(gòu)造最優(yōu)解
二.打分矩陣代碼
import random # 1. 生成一個(gè)指定長(zhǎng)度的隨機(jī)DNA序列
def generate_dna(length): dna_bases = 'ACGT' # DNA的四個(gè)堿基 sequence = '' # 初始化空序列 for _ in range(length): # 循環(huán)length次 sequence += random.choice(dna_bases) # 每次從四個(gè)堿基中隨機(jī)選一個(gè)添加到序列中 return sequence # 返回生成的DNA序列 # 2. 在DNA序列中隨機(jī)位置插入一個(gè)可能突變的motif
def insert_motif(dna, motif, mutation_rate): mutated_motif = '' # 初始化突變的motif為空字符串 for base in motif: # 遍歷motif中的每個(gè)堿基 if random.random() < mutation_rate: # 如果隨機(jī)數(shù)小于突變率 mutated_motif += random.choice('ACGT') # 則該位置堿基隨機(jī)突變 else: mutated_motif += base # 否則保持原樣 insert_point = random.randint(0, len(dna)) # 在DNA序列中隨機(jī)選擇一個(gè)插入點(diǎn) return dna[:insert_point] + mutated_motif + dna[insert_point:] # 插入突變的motif # 3. 生成多條帶有隨機(jī)插入motif的DNA序列
def generate_sequences(num_sequences, dna_length, motif_length, mutation_rate): sequences = [] # 初始化一個(gè)空列表來(lái)存儲(chǔ)生成的序列 motif = generate_dna(motif_length) # 生成一個(gè)隨機(jī)的motif for _ in range(num_sequences): # 循環(huán)生成指定數(shù)量的序列 dna = generate_dna(dna_length) # 生成一個(gè)DNA序列 dna_with_motif = insert_motif(dna, motif, mutation_rate) # 插入motif sequences.append(dna_with_motif) # 將序列添加到列表中 return sequences # 返回生成的序列列表 # 使用函數(shù)生成序列并打印
sequences = generate_sequences(5, 20, 5, 0.1)
for seq in sequences: print(seq)
三.編寫一個(gè)函數(shù),生成m條DNA序列,每條序列長(zhǎng)度為k,然后對(duì)每條序列隨機(jī)插入一個(gè)長(zhǎng)度為L(zhǎng)的motif,motif的突變率為n
import random # 1. 生成一個(gè)指定長(zhǎng)度的隨機(jī)DNA序列
def generate_dna(length): dna_bases = 'ACGT' # DNA的四個(gè)堿基 sequence = '' # 初始化空序列 for _ in range(length): # 循環(huán)length次 sequence += random.choice(dna_bases) # 每次從四個(gè)堿基中隨機(jī)選一個(gè)添加到序列中 return sequence # 返回生成的DNA序列 # 2. 在DNA序列中隨機(jī)位置插入一個(gè)可能突變的motif
def insert_motif(dna, motif, mutation_rate): mutated_motif = '' # 初始化突變的motif為空字符串 for base in motif: # 遍歷motif中的每個(gè)堿基 if random.random() < mutation_rate: # 如果隨機(jī)數(shù)小于突變率 mutated_motif += random.choice('ACGT') # 則該位置堿基隨機(jī)突變 else: mutated_motif += base # 否則保持原樣 insert_point = random.randint(0, len(dna)) # 在DNA序列中隨機(jī)選擇一個(gè)插入點(diǎn) return dna[:insert_point] + mutated_motif + dna[insert_point:] # 插入突變的motif # 3. 生成多條帶有隨機(jī)插入motif的DNA序列
def generate_sequences(num_sequences, dna_length, motif_length, mutation_rate): sequences = [] # 初始化一個(gè)空列表來(lái)存儲(chǔ)生成的序列 motif = generate_dna(motif_length) # 生成一個(gè)隨機(jī)的motif for _ in range(num_sequences): # 循環(huán)生成指定數(shù)量的序列 dna = generate_dna(dna_length) # 生成一個(gè)DNA序列 dna_with_motif = insert_motif(dna, motif, mutation_rate) # 插入motif sequences.append(dna_with_motif) # 將序列添加到列表中 return sequences # 返回生成的序列列表 # 使用函數(shù)生成序列并打印
sequences = generate_sequences(5, 20, 5, 0.1)
for seq in sequences: print(seq)
四.對(duì)生成的已插入突變motif的序列集合,編寫一套函數(shù),尋找其中的motif,可指定motif長(zhǎng)度;
# 定義一個(gè)名為 find 的函數(shù),它接受兩個(gè)參數(shù):
# sequence_set 是一個(gè)包含多個(gè) DNA 序列的列表
# motif_length 是我們想要查找的子序列(也稱為 motif)的長(zhǎng)度
def find(sequence_set, motif_length): # 初始化一個(gè)空集合 motifs,用于存儲(chǔ)找到的所有唯一的 motif motifs = set() # 遍歷 sequence_set 中的每一條序列 for sequence in sequence_set: # 對(duì)于每一條序列,我們從其第一個(gè)堿基開(kāi)始,直到剩下的堿基數(shù)量少于 motif_length 為止 # 這樣確保我們可以從序列中提取出完整長(zhǎng)度的 motif for i in range(len(sequence) - motif_length + 1): # 從當(dāng)前位置 i 開(kāi)始,提取長(zhǎng)度為 motif_length 的子序列 motif = sequence[i:i+motif_length] # 將提取到的 motif 添加到 motifs 集合中 # 由于 motifs 是一個(gè)集合,所以重復(fù)的 motif 會(huì)被自動(dòng)去除 motifs.add(motif) # 函數(shù)返回包含所有唯一 motif 的集合 return motifs # 測(cè)試數(shù)據(jù):一個(gè)包含三條 DNA 序列的列表和一個(gè) motif 長(zhǎng)度值
sequence_set = ['ACGTTAGC', 'GTATCGAG', 'CGTACGTA']
motif_length = 4 # 調(diào)用 find 函數(shù),傳入測(cè)試數(shù)據(jù),并將返回的結(jié)果存儲(chǔ)在變量 motifs 中
motifs = find(sequence_set, motif_length)
# 打印出找到的所有唯一 motif
print(motifs)
五.對(duì)生成的已插入突變motif的序列集合,編寫一套函數(shù),基于分支界定法尋找指定長(zhǎng)度的motif,并與遍歷法比較計(jì)算效率
import itertools
import time # 計(jì)算motif在序列中的得分
def calculate_score(motif, sequences): score = 0 for seq in sequences: min_distance = float('inf') for i in range(len(seq) - len(motif) + 1): distance = sum(motif[j] != seq[i + j] for j in range(len(motif))) min_distance = min(min_distance, distance) score += min_distance return score # 分支界定法
def find_motif_branch_bound(sequences, motif_length): best_motif = None best_score = float('inf') def search(motif, depth): nonlocal best_motif, best_score if depth == motif_length: score = calculate_score(motif, sequences) if score < best_score: best_score = score best_motif = motif return for base in 'ACGT': search(motif + base, depth + 1) start_time = time.time() search('', 0) end_time = time.time() return best_motif, end_time - start_time # 遍歷法
def find_motif_brute_force(sequences, motif_length): best_motif = None best_score = float('inf') start_time = time.time() for motif in itertools.product('ACGT', repeat=motif_length): motif = ''.join(motif) score = calculate_score(motif, sequences) if score < best_score: best_score = score best_motif = motif end_time = time.time() return best_motif, end_time - start_time # 示例序列集合和motif長(zhǎng)度
sequences = ['ACGTAGCTAG', 'ACGGATCGTA', 'TAGCTAGCTA', 'TCGATCGATT']
motif_length = 3 # 使用分支界定法尋找motif
motif_bb, time_bb = find_motif_branch_bound(sequences, motif_length)
print(f"Branch and Bound Motif: {motif_bb}, Time: {time_bb:.4f}s") # 使用遍歷法尋找motif
motif_bf, time_bf = find_motif_brute_force(sequences, motif_length)
print(f"Brute Force Motif: {motif_bf}, Time: {time_bf:.4f}s")