SL法 : 線形・非線形計画法の併用によるコストに基づく仮説推論の準最適解計算

DOI Web Site 被引用文献7件 参考文献16件

書誌事項

タイトル別名
  • SL Method for Computing a Near-Optimal Solution Using Linear and Non-Linear Programming Methods in Cost-Based Hypothetical Reasoning
  • SLホウ : センケイ ・ ヒセンケイ ケイカクホウ ノ ヘイヨウ ニ ヨル

この論文をさがす

抄録

<p>Hypothetical reasoning is an important framework for knowledge based systems due to its theoretical basis and its usefulness for many practical problems. Since its inference time grows exponentially with respect to problem size, its efficiency becomes the most crucial problem when applying it to practical problems. Some approximate solution methods have been proposed for computing cost-based hypothetical reasoning problems efficiently;however, their mechanisms are complex for human to understand. We here present an understandable efficient method called SL(slide-down and lift-up) method, which uses a linear programming technique, namely simplex method, for determining aninitial search point and a non-linear programming technique for efficiently finding a near-optimal 0-1 solution. To escape from trapping into local optima, we have developed a new local handler, which systematically fixes a variable to a locally consistent value when a local optimal point is detected. This SL method can find a near-optimal solution for cost-based hypothetical reasoning in polynomial time when respect to problem size. From pictorially illustrated behaviors of the SL method, its simple inference mechanism can be easily understood.</p>

収録刊行物

  • 人工知能

    人工知能 13 (6), 953-961, 1998-11-01

    一般社団法人 人工知能学会

被引用文献 (7)*注記

もっと見る

参考文献 (16)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