中科院計(jì)算所智能安全(編輯修改稿)
2025-03-31 07:32 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 a Sets ?插入 1%的匹配數(shù)據(jù) ?正則表達(dá)式測(cè)試集（文中沒(méi)說(shuō)明） 最好情況比較差 Deterministic and Robust Mapping ?主要目標(biāo) ? 同時(shí)執(zhí)行的自動(dòng)機(jī)應(yīng)當(dāng)位于不同的內(nèi)存模塊中 避免內(nèi)存沖突 可以通過(guò)使內(nèi)存數(shù)目大于自動(dòng)機(jī)個(gè)數(shù)來(lái)解決 ? default path中的狀態(tài)結(jié)點(diǎn)應(yīng)當(dāng)位于不同的內(nèi)存模塊中 避免 default path中所有狀態(tài)位于一個(gè)內(nèi)存模塊中 需要通過(guò)一定算法來(lái)解決的目標(biāo) ?問(wèn)題形式化 ?問(wèn)題可以 形式化成 graph coloring problem ?顏色代表內(nèi)存模塊， default path代表圖 問(wèn)題轉(zhuǎn)化成：將圖中的結(jié)點(diǎn)涂顏色，使得每條從葉子到根結(jié)點(diǎn)的路 徑都涂上不同的顏色 maxmin algorithm – 介紹 ? 具體算法 ? 使用三個(gè)堆：樹堆、層次堆、顏色堆 ? 每次選樹堆中結(jié)點(diǎn)對(duì)多的一棵樹 ? 對(duì)數(shù)構(gòu)建層次堆（層數(shù)：每層的節(jié)點(diǎn)數(shù)） 選擇顏色堆中顏色使用數(shù)目的最多的顏色 分給層次堆中最少層的所有該層結(jié)點(diǎn) 更新顏色堆中該分配顏色的使用數(shù)目 直至所有層均分配顏色 ?直至所有樹均分配到顏色 即：每次選擇樹堆中最大的樹，在該樹中選層次堆中結(jié)點(diǎn)最少的一 層，配顏色堆中最多使用的顏色 maxmin algorithm 示例 ?缺陷 ?導(dǎo)致顏色不均勻 （下圖所示） Adaptive coloring algorithm ?主要思路 ?maxmin算法沒(méi)有考慮當(dāng)結(jié)點(diǎn)可以涂多種顏色選擇哪種顏色的情況 ?主要思想 ?對(duì)每個(gè)結(jié)點(diǎn)賦予全部的顏色集合 ?當(dāng)結(jié)點(diǎn)賦予某個(gè)顏色時(shí)，將其它顏色去除（僅余一種顏色） ?使用兩個(gè)變量 used 每種顏色使用的次數(shù) deproved 不能使用這種顏色的節(jié)點(diǎn)個(gè)數(shù)， 當(dāng)某一結(jié)點(diǎn)選定某一顏色，則其子結(jié)點(diǎn)均不能使用該顏色 ?選擇最長(zhǎng)深度的節(jié)點(diǎn) ?根據(jù)其默認(rèn)路徑逐一將路徑上的點(diǎn)涂顏色 顏色選 used中最小的并且 deprived中最大的 ?更新 used和 deproved變量。直至全部路徑都涂完顏色。 Adaptive coloring algorithm—示例 實(shí)驗(yàn)結(jié)果 ?實(shí)驗(yàn)數(shù)據(jù) ?測(cè)試數(shù)據(jù)同隨機(jī)測(cè)試 ?實(shí)驗(yàn)結(jié)果 最好情況已較好 小結(jié) ? 提出新自動(dòng)機(jī)表示方法 ? 用時(shí)間來(lái)?yè)Q空間 ?平均減少 95%的 transition
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1