研究内容:組合せ構造の表現法

フロアプランの表現法

 1つの矩形を直線分によりいくつかの小矩形へと分割した図形をフロアプランと呼ぶ。(前述の矩形配置の表現をフロアプランと呼ぶ人も多いが、我々は意図的に両者を区別している。)従来のフロアプランの表現法は主に部屋の隣接関係を無視して直線分による分割の仕方のみを表わすものと部屋の隣接関係も含めて表すものの2つに分けられる。当然であるが、部屋の隣接関係も表現する場合はそうでない場合と比べ情報量が多い分、表現法は複雑とならざるを得なかった。

 これに対し、藤巻は部屋の隣接関係を表現するにも関わらず、そうでない場合と同じく簡単な表現法、すなわち順列表現FT-Squeezeを与えた。

フロアプランの順列表現FT-Squeeze.フロアプランの部屋間の隣接の違いも表現できる.


 今まで部屋間隣接のあるn部屋フロアプランの個数を求めるのにはnに対して指数時間のアルゴリズムしか知られていなかった。井上はこの個数を求める多項式時間のアルゴリズムを考案した[1]。この新しいアルゴリズムは今までn=30程度までしか求めることができなかったフロアプランの個数を一気にn=3000以上に引き上げた。

 ここでは、新しいアルゴリズムで求めたn=50までのフロアプランの個数を公開する。

部屋数個数
1 1
2 2
3 6
4 24
5 116
6 642
7 3938
8 26194
9 186042
10 1395008
11 10948768
12 89346128
13 754062288
14 6553942722
15 58457558394
16 533530004810
17 4970471875914
18 47169234466788
19 455170730152340
20 4459456443328824
21 44300299824885392
22 445703524836260400
23 4536891586511660256
24 46682404846719083048
25 485158560873624409904
26 5089092437784870584576
27 53845049871942333501408
28 574315446827677760726480
29 6172046042022742439905880
30 66800176075969887041459650
31 727797032279902097285639818
32 7979175210417988474769109898
33 87996643649609857136893874186
34 975871936153463355091024568476
35 10879473809053799633560602384620
36 121896518654415357773911904834232
37 1372247021561689880645031943312952
38 15517737792656663385104349011331564
39 176231957251355743204854858247687356
40 2009615000401931704698869466673008476
41 23005461644986237961055740327255577036
42 264339742451516682018764742636507480960
43 3048147749840910627534840845596092241600
44 35268328310941395053942790939643805053144
45 409398797298975820082283897326536580923216
46 4767190331216074473398818435930662478776560
47 55677234499242298671920814912481143642990720
48 652139251307948986691405769245938402524850552
49 7659525505161533038519824924483385383804689680
50 90202039134736313470158945918776957766308113184

関連論文

  1. R. Fujimaki and T. Takahashi,Fujimaki-Takahashi Squeeze : Linear time construction of constraint graphs of floorplan for a given permutation,Proc. The 14th Workshop on Synthesis And System Integration of Mixed Information technologies(SASIMI2007), pp. 208-213, 2007.

  2. R. Fujimaki and T. Takahashi,A Surjective Mapping from Permutations to Room-to- Room Floorplans,IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E90-A, No.4, pp.823-828, 2007.

ページのトップへ戻る