黑白球三維排列游戲

上傳人：仙*** 文檔編號：30494872 上傳時間：2021-10-10 格式：DOC 頁數(shù)：16 大?。?67.50KB

收藏版權(quán)申訴舉報下載

第1頁 / 共16頁

第2頁 / 共16頁

第3頁 / 共16頁

下載文檔到電腦，查找使用更方便

15 積分

下載資源

還剩頁未讀，繼續(xù)閱讀

資源描述：

《黑白球三維排列游戲》由會員分享，可在線閱讀，更多相關(guān)《黑白球三維排列游戲（16頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、黑白球三維排列游戲一、問題提出（略）. 二、問題假設(shè) 1．將黑白球視作沒有大小的點，將每個小方盒也視作一個點。三、符號說明： 0表示第i個盒子放白球，1表示第i個盒子放黑球；：0表示第j條直線上所有的球為相同顏色，1表示第j條直線上的球為不同顏色,j=1，2，…，27. 四、問題分析與建模這雖然是一個排列游戲，但是其中蘊含有相當(dāng)豐富的整數(shù)規(guī)劃特性，因此在此討論它。將14個黑球和13個白球放入333的三維陣中，其排列方式非常多，要想采用窮舉法求解的原問題非常困難的。首先，我們對小方盒編號為1到27，具體的編號規(guī)則為參見圖1。于是，對于每個小方盒，我們可以引入

2、一個0--1變量：表示第i個盒子中裝有白球，表示第i個盒子中裝有黑球，如此引入的0—1變量共有27個。并且由于黑球的個數(shù)為14，因此。 1. 可能的直線對于此問題，首先需要知道：在這個333的三維陣中,哪些小方盒連接起來可以構(gòu)成一條直線？這樣的直線共有多少條？為了確定這些直線，我們首先考慮此333的三維陣的行、列和縱三個方向上的9個截面上的直線有哪些，然后考慮不全在任何一個截面上直線有哪些。與水平面平行的截面有三個，見圖2。對應(yīng)于每一個截面上的三點共線的情況共有8種，分別記為： S3={{19，20，21},{22，23，24},{25,26,27},{19,22,25},

3、{20,23,26},{21,24,27},{19,23,27},{21,23,25}}； S2={{10,11,12},{13,14,15},{16,17,18},{10,13,16},{11,14,17},{12,15,18},{10,14,18},{12,14,16}}； S1={{1,2,3},{4,5,6},{7,8,9},{1,4,7},{2,5,8},{3,6,9},{1,5,9},{3,5,7}}。與水平面相垂直的截面共有6個，見圖3和圖4。與圖3對應(yīng)的每一個截面上共線的三點情況也有8種，由于它們與圖1中的情況會出現(xiàn)重疊，去掉重疊的三種情況，新增加的三點共線情況

4、各有5種，分別記為： S4={{1,10,19}，{2,11,20}，{3,12,21}，{1,11,21}，{3,11,19}}； S5={{4,13,22}，{5,14,23}，{6,15,24}，{4,14,24}，{6,14,22}}； S6={{7,16,25}，{8,17,26}，{9,18,27}，{7,17,27}，{9,17,25}}。與圖4對應(yīng)的每一個截面上共線的三點情況也有8種，由于它們與圖1和圖2中的情況會出現(xiàn)重疊，去掉重疊的6種情況，新增加的三點共線情況各有2種，分別記為： S7={{1,13,25},{7,13,19}}；S8={{2,14,26},

5、{8,14,20}}；S9={{3,15,27},{9,15,21}}。三個點不同在上面所介紹的任何一個或者兩個截面的情況參見圖5。新增加的三點共線的情況有4種，記為： S10={{1,14,27},{3,14,25},{9,14,19},{7,14,21}}。綜合前面的分析，在此333的三維陣中，所有能夠共線的三點共有49種情況，它們組成49條不同的直線，用S表示，則 . 2. 成為直線的條件根據(jù)前面分析的可能的直線的結(jié)果，我們來確定當(dāng)放入黑白球之后，三個相同顏色的球在同一直線上滿足的條件。設(shè)第j條直線上的三個盒子的編號分別為：j1，j2，j3，記為，在直線j上三個盒

