分業巡回セールスマン問題の並列計算機への実装
スポンサーリンク
概要
- 論文の詳細を見る
情報処理学会第48回全国大会で筆者が提案した分業巡回セールスマン問題は、複数のセールスマンが最適に分業し、各々が最適な巡路で巡回をする方法を求める問題であり、並列分散型処理のスケジューりングに対する解を要求される問題を一般化したものである。この問題の最も簡単な場合として2人のセールスマンが分業巡回する2TSP(2-Traveling Salesmen Problem)問題を、ニューラルネットワークを用いて実用時間内に近似的に解くことが可能であることを示したが、今回これをより複雑なn人のセールスマンが分業巡回するnTSPに拡張し、並列計算機(AP1000)上に実装したので報告をする。2TSPと3TSP以上の一般的なnTSP問題では問題の規模が大きく変わり、計算能力・メモリなどの点でも要求量が爆発的に増加する。そこでニューロン間結合を大幅に減らせ、効率的に並列計算できるモデル化を新たに行った。本稿では新しいモデル化と、並列実装による効果について述べる。
- 一般社団法人情報処理学会の論文
- 1994-09-20
著者
関連論文
- Botnetの命令サーバドメインネームを用いたBot感染検出方法(セッション1)
- ARTによる単語の出現頻度処理を応用した概念関係の獲得
- 科学者倫理の確立に向けて声明表出に際しての会長談話, 声明「科学者の行動規範について」
- ICOTone : 立派なベースLPB88
- L-022 仮想マシンモニタにおけるデバイスドライバ安全性向上に関する提案(L分野:ネットワーク・セキュリティ)
- 分散システムにおけるCapabilityを用いた資源アクセス制御
- アプリケーション・プラットフォームとしてのセキュアOSに関する初期的検討
- M_053 分散環境におけるセキュアな資源管理方式に関する研究(M分野:アーキテクチャ・ユビキタス・セキュリティ)
- 対話的整形による幾何学的図形の高速描画(次世代ヒューマンインタフェース・インタラクション)
- 自動認識整形機能をもったペンによる描画システム
- 音楽情景分析の処理モデルOPTIMAにおける和音の認識
- 音楽情景分析の処理モデルOPTIMAにおける単音の認識
- 音楽情景分析の処理モデルOPTIMAにおける統計的単音仮説生成処理
- 音楽情景分析の処理モデルOPTIMAにおけるシーン情報の抽出と利用
- 音楽情景分析の処理モデルOPTIMAの実装
- 処理モデルOPTIMAに基づく音楽情景分析システムの構築 II : 情報統合の実現と評価
- 処理モデルOPTIMAに基づく音楽情景分析システムの構築 I : 各処理モジュールの実現と評価
- 音楽単音記号列生成システムの処理モデルOPTIMAにおける単音仮説生成処理
- 1. 計算機への音楽の入力 : 「音」の分離抽出の難しさ ( 音楽情報処理
- 音楽音響信号から単音記号列を生成するシステムOPTIMAの全体像
- 音源分離システムにおけるパターン照合モジュールの動的負荷分散を用いた並列実装
- 二つの周波数成分の分離知覚に関する工学的モデル : 複数の要因の評価と統合
- 音源分離システムにおけるパターン照合モジュールの並列実装と評価
- 音源分離システムにおける音モデルの自動獲得 : II : ボトムアップ処理と音モデルに基づく処理との協調
- 音源分離システムにおける音モデルの自動獲得 : I : 音モデルの抽象化
- 音楽音響信号を対象とする音源分離システム : 音モデルに基づくアプローチ
- RDTネットワークにおける疑似フルマップ方式の評価
- ディレクトリキャッシュにおける疑似フルマップシステムの定量的評価
- ニューラルネットワークを用いた分業TSPの解法
- 医療分野におけるRFIDタグシステムの情報セキュリティの確保(セッション1-B:セキュリティ応用技術)
- シンクライアントアーキテクチャをベースにしたセキュアクライアントの検討
- 英語名詞の多義性解消における文脈としての場面情報の評価
- 談話解析に基づく場面の同定とその評価
- 場面情報に基づく英語名詞の語義の優先づけ方法と評価
- 結束構造および一貫性に基づく場面構造の解析
- 分業巡回セールスマン問題のニューラルネットワークによる解法
- 辞書ベースの連想記憶に基づく日常生活場面の同定
- 辞書ベースの連想記憶による文脈理解のための場面同定機構
- 辞書ベース連想による場面同定に必要な文脈情報量の推定
- 連想推論における逐次学習方式の定式化とその評価 : 曖昧性解消に必要な文脈情報の定量化
- ニューラルネットワークと記号処理の統合による連想補完文字認識
- PDAI&CDに基づく意味の学習および文脈依存の多義性解消 : 神経回路網と論理記号処理の統合による連想推論
- 神経回路網に基づく超並列連想システムWAVE
- 論理プログラミングを基礎とした認可ポリシ記述言語
- 相互結合網RSOTのルーチング方式
- 機密情報共有に有用な情報フロー制御モデルの提案
- ネットワーク仮想化機構とその評価
- PIE64の通信機能の測定
- 並列計算機PIE64の通信機能の評価
- VLDP3アーキテクチャにおけるメモリリネーミング手法の検討
- VLDP3アーキテクチャにおけるレジスタ値の高速Forwarding手法の提案
- VLDP3 : データフローを高速実行する大規模アーキテクチャ
- C-16 VLDP3アーキテクチャの構想(3) : レジスタフォワーディング機構の初期検討(計算機アーキテクチャと最適化,C.アーキテクチャ・ハードウェア)
- C-15 VLDP3アーキテクチャの構想(2) : ソフトウェア支援(計算機アーキテクチャと最適化,C.アーキテクチャ・ハードウェア)
- C-14 VLDP3アーキテクチャの構想(1) : プロセッサ構成(計算機アーキテクチャと最適化,C.アーキテクチャ・ハードウェア)
- 2000-HPC-82-19 コンパイラによるロード・ストア負荷の軽減
- 実行サイクル数予測に基づく大域的命令スケジューリングの実装と評価
- 2D-3 予測実行サイクル数に基づいた大域的命令スケジューリング
- 「分散処理特集号」の編集にあたって
- 高並列推論エンジンPIEにおけるゴールフレーム表現方式の評価
- スペルベルの象徴解釈モデルに基づく隠喩の検出
- 単語の頻度情報を応用した文の評価
- ARTを利用した多義語の分類とその評価
- ARTを用いた自然言語中の単語の頻度の情報処理 : 文書クラスタリングによる単語の連想関係の取得
- 効率的なセキュリティ要求分析手法の提案
- デジタル教材の著作権料分配方法の提案-新電子教科書プロジェクト-
- マルウェア亜種の動的挙動を利用した自動分類手法の提案と実装
- メンバの入れ替えが生じる環境下でのマルチキャスト通信の暗号化鍵管理方法の評価・検討(情報通信基礎サブソサイエティ合同研究会)
- メンバの入れ替えが生じる環境下でのマルチキャスト通信の暗号化鍵管理方法の評価・検討(情報通信基礎サブソサイエティ合同研究会)
- メンバの入れ替えが生じる環境下でのマルチキャスト通信の暗号化鍵管理方法の評価・検討(情報通信基礎サブソサイエティ合同研究会)
- セキュアなアプリケーション開発のための要求・デザインパターンの提案(セッション5-B:セキュアプロトコルとセキュアソフトウェア開発)
- サイバーワールド論文特集の発行にあたって
- O-010 情報システムへのオープンソースソフトウェア導入に関するガイドライン策定(O分野:情報システム)
- L-034 自己組織化マップを用いた異常検知についての一検討(L分野:ネットワーク・セキュリティ)
- L-033 C&Cセッション分類によるボットネットの検出手法の一検討(L分野:ネットワーク・セキュリティ)
- メモリアクセスの時間的周期性を利用した動的データプリフェッチ機構
- 隠喩理解 : 連想網と意味ネットワークとの整合
- サービスベースシステムにおけるトランザクションの並行制御
- オブジェクト指向に基づいた分散プログラム開発環境
- 関係データベースに基づく演繹データベースの推論実行方式
- 並列計算機PIE64における Committed-choice型言語Flengの負荷分散手法
- Committed-Choice型言語Flengにおける静的負荷分割のPIE64上での実装および評価
- ゴールの融合によるCommitted-Choice型言語Flengの最適化
- PIE64におけるCommitted-Choice型言語flengの動的粒度制御のためのコンパイル手法
- flengの動的粒度制御のための静的解析手法
- データフロー解析に基づくCommitted-Choice型言語Flengの静的負荷分割
- データフロー解闘斤に基づくCommitted Choice型言語のスヶジューリング
- 高並列推論エンジンPIE64研究経過報告 : ソフトウェア
- Committed-Choice型言語へのオブジェクトの導入
- Committed-Choice型言語Flengにおける配列処理の最適化
- 4N-3 並列論理型言語Flengにおけるプリミティブなオーバーヘッド解析
- Committed-Choice型言語Flengにおける粒度制御法の評価
- 共有メモリ型並列計算機上のFleng処理系におけるオーバーヘッドの定量的解析
- Committed-Choice型言語へのループ記述構文の導入
- Committed-Choice型言語Flengにおける静的粒度最適化
- 共有メモリ型並列計算機上へのFleng処理系の実装及び評価
- Committed-Choice型言語Flengのワークステーションクラスタ上処理系の定量的評価
- Committed-Choice型言語Flengのインライン展開による粒度制御手法
- Committed-Choice型言語Flengにおける静的粒度最適化
- 並列論理型言語Flengのワークステーションクラスタへの実装