探索アルゴリズムについて調べてみた

探索アルゴリズムについて調べてみた。
特に幅優先とか深さ優先とか調べたいね。

982 views

幅優先ってなに?

幅優先探索は解を探すために、グラフの全てのノードを網羅的に展開・検査する。最良優先探索とは異なり、グラフ全体を目的のノードがみつかるまで、目的のノードに接近しているかどうかなどは考慮せず探索する(Wikipedea)。

実装_キュー

幅優先の探索は、「キュー」と呼ばれるデータ構造を用いて実装できる。
ここでは、キューを使って実装する。

コード

  1. import os
  2. import queue
  3. # ベースとなるパスとパスを入れておくリスト
  4. basePath = os.path.join(os.path.join(os.environ['USERPROFILE']), 'Sample')
  5. baseDir = os.listdir(path=basePath)
  6. #検索対象のファイル
  7. target = "ロース"
  8. #キュー(キューにはpathを保存する)
  9. que = queue.Queue()
  10. # 最初に取得できるフォルダをスタックに保存する
  11. for i in baseDir:
  12. path = basePath + '\\' + i
  13. que.put(path)
  14. print('検索対象のファイル名:', target)
  15. # フォルダ取得
  16. def searchDir(path):
  17. try:
  18. # 子があるとき
  19. # 取得したフォルダ(複数)を
  20. matchDirs = os.listdir(path=path)
  21. for i in matchDirs:
  22. # キューにpathを入れる
  23. newPath = path + '\\' + i
  24. que.put(newPath)
  25. except:
  26. # 子がないとき
  27. return None
  28. while not que.empty():
  29. targetPath = que.get()
  30. print('検索対象:', targetPath)
  31. if (targetPath.count(target) == 0):
  32. searchDir(targetPath)
  33. else:
  34. print("見つかりました")
  35. print("答え:", targetPath)
  36. break
  37. if que.empty():
  38. print("見つかりませんでした")

出力

見つかるとき

見つからないとき

検索の順路

Page 4 of 5.

前のページ 次のページ



[添付ファイル]


お問い合わせ

プロフィール

owl

自己紹介

駆け出しエンジニア
だいたいweb系をかじってる
最近ちょとブロックチェーンに興味出てきた

サイト/ブログ

https://github.com/owl0109

ツイッター

@kijiken1