6、子中放入的球的顏色情況為：。引入0--1變量：表示第j條直線上的三個球的顏色不完全相同，表示第j條直線上的三個球的顏色完全相同。這樣原問題轉(zhuǎn)化為求一種黑白球的方法，使得取得最小值。并且有約束：（1）（2）此即放入黑白球之后，每條直線上的所有球體顏色相同的條件為（1），每條直線上的所有球體顏色不相同的條件為（2）。此時如何將引入到（1）或者(2)中右邊的表達式中，成為我們考慮的重點。為了將引入表達式（1）中，變成（3）或者將引入表達式（2）中，變成 (4) 注1：此處（3）和（1）

7、并不等價，但是考慮到我們的目標(biāo)為，這樣做也是可以的；注2：此處（4）和（2）是等價的，但是與（3）相比增加了98個約束條件；注3：在建立模型時，（3）和（4）這兩組約束條件只需要一組即可。 3. 數(shù)學(xué)模型根據(jù)前面的分析，我們可以建立如下的0—1規(guī)劃的數(shù)學(xué)模型：該模型是一個含有76個0—1變量，99個約束條件的0—1整數(shù)規(guī)劃問題。五、模型求解 1.求解方法理論上，對于0—1整數(shù)規(guī)劃問題可以采用基于線性規(guī)劃的分枝定界法求解。詳細(xì)算法參見[1]。 2.計算結(jié)果利用數(shù)學(xué)軟件Lingo中已有的關(guān)于分枝定界法的實現(xiàn)，可以方便地求出原問題的解，程序及程序輸出見附錄1。

8、根據(jù)我們計算出來的結(jié)果可知，相同顏色的最少的直線數(shù)為4條，并且有許多的備擇解，下面給出其中一種解的圖形表示（圖6），圖中灰色的盒子表示放黑球，白色的盒子放置白球。黑白球按照圖6所示的放置方法，所形成的四條直線為： {4,13,22}，{10,13,16}全由白球相連構(gòu)成； {6,15,24}，{12,15,18}全由黑球相連構(gòu)成。六、模型推廣及討論（略）. 七、參考文獻 [1] 八、附錄 1. 程序 model: Sets: LineCols/1..3/:; LineRows/1..49/: r; Links(LineRows,LineCols):Li

9、nes; Balls/1..27/:delta; endsets min=@sum(LineRows(i):r(i)); @sum(Balls(i):delta(i))=14; @for(LineRows(i):@sum(LineCols(j):delta(Lines(i,j)))+r(i)>=1); @for(LineRows(i):@sum(LineCols(j):delta(Lines(i,j)))-r(i)<=2); @for(LineRows(i):@bin(r(i))); @for(Balls(i):@bin(delta(i))); data:

10、Lines=1 2 3 4 5 6 7 8 9 1 4 7 2 5 8 3 6 9 1 5 9 3 5 7 10 11 12 13 14 15 16 17 18 10 13 16 11 14 17 12 15 18 10 14 18 12 14 16 19 20 21 22 23 24 25 26 27

11、 19 22 25 20 23 26 21 24 27 19 23 27 21 23 25 1 10 19 2 11 20 3 12 21 1 11 21 3 11 19 4 13 22 5 14 23 6 15 24 4 14 24 6 14 22 7 16 25 8 17 26 9 18 27 7 17 27

12、 9 17 25 1 13 25 7 13 19 2 14 26 8 14 20 3 15 27 9 15 21 1 14 27 3 14 25 7 14 21 9 14 19; enddata end 2. 輸出結(jié)果 Global optimal solution found at iteration: 103652 Objective value:

