亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        一種基于最小沖突集的約束沖突消解方法

        2010-01-01 01:45:02劉曉平
        圖學(xué)學(xué)報(bào) 2010年2期
        關(guān)鍵詞:約束條件設(shè)計(jì)者個(gè)數(shù)

        劉曉平, 季 浩, 石 慧

        (合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院VCC研究室,安徽 合肥 230009)

        在協(xié)同設(shè)計(jì)中,不同設(shè)計(jì)者在網(wǎng)絡(luò)化平臺上依據(jù)各自經(jīng)驗(yàn)和理解對產(chǎn)品進(jìn)行分工設(shè)計(jì),實(shí)際過程中存在著大量相互影響、相互制約的約束關(guān)系。筆者所在的團(tuán)隊(duì)在多年協(xié)同模板理論的研究過程中逐漸發(fā)現(xiàn)協(xié)同模板中約束關(guān)系的復(fù)雜 性[1],當(dāng)在協(xié)作過程中不同的設(shè)計(jì)選擇發(fā)生沖突時(shí),如果設(shè)計(jì)者們對約束信息的組織關(guān)系把握不清楚,無疑會增加沖突消解的難度和設(shè)計(jì)過程的反復(fù),降低協(xié)同設(shè)計(jì)的效率。

        為了保證并行產(chǎn)品設(shè)計(jì)順利進(jìn)行,文獻(xiàn)[2]采用改進(jìn)的區(qū)間傳播算法用于實(shí)時(shí)在線檢測沖突,在約束網(wǎng)絡(luò)中沒有沖突時(shí),給出傳播后變量的取值范圍。文獻(xiàn)[3]提出利用基于最小沖突集修補(bǔ)的算法,求解動(dòng)態(tài)變化的約束滿足問題。但事實(shí)上都不能使設(shè)計(jì)者在變更約束的同時(shí)清楚了解約束條件之間的關(guān)系,而在約束信息發(fā)生沖突時(shí),及時(shí)、準(zhǔn)確地提取約束信息的制約關(guān)系、輔助設(shè)計(jì)者利用已有的知識進(jìn)行協(xié)商調(diào)整約束信息是建立以人為中心的沖突消解方法的關(guān)鍵。

        本文主要工作是從最小沖突集的角度出發(fā),分析最小沖突集元素個(gè)數(shù)范圍和判定方法,并結(jié)合交邊算法[4]實(shí)現(xiàn)對最小沖突集的提取,通過算例說明最小沖突集,該方法對建立以人為中心進(jìn)行控制和管理約束信息、消解約束沖突的有效性。

        1 相關(guān)概念和性質(zhì)

        1.1 相關(guān)概念

        一個(gè)工程設(shè)計(jì)問題實(shí)際上是多個(gè)約束條件滿足問題,即對滿足約束條件

        1.2 相關(guān)性質(zhì)

        為了方便描述和證明最小沖突集的相關(guān)性質(zhì),這里先給出交邊算法的數(shù)學(xué)描述和Helly 定理。

        下面給出在交邊算法中提取最小沖突集時(shí)所用到的一些性質(zhì):

        最小沖突集元素個(gè)數(shù)k 不小于2 是顯然。

        若 1k d> + ,由最小沖突集的定義知

        Ω ( d ,k)= ?, Ωi( d , k? 1)≠?, i = 1,… ,, k ? 1≥ d+1。

        所以最小沖突集的元素個(gè)數(shù)k 滿足2 ≤ k ≤ d+1。

        表1 約束冗余的判斷方法

        對于 L1= L2的情況,通過指向 L1,L2所表示 區(qū)域的法向量是否相同來判斷冗余。

        性質(zhì)1 說明在d 維約束條件中,如果存在最小沖突集, 其元素個(gè)數(shù)k 的應(yīng)該滿足 2 ≤ k ≤ d+1。性質(zhì)2 指出判斷元素個(gè)數(shù)范圍為 [2, d+1]的沖突集方法,其證明由交邊算法的數(shù)學(xué)描述中易得。性質(zhì)3 用來化簡冗余約束。在利用交邊算法判斷原約束集為沖突的同時(shí),利用上述性質(zhì)提取出最小沖突集和冗余約束。

        2 約束沖突消解方法

        本文在上述性質(zhì)的基礎(chǔ)上,結(jié)合交邊算法提取最小沖突集和冗余約束,到達(dá)消解約束的目的。以下是約束沖突消解方法:

        (1) 根據(jù)信息的屬性確定約束信息的維數(shù)d,由性質(zhì)2 得最小沖突集的元素個(gè)數(shù)范圍。

        (2) 將約束信息用改進(jìn)的交邊算法,進(jìn)行求解、檢測沖突和記錄相關(guān)信息。改進(jìn)的交邊算法的非形式的描述如下:

        Step 6 在記錄信息中依據(jù)上述的性質(zhì),化簡冗余約束信息,并提取 2k = 的最小沖突集。

        Step 7 選取k s= 的最小沖突集,滿足:

        Step 8 若 s ≤ d+1,則轉(zhuǎn)Step 7。否則算法結(jié)束。

        (3) 由記錄的信息,去除冗余信息并提取最小沖突集。

        (4) 對最小沖突集中的約束序號進(jìn)行編碼,通過對編碼的運(yùn)算,方便以后查找關(guān)鍵的約束信息。

        (5) 設(shè)計(jì)者依照保留最多的約束、指定的約束等準(zhǔn)則或要求,進(jìn)行協(xié)商消解沖突。

        3 算法示例

        下面給出一個(gè)算例,假設(shè)設(shè)計(jì)者在進(jìn)行約束沖突消解時(shí),以保留最多約束條件為準(zhǔn)則。

        例:

        由于線性約束是2 維的,只可能存在元素個(gè)數(shù)是2 或3 的最小沖突集。通過改進(jìn)的交邊算法判定該約束集是沖突的,并得到如表2 的矛盾信息記錄。

        表2 矛盾信息記錄

        對最小沖突集中的約束進(jìn)行01 編碼:

        將編碼相加得:11010221,因有3 個(gè)最小沖突集,每個(gè)約束至多參與2 個(gè)最小沖突集,所以至少要剔除兩個(gè)約束,才能使得沖突消解。所以依據(jù)保留最多約束條件的準(zhǔn)則,應(yīng)當(dāng)剔除約束條 件 L2, L3,L6。

        圖1 約束條件的直觀圖

        4 結(jié) 束 語

        為了使設(shè)計(jì)者在協(xié)同設(shè)計(jì)中能清晰地把握約束信息的制約關(guān)系,有效地去除冗余信息、消解約束沖突。本文從最小沖突集的角度出發(fā),在分析最小沖突集的相關(guān)性質(zhì)和交邊算法的基礎(chǔ)上,提出了利用改進(jìn)交邊算法提取最小沖突集,方便設(shè)計(jì)者按照一定的準(zhǔn)則去除沖突約束信息。由于對最小沖突集剔除部分約束信息,需要建立在設(shè)計(jì)者的相關(guān)知識和準(zhǔn)則上,并且在約束信息非常多的情況下,設(shè)計(jì)者不容易利用抽象思維完全把握約束信息之間的關(guān)系,而可視化具有細(xì)致、完善地展現(xiàn)約束信息,使設(shè)計(jì)者清晰、直觀地了解約束信息之間的關(guān)系,所以下一步工作將考慮結(jié)合約束信息可視化手段,研究可視約束信息、交互式處理沖突的方法。

        [1] 劉曉平, 石 慧, 毛崢強(qiáng). 協(xié)同模板中的信息可視化[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2005, 17(10): 2334-2338.

        [2] 朱湘毅, 唐 泉, 陳文培, 等. 并行工程中基于約束的沖突檢測研究[J]. 機(jī)械科學(xué)與技術(shù), 2000, 19(5): 849-852.

        [3] 孫吉貴, 高 健, 張永剛. 一個(gè)基于最小沖突修補(bǔ)的動(dòng)態(tài)約束滿足求解算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2007, 44(12): 2078-2084.

        [4] 宋恩民, 黃文奇. 判斷具有多線性約束條件的凸空間是否為空的交邊算法[J]. 計(jì)算機(jī)學(xué)報(bào), 1996, 19(9): 704-708.

        [5] Dimitri P Bertsekas, Angelia Nedic, Asuman E Ozdaglar. Convex analysis and optimization [M]. 北京: 清華大學(xué)出版社, 2006. 112-165.

        猜你喜歡
        約束條件設(shè)計(jì)者個(gè)數(shù)
        基于一種改進(jìn)AZSVPWM的滿調(diào)制度死區(qū)約束條件分析
        怎樣數(shù)出小正方體的個(gè)數(shù)
        2020德國iF設(shè)計(jì)獎(jiǎng)
        等腰三角形個(gè)數(shù)探索
        怎樣數(shù)出小木塊的個(gè)數(shù)
        2019德國IF設(shè)計(jì)大獎(jiǎng)
        怎樣數(shù)出小正方體的個(gè)數(shù)
        A literature review of research exploring the experiences of overseas nurses in the United Kingdom (2002–2017)
        線性規(guī)劃的八大妙用
        楊敬:深水區(qū)醫(yī)改設(shè)計(jì)者
        亚洲av无码无线在线观看| 久久精品中文字幕亚洲| 少妇高潮精品正在线播放| 欧美a级毛欧美1级a大片| 精品国产一区二区三区av片| 久久夜色撩人精品国产小说| 东风日产系列全部车型| 亚洲美女毛片在线视频| 天天躁日日躁狠狠躁欧美老妇| 国产精品麻豆综合在线| 日本一区二区久久精品亚洲中文无| 成人久久黑人中出内射青草| 一区二区三区乱码在线 | 欧洲 | 91极品尤物在线观看播放| 国产av无毛无遮挡网站| 国产精品无码久久综合网| 国产一区二区三区精品免费av| 极品av麻豆国产在线观看| 日韩一区二区肥| 白白白色视频在线观看播放| 久久精品亚洲精品国产区| 中文字幕亚洲综合久久菠萝蜜| 国产第一页屁屁影院| 亚洲精品美女久久久久99| 日本久久精品视频免费| 48久久国产精品性色aⅴ人妻| 久久精品亚洲牛牛影视| 中文字幕久久熟女人妻av免费| 国产禁区一区二区三区| 先锋影音av最新资源| 精品国产一区二区三区亚洲人| 国产视频一区2区三区| 射精专区一区二区朝鲜| 亚洲综合一区二区三区四区五区| 亚洲视频综合在线第一页| 精品一区二区三区人妻久久福利| 又色又爽又黄高潮的免费视频| 国外亚洲成av人片在线观看| 福利一区二区三区视频午夜观看| 加勒比久草免费在线观看| 成人午夜高潮a∨猛片|