コグノスケ

link 未来から過去へ表示  link 過去から未来へ表示(*)
link もっと前
2003年10月28日 >>> 2003年10月28日
 link もっと後

2003年10月28日

link permalink link 編集する

C言語でNクイーン問題、高速化

目次: ベンチマーク

しつこくNクイーン問題を考えてみる。調べてもこれ以上高速なアルゴリズムが見つからなかったので、Cの卑怯技ビット演算による並列化を用いた高速化を図りました。結果は思いのほか上々で、15クイーンが5.8秒で解けました。なんと、一気に2倍ですか。
この問題は並列処理しやすいので多数のPCに振り分けて解くこともできるでしょう。手が空いたら簡単な通信プログラムを付けて、手持ちのPC 2台で分散処理しようと思います。

実行結果（AMD Athlon/1.4GHz, Win 2000, VC 6.0）
N-queens solver Type 5
solver: バックトラック, 左右対称性, 静的配列, 一意性, ビット並列演算
  n:       answer        unique            time
--------------------------------------------------
  2:            0             0            0 ms
  3:            0             0            0 ms
  4:            2             1            0 ms
  5:           10             2            0 ms
  6:            4             1            0 ms
  7:           40             6            0 ms
  8:           92            12            0 ms
  9:          352            46            0 ms
 10:          724            92            0 ms
 11:         2680           341           10 ms
 12:        14200          1787           20 ms
 13:        73712          9233          150 ms
 14:       365596         45752          901 ms
 15:      2279184        285053         5788 ms
 16:     14772512       1846955        39287 ms

何かキーを押すと終了します...
編集者:すずき(2023/09/24 09:05)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする


link もっと前
2003年10月28日 >>> 2003年10月28日
 link もっと後

管理用メニュー

link 記事を新規作成
link RSSを更新
<2003>
<<<10>>>
日月火水木金土
---1234
567891011
12131415161718
19202122232425
262728293031-
link 本日の日記へ

最近のコメント5件

  • link 24年5月17日
    すずきさん (05/20 13:16)
    「そうですねえ、普通はStandardなの...」
  • link 24年5月17日
    hdkさん (05/19 07:45)
    「なるほど、そういうことなんですね。Exc...」
  • link 24年5月17日
    すずきさん (05/19 03:41)
    「Standardだと下記の設定になってい...」
  • link 24年5月17日
    hdkさん (05/18 22:16)
    「ドメインを変えたせいで別サイト扱いになっ...」
  • link 24年4月22日
    hdkさん (04/24 08:36)
    「うちのHHFZ4310は15年突破しまし...」
link もっとみる

最近の記事3件

  • link 24年5月16日
    すずき (05/21 01:23)
    「[イマドキ？のlocale設定方法] 目次: 自宅サーバーLocaleの設定方法は未だによくわかってないのですが、最近ROCK...」
  • link 23年6月1日
    すずき (05/21 01:02)
    「[自宅サーバー - まとめリンク] 目次: 自宅サーバーこの日記システム、Wikiの話。カウンターをPerlからPHPに移植日...」
  • link 24年5月17日
    すずき (05/18 20:34)
    「[TwitterがXに置換された] 今日？あたりからtwitter.comにアクセスするとx.comにリダイレクトされるように...」
link もっとみる

こんてんつ

日記の全文検索

open/close wiki
open/close Linux JM
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 2019年
open/close 2020年
open/close 2021年
open/close 2022年
open/close 2023年
open/close 2024年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDFファイル RSS 1.0

最終更新: 05/21 01:23

管理者: Katsuhiro Suzuki(katsuhiro( a t )katsuster.net)

This is Simple Diary 1.0  Copyright(C) Katsuhiro Suzuki 2006-2023.
Powered by PHP 8.2.15.  using GD bundled (2.1.0 compatible)(png support.)