黑白球三維排列游戲

上傳人：仙*** 文檔編號(hào)：30075987 上傳時(shí)間：2021-10-09 格式：DOC 頁(yè)數(shù)：16 大?。?67.50KB

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

第1頁(yè) / 共16頁(yè)

第2頁(yè) / 共16頁(yè)

第3頁(yè) / 共16頁(yè)

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

15 積分

下載資源

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

資源描述：

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

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

2、一個(gè)0--1變量：表示第i個(gè)盒子中裝有白球，表示第i個(gè)盒子中裝有黑球，如此引入的0—1變量共有27個(gè)。并且由于黑球的個(gè)數(shù)為14，因此。 1. 可能的直線對(duì)于此問(wèn)題，首先需要知道：在這個(gè)333的三維陣中,哪些小方盒連接起來(lái)可以構(gòu)成一條直線？這樣的直線共有多少條？為了確定這些直線，我們首先考慮此333的三維陣的行、列和縱三個(gè)方向上的9個(gè)截面上的直線有哪些，然后考慮不全在任何一個(gè)截面上直線有哪些。與水平面平行的截面有三個(gè)，見(jiàn)圖2。對(duì)應(yīng)于每一個(gè)截面上的三點(diǎn)共線的情況共有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個(gè)，見(jiàn)圖3和圖4。與圖3對(duì)應(yīng)的每一個(gè)截面上共線的三點(diǎn)情況也有8種，由于它們與圖1中的情況會(huì)出現(xiàn)重疊，去掉重疊的三種情況，新增加的三點(diǎ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對(duì)應(yīng)的每一個(gè)截面上共線的三點(diǎn)情況也有8種，由于它們與圖1和圖2中的情況會(huì)出現(xiàn)重疊，去掉重疊的6種情況，新增加的三點(diǎn)共線情況各有2種，分別記為： S7={{1,13,25},{7,13,19}}；S8={{2,14,26},

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

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

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

8、根據(jù)我們計(jì)算出來(lái)的結(jié)果可知，相同顏色的最少的直線數(shù)為4條，并且有許多的備擇解，下面給出其中一種解的圖形表示（圖6），圖中灰色的盒子表示放黑球，白色的盒子放置白球。黑白球按照?qǐng)D6所示的放置方法，所形成的四條直線為： {4,13,22}，{10,13,16}全由白球相連構(gòu)成； {6,15,24}，{12,15,18}全由黑球相連構(gòu)成。六、模型推廣及討論（略）. 七、參考文獻(xiàn) [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

展開(kāi)閱讀全文

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

點(diǎn)擊下載此資源

黑白球三維排列游戲

最新文檔

相關(guān)資源

相關(guān)搜索