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

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

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

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Java

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

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

4回答

1845閲覧

最小値を求めたいです。

退会済みユーザー

退会済みユーザー

総合スコア0

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Java

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

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2018/03/16 02:15

前提・実現したいこと

 Excelで以下の図1のようにセルに一つずつ0~9の整数を入れる作業をしていたところ、
作業で疲れたので少し休もうと近くあった高校の教科書「数学A」を手に取って読んでいました。
(「これマジで懐かしいなぁ・・・」と思いながら)
そこで場合の数のところの最短経路問題のページを見た瞬間、下の図に似ていることに
気づきました。
最短経路問題のように左上から右下まで移動したとき(図2のように)
セル上にある数字を足していきゴールに到達したところまでの合計値を求めることが
できます。今回実現したことはこの合計値の最小値を求めることです。
ただし、経路はすべてn×nの正方形です。
イメージ説明
イメージ説明

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

実際、自分なりにアルゴリズムを考えてプログラミングを構築しましたが、あまりにも実行時間が
長すぎるため、もっと高速化したい。(そもそも考え方自体を変える必要があるかもしれない。)

該当のソースコード

(使用言語: Java8)

package sum; import java.util.*; import java.math.BigInteger; import static oracle.jrockit.jfr.events.Bits.intValue; public class Sum { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String line = sc.nextLine(); /*入力*/ String []data = new String[line.length() - 1]; int [][]number = new int[line.length()][line.length()]; int n = line.length(); int sum; for(int i = 0; i < line.length() - 1;i++){ data[i] = sc.nextLine(); /*ここまでが入力*/ } for(int i = 0; i < line.length(); i++){ number[0][i] = Integer.parseInt(line.substring(i,i+1)); } for(int i = 1; i < line.length(); i++){ for(int j = 0; j < line.length(); j++){ number[i][j] = Integer.parseInt(data[i - 1].substring(j,j+1)); } } BigInteger start = ruijou(n - 1).add(new BigInteger("-1")); BigInteger last = (start.add(new BigInteger("1"))).multiply(start); BigInteger i = start; String line2; int count; int count2; int x; int y; int min = 154781; while(i.compareTo(last) <= 0){ sum = number[0][0]; x = 0; y = 0; line2 = binary(i,n - 1); count = count_number(line2,0); count2 = count_number(line2,1); if(count == n - 1 && count2 == n - 1){ for(int j = 0; j < line2.length(); j++){ if(Integer.parseInt(line2.substring(j,j + 1)) == 0){ x++; sum += number[y][x]; } else if(Integer.parseInt(line2.substring(j,j + 1)) == 1){ y++; sum += number[y][x]; } } if(min > sum){ min = sum; } } i = i.add(new BigInteger("1")); } System.out.println(min); } public static BigInteger ruijou(int n) { BigInteger sum = BigInteger.ONE; for (int i = 1; i <= n; i++) { sum = sum.multiply(new BigInteger("2")); } return sum; } public static String binary(BigInteger n,int length) { BigInteger []binary = new BigInteger[length * 2]; int []binary2 = new int [length * 2]; for(int i = 0; i < length * 2; i++){ binary[i] = new BigInteger("0"); } int digits = 0; while(n.compareTo(new BigInteger("0")) > 0){ binary[digits] = n.remainder(new BigInteger("2")); n = n.divide(new BigInteger("2")); digits++; } for(int i = length * 2 - 1; i >= 0; i--){ binary2[i] = intValue(binary[i]); } char []buf = new char[length * 2]; for(int i = 0; i < length * 2; i++){ buf[i] = (char)('0' + binary2[length * 2 - 1 - i]); } String str = String.valueOf(buf); return str; } public static int count_number(String str,int n) /*nがいくつあるか数える関数*/ { int count = 0; for(int i = 0; i < str.length(); i++){ if(Integer.parseInt(str.substring(i,i+1)) == n){ count++; } } return count; }

試したこと

質問のところでは 8×8の正方形の図を使用しましたが、試したことを簡単に説明するために
3×3(図3)で説明したと思います。
まず、標準入力でint型の2次配列に0~9の数字を格納します。(これは自力で,できました。)
ここから自分が考えた最小合計値を求めるアルゴリズムを説明します。
まず、正方形の大きさが3×3なので右に2 下に2 移動することがわかります。
ここで2進数を使うことを思いつきました。
桁の数字が0の時 右、1の時 下に行くときは1と考えて、経路の通り方が右、右、下、下 の
場合は0011となります。(このように先頭が0の場合もある.)
3×3の場合,右と下 合計4回移動するので二進数の0と1の個数はそれぞれ2個ずつ
計4個ということになります。
つまり、最小値0011 最大値1100のfor文を作り、その中で演算を施せばいいと思いました。
詳しく述べますと、
1.最小値から1ずつ増やしていき0と1がそれぞれ2個ずつあるかチェックする。
(条件にあった場合だけ2に進む。)
2.桁の数が0の時は右、1の時は下に行き、その場所にある整数を足します。
3.あらかじめ、用意した最小値よりも小さい合計値が出た場合は最小値を更新します。

