目次: ベンチマーク
しつこくNクイーン問題を考えてみる。調べてもこれ以上高速なアルゴリズムが見つからなかったので、Cの卑怯技ビット演算による並列化を用いた高速化を図りました。結果は思いのほか上々で、15クイーンが5.8秒で解けました。なんと、一気に2倍ですか。
この問題は並列処理しやすいので多数のPCに振り分けて解くこともできるでしょう。手が空いたら簡単な通信プログラムを付けて、手持ちのPC 2台で分散処理しようと思います。
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 何かキーを押すと終了します...
< | 2003 | > | ||||
<< | < | 10 | > | >> | ||
日 | 月 | 火 | 水 | 木 | 金 | 土 |
- | - | - | 1 | 2 | 3 | 4 |
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 | - |
合計:
本日:
管理者: 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.)