3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

最初に「あい」を学ぶことば日本語でプログラミング入門(Mindで定番アルゴリズム: 幅優先探索 BreadthFirstSearch)

3
Posted at

はじめに

本記事シリーズは母国語のプログラミング言語が存在するという文化的価値をアピールするためのもので、プログラミング一般の入門を意図するものではありません。とはいっても題材としては定番アルゴリズムのいくつかを疑似言語ではなくコンパイル・実行可能なプログラミング言語の日本語で書いてみようというたてつけとなります。

Mind(マインド)

プログラミング言語Mind(マインド)は自然な日本語で記述できるスタック指向の軽量中間コードコンパイラ言語です。ただし単語間の分かち書きが必須であくまで形式言語です。逆ポーランド記法1の範囲で分かち書きされた日本語単語の語順が自然と日本語の語順となるという意味の「自然さ」で書くことができ、独自の軽量中間コードのランタイム実行で非常に高速です。実装言語はCまたはMind。初版の登場は1985年で2025年は生誕40周年となりました。

Mind(マインド)の入手方法

無償版のMind version 8 (windows版linux版)を下記の公式サイトからダウンロードできます。フリーメールでかまいませんのでメールアドレスをご登録くださいませ。

定番アルゴリズム:幅優先探索(BeadthFirstSearch)とは

アルゴリズムは、問題を解決するための手順や計算方法を意味します。アルゴリズムにはいくつかの定番ロジックが存在します。

ここではその中のひとつ「幅優先探索(BFS)」を扱ってみます。「幅優先探索」はグラフや木構造を探索するための定番アルゴリズムの一つです。これは出発点から近い順にノードを順番に探索するロジックとなります。

同様の定番アルゴリズムに「深さ優先探索(DFS)」がありますが、それはこちらの記事をご参照ください。

「幅優先探索」での「近い」とはダイクストラ法のような距離やウェイトを考慮したものではなく、あくまで隣接点の数を意味します。一般的なキュー(線形キューまたは循環キュー)を使います。今回は線形キューを使用します。

「優先度付きキューを使ったダイクストラ法」は、こちらの記事をご参照ください。本記事はこちらの記事の実装の修正版となります。

「線形キュー」は、こちらの記事をご参照ください。

お題のソースコード

今回は下記のような経路を想定します。数字は頂点の番号で4つの頂点があるとします。このロジックでは頂点同士が隣接しているかどうかが問題で、距離などの属性はありません。

  1 --→ 2 --→ 4
   \          ^
    \        /
     +-→ 3 ─+

上記のグラフの頂点間の関係を隣接行列で表現すると下記のようになります。

//F:From T:To
F/T 1 2 3 4
1   0 1 1 0 
2   0 0 0 1 
3   0 0 0 1 
4   0 0 0 0 

Mindの配列の添え字の基数は1から始まりますので、下記のような2次元配列で上記の隣接行列を記述します。

    隣接判定[1,2] = 1;
    隣接判定[1,3] = 1;
    隣接判定[2,4] = 1;
    隣接判定[3,4] = 1;

また、上記の疑似言語表現では一般的なプログラミング言語の配列表現でかぎカッコを使っていますが、Mindの場合はかっこ()表記となります。また、他の組み合わせは0で初期化されているものとします。

breadthfirstsearch.src
頂点数最大は        定数 4頂点。

隣接行列は 構造体
        隣接判定は 変数  (頂点数最大と 頂点数最大の 変数)
    到達頂点は 頂点数最大の 隣接判定
全体は 頂点数最大の 到達頂点。 

Mindの2次元配列は上記のような構造体定義で宣言されます。

breadthfirstsearch.src
隣接行列を初期化するとは (・ → ・)     本定義
    探索済カウンタを セットし
    ※1 → 2, 1 → 3, 2 → 4, 3 → 4
    隣接判定(1,2)を セットし
    隣接判定(1,3)を セットし
    隣接判定(2,4)を セットし
    隣接判定(3,4)を セットすること。

前記の2次元配列の初期化処理の疑似言語表現は、Mindの場合上記のようなイメージとなります。探索済カウンタは結果を表示するためのもので、このロジックの本質には無関係です。

下記がソースコード全文となります。仮定義を使ってメインがなるべく冒頭に来るようにして、各処理の実装はその後で定義してみました。

「"queue"を コンパイルする」は、ライブラリソースとして"queue.src"を使うという意味です。"queue.src"は、前記「線形キュー」の記事をご参照ください。

