題-1_100_100.jpg)
基本信息
- 項(xiàng)目名稱：
- 無向關(guān)系圖結(jié)點(diǎn)定位軟件
- 小類：
- 信息技術(shù)
- 大類：
- 科技發(fā)明制作A類
- 簡(jiǎn)介：
- 《無向關(guān)系圖結(jié)點(diǎn)定位軟件》是將描述結(jié)點(diǎn)及其關(guān)系的無向關(guān)系圖的文本文件或數(shù)據(jù)庫(kù)文件讀入，再經(jīng)過軟件確定結(jié)點(diǎn)在某個(gè)二維矩形區(qū)域內(nèi)的坐標(biāo)位置，最后按照這些坐標(biāo)在屏幕上輸出結(jié)點(diǎn)并按關(guān)系連線，得到連線清晰化的無向關(guān)系圖的圖形化顯示結(jié)果，或者將這些坐標(biāo)依照文本文件或數(shù)據(jù)庫(kù)文件的形式保存輸出，供下游軟件使用。
- 詳細(xì)介紹：
- 在計(jì)算機(jī)科學(xué)與技術(shù)中，描述一組對(duì)象之間的關(guān)系經(jīng)常用無向圖表示，而此類關(guān)系信息的獲取形式往往是無向圖的邏輯表示，如表格、數(shù)據(jù)庫(kù)、鄰接矩陣，這種邏輯表示很不直觀，所以人們喜歡用平面上的圖重新表示，將表示對(duì)象的結(jié)點(diǎn)用一個(gè)圓點(diǎn)或小圓圈表示，再將對(duì)象間的關(guān)系用一條條連接兩個(gè)結(jié)點(diǎn)的線表示。這種圖形化表示固然直觀，但存在一個(gè)問題：如果一開始結(jié)點(diǎn)的位置擺放得不好，畫連線時(shí)會(huì)產(chǎn)生縱橫交錯(cuò)的結(jié)果，畫出來的圖關(guān)系不清晰，連線產(chǎn)生交叉、遠(yuǎn)跨或重疊。所以結(jié)點(diǎn)的定位很重要，如果有一種能保證連線清晰的結(jié)點(diǎn)自動(dòng)定位方法，那么在結(jié)點(diǎn)位置確定之后，根據(jù)無向關(guān)系將一對(duì)對(duì)的結(jié)點(diǎn)用直線段連接起來就行了。這就是我們項(xiàng)目所要研究的無向關(guān)系圖結(jié)點(diǎn)定位技術(shù)。 無向關(guān)系圖結(jié)點(diǎn)定位軟件主要用于基于無向圖的關(guān)系模型如產(chǎn)品關(guān)聯(lián)圖、文檔抄襲關(guān)系圖、數(shù)據(jù)引用圖、路由分布圖、知識(shí)點(diǎn)依賴圖、軟件工程PERT圖、組織關(guān)系圖、模塊關(guān)系圖等的圖形化輸出，通過結(jié)點(diǎn)坐標(biāo)的合理確定，使關(guān)系連線清晰美觀，連通分支分離易辨。 我們可以將無向關(guān)系圖結(jié)點(diǎn)定位技術(shù)植入軟件工程、識(shí)別系統(tǒng)、Visio、Cisco Packet Tracer等應(yīng)用技術(shù)、系統(tǒng)或軟件中去，使這些應(yīng)用技術(shù)、系統(tǒng)或軟件更加自動(dòng)化、智能化、高效率、實(shí)用化和人性化。
作品圖片
作品專業(yè)信息
設(shè)計(jì)、發(fā)明的目的和基本思路、創(chuàng)新點(diǎn)、技術(shù)關(guān)鍵和主要技術(shù)指標(biāo)
- 目的：在計(jì)算機(jī)科學(xué)與技術(shù)中，表示對(duì)象之間的關(guān)系通常用無向圖表示。這種圖形化表示固然直觀，但存在一個(gè)問題：如果一開始結(jié)點(diǎn)的位置擺放得不好，畫出來的圖關(guān)系就會(huì)不清晰。如果有一個(gè)能保證連線清晰化的無向關(guān)系圖結(jié)點(diǎn)定位軟件，對(duì)一副關(guān)系混亂的無向圖重新確定結(jié)點(diǎn)位置后能使關(guān)系圖變得清晰美觀，將很大程度上便于我們分析和理解無向關(guān)系圖。而設(shè)計(jì)這款無向關(guān)系圖結(jié)點(diǎn)定位軟件就是本項(xiàng)目的目的。 基本思路：無向關(guān)系圖結(jié)點(diǎn)定位軟件采用圖內(nèi)割邊、團(tuán)內(nèi)割點(diǎn)的識(shí)別技術(shù)，并基于樹型結(jié)構(gòu)實(shí)現(xiàn)區(qū)域劃分，采用逐步清晰的方法，最終使無向關(guān)系圖達(dá)到視覺上清晰的目的。 創(chuàng)新點(diǎn)：（1）采用割邊割點(diǎn)識(shí)別技術(shù)，將連通圖分解為團(tuán)與子團(tuán)后再定位。 （2）非迭代方法，直接定位，比遺傳算法、模擬退火等進(jìn)化算法要直接、快速得多。 技術(shù)關(guān)鍵和主要技術(shù)指標(biāo)：軟件采用割邊割點(diǎn)識(shí)別技術(shù)，將連通圖分解為團(tuán)與子團(tuán)后再定位，可以使最終顯示的無向關(guān)系圖的關(guān)系連線盡量不交叉、不遠(yuǎn)跨、不重疊，關(guān)系結(jié)點(diǎn)組匯聚成團(tuán)，能清晰地看出結(jié)點(diǎn)間的連接關(guān)系和分組情況。定位結(jié)果既可以直接顯示，又可以通過文件接口輸出，支持文本文件和Access數(shù)據(jù)庫(kù)兩種格式。
科學(xué)性、先進(jìn)性
- 本軟件采用的無向關(guān)系圖結(jié)點(diǎn)定位方法首先將無向關(guān)系圖去除孤立點(diǎn)、分離連通分支，并通過識(shí)別割邊將每個(gè)連通分支分解成一系列的團(tuán)，每個(gè)團(tuán)內(nèi)無割邊，這些團(tuán)以樹型結(jié)構(gòu)連接，然后通過識(shí)別割點(diǎn)和虛連線將每個(gè)團(tuán)分解成子團(tuán)，每個(gè)子團(tuán)內(nèi)無割點(diǎn)，最后將子團(tuán)內(nèi)頂點(diǎn)均勻分布在一個(gè)圓環(huán)上。該方法具有實(shí)現(xiàn)方便，方法簡(jiǎn)單，運(yùn)行高效，輸出結(jié)果美觀，易于并行化等優(yōu)點(diǎn)。
獲獎(jiǎng)情況及鑒定結(jié)果
- 本項(xiàng)目是2009年度浙江省大學(xué)生科技創(chuàng)新活動(dòng)計(jì)劃（新苗人才計(jì)劃）立項(xiàng)（項(xiàng)目編號(hào)：2009R424008）成果，該大學(xué)生科技創(chuàng)新活動(dòng)計(jì)劃項(xiàng)目已于2010年12月通過溫州大學(xué)大學(xué)生科技評(píng)審委員會(huì)評(píng)審，并同意結(jié)題。 2011年3月在浙江省科技信息研究院做科技查新報(bào)告，查新結(jié)論：無向關(guān)系圖結(jié)點(diǎn)定位軟件在檢索到的相關(guān)國(guó)內(nèi)文獻(xiàn)中未見具體述及。 2011年3月在浙江省電子產(chǎn)品檢驗(yàn)所做軟件鑒定評(píng)測(cè)。 2011年3月向中國(guó)版權(quán)保護(hù)中心申請(qǐng)軟件著作權(quán)登記，流水號(hào)：2011R11L015531。 2011年4月向國(guó)家知識(shí)產(chǎn)權(quán)局專利局申請(qǐng)發(fā)明專利。
作品所處階段
- 中試階段
技術(shù)轉(zhuǎn)讓方式
- 軟件銷售，專利轉(zhuǎn)讓。
作品可展示的形式
- 實(shí)物、產(chǎn)品；現(xiàn)場(chǎng)演示。
使用說明,技術(shù)特點(diǎn)和優(yōu)勢(shì),適應(yīng)范圍,推廣前景的技術(shù)性說明,市場(chǎng)分析,經(jīng)濟(jì)效益預(yù)測(cè)
- 使用說明：本軟件的功能是將一副無向關(guān)系圖讀入，通過結(jié)點(diǎn)坐標(biāo)的合理定位使無向圖關(guān)系連線清晰可辨，或者將定位后的無向圖保存，供下游軟件使用。 技術(shù)特點(diǎn)和優(yōu)勢(shì)：（1）定位方法模型簡(jiǎn)單，效率高，且屬于確定性方法。（2）支持多種格式的無向關(guān)系圖的數(shù)據(jù)文件。 適用范圍及推廣情景：我們可以將無向關(guān)系圖結(jié)點(diǎn)定位軟件植入軟件工程、識(shí)別系統(tǒng)、Visio、Cisco Packet Tracer等應(yīng)用技術(shù)、系統(tǒng)或軟件中去，使這些應(yīng)用技術(shù)、系統(tǒng)或軟件更加自動(dòng)化、智能化、高效率、實(shí)用化和人性化。我們也可以將本軟件應(yīng)用于數(shù)據(jù)挖掘、模式識(shí)別等領(lǐng)域。 市場(chǎng)分析和經(jīng)濟(jì)效益預(yù)測(cè)：一方面，Cisco Packet Tracer軟件和Visio軟件是應(yīng)用很廣泛的軟件，但這兩款軟件沒有提供關(guān)系清晰化的技術(shù)，而我們的軟件彌補(bǔ)了這兩款軟件的不足，能使這兩款軟件使用起來更加方便。 另一方面，本軟件能用于超市等機(jī)構(gòu)的產(chǎn)品間數(shù)據(jù)挖掘，使產(chǎn)品間的關(guān)系直觀、清晰，便于決策者做出正確的商業(yè)決策。
同類課題研究水平概述
- 目前，現(xiàn)有的無向關(guān)系圖結(jié)點(diǎn)定位方法各有所長(zhǎng)，也各有所短。他們主要分為兩類，一類是基于最優(yōu)化方法的結(jié)點(diǎn)定位方法，該方法的特點(diǎn)是將無向關(guān)系圖結(jié)點(diǎn)定位問題轉(zhuǎn)發(fā)為函數(shù)優(yōu)化問題，用基于某種算法或模型求目標(biāo)函數(shù)最優(yōu)解的近似解，從而改變結(jié)點(diǎn)位置。該方法的的優(yōu)點(diǎn)在于方法簡(jiǎn)單，易于實(shí)現(xiàn)，普遍適用于不同特點(diǎn)的無向圖，缺點(diǎn)在于計(jì)算量大，最終結(jié)果不確定，且收斂性差。其中，基于遺傳算法實(shí)現(xiàn)無向關(guān)系圖結(jié)點(diǎn)定位的方法是該類方法中一種主流的方法。基于遺傳算法實(shí)現(xiàn)無向關(guān)系圖結(jié)點(diǎn)定位是將無向圖結(jié)點(diǎn)定位問題轉(zhuǎn)化為約束優(yōu)化問題，即轉(zhuǎn)化為計(jì)算某個(gè)帶有約束條件的函數(shù)的最小值或最大值。不同的結(jié)點(diǎn)定位方法其實(shí)質(zhì)在于設(shè)計(jì)不同的目標(biāo)函數(shù)。但遺傳算法屬于概率算法，算法執(zhí)行結(jié)果具有不確定性，同時(shí)，想要得到好的輸出結(jié)果，需要經(jīng)過相當(dāng)長(zhǎng)的時(shí)間演化，因此算法收斂性較差。 另一類方法是基于某類確定算法實(shí)現(xiàn)無向圖結(jié)點(diǎn)定位的方法。該方法的特點(diǎn)是經(jīng)過一個(gè)算法，最終確定結(jié)點(diǎn)的最后位置。相比于前者，該類方法的一個(gè)顯著優(yōu)點(diǎn)在于，計(jì)算量明顯減小，且最終結(jié)點(diǎn)位置確定，不會(huì)隨著執(zhí)行的次數(shù)不同而不同。但設(shè)計(jì)一個(gè)算法適用于不同特點(diǎn)的無向圖并非易事，這樣的結(jié)點(diǎn)定位方法往往對(duì)滿足某些特點(diǎn)的無向圖才能達(dá)到很好的效果。其中，該類方法中，比較有代表性的是將無向圖顯示在環(huán)上，根據(jù)每個(gè)結(jié)點(diǎn)的加權(quán)值確定其所占有的扇形區(qū)域，并將每個(gè)結(jié)點(diǎn)布局在其扇區(qū)的中心線上的方法。