13、 4.000000 Variable Value Reduced Cost R( 1) 0.000000 1.000000 R( 2) 0.000000 1.000000 R( 3) 0.000000 1.000000

14、 R( 4) 0.000000 1.000000 R( 5) 0.000000 1.000000 R( 6) 0.000000 1.000000 R( 7) 0.000000 1.000000

15、 R( 8) 0.000000 1.000000 R( 9) 0.000000 1.000000 R( 10) 0.000000 1.000000 R( 11) 0.000000 1.000000 R( 12) 1.00000

16、0 1.000000 R( 13) 0.000000 1.000000 R( 14) 1.000000 1.000000 R( 15) 0.000000 1.000000 R( 16) 0.000000 1.000000

17、 R( 17) 0.000000 1.000000 R( 18) 0.000000 1.000000 R( 19) 0.000000 1.000000 R( 20) 0.000000 1.000000

18、R( 21) 0.000000 1.000000 R( 22) 0.000000 1.000000 R( 23) 0.000000 1.000000 R( 24) 0.000000 1.000000 R( 25) 0.000000

19、 1.000000 R( 26) 0.000000 1.000000 R( 27) 0.000000 1.000000 R( 28) 0.000000 1.000000 R( 29) 0.000000 1.000000

20、 R( 30) 1.000000 1.000000 R( 31) 0.000000 1.000000 R( 32) 1.000000 1.000000 R( 33) 0.000000 1.000000 R(

21、34) 0.000000 1.000000 R( 35) 0.000000 1.000000 R( 36) 0.000000 1.000000 R( 37) 0.000000 1.000000 R( 38) 0.000000

22、 1.000000 R( 39) 0.000000 1.000000 R( 40) 0.000000 1.000000 R( 41) 0.000000 1.000000 R( 42) 0.000000 1.000000

23、 R( 43) 0.000000 1.000000 R( 44) 0.000000 1.000000 R( 45) 0.000000 1.000000 R( 46) 0.000000 1.000000 R( 47)

24、 0.000000 1.000000 R( 48) 0.000000 1.000000 R( 49) 0.000000 1.000000 LINES( 1, 1) 1.000000 0.000000 LINES( 1, 2) 2.000000

25、 0.000000 LINES( 1, 3) 3.000000 0.000000 LINES( 2, 1) 4.000000 0.000000 LINES( 2, 2) 5.000000 0.000000 LINES( 2, 3) 6.000000 0.000000

26、 LINES( 3, 1) 7.000000 0.000000 LINES( 3, 2) 8.000000 0.000000 LINES( 3, 3) 9.000000 0.000000 LINES( 4, 1) 1.000000 0.000000 LINES( 4, 2)

27、 4.000000 0.000000 LINES( 4, 3) 7.000000 0.000000 LINES( 5, 1) 2.000000 0.000000 LINES( 5, 2) 5.000000 0.000000 LINES( 5, 3) 8.000000

28、 0.000000 LINES( 6, 1) 3.000000 0.000000 LINES( 6, 2) 6.000000 0.000000 LINES( 6, 3) 9.000000 0.000000 LINES( 7, 1) 1.000000 0.000000

29、 LINES( 7, 2) 5.000000 0.000000 LINES( 7, 3) 9.000000 0.000000 LINES( 8, 1) 3.000000 0.000000 LINES( 8, 2) 5.000000 0.000000 LINES( 8, 3)

30、 7.000000 0.000000 LINES( 9, 1) 10.00000 0.000000 LINES( 9, 2) 11.00000 0.000000 LINES( 9, 3) 12.00000 0.000000 LINES( 10, 1) 13.00000 0.

31、000000 LINES( 10, 2) 14.00000 0.000000 LINES( 10, 3) 15.00000 0.000000 LINES( 11, 1) 16.00000 0.000000 LINES( 11, 2) 17.00000 0.000000

32、 LINES( 11, 3) 18.00000 0.000000 LINES( 12, 1) 10.00000 0.000000 LINES( 12, 2) 13.00000 0.000000 LINES( 12, 3) 16.00000 0.000000 LINES( 13, 1) 1

