第三週DFS/BFS、欲張り、二分

26960 ワード

• 中級 ——【アルゴリズム】

記事の目次

、深さ優先検索／広さ優先検索

、検索遍歴

、コードモジュール（Java）

、2端子BFS

、貪欲アルゴリズム

、要約

、適用シーン

、二分検索

、テンプレート-Java

、前提条件（筋肉記憶）

3、二分検索学習宿題

PS：

一、深さ優先検索/広さ優先検索

Depth First Search

Breadth First Search

1、検索遍歴

各ノードは一回

を訪問します。

各ノードは一回だけ

にアクセスします。

は、ノードへのアクセス順序が異なる。

深さ優先：depth first search常用_スタック

広さ優先：bredth first search常用_キュー

2、コードモジュール（Java）

DFS再帰書き方

Set<Node> visited = new HashSet<>();

public void dfs(Node root, Set<Node> visited) {
    if (visited.contains(root)) {//terminator
        // already visited
        return;
    }
    visited.add(root);

    // process current node here.
    for (Node nextNode : node.children) {
        if (!visited.contains(nextNode)) {
            dfs(nextNode, visited);
        }
    }
}

DFS非再帰的書き方

public int[] dfs(Node root){ 
    if (root == null) {
        return new int[0];
    }
    Set<Node> visited = new HashSet<>();
    Stack<Node> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) { 
        Node node = stack.pop();
        visited.add(node);

        process (node); 
        List<Node> nodes = generate_related_nodes(node);
        stack.addAll(nodes); 

        // other processing work 
        // ...
    }
}

BFSコードモジュール


public void bfs(Node root) {
    Set<Node> visited = new HashSet<>();
    Queue<Node> queue = new ArrayQueue<>(); 
    queue.offer(root); 
    visited.add(root);

    while (!queue.isEmpty()) { 
       Node node = queue.poll();
       visited.add(node);

       process(node); 
       List<Node> nodes = generate_related_nodes(node);
       queue.addAll(nodes);
    }
	// other processing work 
	// ...
}

3、デュアルエンドBFS

両端を検索すると、いずれかの部分に「破断」が発生した場合、つまり接続可能な経路が存在しないということです。そのまま0

に戻ります。

ダブルエンドの検索は、時間を最適化するために、いつも少ないのを使って多くのものを探しに行きます。例えば、初めの時に1000個を入れました。最後は3つだけです。きっと少ないほうから行ったほうがいいです。
二、欲張りアルゴリズム
1、要約
Gredyは、各ステップの選択において、現在の状態において最良または最適（すなわち、最も有利）の選択を行い、結果がグローバルで最良または最適化されることを望むアルゴリズムである。見識が狭い

貪欲アルゴリズムとダイナミック企画の違いは、各サブ問題の解決策を選択し、返品できないことです。

ダイナミックプランは以前の演算結果を保存し、以前の結果に基づいて現在を選択し、リターン機能があります。

貪欲：局部最適判断をする。

回トレース：

をリターンすることができます。

ダイナミック企画：最適選択＋キャンセル

2、適用シーン

貪欲法はいくつかの最適な問題を解決することができます。しかし、工程と生活の問題に対しては、欲張り法は一般的に私たちが要求している答えを得ることができません。

一旦問題が欲張り法で解決されると、欲張り法は普通この問題を解決する一番いい方法です。貪欲法の効率性と求める答えは最適結果に近いので、貪欲法は補助アルゴリズムとしても使えます。あるいは要求結果が特に正確ではない問題を直接解決します。

簡単に言えば、問題はサブ問題に分解して解決でき、サブ問題の最適解は最終問題の最適解に伝達され、この種の問題の最適解は最良のサブ構造と呼ばれている。銀貨の問題は欲張りに適しています。それ自体の額面は倍数です。倍数でなければいけません。

後から前を見ると、欲張りかどうか、または一部から見ると

です。
三、二分検索
1、テンプレート-Java

public int findIndexOf(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

2、前提条件（筋肉記憶）

ターゲット関数の単調性（単調なインクリメントまたは減少）−順序セット

上下界

が存在します。

はインデックスで

にアクセスすることができます。
3、二分検索学習作業
二分検索を使って、「4、5、6、7、0、1、2」の中間無秩序なところを探します。学生たちは自分の考え、コードを第3週の学習総括に書いてもいいです。
時間が限られていますので、最適化をお願いします。

//                （       while          ）
public int searchMinValueIndex(int[] nums) {
    //   ， mid         ，     ，  mid      ，   mid  ，    
    int point = nums[0];
    int i = 0;
    int j = nums.length - 1;
    while (i < j) {
        int mid = i + (j - i) / 2;
        //  i + 1 = j，  j         ，
        //       i j     ，  j   i ，         ，  j  
        if (i + 1 == j) {
            if (nums[i] > nums[j]) {
                return j;
            }
            //j     i             。  0  
            return 0;
        }
        if (point > nums[mid]) {
            j = mid;
        } else {
            i = mid;
        }
    }
    return 0;
}

public static void main(String[] args) {
    Assert.assertEquals(3, new Test().searchMinValueIndex(new int[]{7, 8, 9, 0, 1, 2, 3, 4, 5, 6}));
    Assert.assertEquals(1, new Test().searchMinValueIndex(new int[]{9, 0, 1, 2, 3, 4, 5, 6, 7, 8}));
    Assert.assertEquals(6, new Test().searchMinValueIndex(new int[]{4, 5, 6, 7, 8, 9, 0, 1, 2, 3}));
    Assert.assertEquals(8, new Test().searchMinValueIndex(new int[]{2, 3, 4, 5, 6, 7, 8, 9, 0, 1}));
    Assert.assertEquals(0, new Test().searchMinValueIndex(new int[]{1, 2, 3}));
}

PS:
時間の関係で。多くのhomeworkはうまくできませんでした。悪いところを探してくれるクラスメートがほしいです。ありがとうございます。クリックして
時間の関係で。多くのhomeworkはうまくできませんでした。悪いところを探してくれるクラスメートがほしいです。ありがとうございます。クリックして
時間の関係で。多くのhomeworkはうまくできませんでした。悪いところを探してくれるクラスメートがほしいです。ありがとうございます。クリックして

【JAVA】2.複雑なチェーンテーブル（各ノードにノード値があり、二つのポインタ、一つは次のノードを指し、もう一つの特殊なポインタは任意のノードを指す）を入力し、結果はコピー後の複雑なチェーンテーブルのheadを返します。注意出力結果はパラメータに戻らないでください。

Android Mの新たな実行時に権限開発者が知るべきことはすべて