イメージ説明

4.右、右、下、下の時は図4のようになり、合計値は
1+7+9+0+5=22になります。

これを一般化するとn×nのとき、0と1がそれぞれ(n - 1)個ある二進数の
最小値0000...1111と最大値1111....0000のfor文を使います。
しかし、これだとnの数が大きくなった時、処理に時間がかかります。
そもそも、二進数のところの最小値と最大値のところは、すべて10進数を2進数に
変える関数を使って(自分で作ったものですが)計算しています。
(n = 10の時は0と1がそれぞれ9個ずつなので最大値は10進数で約2^18と
大きな数字になり、for文のループする回数が多くなる。)
nが大きいとき条件に合わない2進数が多すぎて処理に時間がかかっているのです。
最小値と最大値はそれぞれ10進数で表すことができたので、
(ソースコードではそれぞれstart,lastにしてあります。)
これを解決するには
1.0と1がそれぞれ(n-1)個ある2進数のみ抽出できるようにする。
(これができると処理時間が短くて済む。具体的な数だと(2n-2)!/{(n - 1)!}{(n - 1)!})
2.そもそもこの考え方以外にもっと効率的な考え方がある

が考えられます。どなたがご教授お願い致します

補足情報(FW/ツールのバージョンなど)

NetBeans IDE 8.1 Java言語でプログラミングを構築しています。

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

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

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

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

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

guest

回答4

0

すみません。提示コードは見ていません。
このような場合は「どの方向から来たか(左or上)」と「その地点の累積長」を格子分保持するメモを利用するのが一般的です。

たとえば以下の例での(1,1)の地点では、上側の「→8」と左側の「↓9」を比べ、小さいほうの上側を選び「↓10(2+8)」となります。
これを左上(スタート)から右下まで順に行うと、右下(ゴール)地点での最小値が求まります。
また、右下(ゴール)から、記録された方向データをもとに逆に追っていくと経路が分かります。

あ、方向データはいらないですね。
逆から経路を追っていくときも小さいほうを辿ればいいので。

イメージ説明

投稿2018/03/16 02:50

編集2018/03/16 03:40
can110

総合スコア38233

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

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

0

右か下しかないなら、「ダイクストラ法」を調べてみては?

投稿2018/03/16 03:21

swordone

総合スコア20649

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

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

KSwordOfHaste

2018/03/16 04:24

4方向全部ありでもダイクストラ法でOKではないのでしょうか?
guest

0

ベストアンサー

投稿2018/03/16 02:34

mkgrei

総合スコア8560

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

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

退会済みユーザー

退会済みユーザー

2018/03/16 05:31

回答ありがとうございました。紹介してくださったサイトを参考に無事解決することができました。 今回の問題を通して一つの概念にとらわれず、いろいろなアイデアで解く大切さを知りました。 おかげで、実行時間の短縮に成功しました。ありがとうございます。
guest

0

今の実装は、以下の時、すべて0を通りますか?

-----
00000
11110
00000
01111
00000

質問に記載の感じだと、右と下しか考慮されていないようなので、
左と上も追加する必要があると思います。
(ソースにコメントがほどんどないので、ソース読んでません、すいません。)

あとはfor文やwhile文にbreakの条件を付けることができれば、
実行時間は短縮すると思います。

なんとなくですが、考えたのは、
1セル1セルの数字をデータ構造として保持して、
スタックに積んだほうが計算しやすいんじゃないかと。

明確な回答じゃなくてすいません。

追加データパターン

-----
00000
43219
54329
09999
00000

投稿2018/03/16 02:52

編集2018/03/16 03:26
szk.

総合スコア1400

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

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

退会済みユーザー

退会済みユーザー

2018/03/16 03:11

回答ありがとうございます。すみませんが、私が考えているのは スタート地点が一番左上、ゴール地点が一番右下における正方形の中で 最短経路をたどりその合計値の最小値を求めることです。 (3×3の場合は最短経路が6通りあります。この6個の中で最小値を求めることになります。) よって、最短経路をたどるとき スタート地点から右と下方向だけでゴールに到達するため、 左方向と上方向にはいきません。 (逆走になるので)説明不足で誤解を招いてしまい すみません。
szk.