33、1.00000 0.000000 LINES( 13, 2) 14.00000 0.000000 LINES( 13, 3) 17.00000 0.000000 LINES( 14, 1) 12.00000 0.000000 LINES( 14, 2) 15.00000 0.000

34、000 LINES( 14, 3) 18.00000 0.000000 LINES( 15, 1) 10.00000 0.000000 LINES( 15, 2) 14.00000 0.000000 LINES( 15, 3) 18.00000 0.000000 L

35、INES( 16, 1) 12.00000 0.000000 LINES( 16, 2) 14.00000 0.000000 LINES( 16, 3) 16.00000 0.000000 LINES( 17, 1) 19.00000 0.000000 LINES( 17, 2) 20.0

36、0000 0.000000 LINES( 17, 3) 21.00000 0.000000 LINES( 18, 1) 22.00000 0.000000 LINES( 18, 2) 23.00000 0.000000 LINES( 18, 3) 24.00000 0.000000

37、 LINES( 19, 1) 25.00000 0.000000 LINES( 19, 2) 26.00000 0.000000 LINES( 19, 3) 27.00000 0.000000 LINES( 20, 1) 19.00000 0.000000 LINE

38、S( 20, 2) 22.00000 0.000000 LINES( 20, 3) 25.00000 0.000000 LINES( 21, 1) 20.00000 0.000000 LINES( 21, 2) 23.00000 0.000000 LINES( 21, 3) 26.0000

39、0 0.000000 LINES( 22, 1) 21.00000 0.000000 LINES( 22, 2) 24.00000 0.000000 LINES( 22, 3) 27.00000 0.000000 LINES( 23, 1) 19.00000 0.000000

40、 LINES( 23, 2) 23.00000 0.000000 LINES( 23, 3) 27.00000 0.000000 LINES( 24, 1) 21.00000 0.000000 LINES( 24, 2) 23.00000 0.000000 LINES(

41、24, 3) 25.00000 0.000000 LINES( 25, 1) 1.000000 0.000000 LINES( 25, 2) 10.00000 0.000000 LINES( 25, 3) 19.00000 0.000000 LINES( 26, 1) 2.000000

42、 0.000000 LINES( 26, 2) 11.00000 0.000000 LINES( 26, 3) 20.00000 0.000000 LINES( 27, 1) 3.000000 0.000000 LINES( 27, 2) 12.00000 0.000000

43、 LINES( 27, 3) 21.00000 0.000000 LINES( 28, 1) 1.000000 0.000000 LINES( 28, 2) 11.00000 0.000000 LINES( 28, 3) 21.00000 0.000000 LINES( 29,

44、 1) 3.000000 0.000000 LINES( 29, 2) 11.00000 0.000000 LINES( 29, 3) 19.00000 0.000000 LINES( 30, 1) 4.000000 0.000000 LINES( 30, 2) 13.00000

45、 0.000000 LINES( 30, 3) 22.00000 0.000000 LINES( 31, 1) 5.000000 0.000000 LINES( 31, 2) 14.00000 0.000000 LINES( 31, 3) 23.00000 0.000000

46、 LINES( 32, 1) 6.000000 0.000000 LINES( 32, 2) 15.00000 0.000000 LINES( 32, 3) 24.00000 0.000000 LINES( 33, 1) 4.000000 0.000000 LINES( 33, 2)

47、 14.00000 0.000000 LINES( 33, 3) 24.00000 0.000000 LINES( 34, 1) 6.000000 0.000000 LINES( 34, 2) 14.00000 0.000000 LINES( 34, 3) 22.00000

48、 0.000000 LINES( 35, 1) 7.000000 0.000000 LINES( 35, 2) 16.00000 0.000000 LINES( 35, 3) 25.00000 0.000000 LINES( 36, 1) 8.000000 0.000000

