鑄鐵拔叉零件夾具設(shè)計(jì)【含非標(biāo)件】【全套含CAD圖紙、說明書】

資源目錄里展示的全都有，所見即所得。下載后全都有,請(qǐng)放心下載。原稿可自行編輯修改=【QQ：401339828 或11970985 有疑問可加】 編號(hào)： 畢業(yè)設(shè)計(jì)(論文)外文翻譯 （譯文） 院 （系）： 機(jī)電工程學(xué)院 專 業(yè)： 機(jī)械設(shè)計(jì)制造及其自動(dòng)化 學(xué)生姓名： 學(xué) 號(hào)： 指導(dǎo)教師單位： 姓 名： 職 稱： 年 6月 3 日 翻譯論文：CONTENT BASED SEARCH OF MECHANICAL ASSEMBLIES 基于機(jī)械裝配體內(nèi)容的搜索 Associate Professor Satyandra K. Gupta 摘要：由于越來越多的國(guó)家使用三維 CAD 系統(tǒng)軟件開發(fā)產(chǎn)品，而導(dǎo)致了裝配體數(shù)據(jù)庫(kù)大型化， 未來這些裝配體數(shù)據(jù)還會(huì)繼續(xù)爆炸性增長(zhǎng)。當(dāng)前，這種爆炸性地增長(zhǎng)使得沒有有效的技術(shù)能基 于內(nèi)容在其中進(jìn)行搜索。然而基于內(nèi)容搜索這些數(shù)據(jù)庫(kù)對(duì)設(shè)計(jì)師們有如下兩點(diǎn)幫助，第一：它 可以促進(jìn)現(xiàn)有裝配設(shè)計(jì)的重用，從而減少設(shè)計(jì)時(shí)間。第二：更多有用的設(shè)計(jì)，制造和裝配（DFMA） 知識(shí)嵌入到現(xiàn)有的裝配體中。利用這種技術(shù)，設(shè)計(jì)師們可以分析和檢查現(xiàn)有的裝配體，也可以 作為一種學(xué)習(xí)工具借鑒現(xiàn)有的裝配設(shè)計(jì)，從而更好的使 DFMA 實(shí)踐到新設(shè)計(jì)當(dāng)中。 關(guān)鍵詞：搜索；裝配體搜索；DFMA；裝配體內(nèi)容 引言： 本文闡述了一種基于內(nèi)容搜索裝配體數(shù)據(jù)庫(kù)的系統(tǒng)，并列出已被認(rèn)定為全面搜索模板和描 述算法的基于內(nèi)容進(jìn)行機(jī)械裝配體搜索。其根據(jù)機(jī)械裝配體的特點(diǎn)進(jìn)行分類鑒定并根據(jù)他們的 相似度進(jìn)行比較和復(fù)雜計(jì)算。從 CAD 數(shù)據(jù)中提取特征并為之設(shè)置獨(dú)立的計(jì)算機(jī)輔助設(shè)計(jì)(CAD) 簽名，搜索方法包含字符串匹配的精確和近似、數(shù)字和計(jì)算圖匹配的兼容性。各種各樣的研究 團(tuán)隊(duì)解決了前兩個(gè)問題。本文介紹了一種新的算法利用分支定界搜索來解決數(shù)字和計(jì)算圖匹配 的兼容性問題，該算法運(yùn)算執(zhí)行使用了隨機(jī)生成的圖形特點(diǎn)。 本搜索軟件提供了一個(gè)單獨(dú)的工具來執(zhí)行基于裝配體內(nèi)容形式為基礎(chǔ) CAD 格式搜索。在 這篇論文中通過幾個(gè)實(shí)例來說明搜索軟件的能力。這個(gè)搜索工具有助于降低了設(shè)計(jì)時(shí)間和重用 已有設(shè)計(jì)的知識(shí)。 目錄 第一章 1 1.1 CAD 軟件系統(tǒng)中的機(jī)械零件 1 1.2 運(yùn)動(dòng)副 2 1.3 研究的問題 3 1.4 論文概要 6 第二章 6 2.1 裝配建模 6 2.2 部分搜索技術(shù) 8 2.3 搜索的基本功能 10 2.4 子圖同構(gòu)的概述 12 桂林電子科技大學(xué)畢業(yè)設(shè)計(jì)（論文）報(bào)告用紙 第 14 頁(yè) 共 13 頁(yè) 第一章 簡(jiǎn)介 這一章內(nèi)容如下：第 1.1 節(jié)討論 CAD 軟件系統(tǒng)中的機(jī)械零件，第 1.2 節(jié)介紹運(yùn)動(dòng)的裝配 體搜索系統(tǒng)研究的背景，第 1.3 節(jié)介紹這項(xiàng)研究中遇到的問題和第 1.4 節(jié)介紹論文大綱。本論 文大多數(shù)基礎(chǔ)研究的工作報(bào)告將在報(bào)刊上登出。 1.1 CAD 軟件系統(tǒng)中的機(jī)械零件 在過去十年中，整個(gè)產(chǎn)業(yè)的發(fā)展中三維 CAD 系統(tǒng)已經(jīng)變得非常流行，這些 CAD 系統(tǒng)用 來建立 3D 模型零件和裝配體。以這些模型為基礎(chǔ)，進(jìn)行工程分析與生成的生產(chǎn)計(jì)劃。因?yàn)橛?了三維模型的虛擬樣機(jī)而減少了物理樣機(jī)的需要。如今，在產(chǎn)品開發(fā)過程中所有參與者的 CAD 模型建立工作均獲得各部門的三維數(shù)據(jù)庫(kù)支持。特別是，設(shè)計(jì)、制造和售后工程師將受益于這 些數(shù)據(jù)庫(kù)。設(shè)計(jì)工程師設(shè)計(jì)產(chǎn)品時(shí)可以通過訪問數(shù)據(jù)庫(kù)中的零件和裝配體獲得類似的數(shù)據(jù)，生 產(chǎn)工程師可以使用這些資料庫(kù)找出生產(chǎn)計(jì)劃及供應(yīng)商制造零件和裝配體，售后工程師可以獲得 組裝產(chǎn)品拆卸的維護(hù)和維修方法。這些數(shù)據(jù)庫(kù)中的零件和裝配體更新到最新的版本后可以顯著 提高信息傳播。企業(yè)的 CAD 數(shù)據(jù)庫(kù)規(guī)模龐大，每一個(gè)產(chǎn)品的裝配體都包含很多零件，每個(gè)零 件又包含很多部分。因此，即使是一家小公司一年的數(shù)據(jù)庫(kù)也會(huì)因?yàn)槎鄠€(gè)產(chǎn)品線而導(dǎo)致數(shù)以百 計(jì)裝配數(shù)據(jù)的增加。 機(jī)械裝配體由幾何特征構(gòu)成的機(jī)械零件組成。裝配體在 CAD 系統(tǒng)中可由零件或子裝配體 組成，這個(gè)子裝配體由多個(gè)零件組成。裝配體明細(xì)表由各組成部件、子裝配體在一個(gè)結(jié)構(gòu)樹中 表示。裝配體的組成部分被放置在特定結(jié)構(gòu)樹位置表示不同的裝配關(guān)系，虛擬裝配樣機(jī)是產(chǎn)品 的一個(gè)重要組成部分。許多產(chǎn)品都有關(guān)聯(lián)，這些關(guān)聯(lián)用運(yùn)動(dòng)副來表示，這些裝配體中的節(jié)點(diǎn)可 以模擬出不同地運(yùn)動(dòng)。在產(chǎn)品制造之前可以對(duì)零件和裝配體進(jìn)行不同的分析，如分析裝配體的 可加工性、強(qiáng)度和運(yùn)動(dòng)分析。通常這樣的分析結(jié)果包含產(chǎn)品制造(PMI)裝配體數(shù)據(jù)存儲(chǔ)中。相 比而言，公司產(chǎn)品的機(jī)械裝配體 CAD 數(shù)據(jù)中包含了更多的產(chǎn)品信息。 裝配的數(shù)據(jù)庫(kù)，除了支持下游制造業(yè)和售后服務(wù)業(yè)的工作之外，在設(shè)計(jì)階段中也是非常有 用的。在設(shè)計(jì)階段裝配數(shù)據(jù)庫(kù)有兩個(gè)主要用途： ? 第一個(gè)用途是在裝配體中找出可能重復(fù)使用產(chǎn)品。這樣的設(shè)計(jì)重用有利于許多現(xiàn)有不同 設(shè)計(jì)，減少了設(shè)計(jì)時(shí)間的同時(shí)消除裝配中模型的建立和分析重用。此外，現(xiàn)有裝配測(cè)試還能建 立生產(chǎn)計(jì)劃，這進(jìn)一步降低了產(chǎn)品的開發(fā)時(shí)間和成本，在多個(gè)產(chǎn)品線中重用部件也有利于公司 的計(jì)劃經(jīng)濟(jì)。例如萬向節(jié)的設(shè)計(jì)可以重復(fù)使用另一個(gè)萬向節(jié)設(shè)計(jì)，萬向節(jié)的設(shè)計(jì)如圖 1.1 所示： 圖 1.1：一種普遍的連接——重用現(xiàn)有的設(shè)計(jì) ? 第二個(gè)用途是給現(xiàn)有的設(shè)計(jì)提供相關(guān)方面的知識(shí)。設(shè)計(jì)裝配體需要相當(dāng)?shù)呐?，?chuàng)造良 好的裝配設(shè)計(jì)需要細(xì)致到應(yīng)用分析及設(shè)計(jì)制造與裝配（DFMA）的原則，公司產(chǎn)品設(shè)計(jì)應(yīng)嵌入 這些規(guī)則。在公司及其供應(yīng)商需求中，這些規(guī)則可以調(diào)整設(shè)計(jì)以適應(yīng)生產(chǎn)要求。同時(shí)新的設(shè)計(jì) 師也可以通過參考和復(fù)制出成功的設(shè)計(jì)。而且，當(dāng)設(shè)計(jì)師們需要找到一個(gè)裝配所需的特性時(shí)他 們也可以訪問相關(guān)的數(shù)據(jù)，如成本、可靠性和故障報(bào)告。也可以用于通過訪問裝配體的信息， 而把他們適合緊緊聯(lián)系在一起。例如攝影機(jī)框架裝配如圖 1.2： 圖 1.2：一種攝影機(jī)框架——利用設(shè)計(jì)方面的知識(shí) 1.2 運(yùn)動(dòng)副 本節(jié)介紹裝配體的運(yùn)動(dòng)副搜索系統(tǒng)研究的背景。 1.2.1 裝配體搜索系統(tǒng)的需求 Saaksvuori 的報(bào)告中說道，如果利用現(xiàn)有的基礎(chǔ)知識(shí)重用到新的設(shè)計(jì)當(dāng)中可以節(jié)約公司設(shè) 計(jì)師高達(dá) 70%的時(shí)間。新的裝配設(shè)計(jì)過程中這種能搜索數(shù)據(jù)庫(kù)的能力尤為重要。目前，基于裝 配內(nèi)容的搜索工具沒有規(guī)范化的標(biāo)準(zhǔn)。因此，設(shè)計(jì)師們只能使用 CAD 系統(tǒng)中結(jié)合文本檢索方 法和部分基于手動(dòng)開放式的各種文件去瀏覽需要的內(nèi)容。設(shè)計(jì)中這個(gè)效率非常低下的方法在數(shù) 據(jù)庫(kù)總成數(shù)據(jù)大型化后已成為嚴(yán)重的問題，同時(shí)還需要設(shè)計(jì)師訪問 CAD 軟件。昂貴的三維 CAD 軟件將有助于搜索數(shù)據(jù)庫(kù)而不需要訪問 CAD 軟件。如果一個(gè)設(shè)計(jì)師能在不使用 CAD 軟件的 情況下夠獲取裝配信息進(jìn)行設(shè)計(jì)則將有助于降低成本。 1.2.2 現(xiàn)有的搜索方法及其局限性 設(shè)計(jì)師搜索方式有幾種類型。如果裝配體儲(chǔ)存在硬盤中，他們可以使用文件名稱來搜索。 這種方法只在文件命名有規(guī)定方式的單個(gè)工程中有意義。然而，在大公司中發(fā)展和部署基于文 件命名規(guī)則是不實(shí)際的。越來越多的集團(tuán)開始在不同的地方建造制造工廠，合并兩個(gè)在不同的 地方的不同公司也將導(dǎo)致兩個(gè)完全不同的命名規(guī)則。這種方式只能滿足不同生產(chǎn)單位各自的需 要，而不能作為一個(gè)裝配搜索系統(tǒng)中搜索的標(biāo)準(zhǔn)。在這種情況下，在兩個(gè)不同的生產(chǎn)單位中設(shè) 計(jì)者不能有效的參考并使用產(chǎn)品的信息進(jìn)行設(shè)計(jì)。新的約定協(xié)議也無法用來搜索公司遺留下來 的數(shù)據(jù)。任何公司通常都會(huì)有非常龐大的遺留數(shù)據(jù)，其均很難通過改變或?qū)嵤┟麉f(xié)定來達(dá)到 公司要求。另一種方法是在產(chǎn)品數(shù)據(jù)管理(PDM)數(shù)據(jù)庫(kù)中附文本符號(hào)標(biāo)識(shí)一起保存，這個(gè)方式 也只能提供有限的搜索能力和有限的標(biāo)識(shí)能力。此外，裝配還需要手動(dòng)注釋說明，搜索標(biāo)識(shí)文 本也不能表示機(jī)械裝配的所有屬性。此外，基于這些文本屬性搜索部件不可避免人為的錯(cuò)誤詮 釋，從而降低了內(nèi)容準(zhǔn)確性。如今，基于圖形搜索的工具層出不窮。然而，通過這些工具搜索 卻常常搜索出不是非常有用處的部件。他們只顯示整體造型的裝配而不能解釋零件結(jié)構(gòu)中存在 的配合關(guān)系。整體造型是一種特殊裝配而有所不同。例如，在圖 1.3 中四連桿機(jī)構(gòu)就有不同的 位置形式，只有文本標(biāo)識(shí)搜索工具和基于圖形的搜索工具顯然是不足以搜索零件。這項(xiàng)研究已 經(jīng)為公司提供了一種基于內(nèi)容的搜索工具服務(wù)于產(chǎn)品裝配設(shè)計(jì)過程當(dāng)中。 圖1.3：不同相對(duì)位置的曲柄滑塊機(jī)構(gòu)的部分 1.3 研究的問題 1.3.1 軟件搜索系統(tǒng)所需的特點(diǎn) 此項(xiàng)研究的目的是建立一個(gè)基于裝配體內(nèi)容能從現(xiàn)有的數(shù)據(jù)庫(kù)中搜索出現(xiàn)不同的特征的 檢索系統(tǒng)。采用此系統(tǒng)來搜索整個(gè)數(shù)據(jù)庫(kù)中典型裝配包含的特征。因此，此系統(tǒng)需要支持全面 的、用戶可以定義的基于特征列表總成的搜索，系統(tǒng)包括的特點(diǎn)會(huì)在后面的章節(jié)列舉。系統(tǒng)應(yīng) 當(dāng)足夠靈活方便用戶通過搜索出任何組合的特點(diǎn)，搜索出或太或少的結(jié)果。因此，如果搜索結(jié) 果太少則提醒用戶減少搜索條件（精準(zhǔn)度）。同樣，如果搜索結(jié)果過多則能為使用者進(jìn)行迭代 求精。這就要制約裝配特征的搜索，并執(zhí)行搜索和再精煉搜索，本搜索算法是一種有效的產(chǎn)生 精準(zhǔn)及一定準(zhǔn)確數(shù)量搜索結(jié)果的算法。用戶在任何時(shí)候搜索都應(yīng)能夠?yàn)槠渑懦魏窝b配體而進(jìn) 一步再搜索。最后，本系統(tǒng)應(yīng)具有一個(gè)易于使用的界面和能夠幾秒鐘內(nèi)從一個(gè)裝配數(shù)據(jù)庫(kù)中找 到有用信息的效率。本研究的目的如圖 1.4 所示： 搜索標(biāo)準(zhǔn) 算法標(biāo)準(zhǔn) 搜索策略 基于產(chǎn)品裝配內(nèi)容建立的搜索軟件 圖 1.4：研究的目的 本論文描述了一種基于裝配數(shù)據(jù)庫(kù)系統(tǒng)運(yùn)行的搜索。接下來的研究發(fā)現(xiàn)了已經(jīng)各種各樣的 所描述的搜索模塊應(yīng)用于現(xiàn)代的 CAD 系統(tǒng)當(dāng)中。其也是一種基于機(jī)械裝配體內(nèi)容搜索開發(fā)的 模塊算法。同時(shí)這些算法已應(yīng)用到系統(tǒng)中，是本論文插圖結(jié)合實(shí)例說明使用的原型系統(tǒng)。 1.3.2 為搜索識(shí)別和提取裝配的特征 已發(fā)表的文獻(xiàn)中的裝配模型 驗(yàn)證數(shù)據(jù)的可用性 Pro/Engineer Unigraphics 添加額外的裝配特征 通用搜索標(biāo)準(zhǔn) 最初的研究部分是為了確定一個(gè)裝配體的特征的全面性，這些信息應(yīng)包括特征所有可能的 信息以符合設(shè)計(jì)師搜索裝配的需求。我們決定以 Pro/Engineer 軟件為基礎(chǔ)，參考現(xiàn)有的 CAD 系統(tǒng)和裝配建模技術(shù)領(lǐng)域，建立一個(gè)列表集合所有的特征方便進(jìn)行搜索。因此，我們的所有特 征列表研究可在 Pro/Engineer 軟件中使用，我們開發(fā)了一個(gè)初步支持基于裝配特征搜索的列表 模型應(yīng)用在 Pro/Engineer 軟件。為確保這些特征并不只是針對(duì) Pro/Engineer 軟件，我們還確保 其在另一個(gè)計(jì)算機(jī)輔助設(shè)計(jì)(CAD)系統(tǒng)——Unigraphics 軟件中有效，并保證我們的列表信息在 Unigraphics 軟件中也兼容。研究數(shù)據(jù)顯示該搜索能從 CAD 系統(tǒng)中提取信息，從 CAD 系統(tǒng)應(yīng) 用編程接口(API)提取的數(shù)據(jù)可在裝配簽名前執(zhí)行，基于 Pro/Engineer 的特征能使用于 CAD 系 統(tǒng) API 程序接口并驗(yàn)證簽名，這將使搜索系統(tǒng)能夠在任何 CAD 系統(tǒng)中獨(dú)立運(yùn)行。圖 1.5 總結(jié) 裝配特征識(shí)別的過程。 圖 1.5：裝配特征識(shí)別方法 相互關(guān)系 裝配體 零件 運(yùn)動(dòng)副 配合 每一個(gè)裝配都會(huì)伴隨大量的相關(guān)特征，利用不同特征直觀上特殊的差異進(jìn)行區(qū)分，并在這 個(gè)基礎(chǔ)上開發(fā)搜索系統(tǒng)，但搜索系統(tǒng)要有一個(gè)直觀的界面。特征鑒定分為四個(gè)主要的類型，在 裝配設(shè)計(jì)過程中為其特征分類。裝配特征層級(jí)如圖 1.6 所示： 圖 1.6：裝配特征層級(jí) 然后，開發(fā)一種即在一個(gè)裝配中保存有所有特征的簽名也獨(dú)立于任何 CAD 系統(tǒng)的合適格 式，這種裝配格式作為保存簽名裝配體的基礎(chǔ)，使裝配位置的每部分裝配都有一個(gè)獨(dú)立圖形信 息表示運(yùn)動(dòng)副。由基本部件加上附加部件組成了運(yùn)動(dòng)副，每種運(yùn)動(dòng)副又只描述一種類型。通過 保存的簽名數(shù)據(jù)的運(yùn)動(dòng)副和配合條件可以創(chuàng)建一個(gè)圖表，只用來表示在 Pro/Engineer 中的配合 條件和運(yùn)動(dòng)副。不需要使用 CAD 文件，簽名編號(hào)就完全可以表示裝配，因此，在任何 CAD 軟件中可以獨(dú)立查看并搜查這些裝配。因?yàn)檫@些簽名編號(hào)不依賴于任何一個(gè)單獨(dú)的 CAD 軟件， 所以可以使用不同的 CAD 軟件用來瀏覽和搜索裝配設(shè)計(jì)。這種可以在設(shè)計(jì)過程使用不同的 CAD 軟件和不同公司數(shù)據(jù)交換的能力對(duì)大公司來說是非常有用的。 1.3.3 不同的特征的搜索方法 許多裝配體的特征都是基本文字或基本的幾何圖形，因此基于文本、字符串匹配的搜索算 法都是可取的。這種算法和字符串近似準(zhǔn)確匹配這個(gè)難題已經(jīng)研究得很透徹了。為了做搜索系 統(tǒng)曾提出各式各樣的想法，比如做精確幾何形狀比較、匹配。本研究將進(jìn)行實(shí)驗(yàn)比較搜索時(shí)間 效率來排序每一種方法?；谒阉鞑糠值慕Y(jié)果來匹配圖形的相似度。用戶需定義一個(gè)在裝配體 數(shù)據(jù)庫(kù)中能部分代表配合條件的圖形，這兩個(gè)圖需要相互匹配，這就需要一種圖形兼容性的算 法。采用基于多運(yùn)動(dòng)狀態(tài)形勢(shì)搜索，當(dāng)數(shù)據(jù)庫(kù)保存有一種連接介于兩種不同的運(yùn)動(dòng)狀態(tài)時(shí)則應(yīng) 當(dāng)出現(xiàn)多種情況的搜索結(jié)果。這就需要建立一種能提供查詢數(shù)據(jù)庫(kù)又能保存有效配合關(guān)系數(shù)據(jù) 的數(shù)據(jù)結(jié)構(gòu)。這種搜索、查詢方法涉及裝配數(shù)據(jù)庫(kù)中字符串準(zhǔn)確比較，并找到存在相互關(guān)聯(lián)。 1.4 論文概要 論文有以下安排，有四種不同主要搜索定義類型用于搜索裝配的特征，將在后面不同的章 節(jié)說明。其中包含總裝配體中特征的大小和數(shù)目統(tǒng)計(jì)等部分，第三章將討論基于這些統(tǒng)計(jì)數(shù)字 的搜索，將會(huì)有一部分總結(jié)裝配體特征的材質(zhì)、尺寸等特征。頁(yè)可以使用裝配體特征中一種不 常用的部分進(jìn)行搜索。第四章討論一種利用裝配體部分特征進(jìn)行的搜索，其中配合關(guān)系在裝配 體中扮演著重要的角色。因此，我們需要它支持基于文本類型及配合條件進(jìn)行的搜索，這種搜 索將在第 5 章中闡述。通過兩個(gè)部件定義裝配體運(yùn)動(dòng)副的情況，裝配自由度的限制決定了運(yùn)動(dòng) 副的種類。因此，我們需要基于剛性連接搜索算法的支持。這種搜索方式將在第六章中闡述。 第七章論述了實(shí)施中細(xì)則方面的研究。第八章概括研究的預(yù)期結(jié)論及此領(lǐng)域未來的研究方向。 相關(guān)研究 第二章 本章提出了一種基于裝配建模及表示方法、零件幾何形狀裝配搜索和子圖同構(gòu)審查功能的 先進(jìn)搜索引擎，經(jīng)過廣泛研究的裝配建模及表示方法對(duì)于搜索引擎中的鑒別特征搜索和部件表 示功能尤為重要，為實(shí)現(xiàn)基于這些重要部件的搜索已經(jīng)提出各種各樣的方法?，F(xiàn)有基于裝配體 搜索技術(shù)多是跟據(jù)考量與識(shí)別這些裝配重要的數(shù)據(jù)特征、功能和性能，及裝配體的局限性提出 的。一直嘗試用圖表示各種不同零件之間的配合情況，圖的一部分可以用來尋找裝配，這便可 以實(shí)現(xiàn)了解、研究更多的子圖同構(gòu)。這一章的內(nèi)容如下：第 2.1 節(jié)討論裝配建模方法；第 2.2 節(jié)討論基于部分內(nèi)容搜索的方法；第 2.3 節(jié)討論了基于裝配內(nèi)容搜索的功能和性能；最后第 2.4 節(jié)概述子圖同構(gòu)。 2.1 裝配建模 裝配常見的解釋是根據(jù)一定的配合關(guān)系把零件集合到一起。許多的裝配體只是利用最基本 的配合關(guān)系把零件結(jié)合到一起， 其只是努力強(qiáng)調(diào)功能和性能之間的基本聯(lián)系。為了支持計(jì)算 機(jī)輔助裝配建模設(shè)計(jì)而在電腦上嘗試各種各樣裝配表示方式，該模型是總結(jié)不同研究小組得出 的不同特征和不同裝配應(yīng)用的基礎(chǔ)上提出的。為實(shí)現(xiàn)基于內(nèi)容搜索，我們需要評(píng)估這些方案并 決定哪些對(duì)搜索引擎中有用。根據(jù)這些方案所提供了依據(jù)，建立可在基于計(jì)算機(jī)的搜索系統(tǒng)中 使用的特征標(biāo)識(shí)的信息的格式。本節(jié)總述不同學(xué)者提出的搜索方案。 CAD 系統(tǒng)通常會(huì)有兩個(gè)獨(dú)立的模塊分別創(chuàng)建零件和裝配體， 個(gè)別零件的幾何形狀是根據(jù) 產(chǎn)品裝配體的需要建立的，CAD 系統(tǒng)中零件的位置是根據(jù)裝配約束條件確定的。用戶可以在 CAD 系統(tǒng)中選擇和指定連接點(diǎn)的連接順序。關(guān)于配合條件和節(jié)點(diǎn)數(shù)據(jù)可以從 CAD 系統(tǒng)中提取。 現(xiàn)有的 CAD 系統(tǒng)不存儲(chǔ)裝配體的功能和性能數(shù)據(jù)。 Gupta 等人提出一種智能的裝配建模與仿真環(huán)境(IAMS)裝配仿真及可視化方案，其可提供 詳細(xì)的數(shù)據(jù)結(jié)構(gòu)來表示零件和裝配的工具、工作空間和計(jì)劃。他們這種嵌套列表式的表現(xiàn)形式 的有組織所有部件和存儲(chǔ)屬性的能力。每部分都有一個(gè)名字描述、一個(gè)指向的幾何體、和一個(gè) 轉(zhuǎn)變關(guān)聯(lián)，這使得每部分零件在裝配體中都有其裝配位置。并可以擴(kuò)展到存儲(chǔ)的零件的文本屬 性。由每一個(gè)聯(lián)合類型、名稱，形成其共同的基礎(chǔ)和附加部分的名稱，配合條件數(shù)據(jù)存儲(chǔ)在可 以讀寫的簽名圖表中。方案中提供一個(gè)裝配的編輯器讓用戶定義屬性、裝配序列和計(jì)劃。 在本文提出的研究中，Gupta 等人定義的裝配格式作為基礎(chǔ)來儲(chǔ)存簽名裝配體。他們提出 有關(guān)裝配的單一數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)形式，并可以擴(kuò)展到包括在本論文中提出的附加條件的數(shù)據(jù) 當(dāng)中。他們所提出的許多數(shù)據(jù)文件都是裝配文件和零件文件相結(jié)合，并在文中用來表示裝配體。 然而，他們的工具產(chǎn)生數(shù)據(jù)之間的零件幾何接觸部分取決于用戶輸入?yún)?shù)，并利用裝配體裝配 序列的編輯。利用這些模型的能夠建立一個(gè)基于產(chǎn)品裝配內(nèi)容的搜索工具，因?yàn)樗麄兛梢援a(chǎn)生 的數(shù)據(jù)不需要用戶手工輸入產(chǎn)生，然而無法在共同的 CAD 系統(tǒng)中使用所產(chǎn)生的裝配模型。因 此本文的研究工作的一部分就是從 CAD 模型提取的裝配體數(shù)據(jù)用來表示裝配關(guān)系。 Noort 等人提出一個(gè)結(jié)合裝配數(shù)據(jù)表示它部分產(chǎn)品和組裝等的方案。這個(gè)組合表示保證任 何部分關(guān)系或裝配關(guān)系的變化都能反映在另一個(gè)數(shù)據(jù)關(guān)系中，它為部分特征和裝配特征的更新 或任何其他的改變時(shí)提供了獨(dú)立的表示觀點(diǎn)的方法。該關(guān)系方案支持概念設(shè)計(jì)、部件詳細(xì)設(shè)計(jì)、 裝配設(shè)計(jì)、制造、裝配規(guī)劃部分的觀念。 作為一個(gè)集中零部件的裝配體以及單個(gè)零件裝配對(duì)于基于內(nèi)容的檢索系統(tǒng)都有重要的，通 過這種方式提供了一個(gè)聯(lián)合關(guān)系的方法。這種表現(xiàn)方式在自然界非常通用，并將因此而被用于 多個(gè)應(yīng)用程序就像裝配序列規(guī)劃和部分制造一樣。作為相關(guān)的意見，在任一部件或組裝裝配的 變化時(shí)的影響都是顯而易見的。然而，這些關(guān)聯(lián)不使用于匹配 CAD 文件規(guī)定的狀態(tài)，而是更 高層次的關(guān)系，其能推斷出來的部件的幾何形狀?，F(xiàn)有的 CAD 系統(tǒng)并不支持這樣的關(guān)系，盡 管這些能更直觀的記憶和使用。因此，高級(jí)關(guān)系不能方便地用于裝配搜索。 Nanda 等人提出了目前在產(chǎn)品設(shè)計(jì)的各階段利用基于網(wǎng)絡(luò)本體語(yǔ)言（OWL）系統(tǒng)進(jìn)行研 究和部署的方案。該模型滿足消費(fèi)者對(duì)產(chǎn)品功能和零件的需要。運(yùn)用該模型可為每一個(gè)需要提 供一個(gè)函數(shù)映射組件，并用實(shí)體列表來完成這個(gè)功能。該項(xiàng)功能提供使用 OWL 含義表示數(shù)據(jù) 結(jié)構(gòu)，OWL 表示比 XML 表示多使用了這些數(shù)據(jù)結(jié)構(gòu)。利用描述邏輯(DL)使一個(gè)以計(jì)算機(jī)為 基礎(chǔ)的語(yǔ)義解釋，而完全不需要人為介入。 從這種方法的優(yōu)勢(shì)就是共享各部分不同類型的設(shè)計(jì)，它也將會(huì)是裝配設(shè)計(jì)的各個(gè)階段中尋 找設(shè)計(jì)信息的過程當(dāng)中很有幫助。該模型方案有助于捕捉功能和運(yùn)動(dòng)裝配， OWL 表示法可以 用于創(chuàng)造基于函數(shù)和運(yùn)動(dòng)裝配內(nèi)容的搜索工具。 然而這種方法不用考慮裝配的形式。本研究 中提出了基于他們的結(jié)構(gòu)特點(diǎn)的算法搜索裝配，因此我們并沒有用過這種表示方案。而本文建 立的標(biāo)簽就可以很容易地存儲(chǔ)在 OWL 格式當(dāng)中，因此本文所做的工作跟這種方法是相輔相成 的。 Rachuri 等人提出了一種用對(duì)象為導(dǎo)向的開放式裝配模型（OAM）來代表機(jī)電組件的裝配 設(shè)計(jì)的定義，并用這個(gè)這個(gè)模型表示系統(tǒng)格式、功能和運(yùn)動(dòng)方式。裝配體由幾何部件和其他部 件配合約束和零件間運(yùn)動(dòng)關(guān)節(jié)裝配而成，設(shè)計(jì)中只考慮用幾何形態(tài)的形式表示；用該功能來表 示輸入/輸出之間的變換；用裝配體表示其運(yùn)動(dòng)和有意無意的物質(zhì)相互作用。如此說來其便是 一個(gè)行為函數(shù)的子集，它是一個(gè)有概念層次的模型。該模型包括工件的所有父類或子類，裝配 有關(guān)的信息都存儲(chǔ)在類中。該模型也有儲(chǔ)存設(shè)計(jì)的理念。如大小的其他信息、幾何公差、材料 會(huì)附在單獨(dú)的公差模型類當(dāng)中，并使用統(tǒng)一建模語(yǔ)言（UML）來表示裝配體。 可用于協(xié)同設(shè)計(jì)的 OAM 功能，可以用于基于任何形式、功能或裝配特征的搜索系統(tǒng)的設(shè) 計(jì)中。因此，該模型可以用于設(shè)計(jì)的任何階段。這種模式的核心產(chǎn)品模型（CPM）和 STEP 標(biāo) 準(zhǔn)可擴(kuò)展到表示裝配體，本論文研究工作提出的這個(gè)模式可以擴(kuò)展使用到任意獨(dú)立 CAD 系統(tǒng) 組件的簽名中，這種由 Rachuri 等人提出的表示模式，能減少作為文本文件的簽名裝配從 CAD 數(shù)據(jù)庫(kù)中的存取時(shí)間。該表示模式，也可以作為他們從沒有任何人工干預(yù)的組件中提取數(shù)據(jù)的 工具，并以能夠獲取裝配的功能和性能的能力確保這項(xiàng)研究工作持續(xù)下去。 Wang and Ozsoy 提出用裝配圖形的形式表示裝配，使用零件和零件之間初級(jí)和末級(jí)節(jié)點(diǎn) 的形式表示裝配體。設(shè)置不同配合情況來記錄每一個(gè)零件或子裝配體的每個(gè)構(gòu)件之間的連接， 并利用這一數(shù)據(jù)結(jié)構(gòu)進(jìn)行裝配公差分析，利用配合和裝配的總體尺寸來查找出各個(gè)環(huán)節(jié)公差鏈 后得出基本方程式。 本論文使用了 Wang and Ozsoy 提出的基于圖形表示方案，然而 Wang and Ozsoy 提出的方 案只支持三種配合關(guān)系。用匹配、相向和平行來表示零件或裝配體的位置，然而這三個(gè)交配條 件不足以描述零件在裝配組件沒有接觸情況下的裝配約束。本論文的研究擴(kuò)展了數(shù)據(jù)結(jié)構(gòu)涵蓋 到在 Pro/Engineer CAD 系統(tǒng)所有可能出現(xiàn)的配合條件。 2.2 部分搜索技術(shù) 裝配體是一個(gè)基于特征組成的零件的集合，并可以在搜索使用。因此，本研究支持根據(jù)裝 配組成部件搜索。其涉及到基于部件組成部分的幾何形狀、文本屬性進(jìn)行搜索，并可在目前的 PLM 系統(tǒng)中基于文本屬性搜索有字符串匹配的操作?？蓪⒒谖谋具M(jìn)行的搜索擴(kuò)展到搜索系 統(tǒng)中，基于文本搜索的技術(shù)將在本論文第四章說明?？商峁┙o用戶不同方法的基于幾何進(jìn)行搜 索的應(yīng)用程序。許多的研究小組都已經(jīng)提出了不同部件相似性評(píng)估，及搜索工具與綜合搜索技 術(shù)。此外，該技術(shù)是基于幾何形狀的部件，并可以用于確定裝配的搜索標(biāo)準(zhǔn)。本節(jié)討論基于搜 索技術(shù)的部件幾何形狀。 2.2.1 基于部件查詢的搜索 在許多應(yīng)用中，部件查詢的目標(biāo)是在所有裝配體的零件數(shù)據(jù)庫(kù)中找出有類似的部分。這樣 的搜索定位此類零件方式是如圖 2.1 所示。一種常見的情況如搜索可重用的類似部分輕微修改 的夾具組件，并已開發(fā)了各種技術(shù)進(jìn)行 3D 實(shí)體模型之間的相似性評(píng)估。兩個(gè) 3D 零件之間的 最新設(shè)計(jì)的部件 自動(dòng)搜索數(shù)據(jù)庫(kù)中零 件幾何相似的部分 零件數(shù) 據(jù)庫(kù) 數(shù)據(jù)庫(kù)中發(fā)現(xiàn)相似的部分 相似性評(píng)估主要包括兩個(gè)步驟。第一步是計(jì)算物體的形狀、標(biāo)簽；第二個(gè)步驟是比較合適形狀 的距離函數(shù)。主要利用造型相似性評(píng)估領(lǐng)域的技術(shù) 圖2.1：零件搜索的架構(gòu) 作為這個(gè)形狀相似性評(píng)價(jià)方法中描述的對(duì)象代表著進(jìn)行全球幾何性質(zhì)測(cè)量的形狀分布函 數(shù)，這種技術(shù)可以用來作為第一個(gè)濾波器以確定不同的對(duì)象，在文獻(xiàn)[03]中將為新濾波器形狀 匹配提供了理論依據(jù)，這些過濾技術(shù)已經(jīng)應(yīng)用到大型機(jī)械的零件數(shù)據(jù)庫(kù)中。在文獻(xiàn)[04]，每一 個(gè) 3D 模型和單元所代表的不變矩矢量元件、幾何參數(shù)、矢量值和特征樹形狀。 基于轉(zhuǎn)換成實(shí)體模型的圖形技術(shù)歸功于用圖形表示的各種幾何和拓?fù)鋵?shí)體模型中實(shí)體之 間的關(guān)系。在已使用的圖形類型中，有簽名型號(hào)的圖和大分辨率的 Reeb 圖。雖然這些技術(shù)易 于實(shí)現(xiàn)，但可能沒有有很高的辨別能力。 2.2.2 基于草圖的搜索 3D 模型并不總是作為有空搜索、查詢的基礎(chǔ)，因?yàn)閯?chuàng)建一個(gè)復(fù)雜的三維模型零件作為查 詢會(huì)非常耗時(shí)。這種方式可以幫助設(shè)計(jì)師使用相關(guān)特性 2D 草圖代替 3D 模型。因此，在許多 搜索設(shè)計(jì)再利用的應(yīng)用程序中用戶可能都不會(huì)建立詳細(xì)的 CAD 模型進(jìn)行搜索。在這種情況下， 為用基礎(chǔ)工具零件草圖代替也可以用來尋找所需的部分或定位一個(gè)查詢的部分。這些草圖通常 是標(biāo)準(zhǔn)的 2D 圖，如頂視圖、前視圖或側(cè)面視圖的一部分。 之前提出的技術(shù)能夠讓用戶免費(fèi)的根據(jù)基本草圖數(shù)據(jù)庫(kù)檢索 3D 零件。使 3D 零件在用戶 檢索后有進(jìn)一步的反饋，用戶可在三個(gè)視圖的基礎(chǔ)上搜索每一部分。該技術(shù)包括三個(gè)主要步驟： （1）視 3D 零件方向確定；（2）生成 2D 草圖；（3）計(jì)算草圖和 3D 部分的預(yù)測(cè)之間的相似 程度。這種相似性的措施是轉(zhuǎn)換不變的情況下，在用二維視圖進(jìn)行比較的基礎(chǔ)上獲得由相交的 二維圖像的距離變換成一個(gè)同心圓的傅里葉系數(shù)函數(shù)。 裝配搜索技術(shù)可以推廣整合到基于零件基本草圖的搜索工具中，并用于尋找構(gòu)成部件。該 工具也可以找到用數(shù)據(jù)庫(kù)類似的部分來作為一個(gè)查詢的部分。該搜索技術(shù)的一個(gè)主要應(yīng)用便是 搜索裝配體中的草圖，基于草圖的裝配體用零件之間的配合狀態(tài)表示。裝配搜索系統(tǒng)采用基于 零件之間的配合狀態(tài)圖形表示，并允許用戶自定義搜索裝配時(shí)使用這些圖的一部分。這項(xiàng)搜索 技術(shù)基于零件草圖搜索技術(shù)，用戶可以在零件數(shù)據(jù)庫(kù)中定義零件草圖進(jìn)行搜索。 2.2.3 零件數(shù)據(jù)庫(kù)可視化瀏覽的搜索 在很多情況下，用戶并沒有需要查詢的條件。此外，由于用戶對(duì)零件復(fù)雜性和工程制圖概 念的熟悉程度有限，這就不可能使用以草圖為基礎(chǔ)的查詢方法。在這樣的情況下,可視化瀏覽 CAD 數(shù)據(jù)庫(kù)便是一個(gè)有效的解決方法。 假設(shè)設(shè)計(jì)師想找到一個(gè)由上千個(gè)零件組成的設(shè)計(jì)數(shù)據(jù)庫(kù)中可重用的設(shè)計(jì)信息時(shí)，會(huì)產(chǎn)生有 兩種可能的情況：第一，設(shè)計(jì)師都有查詢部分和想要找到相似的部分查詢，在這種情況下基于 幾何學(xué)的搜索技術(shù)便可用于定位相似部分；然而，在另一種情況下設(shè)計(jì)師通過幾何搜索技術(shù)查 找時(shí)可能會(huì)不記得確切的部件幾何細(xì)節(jié)，在這種情況下用戶需要瀏覽 CAD 數(shù)據(jù)庫(kù)找到理想的 對(duì)象，一旦設(shè)計(jì)師找到所需部件的相似的一部分，他/她可以用于基于部件的查詢技術(shù)中。因 此，一個(gè)完整的系統(tǒng)可以協(xié)助設(shè)計(jì)師定位相似的零件幾何以及有用的可視化搜索。 一個(gè)類似的瀏覽能力已應(yīng)用于基于裝配搜索系統(tǒng)中，并利用該系統(tǒng)來瀏覽裝配體的 CAD 數(shù)據(jù)庫(kù)。用戶可以指定所有搜索標(biāo)準(zhǔn)的通配符來瀏覽整個(gè)數(shù)據(jù)庫(kù)的零件，同時(shí)還可以指定一些 可移除部分零件的搜索標(biāo)準(zhǔn)來瀏覽數(shù)據(jù)庫(kù)或?yàn)g覽其余配件，并為使用者提供了一個(gè)單獨(dú)的裝配 查看器工具來查看個(gè)別組件的詳細(xì)信息。 2.3 搜索的基本功能 在本論文研究工作描述了一個(gè)基于裝配形式的搜索系統(tǒng)，裝配體的功能和性能同樣重要。 其文本屬性能夠很好地描述本研究工作，可擴(kuò)展到搜索時(shí)使用工具自動(dòng)提取有效數(shù)據(jù)。盡管我 們現(xiàn)在的大部分陳述都是基于在設(shè)計(jì)過程中收集到的功能和性能信息。從 2.1 節(jié)中的文獻(xiàn)綜述 中可以推斷，現(xiàn)代 CAD 系統(tǒng)尚未不存儲(chǔ)這些設(shè)計(jì)資料的信息，而是依賴 PLM 這樣的外部工 具來存儲(chǔ)這些信息。本節(jié)討論在裝配體的功能和性能的基礎(chǔ)上尋找一些方法。 Shaffer 等人提出基于目前的 Web 服務(wù)可以整合一些不同的方法來搜索組件，并增加了額 外的功能，提供一個(gè) Web 服務(wù)描述語(yǔ)言（WSDL）文檔描述數(shù)據(jù)庫(kù)新的功能?？梢允褂弥薪?的 WSDL 文檔數(shù)據(jù)獲得該服務(wù)并生成目標(biāo)語(yǔ)言的數(shù)據(jù)接口。 這樣的一個(gè)系統(tǒng)，其優(yōu)點(diǎn)是它融合了現(xiàn)有的不同方法來搜索組件，并提供了一個(gè)可以用來 整合任何新方法的搜索框架。因此，設(shè)計(jì)師也就不用花時(shí)間去理解接口和研究不同搜索系統(tǒng)。 此外，設(shè)計(jì)者在設(shè)計(jì)過程中可以使用搜索系統(tǒng)計(jì)劃或估算成本。這個(gè)方法不使用關(guān)系數(shù)據(jù)庫(kù)模 型，從而不必事先索引模型的信息。Shaffer 等人提出的架構(gòu)可為這篇論文中提出的基于 web 服務(wù)的搜索工具服務(wù)。這將使這個(gè)搜索工具獨(dú)立于任何 CAD 軟件，并可擴(kuò)展到以功能和性能 為基礎(chǔ)的裝配體搜索中。 Kopena 等人提出了一個(gè)基于語(yǔ)義 Web 的概念設(shè)計(jì)用來代表和訪問組件的方法。他們發(fā)明 了描述概念設(shè)計(jì)界面的產(chǎn)品，并可以用來詮釋設(shè)計(jì)與基于這些注解進(jìn)行搜索，同時(shí)還可用于分 類設(shè)計(jì)。該系統(tǒng)應(yīng)用這些類描述進(jìn)行搜索。相比目前所使用的技術(shù)語(yǔ)義 Web 不僅允許有效的 收集和組織大量數(shù)據(jù)，還允許加價(jià)出版設(shè)計(jì)。使用語(yǔ)義 Web 建立定義描述產(chǎn)品裝配的邏輯， 因此該方法有自動(dòng)推理、識(shí)別裝配體的功能。 在概念設(shè)計(jì)階段，他們還提出一種用于來捕捉結(jié)構(gòu)和功能設(shè)計(jì)的方法。一旦結(jié)構(gòu)和功能確 定了, 搜索引擎便可以在設(shè)計(jì)資源庫(kù)中定義。在這個(gè)系統(tǒng)中可以創(chuàng)造集標(biāo)注功能和流動(dòng)功能于 一體的三維草圖。在系統(tǒng)中推理者可以簽名、描述類。在數(shù)據(jù)庫(kù)中進(jìn)行搜索得到的所有設(shè)計(jì)類 的描述結(jié)果均可反饋給設(shè)計(jì)師，基于語(yǔ)義 Web 的方法可以有效的提高搜索軟件的效率。組成 簇?cái)?shù)據(jù)庫(kù)中的類似組件可用于分類設(shè)計(jì)，這將有助于提高搜索軟件的效率。由 Kopena 等人提 出的這種方法有益在設(shè)計(jì)過程中捕捉裝配體的功能。然而，這種方法不能用于查找傳統(tǒng)的 CAD 數(shù)據(jù)信息，傳統(tǒng)的裝配的格式將會(huì)失效。截至目前，沒有一個(gè)工具可以從沒有任何人機(jī)互動(dòng)的 傳統(tǒng)裝配數(shù)據(jù)庫(kù)中提取數(shù)據(jù)。盡管任何公司組織的數(shù)據(jù)庫(kù)中傳統(tǒng)數(shù)據(jù)都占有很大的部分，卻還 是使用這種卻僅僅適用于新設(shè)計(jì)的方法。 Karnik 等人提供方法，能夠?qū)υ谠O(shè)計(jì)過程中所做的更改的零件幾何形狀進(jìn)行設(shè)計(jì)信息搜索， 最終設(shè)計(jì)可視化的裝配導(dǎo)航系統(tǒng)?？墒蛊髽I(yè)很容易的在一臺(tái)計(jì)算機(jī)上使用搜索工具獲取計(jì)算機(jī) 可識(shí)別的格式信息。該系統(tǒng)還將提供了裝配體中各個(gè)部件之間的技術(shù)要求和技術(shù)規(guī)范。該系統(tǒng) 包括功能建模，基本原理建模和建模設(shè)計(jì)歷史。根據(jù)裝配不同方面的搜索工具已整合在一個(gè)框 架中。 該系統(tǒng)有益于對(duì)部門產(chǎn)品的 CAD 裝配體的功能和設(shè)計(jì)歷史進(jìn)行搜索。然而，只有設(shè)計(jì)建 模者能夠利用這些數(shù)據(jù)。在更新 CAD 模型后，部門數(shù)據(jù)庫(kù)中的傳統(tǒng) CAD 數(shù)據(jù)的設(shè)計(jì)歷史將 會(huì)失效。使用工具并不能推斷出產(chǎn)品 CAD 裝配體的功能。因此，這個(gè)工具不能用于基于內(nèi)容 的搜索系統(tǒng)。該方法能夠結(jié)合建立基于產(chǎn)品裝配內(nèi)容的搜索工具，當(dāng)所需資料時(shí)即開放給所有 數(shù)據(jù)庫(kù)。 Bohm 等人提出了以存檔功能為基礎(chǔ)的設(shè)計(jì)生成設(shè)計(jì)理念，使用指數(shù)矩陣和形態(tài)學(xué)矩陣技 術(shù)來產(chǎn)生設(shè)計(jì)思路。他們指出，76％的指定子函數(shù)返回結(jié)果，平均 61.35％組成部分可以通過 使用形態(tài)的搜索功能產(chǎn)生。并使用功能的基礎(chǔ)語(yǔ)言來形容的功能，由一個(gè)名詞描述流和動(dòng)詞描 述功能，搜索后會(huì)產(chǎn)生類似功能的構(gòu)件。 形態(tài)學(xué)矩陣由該方法手動(dòng)操作生成，并必須有從傳統(tǒng)的 CAD 數(shù)據(jù)中自動(dòng)提取矩陣的方法。 這種方法可以結(jié)合不同的子功能，并返回它們作為單一的輸入查詢的結(jié)果。該方法也考慮將該 功能使用于其他領(lǐng)域，例如機(jī)電配件。然而需要用戶選擇輸入領(lǐng)域進(jìn)行搜索。作者聲明增加數(shù) 據(jù)庫(kù)的大小將增加主要搜索目標(biāo)的生成。 2.4 子圖同構(gòu)的概述 如果兩圖形的同一節(jié)點(diǎn)和邊之間存在一一對(duì)應(yīng)的映射關(guān)系，則兩圖同構(gòu)。倘若兩圖拓?fù)渥?圖同構(gòu)，那么一個(gè)圖形一些節(jié)點(diǎn)和邊也與另一個(gè)圖形所有的節(jié)點(diǎn)和邊之間存在著一一對(duì)應(yīng)的映 射。子圖同構(gòu)問題屬于 NP（完全）問題。該研究涉及類似于子圖同構(gòu)的兼容問題求解圖形。 本節(jié)將討論解決子圖同構(gòu)問題的各種方法。 Ullmann 曾提出方法試圖解決子圖同構(gòu)問題，他試圖用多級(jí)優(yōu)先樹型搜索的方法來解決這 個(gè)問題，并窮舉反饋搜索結(jié)果。早期大部分的搜索都是用反饋的方法來解決這個(gè)問題，用該方 法同時(shí)處理兩個(gè)圖。這種方法使用一個(gè)用對(duì) 1 和 0 作為元素的鄰接矩陣，使用一個(gè)改良程序來 連續(xù)推斷回饋搜索結(jié)果以減少節(jié)點(diǎn)訪問，找出兩個(gè)圖形之間的同構(gòu)，但該方法僅供測(cè)試連接圖。 該算法仍十分受歡迎，并且用來查詢數(shù)量有限的節(jié)點(diǎn)和邊的圖形。在許多有效的優(yōu)化精簡(jiǎn) 搜索空間技術(shù)的基礎(chǔ)上 Ullmann 提出了反饋方法。然而，這種算法并不能在查詢圖存在大量節(jié) 點(diǎn)的情況下有效。因?yàn)檫@種算法沒有考慮到任何以前的圖形節(jié)點(diǎn)查詢知識(shí)和數(shù)據(jù)庫(kù)圖表之間的 通信，我們提出的算法是模仿這種方法。在本論文的研究不同搜索所有同構(gòu)卻能通過一個(gè)實(shí)例 可以在較少的時(shí)間內(nèi)與 Ullmann 提出的方法進(jìn)行比較。 Yu 和 Wang 已經(jīng)使用了一種 2D 連續(xù)的神經(jīng)網(wǎng)絡(luò)模型得到一個(gè)子圖中同構(gòu)于查詢圖表的圖 形。該算法就使用了連接圖，并建立一個(gè)兩個(gè)圖相同數(shù)量的節(jié)點(diǎn)神經(jīng)網(wǎng)絡(luò)。用一個(gè)功能函數(shù)定 義有關(guān)參數(shù)，并推導(dǎo)出網(wǎng)絡(luò)中傳遞函數(shù)。該這種方法中使用隨機(jī)或已定的神經(jīng)元數(shù)進(jìn)行函數(shù)初 始化，并用四階的龍格-庫(kù)塔法來解決方程。 他們定義了子圖同構(gòu)的基本條件，并可以在任何解決子圖同構(gòu)的方法中用作修剪條件。在 這種方法中使用的修剪條件在本質(zhì)上是通用的，可用于任何子圖同構(gòu)的方法。本論文采用由 Yu 等人提出的修剪技術(shù)。然而，Ullmann 的方法更符合這篇論文的邊界條件。因此，在這項(xiàng) 研究中提出的子圖同構(gòu)算法并不基于由 Yu 等人提出以神經(jīng)網(wǎng)絡(luò)為基礎(chǔ)的方法。 Messmer 等人提出在決策樹中創(chuàng)建一個(gè)預(yù)處理步驟，并在使用這些決策樹時(shí)對(duì)子圖同構(gòu)進(jìn) 行檢測(cè)。同時(shí)他們還推薦了幾種減少?zèng)Q策樹的大小修剪技術(shù)，及建立決策樹模型轉(zhuǎn)換數(shù)據(jù)庫(kù)中 鄰接矩陣圖形。 他們聲稱，這種算法具有最壞情況下二次查詢圖中節(jié)點(diǎn)數(shù)量，并且在獨(dú)立模型圖與任意圖 形邊數(shù)減少時(shí)間復(fù)雜度。然而，建立決策樹的預(yù)處理環(huán)節(jié)并不包括這個(gè)時(shí)間復(fù)雜度。這種方法 的主要缺點(diǎn)是決策樹具有指數(shù)關(guān)聯(lián)。該算法的最壞情況是 O(Lmnn2)復(fù)雜度，其中 L 是圖形數(shù) 據(jù)庫(kù)中大小、m 是查詢圖號(hào)節(jié)點(diǎn)數(shù)、n 是模型圖中的節(jié)點(diǎn)數(shù)量。他們建議在子圖同構(gòu)測(cè)試時(shí)根 據(jù)之前的節(jié)點(diǎn)匹配以消除一些數(shù)據(jù)庫(kù)節(jié)點(diǎn)特有的排列圖，并確定子修剪技術(shù)的大小。然而，這 種方法還沒有用于制定的子圖同構(gòu)以減少?zèng)Q策樹的復(fù)雜性。 Fuchs 等人提出的容差算法，使用先前的知識(shí)查詢數(shù)據(jù)庫(kù)中圖與圖節(jié)點(diǎn)之間的關(guān)聯(lián)。他們 把數(shù)據(jù)庫(kù)中的圖形和外部信息傳播過程中圖形遞歸分解成子圖，該算法已經(jīng)應(yīng)用于 3D 建筑重 建圖像。他們也建議編輯包括外部信息圖形的數(shù)據(jù)結(jié)構(gòu)。 最壞的情況下使用先前知識(shí)的節(jié)點(diǎn)之間復(fù)雜度 O(Lmqq3)算法匹配不了解的節(jié)點(diǎn)，其中 L 是圖形數(shù)據(jù)庫(kù)中的數(shù)、m 為查詢圖中的節(jié)點(diǎn)數(shù)、q 是從查詢節(jié)點(diǎn)圖的數(shù)量。他們聲稱匹配兩個(gè) 節(jié)點(diǎn)這一步很有效，因?yàn)閳D形數(shù)據(jù)結(jié)構(gòu)整合了外部信息。該算法具有很好的圖形容差兼容性， 并可在查詢數(shù)據(jù)庫(kù)之前知道圖與圖節(jié)點(diǎn)之間的映射，顯著降低了 DFS 的空間搜索。同時(shí)，在 不了解本論文研究的任何有關(guān)知識(shí)時(shí)也可以結(jié)合數(shù)據(jù)庫(kù)檢索系統(tǒng)實(shí)現(xiàn)檢索。該方法為進(jìn)一步研 究有用的裝配體搜索系統(tǒng)。 Cordella 等人提出了一種大型圖表的算法。聲稱 Ullmann 的做法已經(jīng)取得了顯著的改善， 他們的做法幾乎能夠獨(dú)立查詢圖中的節(jié)點(diǎn)數(shù)量。該算法的主要貢獻(xiàn)之一是空間搜索過程中使用 了高效的內(nèi)存讀取結(jié)構(gòu)數(shù)據(jù)，該算法減少使用信息的匹配時(shí)間要?dú)w功于的關(guān)系圖與語(yǔ)法。 在該算法過程中用狀態(tài)空間表示法(SSR)匹配。其包括五個(gè)規(guī)則，包括節(jié)點(diǎn)句法和語(yǔ)義可 行性比較。五個(gè)規(guī)則中有兩個(gè)是用來檢測(cè)方案的可行性，另外三種用于修剪搜索樹。算法不承 擔(dān)任何約束圖的拓?fù)浣Y(jié)構(gòu)，因此其擁有通用的適用性。該算法利用向量提供常量訪問，從而降 低算法對(duì)成千上萬可用圖節(jié)點(diǎn)和邊的內(nèi)存需求，并使用深度優(yōu)先策略搜索圖形。在本研究中查 詢圖預(yù)計(jì)將有超過 15 個(gè)節(jié)點(diǎn)，因此該算法并沒有很好的圖形兼容性。此外，由于本研究中使 用的查詢和數(shù)據(jù)庫(kù)圖表有可以修剪搜索樹節(jié)點(diǎn)和邊的屬性，Ullmann 的基本方法已用于本算法。