2018/03/16 03:26

条件的に 第1条件:最短 第2条件:最小 ということですね。。。 データパターン上、総当たりしないとダメな気がします。 特異なデータパターンですが追加しました。 最小は9ですが、これを通すには全ルート確かめないと出てこないと思います。 (ゴールからたどれば一発ですが。。。)
mkgrei

2018/03/16 03:57

横から失礼します。 全ルートを試す時に、過去の探索結果をできうる限りメモして再計算しない方法というのが「ダイクストラ法」かと。
KSwordOfHaste

2018/03/16 04:22

一般化された網での最短経路(経路の重み最小)がダイクストラ法のポイントと思うので、むしろ逆走とかそういう仮定自体がないように思います。
szk.

2018/03/16 04:34

はい、ダイクストラ法を否定しているわけではなく、 全パターンを計算と結果がわからないと考えているだけです。 ダイクストラ法ちょっと理解難しいんですが、 mkgreiさんが最初に提示されているtree構造にして、 そこまでの計算結果を残しておけば処理速度は速くなると思います。 一番最後のノードで最小の計算結果を評価すればいいだけなので。 仮にすべて同じ数字だった場合は、何が期待されるのでしょうか。 おそらくどんなアルゴリズムを使っても全パターン算出してしまうかと。
KSwordOfHaste

2018/03/16 04:37 編集

あーごめんなさい、自分のコメントは直前のmkgreiさんの「四方向進める時にもダイクストラで解いてる…」に対するものです。 --- あ・・・szk.さんコメント自体がmkgreiさんに対するものですね! (バッタリ orz)
mkgrei

2018/03/16 04:36

KSwordOfHasteさん、コメントをありがとうございます。 おっしゃるとおりですね。 問題の定式化次第で問わず解けるのがダイクストラ法ですね。 もともとのシンプルの問題の場合はもっと素直な動的計画法で解けて、 それをダイクストラ法の文脈で読み替えることは可能である、と。 でもダイクストラ法は広い意味で動的計画法である、と。 認識が誤っていたら正してください。 よろしくお願い致します。
mkgrei

2018/03/16 04:37

szk.さん、すべて同じ数字の場合、if文の書き方次第で上L字か、下L字になる気がします。
KSwordOfHaste

2018/03/16 04:47

> もっと素直な動的計画法 そんな気がします。 ちなみにcan110さんの方法は事実上ダイクストラ法のバリエーションとみなすこともできるように思いました。経路が片方向になっている特別な場合という感じで。
KSwordOfHaste

2018/03/16 04:51

to: szk.さん > 仮にすべて同じ数字だった場合は、何が期待される? 大抵の場合「最短経路を全て求めたい」のではなく「最短経路の一つを早く見つける」ことにポイントを置くのではないでしょうか?ご質問のタイトルは「最小値を求めたい」なので最短経路が一つ見つかれば済むというふうに見えました。
szk.

2018/03/16 05:03

mkgreiさん 結果的には、上L字か下L字になると思います。 ただ、性能的にはすべてのパターンを計算した結果が上L字か下L字になるので、 かなり実行時間がかかるものだとも思っています。 KSwordOfHasteさん 少なくとも右と下にしか行けない前提だと、どのパターンも最短経路になります。 全てが最短経路なわけですから「最短経路の一つを早く見つける」ではなく、 「最小値を求めたい」というところにポイントを置いて考えています。 その最小値が本当に最小値か判断するのに、全パターン確認する必要があり、 それは何かのアルゴリズムで早くなったり簡単になったりするものではないかと。
KSwordOfHaste

2018/03/16 05:09 編集

うーん、混乱させたようでスミマセン。自分がいう最短経路は「経路上の数字の合算」のことで本件の問題の「格子状にならんだ経路の幾何的な距離」のことではないです。
mkgrei

2018/03/16 05:15

szk.さん そのような問題は非常に特殊なケースになります。 同じ数字が反復するブロックが多く発生する問題の場合、事前にブロックを数個分割してしまう前処理が考えられます。 後はコーディングの面倒さとそれによって得られるご利益が釣り合うかですね。
szk.

2018/03/16 05:27

KSwordOfHasteさん なんて言うんですかね。。。 「経路上の数字の合算」の最小値は、 全てのパターンを確認しないと分からないと考えているのと、 それは処理時間がかかるものだと言いたいだけなのですが。。。 すべて同じ数字だった場合に、 その合算値が最小値かどうかって最後のパターンを通すまで分からなくないですか。 単純に左か下かで判断するとそれは最小の合算値として正しくない。 そのルート(パターン)で最小値を求めないといけないわけで。。。。 mkgreiさん はい、最初に申している通り特異なデータパターンです。 ただ同じ数字でなくても、789789・・・が続くパターンなど、 特異なパターンと特異でないパターンを切り分けるのは不可能だと思っています。
mkgrei

