【アルゴリズム】201800905アルゴリズムノート整理
2491 ワード
1、時間複雑度O(1)ウォーズ式:データ構造+アルゴリズム=プログラム
2、窮挙と遡及遡及法:前へ進み、壁にぶつかって遡及アルゴリズムの最適化問題:制約条件から着手し、対称性を利用してサブツリーを削減し、サブ問題に分けることができるなど-分岐設計優先戦略-取値点と遡及点の調整-制約条件の調整
遡及アルゴリズムの効率に影響する要因:-探索ツリーの構造-分岐が均一かどうか-ツリーの深さ-対称度-解の分布-分布深さ-制約条件の判断:計算が簡単かどうか
3、再帰と分治問題の分解、サブセット解の合併、Hanoi問題ステップ:-再帰関係の記述-再帰境界の決定-再帰関数の復号-プログラム完備
データの検索とソート、マトリクス乗算、馬の周遊ルート、カウント逆順位問題、信号のノイズ除去、碁盤カバーなど
4、繰返し数列、数陣解と解計数応用問題の面での応用ある現象の変化結果とその前の変化に近い1つまたはいくつかの結果と密接に関連する鍵は隣接するデータ項目の繰返し関係、帰納法則→抽象的に数学モデルである
5、欲張りアルゴリズム数字削除、リュックサック、カバー、図の着色、遍歴、ハフマン符号化、最小コスト生成ツリーなどの問題の解最適サブ構造特性→動的計画欲張りアルゴリズムは動的計画より効率が高く、空間制限の影響がなく、NP完全問題または大規模最適化問題を解決でき、よく近似解を得る
6、動的計画多段階決定問題の最適化目標は、問題の最適値をもたらす最適決定シーケンス条件を取得することである:-問題中の状態は最適性原理を満たさなければならない-問題中の状態は無後効性を満たさなければならない
ステップ:-求める最適化問題はいくつかの段階に分けられ、その構造特効-各段階の状態表現と繰返し関係を描き、初期(境界)条件を決定する-繰返しを適用して最適値を解く-最適値を計算し、最適解を構築する
7、オペレーティング学-計画論-図論とネットワーク分析-行列論-決定論-記憶論-ゲーム論-ランダムオペレーティングモデル
8、線形計画は一般的に、連続的で制御可能な決定変数の前提の下で、1つの線形関数の1組の線形制約条件の下での最大化を求める.最小化問題-非線形計画数学モデル(^2以上)-動的計画数学モデル(時間系列などの変化)-ランダム計画数学モデル(すぐに計画)-整数計画モデル-マルチターゲット線形計画問題数学モデル
意思決定変数、資源制限、消費(効果、技術)係数、価値係数
感度分析:パラメータが変化した場合、元の最適解がどのように変化するか、あるいはパラメータがどの範囲内で変化した場合、元の最適解に影響しない変数や条件が変化した場合、元の最適解にどのような影響を及ぼすか、「最適解」に基づくこのような分析を感度分析と呼ぶ目標関数における価値係数Cの変化 右端項資源制約常熟bの変化 制約条件における技術係数Aの変化 新しい決定変数と新しい制約条件の変化 を増加する目標係数または右端項に含むパラメータの変化 9、動的計画フェーズ:k 状態:Sk 決定:Uk 戦略:P 1 n(S 1)＝(U 1(S 1),U 2(S 2),…,Un(Sn),) 状態遷移方程式:Sk+1=Tk(Sk,Uk) 指標関数と最適指標値: 分類:-決定プロセス:確定性、ランダム性-時間パラメータ:離散、連続
最適化原理:ポリシー全体が最適である場合、その任意のサブポリシーも最適である必要があります.
10、オラ回路の判定ルール:奇数ブリッジを接続する頂点が2つより多い場合、オーラループ は存在しない.奇数橋を結ぶのは2つの点だけなら、この2つの場所の1つから出発して、オラ回路 を見つけることができます.奇数橋を結ぶ点が一つもなければ、どこから出発してもオーラ戻り路 が見つかる.
11、ネットワーク計画:ネットワーク分析の方法で作成した計画、技術は:-キールート法CPM-計画審査技術PERT
手順:-ネットワーク図の描画-時間パラメータの計算-キーパスとネットワーク最適化の決定
12、ストレージ論関連モデル:欠品は許されず、補充時間は短い 欠品は許されず、補充には一定時間がかかる 欠品が許可され、補充には一定時間がかかる 欠品が許可され、補充時間が短い 価格割引のあるストレージの問題 需要は離散ランダム変数 である.需要は連続的なランダム変数 である.(s,S)型ストレージポリシー(連続型) (s,S)型ストレージポリシー(ディスクリート) 13、行列論の三つの研究内容:性状態問題:キューシステム確率規則性 最適化問題:静的最適化と動的最適化 キューシステムの統計推定: キューモデルのシンボル表示:X/Y/Z/A/B/C
一般的な分布: M:負の指数分布
2、窮挙と遡及遡及法:前へ進み、壁にぶつかって遡及アルゴリズムの最適化問題:制約条件から着手し、対称性を利用してサブツリーを削減し、サブ問題に分けることができるなど-分岐設計優先戦略-取値点と遡及点の調整-制約条件の調整
遡及アルゴリズムの効率に影響する要因:-探索ツリーの構造-分岐が均一かどうか-ツリーの深さ-対称度-解の分布-分布深さ-制約条件の判断:計算が簡単かどうか
3、再帰と分治問題の分解、サブセット解の合併、Hanoi問題ステップ:-再帰関係の記述-再帰境界の決定-再帰関数の復号-プログラム完備
データの検索とソート、マトリクス乗算、馬の周遊ルート、カウント逆順位問題、信号のノイズ除去、碁盤カバーなど
4、繰返し数列、数陣解と解計数応用問題の面での応用ある現象の変化結果とその前の変化に近い1つまたはいくつかの結果と密接に関連する鍵は隣接するデータ項目の繰返し関係、帰納法則→抽象的に数学モデルである
5、欲張りアルゴリズム数字削除、リュックサック、カバー、図の着色、遍歴、ハフマン符号化、最小コスト生成ツリーなどの問題の解最適サブ構造特性→動的計画欲張りアルゴリズムは動的計画より効率が高く、空間制限の影響がなく、NP完全問題または大規模最適化問題を解決でき、よく近似解を得る
6、動的計画多段階決定問題の最適化目標は、問題の最適値をもたらす最適決定シーケンス条件を取得することである:-問題中の状態は最適性原理を満たさなければならない-問題中の状態は無後効性を満たさなければならない
ステップ:-求める最適化問題はいくつかの段階に分けられ、その構造特効-各段階の状態表現と繰返し関係を描き、初期(境界)条件を決定する-繰返しを適用して最適値を解く-最適値を計算し、最適解を構築する
7、オペレーティング学-計画論-図論とネットワーク分析-行列論-決定論-記憶論-ゲーム論-ランダムオペレーティングモデル
8、線形計画は一般的に、連続的で制御可能な決定変数の前提の下で、1つの線形関数の1組の線形制約条件の下での最大化を求める.最小化問題-非線形計画数学モデル(^2以上)-動的計画数学モデル(時間系列などの変化)-ランダム計画数学モデル(すぐに計画)-整数計画モデル-マルチターゲット線形計画問題数学モデル
意思決定変数、資源制限、消費(効果、技術)係数、価値係数
感度分析:パラメータが変化した場合、元の最適解がどのように変化するか、あるいはパラメータがどの範囲内で変化した場合、元の最適解に影響しない変数や条件が変化した場合、元の最適解にどのような影響を及ぼすか、「最適解」に基づくこのような分析を感度分析と呼ぶ
最適化原理:ポリシー全体が最適である場合、その任意のサブポリシーも最適である必要があります.
10、オラ回路の判定ルール:
11、ネットワーク計画:ネットワーク分析の方法で作成した計画、技術は:-キールート法CPM-計画審査技術PERT
手順:-ネットワーク図の描画-時間パラメータの計算-キーパスとネットワーク最適化の決定
12、ストレージ論関連モデル:
- X：
- Y：
- Z：
- A： N
- B： m
- C：
一般的な分布: