質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

解決済

3回答

363閲覧

JavaのOutOfMemoryを解決することができません

HAL_2487

総合スコア13

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

0クリップ

投稿2019/03/23 00:56

前提・実現したいこと

下記のアルゴリズムの問題に挑戦をしておりまして、Javaで実装してみたのですが
OutOfMemoryが解決できなくて正解を導き出すことができません。
どのように変更したら解決できそうかアドバイスをいただけたらと思います。
宜しくお願い致します。

【問題】
男女それぞれで15人の学級で、横6×縦5の座席で席替えを行います。
前後左右のいずれかに必ず異性が座る男女の配置が何通りあるかを
求めてください。(左右、前後などの反転は別々とカウントすることにします、また
個々の生徒がどこに座るかは無関係で、男女の配置のみを考えるものとします)

下記のようなパターンはNGなのでカウントできません。

NG例1  中央の男の前後左右すべてが男であるのでNG(女も同様)

列1列2列3

NG例2  右端の上と左がどちらも女であるのでNG(男も同様)

列1列2列3

発生している問題・エラーメッセージ

Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded at algolithm.Q69.clone(Q69.java:145) at algolithm.Q69.main(Q69.java:43)

該当ソースコード

package algolithm; import java.awt.Point; import java.time.LocalDateTime; import java.util.ArrayDeque; import java.util.Queue; public class Q69 { private static int side = 6; private static int length = 5; public static void main(String[] args) { System.out.println("処理開始:" + LocalDateTime.now()); int startSeatLineup[][] = setData(side + 2, length + 2); int count = 0; int sidezero = 0; int lengthzero = 0; Queue<int[][]> queue = new ArrayDeque<int[][]>(); queue.add(startSeatLineup); while (!queue.isEmpty()) { boolean zeroNone = true; int[][] seatLineupState = queue.remove(); //ゼロのある場所を特定する loopEnd: for (int k = 0; k < length + 2; k++) { for (int n = 0; n < side + 2; n++) { if (seatLineupState[k][n] == 0) { sidezero = k; lengthzero = n; zeroNone = false; break loopEnd; } } } if (zeroNone) { count++; print(seatLineupState); continue; } for (int d = 1; d <= 2; d++) { int[][] tmp = clone(seatLineupState); tmp[sidezero][lengthzero] = d; if (harfJudge(tmp)) { if (changeSheetCheck(tmp)) { queue.add(tmp); } } } } System.out.println(count + "通り"); System.out.println("処理終了:" + LocalDateTime.now()); } //男女それぞれの人数が全体の半数を超えているかいないかを判断する private static boolean harfJudge(int[][] tmp) { boolean halfAnswer = true; int manCount = 0; int womanCount = 0; for (int e = 0; e < length + 2; e++) { for (int w = 0; w < side + 2; w++) { if (tmp[e][w] == 1) { manCount++; } else if (tmp[e][w] == 2) { womanCount++; } } } if (manCount > side * length / 2 || womanCount > side * length / 2) { halfAnswer = false; } return halfAnswer; } //上下左右が全て同性でないかをチェックする private static boolean changeSheetCheck(int[][] seatLineup) { boolean check = false; loopEnd: for (int r = 0; r < length + 2; r++) { for (int q = 0; q < side + 2; q++) { if (seatLineup[r][q] == -1) { continue; } else if (seatLineup[r][q] == 0) { break loopEnd; } check = false; Point point = new Point(r, q); point.translate(0, -1); if (!(seatLineup[point.x][point.y] == seatLineup[r][q]) && !(seatLineup[point.x][point.y] == -1)) { check = true; } point.setLocation(r, q); point.translate(0, 1); if (!(seatLineup[point.x][point.y] == seatLineup[r][q]) && !(seatLineup[point.x][point.y] == -1)) { check = true; } point.setLocation(r, q); point.translate(-1, 0); if (!(seatLineup[point.x][point.y] == seatLineup[r][q]) && !(seatLineup[point.x][point.y] == -1)) { check = true; } point.setLocation(r, q); point.translate(1, 0); if (!(seatLineup[point.x][point.y] == seatLineup[r][q]) && !(seatLineup[point.x][point.y] == -1)) { check = true; } if (!check) { break loopEnd; } } } return check; } //初期状態のセット 誰も席に座っていない private static int[][] setData(int side, int length) { int seatLineup[][] = new int[length][side]; for (int i = 0; i < length; i++) { for (int j = 0; j < side; j++) { if (i == 0 || i == length - 1 || j == 0 || j == side - 1) { seatLineup[i][j] = -1; } else { seatLineup[i][j] = 0; } System.out.print(seatLineup[i][j] + " "); } System.out.println(""); } System.out.println(""); return seatLineup; } private static int[][] clone(int[][] target) { int[][] res = new int[length + 2][side + 2]; for (int col = 0; col < length + 2; col++) { res[col] = target[col].clone(); } return res; } private static void print(int[][] seatLineupState) { for (int s = 0; s < length + 2; s++) { for (int v = 0; v < side + 2; v++) { if (seatLineupState[s][v] == -1) { continue; } if (seatLineupState[s][v] == 1) { System.out.print("●" + " "); } else { System.out.print("○" + " "); } } System.out.println(""); } } }

試したこと

下記でクローンしているところを、クローンを使わずに別の配列にひとつずつ値を詰め直してみたりもしましたが結果は変わりませんでした。

private static int[][] clone(int[][] target) { int[][] res = new int[length + 2][side + 2]; for (int col = 0; col < length + 2; col++) { res[col] = target[col].clone(); } return res; }

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答3

0

キューに配列を詰めすぎて、メモリが足りなくなっています。その状態で配列を作ろうとしたため、そのエラーが出ます。クローンだろうが配列コピーだろうがこれは変わりません。
ちゃんと見たわけではありませんが、アルゴリズムから無理があると思われます。

投稿2019/03/23 01:50

swordone

総合スコア20649

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

HAL_2487

2019/03/23 09:32

ご回答いただきましてありがとうございます! やっぱり現状のままでは少しプログラムを変えるぐらいでは難しそうですね。 キューを使わずに実装できる方法を考えて試してみようかと思います。
guest

0

男女2択, 5x6=30 なので, int seats (の下位30ビット)で着席状態を表現できます.
合っているか確認していませんが...

処理開始:2019-03-23T14:34:10.785 有効件数:13374192 処理終了:2019-03-23T14:34:29.876

java

1package algolithm; 2 3import java.time.LocalDateTime; 4 5public class Q69 { 6 private static final int SIDE = 6; 7 private static final int LENGTH = 5; 8 private static final int HARF = 15; 9 10 public static void main(String[] args) { 11 System.out.println("処理開始:" + LocalDateTime.now()); 12 int count = 0; 13 for(int seats=(1<<HARF)-1; seats <= ((1<<HARF)-1)<<HARF; seats++) { 14 if(checkSeats(seats)) { 15 count ++; 16 //System.out.println("---- "+count); 17 //printSeats(seats); 18 } 19 } 20 System.out.println("有効件数:" + count); 21 System.out.println("処理終了:" + LocalDateTime.now()); 22 } 23 24 /** 25 * 着席状態が有効かを返す. 26 * @param seats 着席状態 27 * @return true=有効(ビット'1'=15, 全席異値との隣接あり) 28 */ 29 private static boolean checkSeats(int seats) { 30 if(Integer.bitCount(seats) != HARF) return false; 31 for (int length = 0; length < LENGTH; length++) { 32 for (int side = 0; side < SIDE; side++) { 33 if(!checkCross(seats, length, side)) return false; 34 } 35 } 36 return true; 37 } 38 39 /** 40 * 指定した席の値(0 or 1)を返す. 41 * @param seats 着席状態 42 * @param length Y 43 * @param side X 44 * @return 0 or 1 45 */ 46 private static int getBit(int seats, int length, int side) { 47 return (seats >> (length * SIDE + side)) & 1; 48 } 49 50 /** 51 * 指定した席の周囲(前後左右)の値をチェックする 52 * @param seats 着席状態 53 * @param length Y 54 * @param side X 55 * @return true=問題なし(周囲に異値あり), false=問題あり(周囲が同値のみ) 56 */ 57 private static boolean checkCross(int seats, int length, int side) { 58 int v = getBit(seats, length, side); 59 if(length > 0) if(getBit(seats, length-1, side) != v) return true; 60 if(length < LENGTH-1) if(getBit(seats, length+1, side) != v) return true; 61 if(side > 0) if(getBit(seats, length, side-1) != v) return true; 62 if(side < SIDE-1) if(getBit(seats, length, side+1) != v) return true; 63 return false; 64 } 65 66 /** 67 * 着席状態を表示する 68 * @param seats 着席状態 69 */ 70 private static void printSeats(int seats) { 71 String[] marks = { "○", "●" }; 72 for (int length = 0; length < LENGTH; length++) { 73 for (int side = 0; side < SIDE; side++) { 74 System.out.print(marks[getBit(seats,length,side)]); 75 } 76 System.out.println(); 77 } 78 } 79}

投稿2019/03/23 05:20

編集2019/03/23 05:37
jimbe

総合スコア12545

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2019/03/23 05:27

男子・女子・欠席のきがしたが席順変更だから 2^30 でいいのか
HAL_2487

2019/03/23 10:13

ご回答いただきましてありがとうございます! 問題の答えを書いておらず申し訳ありませんでした。 有効件数合っております! コードもシンプルですごく読みやすいのですが、私がまだ未熟者でビットを使っての実装をしたことがないのでどのようなプログラムになっているのかがまだ正直わかっておりません。 実装していただいたコードを少しずつ解読して、理解したいと思います!
jimbe

2019/03/23 11:31

int の各ビットを席と考えて, 「2次元配列を展開した( '0' と '1' しか入らない)1次元配列」として扱っています.
guest

0

ベストアンサー

アルゴリズムそのものは正しいと思います。しかしキューの大きさは
1
2 (男、女)
3 (女, 男男、男女)
4 (男男、男女, 女男, 女女)
...
のようにキューから取り出した「不完全な座席表」に「条件に反しないようにして男・女を座らせてそれを再びキューに入れる」という方針のため最終的にあり得る全ての組み合わせがキューに登録されることとなります。座席表はintの87の二次元配列であり4byte8*7=224byte+α程度のメモリーを要しますので組み合わせの数が万オーダーなら2MB程度となり結果が出せると思います。
しかし組み合わせの数がもっと大きな数になるとしたらこのアプローチで「計算機を用いて」解を出すには少々苦しそうです。ご存じのとおり計算機の記憶域(メモリー)は有限ですので。

本件の問題条件のうち「男女15人ずつ」という条件の組み合わせは30席の中から男が座る席15個を取り出す組み合わせと考えることができるので30C15=155,117,520、つまり約150メガ通りです。
「上下左右に異性が座っていること」という条件でかなり組み合わせの数が小さくなるでしょうけどもそれでも相当の大きさになりそうですので質問者さんのプログラムのアプローチでは少々厳しそうです。

キューに「これから計算しなくてはならない全ての候補」を登録するのではなく「今探索している組み合わせだけを記憶する」というアプローチにするとメモリー消費がそれほど激しくならないように思います。

例えばキューによるループの代わりに「不完全・あるいは完全な座席表」を引数にした関数

int countCombination(int[][] seat)

を考え、「与えられた座席表を元に生成できる条件に合う組み合わせの数を返す」というアプローチにしてはいかがでしょう?

  • もし座席表に空きがあるなら

今のアプローチと同様、空いている席に「男」「女」を座らせてみて、それぞれが条件に反しないなら新たな座席表に対して自分自身を呼び出し返ってきた組み合わせが求まる。

  • もし座席表に空きがないなら

条件が成立している完全な座席表のはずだから1を返す。

座席表は30席ですので再帰呼び出しを用いたとしてもスタックオーバーフローにはならないでしょう。また最大でも座席表は30個程度しか一時に存在しないので元のプログラムのようにメモリーがパンクするようなこともないでしょう。

java

1... 2static int countCombination(int[][] seat) { 3 if (座席表に空きがある) { 4 int count = 0; 5 for (int gender = 1; gender <= 2; gender++) { 6 int[][] seat1 = clone(seat); 7 seat1[空き位置] = gender; 8 if (seat1の男・女の数が15人を超えない && seat1で上下左右に異性が座っている) { 9 count += countCombination(seat1); 10 } 11 } 12 return count; 13 } else { 14 return 1; 15 } 16} 17...

こんな雰囲気です。キューを廃して再帰呼び出しに変える以外の論理はとりあえず元のコードを生かすことにして一度やってみてはいかがでしょうか?

投稿2019/03/23 04:14

KSwordOfHaste

総合スコア18392

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

KSwordOfHaste

2019/03/23 04:19

例示したコードは考え方を書いたため文法エラーがでるようなコードです。それでも質問者さんご自身には「何を言わんとしているか」をくみ取っていただけるのではないかと思い文法エラーがない完全なコードにまではしませんでした。
HAL_2487

2019/03/23 10:00

ご回答いただきましてありがとうございます! キューを使用した今の実装のままでは難しそうですね。 コメントいただきました「与えられた座席表を元に生成できる条件に合う組み合わせの数を返す」というアプローチは全く発想がありませんでした。 このやり方であれば現状のアプローチに比べて、かなり効率的に実装できそうですね。 ご参考にさせていただいてキューを使わずに再帰を使うアプローチで組み直してみたいと思います。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問