2018/03/16 05:34

szk.さん 多分KSwordOfHasteさんは全パターンが答えとしてあり得るが、全探索後にそのうちの1つが選ばれるということを言っているのだと思います。 探索せずには最小であることを保証できません。 また、切り分けが不可能な場合は素直にやるしかありません。 切り分けが可能な場合にのみ高速化できます。
退会済みユーザー

退会済みユーザー

2018/03/16 06:52 編集

皆さん、回答ありがとうございます。 自分が最初考えた2進数のアイデアはコードを書くときも苦労した上に実行時間が長かったのですが ダイクストラ法をはじめ、たくさんの方のアイデアを参考にして 無事解決することができました。(実行時間が短くなりました。) 解決できなかった原因は、私の頭が固いことと一つの概念にとらわれすぎていること そして知識不足だったことが挙げられます。やはり考えた方を根本から変えるべきでした。 皆さんのおかげで一つ問題を解決することができてうれしいです。 本当にありがとうございます。
KSwordOfHaste

2018/03/16 05:44

> 「経路上の数字の合算」の最小値は、全てのパターンを確認しないと分からないと考えている 総当たりで解くこと前提に考えるとそうなるのですが、そこをうまく「全部の組み合わせを調べなくてよい」方法も往々にしてあり、本件もそういうものの一つです。can110さんの回答(自分は勝手に変形ダイクストラ法といっちゃいます)を使うとそういうことができます。 この方法ですが、あるセルの下と右のセルを糸で結んでその糸の長さがもとのセルの数字であるような長さであると仮定し、左上端のセルを指でつかんでそーっと上に引き上げると糸が短い経路のセルが早く引き上げられそのようなセルを繋ぐ糸だけが「ピーン」と張ったような感じになる・・・そんなイメージを計算したのがダイクストラ法といっていいんじゃないでしょうか。
szk.

2018/03/16 05:58

mkgreiさん >多分KSwordOfHasteさんは全パターンが答・・・ お~そういうことですか。 私が非常に特異なパターンを出してしまったからですね、すいません。 KSwordOfHasteさん そうですね、総当たりに近い感じで考えていましたが、 おっしゃる通りcan110さんの回答は、 全ノードで計算することで結果が求まるって言っているんですね。 直感的な解説ありがとうございます。 Stars1024さん いろいろお騒がせしました。 私自身も勉強になりました、ありがとうございます。
退会済みユーザー

退会済みユーザー

2018/03/16 06:03

ごちらこそありがとうございます。私自身も勉強になりました。
can110

2018/03/16 06:14

流れに追いつけていませんが(^^; 私の回答は問題文の「左上から右下まで移動した」より「次は右か下にしか移動できない」という制約をもうけています。 ですので「上下左右に動ける」場合 [1,9,9,9,9,9], [1,9,1,1,1,9], [1,1,1,9,1,9], [9,9,9,9,1,9], [9,9,9,9,1,1], [9,9,9,9,9,1]] のような上に抜けるルートがある場合は正しい答えが得られません(^^; で、上下左右移動できる場合は、各ルートを再帰で探索していく(最悪全パターン走査する)必要があります。 ただこkの場合でも、ある地点の累積値をメモ化しておくと枝刈ができるので、全パターン走査されることほぼないはずです。
szk.

2018/03/16 06:29

Stars1024さん >新たに書いたコードを乗せようと思うのですが(アルゴリズムの説明も含む)・・・ 何を目的に乗せようと思っていますか? 新しいコードに何か具体的な問題がありますか? 単純にレビューしてほしいとかだったらteratailへの投稿やめておいたほうがいいです。 can110さん コメントありがとうございます。 「上下左右に動ける」場合、、、、、、 ちょっと考えないことにしましょう! 午後の仕事に響きますw
退会済みユーザー

退会済みユーザー

2018/03/17 08:38 編集

皆さんのおかげで無事解決できたのでそのコードを載せるという意味です やめたほうがいいのでしょうか?
szk.

2018/03/16 06:37

はい、不要だと思います。 どうしてもというのであれば、この質問を編集して、 質問の最下部に追記されるのがいいかと。
退会済みユーザー

退会済みユーザー

2018/03/16 06:40

分かりました。teratail初心者で何もわからず ご迷惑をおかけしすみませんでした。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問