49、 LINES( 36, 2) 17.00000 0.000000 LINES( 36, 3) 26.00000 0.000000 LINES( 37, 1) 9.000000 0.000000 LINES( 37, 2) 18.00000 0.000000 LINES( 37, 3)

50、 27.00000 0.000000 LINES( 38, 1) 7.000000 0.000000 LINES( 38, 2) 17.00000 0.000000 LINES( 38, 3) 27.00000 0.000000 LINES( 39, 1) 9.000000

51、 0.000000 LINES( 39, 2) 17.00000 0.000000 LINES( 39, 3) 25.00000 0.000000 LINES( 40, 1) 1.000000 0.000000 LINES( 40, 2) 13.00000 0.000000

52、 LINES( 40, 3) 25.00000 0.000000 LINES( 41, 1) 7.000000 0.000000 LINES( 41, 2) 13.00000 0.000000 LINES( 41, 3) 19.00000 0.000000 LINES( 42, 1)

53、 2.000000 0.000000 LINES( 42, 2) 14.00000 0.000000 LINES( 42, 3) 26.00000 0.000000 LINES( 43, 1) 8.000000 0.000000 LINES( 43, 2) 14.00000 0.

54、000000 LINES( 43, 3) 20.00000 0.000000 LINES( 44, 1) 3.000000 0.000000 LINES( 44, 2) 15.00000 0.000000 LINES( 44, 3) 27.00000 0.000000

55、 LINES( 45, 1) 9.000000 0.000000 LINES( 45, 2) 15.00000 0.000000 LINES( 45, 3) 21.00000 0.000000 LINES( 46, 1) 1.000000 0.000000 LINES( 46, 2) 1

56、4.00000 0.000000 LINES( 46, 3) 27.00000 0.000000 LINES( 47, 1) 3.000000 0.000000 LINES( 47, 2) 14.00000 0.000000 LINES( 47, 3) 25.00000 0.000

57、000 LINES( 48, 1) 7.000000 0.000000 LINES( 48, 2) 14.00000 0.000000 LINES( 48, 3) 21.00000 0.000000 LINES( 49, 1) 9.000000 0.000000 L

58、INES( 49, 2) 14.00000 0.000000 LINES( 49, 3) 19.00000 0.000000 DELTA( 1) 1.000000 0.000000 DELTA( 2) 1.000000 0.000000 DELTA( 3) 0.00

59、0000 0.000000 DELTA( 4) 0.000000 0.000000 DELTA( 5) 0.000000 0.000000 DELTA( 6) 1.000000 0.000000 DELTA( 7) 1.000000 0.000000

60、 DELTA( 8) 0.000000 0.000000 DELTA( 9) 0.000000 0.000000 DELTA( 10) 0.000000 0.000000 DELTA( 11) 0.000000 0.000000 D

61、ELTA( 12) 1.000000 0.000000 DELTA( 13) 0.000000 0.000000 DELTA( 14) 1.000000 0.000000 DELTA( 15) 1.000000 0.000000 DELTA( 16) 0.00000

62、0 0.000000 DELTA( 17) 1.000000 0.000000 DELTA( 18) 1.000000 0.000000 DELTA( 19) 1.000000 0.000000 DELTA( 20) 1.000000 0.000000

63、 DELTA( 21) 0.000000 0.000000 DELTA( 22) 0.000000 0.000000 DELTA( 23) 1.000000 0.000000 DELTA( 24) 1.000000 0.000000 DELT

64、A( 25) 1.000000 0.000000 DELTA( 26) 0.000000 0.000000 DELTA( 27) 0.000000 0.000000 Row Slack or Surplus Dual Price 1 4.000000

65、 -1.000000 2 0.000000 0.000000 3 1.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000

66、 6 1.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 0.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000 12 1.000000 0.000000

展開閱讀全文

溫馨提示:
1: 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

點擊下載此資源

黑白球三維排列游戲

最新文檔

相關(guān)資源

相關(guān)搜索