問題定義：
使用A星演算法，計算圖g和查詢圖q之間的編輯距離。圖編輯操作一共有6種：頂點標簽的增加、洗掉、替換，邊標簽的增加、洗掉、替換。其中每一種操作都有預定義的代價，假設這里預定義的代價值都為1.那么倆個圖之間的編輯距離值，等于倆個圖之間最小代價編輯操作值。
例：圖g1和查詢圖q之間的編輯操作如下：
演算法的輸入：屬性圖g,屬性圖q,頂點和邊的編輯代價為1
演算法的輸出：一條代價最優的編輯路徑。上面例子的輸出為cost =2,MinPath =
[((u1,v1), (u2,v2),(u3,v3),(u4,v4),(u5,v5)),
(((u1,u2),(v1,v2)),
((u1,u3),(v1,v3)),
((u2,u4),(v2,v4)),
((u3,u5),(v3,v5)),
((u5,u4),(v5,v4)),
((NONE),(v3,v4))]
原文演算法：
原文鏈接https://www.researchgate.net/publication/275463562_An_Exact_Graph_Edit_Distance_Algorithm_for_Solving_Pattern_Recognition_Problems
中文翻譯：
第四步：演算法3-20行（比較難翻譯就沒翻譯了）
搜索空間：
如果按照上面的例子，則會有如下的運算程序，集合m即演算法的OPEN集合：
資料集：
資料說明：
資料集名稱test.txt
t # 30 //圖的ID
v 1 C //圖中的頂點ID為1，此頂點的label為C
v 2 C//圖的頂點ID為2，此頂點的label為C
e 1 2 1//頂點ID=1和頂點ID=2之間構成了一條邊，這條邊的label是1.
此資料集中存在1500個圖，圖平均頂點個數25，平均邊個數27，平均的最大頂點度12。頂點的標簽是63中化學元素的名稱，邊的標簽有三種，為1,2,3.該資料集來自化學資料庫AIDS.
需求如下：
1.想知道程式如何把圖存盤在計算里面呢？物理結構怎么表示啊？主要是這里的表示方法，明白有二維陣列的順序表示和鏈表的非順序表示方法，可是到這里就不會用了。麻煩大神用您熟悉的語言展示下。
2.如何實作檔案操作，將test資料全部作為輸入，并且計算程式的運行時間和空間占用？因為資料結構里面都是無檔案匯入的，這邊匯入檔案，不曉得如何寫代碼。
3. 可能演算法我解釋得不大清楚，但是按照演算法的偽代碼應該可以按斬訓于程序的撰寫思路寫出來。希望可以和資料結構和C語言方面的大神一起探討下。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/32526.html
標籤：C語言
下一篇：Vs小白求助大神！