breadthfirstsearch.src
"queue"を コンパイルする。

頂点数最大は        定数 4頂点。

隣接行列は 構造体
        隣接判定は 変数  (頂点数最大と 頂点数最大の 変数)
    到達頂点は 頂点数最大の 隣接判定
全体は 頂点数最大の 到達頂点。 

探索済は 頂点数最大の 変数。 
探索順は 頂点数最大の 変数。
探索済カウンタは       変数。 

隣接行列を初期化するとは (・ → ・)     仮定義。
隣接行列を表示するとは (・ → ・)       仮定義。
幅優先で探索するとは (・ → ・)         仮定義。
結果を表示するとは (・ → ・)           仮定義。

メインとは (・ → ・)
    隣接行列を初期化し
    1で 幅優先で探索し
    隣接行列を表示し
    結果を表示すること。

隣接行列を初期化するとは (・ → ・)     本定義
    探索済カウンタを セットし
    ※1 → 2, 1 → 3, 2 → 4, 3 → 4
    隣接判定(1,2)を セットし
    隣接判定(1,3)を セットし
    隣接判定(2,4)を セットし
    隣接判定(3,4)を セットすること。

幅優先で探索するとは (頂点No → ・)       本定義
        頂点Noは 変数

    頂点Noに 入れ
    キューを初期化し
    探索済(頂点No)を セットし
    頂点Noを キューに入れ
    探索順(探索済カウンタ)に 頂点Noを 入れ
    探索済カウンタを 一つ増加し

    ここから
        キューが空? ならば 打ち切り つぎに
        キューから出して 頂点Noに 入れ
        頂点数最大で 回数指定し
            隣接判定(頂点No,回数)が 1に 等しい
            かつ 探索済(回数)が 偽?
            ならば
                探索済(回数)を セットし
                回数を キューに入れ
                探索順(探索済カウンタ)に 回数を 入れ
                探索済カウンタを 一つ増加し
            つぎに
        繰り返し
    繰り返すこと。

隣接行列を表示するとは (・ → ・)     本定義
        頂点No1は 変数
        頂点No2は 変数
    「隣接行列の状態」を 一行表示し
    「F/T 1 2 3 4」を 一行表示し
    頂点No1に 1を 入れ
    頂点数最大で 回数指定し
        頂点No1を 数値表示し 「   」を 表示し
        頂点No2に 1を 入れ
        頂点数最大で 回数指定し
            隣接判定(頂点No1,頂点No2)を 数値表示し
            「 」を 表示し
        
            頂点No2を 一つ増加
        繰り返す
        改行し
        頂点No1を 一つ増加 
    繰り返すこと。

結果を表示するとは (・ → ・)           本定義
    「幅優先探索での探索済頂点No順」を 一行表示し
    頂点数最大で 回数指定し
        「探索済頂点No:」を 表示し 探索順(回数)を 数値表示し 改行し
    繰り返すこと。

お題のソースコードをコンパイル

では、コンパイルしてみます。Mind8によるコンパイル結果です。

C:\developments\vscode\mind9\algorithm>mind breadthfirstsearc file

日本語プログラミング言語 Mind Version 8.07 for Windows
          Copyright(C) 1985 Scripts Lab. Inc.
コンパイル中 .. 終了
Coping.. c:\pmind\bin\mindex.exe --> breadthfirstsearch.exe

実行結果

実行結果です。

C:\developments\vscode\mind9\algorithm>breadthfirstsearch
隣接行列の状態
F/T 1 2 3 4
1   0 1 1 0 
2   0 0 0 1 
3   0 0 0 1 
4   0 0 0 0 
幅優先探索での探索済頂点No順
探索済頂点No:1
探索済頂点No:2
探索済頂点No:3
探索済頂点No:4

かなり芸のない出力ですが、探索順が出力されました:tada:

おわりに

いかがでしたでしょうか?わたしはわが国に母語によるプログラミング言語が存在することを誇りに思っております。言語は文化。こんにちの日本語のポップスやアニメソングなどが海外でそのまま歌われるような近況を鑑みますと、純然たる技術基盤として超強力な米欧発プログラミング言語勢と存在意義を争うこともなく、日本語の文化として海外でも日本語プログラミング言語の愛される日が来るのやもしれません。

  1. 演算子を被演算子の中間に記述する中置記法 1 + 2、前に記述する前置記法(ポーランド記法)+ 1 2、後に記述する後置記法(逆ポーランド記法)1 2 +がある。日本語は1と 2を 足す。 ↩

3
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?